candybietyeu
New Member
Download Luận văn Phương pháp phân cụm tài liệu web và áp dụng vào máy tìm kiếm
MỤC LỤC
DANH MỤC CHỮVIẾT TẮT . 5
DANH MỤC HÌNH VẼ, BẢNG BIỂU . 6
MỞ ĐẦU . 7
CHƯƠNG 1 - KHÁI QUÁT VỀKHAI PHÁ DỮLIỆU WEB . 9
1.1. Khai phá dữliệu Web . 9
1.1.1. Giới thiệu vềKhai phá dữliệu . 9
1.1.2. Dữliệu Web và nhu cầu khai thác thông tin . 11
1.1.3. Đặc điểm của dữliệu Web . 12
1.1.4. Các hướng tiếp cận khai phá dữliệu Web . 13
1.1.5. Nhu cầu Phân cụm tài liệu Web . 14
1.2. Mô hình tìm kiếm thông tin . 15
1.2.1. Giới thiệu . 15
1.2.2. Quy trình tìm kiếm thông tin trong hệthống . 15
1.2.3. Ứng dụng phân cụm vào hệthống tìm kiếm . 18
1.3. Kết luận chương 1 . 19
CHƯƠNG 2 - THUẬT TOÁN PHÂN CỤM WEB . 20
2.1. Một sốnội dung cơbản vềthuật toán phân cụm tài liệu . 20
2.2. Tiêu chuẩn đánh giá thuật toán phân cụm . 22
2.3. Các đặc tính của các thuật toán phân cụm web . 24
2.3.1. Mô hình dữliệu . 24
2.3.2. Độ đo vềsựtương tự. 27
2.3.3. Mô hình phân cụm . 29
2.4. Một sốkỹthuật Phân cụm Web điển hình . 30
2.4.1. Phân cụm theo thứbậc . 30
2.4.2. Phân cụm bằng cách phân mảnh . 33
2.5. Các yêu cầu đối với các thuật toán phân cụm Web . 35
2.5.1. Tách các thông tin đặc trưng . 35
2.5.2. Phân cụm chồng lặp . 36
2.5.3. Hiệu suất . 36
2.5.4. Khảnăng khửnhiễu . 36
2.5.5. Tính tăng . 37
2.5.6. Việc biểu diễn kết quả. 37
2.6. Bài toán tách từtự động tiếng Việt . 37
2.6.1. Một sốkhó khăn trong phân cụm trang Web tiếng Việt . 37
2.6.2.Tiếng và Từtrong tiếng Việt . 39
2.6.3. Phương pháp tách từtự động tiếng Việt fnTBL . 39
2.6.4. Phương pháp Longest Matching . 43
2.6.5. Kết hợp giữa fnTBL và Longest Matching . 44
2.7. Kết luận chương 2 . 44
CHƯƠNG 3 - THUẬT TOÁN PHÂN CỤM CÂY HẬU TỐVÀ THUẬT TOÁN
CÂY PHÂN CỤM TÀI LIỆU . 45
3.1. Giới thiệu vềthuật toán phân cụm trang Web có tính tăng . 45
3.2. Thuật toán phân cụm cây hậu tố. 46
3.2.1. Mô tả. 46
3.2.2. Thuật toán STC . 47
3.3. Thuật toán phân cụm sửdụng cây phân cụm tài liệu . 51
3.3.1. Giới thiệu . 51
3.3.2. Trích chọn đặc trưng và phân cụm tài liệu . 51
3.3.3. Cây phân cụm tài liệu –DC Tree . 55
3.4. Kết luận chương 3 . 60
CHƯƠNG 4 - PHẦN MỀM THỬNGHIỆM VÀ KẾT QUẢTHỰC NGHIỆM . 61
4.1. Giới thiệu . 61
4.2. Thiết kếcơsởdữliệu . 62
4.3. Chương trình thửnghiệm . 65
4.4. Kết quảthực nghiệm . 66
4.5. Kết luận chương 4 .
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Dựa vào các vùng vấn đề, thỉnh thoảng các đối tượng biểu diễn dữ liệu
đặc trưng không có cùng kiểu. Một sự kết hợp giữa các kiểu dữ liệu số, phân
loại, không gian hay text có thể được sử dụng. Trong trường hợp này, vấn đề
quan trọng là nghĩ ra một phương pháp có thể nắm giữ tất cả các thông tin một
cách hiệu quả. Một quy trình chuyển đổi nên được áp dụng để chuyển đổi từ một
kiểu dữ liệu này thành một kiểu dữ liệu khác. Thỉnh thoảng một kiểu dữ liệu
không thể áp dụng vào được, lúc đó thuật toán phải được chỉnh sửa để làm việc
với các kiểu dữ liệu khác [18].
2.3.2. Độ đo về sự tương tự
Nhân tố chính trong thành công của bất kỳ một thuật toán phân cụm nào
đó chính là độ đo về sự tương tự của nó. Để có thể nhóm các đối tượng dữ liệu,
một ma trận xấp xỉ đã được sử dụng để tìm kiếm những đối tượng (hay phân
cụm) tương tự nhau. Có một số lượng lớn các ma trận tương tượng đã được đề
cập đến trong các tài liệu, ở đây, chúng ta chỉ xem qua một số ma trận thông
thường nhất.
Việc tính toán độ (không) tương tự giữa 2 đối tượng được thực hiện
thông qua các hàm tính khoảng cách (distance), thỉnh thoảng cũng có thể sử
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 28 -
dụng các hàm tính về độ không tương tự (dissimilarity). Với 2 véc tơ đặc trưng x
và y, cần tìm ra độ tương tự (hay không tương tự) giữa chúng.
Một lớp rất hay được sử dụng của các hàm khoảng cách đó là “gia đình
các khoảng cách Minkowski” [7], được mô tả như phía dưới:
p
n
i
p
ii yxyx ∑
=
−=−
1
Trong đó x,y ∈ Rn. Hàm khoảng cách này thực ra là mô tả một họ vô số
các khoảng cách được đưa ra bởi p. Thông số này giả thiết là các giá trị lớn hơn
hay bằng 1. Một vài giá trị chung của p và các hàm khoảng cách là:
p = 1: Khoảng cách Hamming ∑
=
−=−
n
i
ii yxyx
1
p = 2: Khoảng cách Euclidean ∑
=
−=−
n
i
ii yxyx
1
2
p = ∞: Khoảng cách Tschebyshev =− yx maxi=1,2,...,n ii yx −
Một độ đo độ tương tự hay được dùng, đặc biệt là trong phân cụm tài
liệu đó là độ đo liên quan cosine (cosine correlation) (được sử dụng trong [4],
[15], và [13]), được định nghĩa là:
yx
yxyx .),cos( =
trong đó . biểu thị việc nhân vector và ||.|| biểu thị cho độ dài của vector.
Một độ đo hay được dùng khác đó là độ đo Jaccard (được sử dụng trong
[8], [9]), được định nghĩa là:
),max(
),min(
),(
1
1
i
n
i i
i
n
i i
yx
yx
yxd ∑
∑
=
==
trong trường hợp các vector đặc trưng nhị phân, có thể đơn giản hóa
thành:
yx
yx
yxd ∪
∩=),(
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 29 -
cần chú ý rằng từ “khoảng cách” không có gì nhập nhằng với
“tương tự”. Những từ này là trái nghĩa với nhau, cho chúng ta biết độ tương tự
giữa 2 đối tượng. Độ tương tự giảm khi khoảng cách tăng. Thêm một điểm cần
chú ý khác đó là nhiều thuật toán sử dụng hàm khoảng cách (hay tương tự) để
tính toán sự tương tự giữa 2 phân cụm, một phân cụm và một đối tượng, hai đối
tượng. Việc tính toán khoảng cách giữa 2 phân cụm (hay các phân cụm và các
đối tượng) yêu cầu một vector đặc trưng thay mặt cho phân cụm.
Thường thì các thuật toán phân cụm thường sử dụng một ma trận tương
tự (similarity matrix). Một ma trận tương tự cỡ N × N ghi nhận các khoảng cách
(hay độ tương tự) giữa từng cặp đối tượng. Hiển nhiên ma trận tương tự là một
ma trận đối xứng do đó chúng ta chỉ cần lưu phần trên bên phải hay phần dưới
bên trái của nó.
2.3.3. Mô hình phân cụm
Bất cứ thuật toán phân cụm nào cũng thừa nhận một cấu trúc phân cụm
nào đó. Đôi khi cấu trúc phân cụm không thực sự rõ ràng tùy theo nhu cầu của
bản thân thuật toán phân cụm. Ví dụ, thuật toán k-means sử dụng các phân cụm
hình cầu (hay các phân cụm lồi). Đó là vì theo cách k-means tìm kiếm phân cụm
trung tâm và cập nhật các đối tượng thành viên. Nếu như không cẩn thận, chúng
ta có thể kết thúc việc phân cụm với các phân cụm kéo dài (elongated cluster),
trong đó kết quả là có ít phân cụm lớn và có nhiều phân cụm rất nhỏ. Wong và
Fu [16] đã đưa ra một giải pháp để giữ kích cỡ phân cụm trong một khoảng nào
đó, nhưng việc giữ kích cỡ phân cụm trong một khoảng nào đó không phải bao
giờ cũng đáng thực hiện. Một mô hình động để tìm kiếm các phân cụm không
thích hợp với cấu trúc của chúng đó là CHAMELEON, được đưa ra bơi Karypis
[13].
Tùy theo vấn đề, chúng ta có thể có các phân cụm tách rời (disjoint)
hay các phân cụm chồng chéo (overlapping). Trong ngữ cảnh phân cụm tài liệu
thường mong muốn có các phân cụm chồng chéo bởi vì tài liệu có xu hướng có
nhiều hơn một chủ đề (ví dụ một tài liệu có thể chứa thông tin về đua ô tô và các
công ty ô tô). Một ví dụ khác về việc tạo ra các phân cụm chồng chéo là hệ thống
cây hậu tố (STC) được đưa ra bởi Zamir và Etzionin [5]. Một cách khác để tạo ra
các phân cụm chồng chéo đó là phân cụm mờ trong đó các đối tượng có thể
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 30 -
thuộc vào các phân cụm khác nhau dựa vào các cấp độ khác nhau của tư cách
thành viên [8].
2.4. Một số kỹ thuật Phân cụm Web điển hình
Kỹ thuật phân cụm được chia thành 2 nhóm chính: Phân cụm theo thứ
bậc và phân cụm bằng cách phân mảnh.
2.4.1. Phân cụm theo thứ bậc
Các kỹ thuật phân cụm theo thứ bậc đưa ra một chuỗi các phần chia lồng
vào nhau với một phân cụm gốc ở trên cùng và các phân cụm đơn của các đối
tượng đơn lẻ ở phía dưới. Các phân cụm ở cấp độ trên chứa các phân cụm phía
dưới chúng theo thứ bậc. Kết quả của thuật toán phân cụm theo thứ bậc có thể
xem như một cây, được gọi là một dendogram (Hình 3).
Hình 3: Một ví dụ dendogram của phân cụm sử dụng phân cụm có thứ bậc
Tùy thuộc vào định hướng của việc xây dựng thứ tự, chúng ta có thể chỉ
ra các cách của phân cụm theo thứ bậc: tích tụ (Agglomerative) hay
chia xẻ (Divisive). cách tích tụ được sử dụng trong hầu hết các phân cụm
theo thứ bậc.
a, Phân cụm tích tụ theo thứ bậc (AHC)
cách này bắt đầu với tập các đối tượng là các phân cụm đơn lẻ,
tiếp đó, tại mỗi bước kết nối 2 phân cụm giống giau nhất với nhau. Quá trình này
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 31 -
được lặp lại cho đến khi số lượng phân cụm còn lại đạt đến một ngưỡng cho phép
hay là nếu cần hoàn thành toàn bộ thứ bậc thì quá trình này sẽ tiếp tục cho
đến khi chỉ còn 1 phân cụm. Phân cụm tích tụ làm việc theo mô hình tham ăn
(greedy), trong đó cặp nhóm tài liệu được chọn cho việc tích tụ là cặp mà được
coi là giống nhau nhất theo một số tiêu chuẩn nào đó.
cách này tương đối đơn giản nhưng cần định nghĩa rõ việc
tính khoảng cách giữa 2 phân cụm. Có 3 cách hay được dùng nhất để tính
toán khoảng cách này đư...
Download miễn phí Luận văn Phương pháp phân cụm tài liệu web và áp dụng vào máy tìm kiếm
MỤC LỤC
DANH MỤC CHỮVIẾT TẮT . 5
DANH MỤC HÌNH VẼ, BẢNG BIỂU . 6
MỞ ĐẦU . 7
CHƯƠNG 1 - KHÁI QUÁT VỀKHAI PHÁ DỮLIỆU WEB . 9
1.1. Khai phá dữliệu Web . 9
1.1.1. Giới thiệu vềKhai phá dữliệu . 9
1.1.2. Dữliệu Web và nhu cầu khai thác thông tin . 11
1.1.3. Đặc điểm của dữliệu Web . 12
1.1.4. Các hướng tiếp cận khai phá dữliệu Web . 13
1.1.5. Nhu cầu Phân cụm tài liệu Web . 14
1.2. Mô hình tìm kiếm thông tin . 15
1.2.1. Giới thiệu . 15
1.2.2. Quy trình tìm kiếm thông tin trong hệthống . 15
1.2.3. Ứng dụng phân cụm vào hệthống tìm kiếm . 18
1.3. Kết luận chương 1 . 19
CHƯƠNG 2 - THUẬT TOÁN PHÂN CỤM WEB . 20
2.1. Một sốnội dung cơbản vềthuật toán phân cụm tài liệu . 20
2.2. Tiêu chuẩn đánh giá thuật toán phân cụm . 22
2.3. Các đặc tính của các thuật toán phân cụm web . 24
2.3.1. Mô hình dữliệu . 24
2.3.2. Độ đo vềsựtương tự. 27
2.3.3. Mô hình phân cụm . 29
2.4. Một sốkỹthuật Phân cụm Web điển hình . 30
2.4.1. Phân cụm theo thứbậc . 30
2.4.2. Phân cụm bằng cách phân mảnh . 33
2.5. Các yêu cầu đối với các thuật toán phân cụm Web . 35
2.5.1. Tách các thông tin đặc trưng . 35
2.5.2. Phân cụm chồng lặp . 36
2.5.3. Hiệu suất . 36
2.5.4. Khảnăng khửnhiễu . 36
2.5.5. Tính tăng . 37
2.5.6. Việc biểu diễn kết quả. 37
2.6. Bài toán tách từtự động tiếng Việt . 37
2.6.1. Một sốkhó khăn trong phân cụm trang Web tiếng Việt . 37
2.6.2.Tiếng và Từtrong tiếng Việt . 39
2.6.3. Phương pháp tách từtự động tiếng Việt fnTBL . 39
2.6.4. Phương pháp Longest Matching . 43
2.6.5. Kết hợp giữa fnTBL và Longest Matching . 44
2.7. Kết luận chương 2 . 44
CHƯƠNG 3 - THUẬT TOÁN PHÂN CỤM CÂY HẬU TỐVÀ THUẬT TOÁN
CÂY PHÂN CỤM TÀI LIỆU . 45
3.1. Giới thiệu vềthuật toán phân cụm trang Web có tính tăng . 45
3.2. Thuật toán phân cụm cây hậu tố. 46
3.2.1. Mô tả. 46
3.2.2. Thuật toán STC . 47
3.3. Thuật toán phân cụm sửdụng cây phân cụm tài liệu . 51
3.3.1. Giới thiệu . 51
3.3.2. Trích chọn đặc trưng và phân cụm tài liệu . 51
3.3.3. Cây phân cụm tài liệu –DC Tree . 55
3.4. Kết luận chương 3 . 60
CHƯƠNG 4 - PHẦN MỀM THỬNGHIỆM VÀ KẾT QUẢTHỰC NGHIỆM . 61
4.1. Giới thiệu . 61
4.2. Thiết kếcơsởdữliệu . 62
4.3. Chương trình thửnghiệm . 65
4.4. Kết quảthực nghiệm . 66
4.5. Kết luận chương 4 .
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung:
pDựa vào các vùng vấn đề, thỉnh thoảng các đối tượng biểu diễn dữ liệu
đặc trưng không có cùng kiểu. Một sự kết hợp giữa các kiểu dữ liệu số, phân
loại, không gian hay text có thể được sử dụng. Trong trường hợp này, vấn đề
quan trọng là nghĩ ra một phương pháp có thể nắm giữ tất cả các thông tin một
cách hiệu quả. Một quy trình chuyển đổi nên được áp dụng để chuyển đổi từ một
kiểu dữ liệu này thành một kiểu dữ liệu khác. Thỉnh thoảng một kiểu dữ liệu
không thể áp dụng vào được, lúc đó thuật toán phải được chỉnh sửa để làm việc
với các kiểu dữ liệu khác [18].
2.3.2. Độ đo về sự tương tự
Nhân tố chính trong thành công của bất kỳ một thuật toán phân cụm nào
đó chính là độ đo về sự tương tự của nó. Để có thể nhóm các đối tượng dữ liệu,
một ma trận xấp xỉ đã được sử dụng để tìm kiếm những đối tượng (hay phân
cụm) tương tự nhau. Có một số lượng lớn các ma trận tương tượng đã được đề
cập đến trong các tài liệu, ở đây, chúng ta chỉ xem qua một số ma trận thông
thường nhất.
Việc tính toán độ (không) tương tự giữa 2 đối tượng được thực hiện
thông qua các hàm tính khoảng cách (distance), thỉnh thoảng cũng có thể sử
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 28 -
dụng các hàm tính về độ không tương tự (dissimilarity). Với 2 véc tơ đặc trưng x
và y, cần tìm ra độ tương tự (hay không tương tự) giữa chúng.
Một lớp rất hay được sử dụng của các hàm khoảng cách đó là “gia đình
các khoảng cách Minkowski” [7], được mô tả như phía dưới:
p
n
i
p
ii yxyx ∑
=
−=−
1
Trong đó x,y ∈ Rn. Hàm khoảng cách này thực ra là mô tả một họ vô số
các khoảng cách được đưa ra bởi p. Thông số này giả thiết là các giá trị lớn hơn
hay bằng 1. Một vài giá trị chung của p và các hàm khoảng cách là:
p = 1: Khoảng cách Hamming ∑
=
−=−
n
i
ii yxyx
1
p = 2: Khoảng cách Euclidean ∑
=
−=−
n
i
ii yxyx
1
2
p = ∞: Khoảng cách Tschebyshev =− yx maxi=1,2,...,n ii yx −
Một độ đo độ tương tự hay được dùng, đặc biệt là trong phân cụm tài
liệu đó là độ đo liên quan cosine (cosine correlation) (được sử dụng trong [4],
[15], và [13]), được định nghĩa là:
yx
yxyx .),cos( =
trong đó . biểu thị việc nhân vector và ||.|| biểu thị cho độ dài của vector.
Một độ đo hay được dùng khác đó là độ đo Jaccard (được sử dụng trong
[8], [9]), được định nghĩa là:
),max(
),min(
),(
1
1
i
n
i i
i
n
i i
yx
yx
yxd ∑
∑
=
==
trong trường hợp các vector đặc trưng nhị phân, có thể đơn giản hóa
thành:
yx
yx
yxd ∪
∩=),(
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 29 -
cần chú ý rằng từ “khoảng cách” không có gì nhập nhằng với
“tương tự”. Những từ này là trái nghĩa với nhau, cho chúng ta biết độ tương tự
giữa 2 đối tượng. Độ tương tự giảm khi khoảng cách tăng. Thêm một điểm cần
chú ý khác đó là nhiều thuật toán sử dụng hàm khoảng cách (hay tương tự) để
tính toán sự tương tự giữa 2 phân cụm, một phân cụm và một đối tượng, hai đối
tượng. Việc tính toán khoảng cách giữa 2 phân cụm (hay các phân cụm và các
đối tượng) yêu cầu một vector đặc trưng thay mặt cho phân cụm.
Thường thì các thuật toán phân cụm thường sử dụng một ma trận tương
tự (similarity matrix). Một ma trận tương tự cỡ N × N ghi nhận các khoảng cách
(hay độ tương tự) giữa từng cặp đối tượng. Hiển nhiên ma trận tương tự là một
ma trận đối xứng do đó chúng ta chỉ cần lưu phần trên bên phải hay phần dưới
bên trái của nó.
2.3.3. Mô hình phân cụm
Bất cứ thuật toán phân cụm nào cũng thừa nhận một cấu trúc phân cụm
nào đó. Đôi khi cấu trúc phân cụm không thực sự rõ ràng tùy theo nhu cầu của
bản thân thuật toán phân cụm. Ví dụ, thuật toán k-means sử dụng các phân cụm
hình cầu (hay các phân cụm lồi). Đó là vì theo cách k-means tìm kiếm phân cụm
trung tâm và cập nhật các đối tượng thành viên. Nếu như không cẩn thận, chúng
ta có thể kết thúc việc phân cụm với các phân cụm kéo dài (elongated cluster),
trong đó kết quả là có ít phân cụm lớn và có nhiều phân cụm rất nhỏ. Wong và
Fu [16] đã đưa ra một giải pháp để giữ kích cỡ phân cụm trong một khoảng nào
đó, nhưng việc giữ kích cỡ phân cụm trong một khoảng nào đó không phải bao
giờ cũng đáng thực hiện. Một mô hình động để tìm kiếm các phân cụm không
thích hợp với cấu trúc của chúng đó là CHAMELEON, được đưa ra bơi Karypis
[13].
Tùy theo vấn đề, chúng ta có thể có các phân cụm tách rời (disjoint)
hay các phân cụm chồng chéo (overlapping). Trong ngữ cảnh phân cụm tài liệu
thường mong muốn có các phân cụm chồng chéo bởi vì tài liệu có xu hướng có
nhiều hơn một chủ đề (ví dụ một tài liệu có thể chứa thông tin về đua ô tô và các
công ty ô tô). Một ví dụ khác về việc tạo ra các phân cụm chồng chéo là hệ thống
cây hậu tố (STC) được đưa ra bởi Zamir và Etzionin [5]. Một cách khác để tạo ra
các phân cụm chồng chéo đó là phân cụm mờ trong đó các đối tượng có thể
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 30 -
thuộc vào các phân cụm khác nhau dựa vào các cấp độ khác nhau của tư cách
thành viên [8].
2.4. Một số kỹ thuật Phân cụm Web điển hình
Kỹ thuật phân cụm được chia thành 2 nhóm chính: Phân cụm theo thứ
bậc và phân cụm bằng cách phân mảnh.
2.4.1. Phân cụm theo thứ bậc
Các kỹ thuật phân cụm theo thứ bậc đưa ra một chuỗi các phần chia lồng
vào nhau với một phân cụm gốc ở trên cùng và các phân cụm đơn của các đối
tượng đơn lẻ ở phía dưới. Các phân cụm ở cấp độ trên chứa các phân cụm phía
dưới chúng theo thứ bậc. Kết quả của thuật toán phân cụm theo thứ bậc có thể
xem như một cây, được gọi là một dendogram (Hình 3).
Hình 3: Một ví dụ dendogram của phân cụm sử dụng phân cụm có thứ bậc
Tùy thuộc vào định hướng của việc xây dựng thứ tự, chúng ta có thể chỉ
ra các cách của phân cụm theo thứ bậc: tích tụ (Agglomerative) hay
chia xẻ (Divisive). cách tích tụ được sử dụng trong hầu hết các phân cụm
theo thứ bậc.
a, Phân cụm tích tụ theo thứ bậc (AHC)
cách này bắt đầu với tập các đối tượng là các phân cụm đơn lẻ,
tiếp đó, tại mỗi bước kết nối 2 phân cụm giống giau nhất với nhau. Quá trình này
Nguyễn Thị Thu Hằng-Luận văn cao học-Trường Đại học Công nghệ-2007.
- 31 -
được lặp lại cho đến khi số lượng phân cụm còn lại đạt đến một ngưỡng cho phép
hay là nếu cần hoàn thành toàn bộ thứ bậc thì quá trình này sẽ tiếp tục cho
đến khi chỉ còn 1 phân cụm. Phân cụm tích tụ làm việc theo mô hình tham ăn
(greedy), trong đó cặp nhóm tài liệu được chọn cho việc tích tụ là cặp mà được
coi là giống nhau nhất theo một số tiêu chuẩn nào đó.
cách này tương đối đơn giản nhưng cần định nghĩa rõ việc
tính khoảng cách giữa 2 phân cụm. Có 3 cách hay được dùng nhất để tính
toán khoảng cách này đư...