Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
------------------------ TRƯƠNG MẠNH HÀ NGHIÊN CỨU MỘT SỐ KỸ THUẬT LẤY TIN
TỰ ĐỘNG TRÊN INTERNET
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

Người hướng dẫn khoa học: TS. Phạm Việt Bình
Thái Nguyên - Năm 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

LỜI CAM ĐOAN
Tôi xin cam đoan toàn bộ nội dung bản luận văn này là do tôi tự sưu tầm,
tra cứu và sắp xếp cho phù hợp với nội dung yêu cầu của đề tài.
Nội dung luận văn này chưa từng được công bố hay xuất bản dưới bất kỳ
hình thức nào và cũng không được sao chép từ bất kỳ một công trình nghiên
cứu nào.

tài liệu phù hợp. Ngoài ra các thông tin đó thường rất phong phú, đa dạng và
liên quan đến nhiều đối tượng khác nhau. Điều này tạo nên sự nhập nhằng gây
khó khăn cho người sự dụng trong việc lấy được các thông tin cần thiết.
Có nhiều hướng tiếp cận khác nhau để giải quyết vấn đề này, các hướng
này thường chú ý giảm sự nhập nhằng bằng các phương pháp lọc hay thêm
các tùy chọn để cắt bớt thông tin và hướng biểu diễn các thông tin trả về bởi
các máy tìm kiếm thành từng cụm để cho người dùng có thể dễ dàng tìm được
thông tin mà họ cần. Đã có nhiều thuật toán phân cụm tài liệu dựa trên phân
cụm ngoại tuyến toàn bộ tập tài liệu. Tuy nhiên việc tập hợp tài liệu của các
máy tìm kiếm là quá lớn và luôn thay đổi để có thể phân cụm ngoại tuyến. Do
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2

đó, việc phân cụm phải được ứng dụng trên tập các tài liệu nhỏ hơn được trả
về từ các truy vấn và thay vì trả về một danh sách rất dài các thông tin gây
nhập nhằng cho người sử dụng cần có một phương pháp tổ chức lại các kết
quả tìm kiếm một cách hợp lý.
Do những vấn đề cấp thiết được đề cập ở trên nên em chọn đề tài:
"Nghiên cứu một số kỹ thuật lấy tin tự động trên internet"
Mục tiêu của đề tài: Nghiên cứu xây dựng giải pháp phát triển hệ thống
phần mềm thu thập, đánh giá và phân cụm thông tin tự động trên Internet
phục vụ cho việc nghiên cứu, học tập, giảng dạy.
Ngoài phần mở đầu, phần kết luận, mục lục, tài liệu tham khảo, phụ lục,
luận văn gồm 3 chương:
- Chương 1: Khái quát về khai phá dữ liệu và phân cụm tài liệu Web
Giới thiệu một số khái niệm cơ bản về khai phá dữ liệu, khai phá dữ liệu
web, các hướng tiếp cận, ứng dụng của khai phá dữ liệu, và nêu bài toàn phân
cụm tài liệu Web.
- Chương 2: Một số thuật toán phân cụm tài liệu
Nghiên cứu một số kỹ thuật phân cụm tài liệu liên quan, tư tưởng của

1.1 Khai phá dữ liệu:
Trong thời đại ngày nay, với sự phát triển vượt bậc của công nghệ thông
tin, các hệ thống thông tin có thể lưu trữ một khối lượng lớn dữ liệu về hoạt
động hàng ngày. Từ khối dữ liệu này, các kỹ thuật trong Khai phá dữ liệu và
Máy học có thể dùng để trích xuất những thông tin hữu ích mà chúng ta chưa
biết. Các tri thức vừa học được có thể vận dụng để cải thiện hiệu quả hoạt
động của hệ thống thông tin ban đầu.
Giáo sư Tom Mitchell đã đưa ra định nghĩa của Khai phá dữ liệu như
sau: “Khai phá dữ liệu là việc sử dụng dữ liệu lịch sử để khám phá những qui
tắc và cải thiện những quyết định trong tương lai.” Với một cách tiếp cận ứng
dụng hơn, Tiến sĩ Fayyad đã phát biểu: “Khai phá dữ liệu, thường được xem
là việc khám phá tri thức trong các cơ sở dữ liệu, là một quá trình trích xuất
những thông tin ẩn, trước đây chưa biết và có khả năng hữu ích, dưới dạng
các qui luật, ràng buộc, qui tắc trong cơ sở dữ liệu”. Nói tóm lại, Khai phá dữ
liệu là một quá trình học tri thức mới từ những dữ liệu đã thu thập được [4].
Mô hình khai phá dữ liệu bao gồm năm giai đoạn chính:
- Tìm hiểu nghiệp vụ và dữ liệu
- Chuẩn bị dữ liệu
- Mô hình hoá dữ liệu
- Hậu xử lý và đánh giá mô hình
- Triển khai tri thức
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
5

Quá trình này có thể được lặp lại nhiều lần một hay nhiều giai đoạn dựa
trên phản hồi từ kết quả của các giai đoạn sau. Tham gia chính trong quá trình
Khai phá dữ liệu là các nhà tư vấn và phát triển chuyên nghiệp trong lĩnh vực
Khai phá dữ liệu.
Trong giai đoạn đầu tiên, tìm hiểu nghiệp vụ dữ liệu, nhà tư vấn nghiên
cứu kiến thức về lĩnh vực sẽ áp dụng, bao gồm các tri thức cấu trúc về hệ

tìm kiếm các qui tắc ẩn và chưa biết. Công việc quan trọng nhất trong giai
đoạn này là lựa chọn kỹ thuật phù hợp để giải quyết các vấn đề đặt ra. Các bài
toán được phân loại vào một trong những nhóm bài toán chính trong Khai phá
dữ liệu dựa trên đặc tả của chúng [4].
Các mô hình kết quả của giai đoạn ba sẽ được hậu xử lý và đánh giá
trong giai đoạn (d). Dựa trên các đánh giá của người dùng sau khi kiểm tra
trên các tập thử, các mô hình sẽ được tinh chỉnh và kết hợp lại nếu cần. Chỉ
các mô hình đạt được mức yêu cầu cơ bản của người dùng mới đưa ra triển
khai trong thực tế. Trong giai đoạn này, các kết quả được biến đổi từ dạng học
thuật sang dạng phù hợp với nghiệp vụ và dễ hiểu hơn cho người dùng.
Trong giai đoạn cuối, Triển khai tri thức, các mô hình được đưa vào
những hệ thống thông tin thực tế dưới dạng các module hỗ trợ việc đưa ra
quyết định.
Mối quan hệ chặt chẽ giữa các giai đoạn trong quá trình Khai phá dữ liệu
là rất quan trọng cho việc nghiên cứu trong Khai phá dữ liệu [3]. Một giải
thuật trong Khai phá dữ liệu không thể được phát triển độc lập, không quan
tâm đến bối cảnh áp dụng mà thường được xây dựng để giải quyết một mục
tiêu cụ thể. Do đó, sự hiểu biết bối cảnh vận dụng là rất cần thiết. Thêm vào
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
7

đó, các kỹ thuật được sử dụng trong các giai đoạn trước có thể ảnh hưởng đến
hiệu quả của các giải thuật sử dụng trong các giai đoạn tiếp theo.
1.1.1 Các dạng dữ liệu
1.1.1.1 Full text
Dữ liệu dạng Full text là một dạng dữ liệu phi cấu trúc với thông tin chỉ
gồm các tài liệu dạng text. Mỗi tài liệu chứa thông tin về một vấn đề nào đó
thể hiện qua nội dung của tất cả các từ cấu thành tài liệu đó. Ý nghĩa của mỗi
từ trong tài liệu không cố định mà tùy thuộc vào từng ngữ cảnh khác nhau sẽ
mang ý nghĩa khác nhau. Các từ trong tài liệu được liên kết với nhau theo một

Bên cạnh đó, Hypertext cũng là một dạng văn bản Text đặc biệt nên
cũng có thể bao gồm các chữ viết liên tục (là dạng phổ biến nhất của chữ
viết). Do không bị hạn chế bởi tính liên tục trong Hypertext, chúng ta có thể
tạo ra các dạng trình bày mới, do đó tài liệu sẽ phản ánh tốt hơn nội dung
muốn diễn đạt. Hơn nữa người đọc có thể chọn cho mình một cách đọc phù
hợp chẳng hạn như đi sâu vào một vấn đề mà họ quan tâm. Sáng kiến tạo ra
một tập các văn bản cùng với các con trỏ tới các văn bản khác để liên kết một
tập các văn bản có mối quan hệ với nhau là một cách thực sự hay và hữu ích
để tổ chức thông tin. Với người viết, cách này cho phép họ có thể thoải mái
loại bỏ những băn khoăn về thứ tự trình bày mà có thể tổ chức vấn đề thành
những phần nhỏ rồi sử dụng kết nối để chỉ ra mối liên hệ giữa các phần nhỏ
đó với nhau.
Với người đọc, cách này cho phép họ có thể đi tắt trên mạng thông tin và
quyết định phần thông tin nào có liên quan đến vấn đề mà họ quan tâm để tiếp
tục tìm hiểu. So sánh với cách đọc tuyến tính tức là đọc lần lượt thì Hypertext
đã cung cấp cho chúng ta một giao diện để có thể tiếp xúc với nội dung thông
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
9

tin hiệu quả hơn rất nhiều. Theo khía cạnh của các thuật toán học máy thì
Hypertext đã cung cấp cho chúng ta cơ hội nhìn ra ngoài phạm vi một tài liệu
để đánh giá nó, nghĩa là có tính cả đến các tài liệu có liên kết với nó. Tất
nhiên không phải tất cả các tài liệu có liên kết đến nó đều có ích cho việc
đánh giá, đặc biệt là khi các siêu liên kết có thể chỉ đến nhiều loại các tài liệu
khác nhau.
Có hai khái niệm về Hypertext cần quan tâm:
Hypertext Document (Tài liệu siêu văn bản): Là một tài liệu văn bản đơn
trong hệ thống siêu văn bản. Nếu tưởng tượng hệ thống siêu văn bản là một
đồ thị thì các tài liệu tương ứng các nút.
Hypertext Link (Liên kết siêu văn bản): Là một tham chiếu để nối một

kèm với nhau trong siêu thị.
Các kỹ thuật Phân cụm (Clustering) sẽ nhóm các đối tượng dữ liệu có tính
chất giống nhau vào cùng một nhóm. Có nhiều cách tiếp cận với những mục tiêu
khác nhau trong phân loại. Các kỹ thuật trong bài toán này thường được vận
dụng trong vấn đề phân hoạch dữ liệu tiếp thị hay khảo sát sơ bộ các dữ liệu.
1.1.3 Các môi trường khai phá dữ liệu
Do các đặc tính được nêu ra trong phần 2, các công cụ Khai phá dữ liệu
thường được xây dựng theo dạng môi trường phát triển, dễ thử nghiệm và
thay đổi các tác vụ Khai phá dữ liệu. Hình 1.1 giới thiệu giao diện trực quan
của một quá trình Khai phá dữ liệu trong môi trường Clementine [4].
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
11 Hình 1.1: Giao diện trực quan của môi trường khai phá dữ liệu Clementine
Trong các môi trường này, một quá trình Khai phá dữ liệu được mô tả
như một dòng các tác vụ nối tiếp, bắt đầu bằng việc lấy dữ liệu thực từ nguồn
dữ liệu lịch sử, thao tác biến đổi dữ liệu sang dạng thích hợp, học và sinh ra
mô hình mới. Mô hình này sau đó được thử nghiệm trên dữ liệu thực để đưa
ra các đánh giá. Nếu mô hình được đánh giá chưa thỏa mãn các yêu cầu đề ra,
các tác vụ trong quá trình được tinh chỉnh rồi thực hiện lại. Qui trình này
được lặp lại cho đến khi nào mô hình sinh ra được đánh giá có hiệu quả tốt.
Mô hình sinh ra cuối cùng sẽ được triển khai sử dụng trong thực tế. Các môi
trường như vậy rất phù hợp cho quá trình Khai phá dữ liệu vì tính chất thử
nghiệm và cần thay đổi nhiều của nó.
Việc sử dụng các môi trường thử nghiệm đã thúc đẩy nhanh việc áp
dụng Khai phá dữ liệu. Thay vì phải bỏ nhiều công sức và thời gian vào việc
xây dựng các chương trình hoàn chỉnh và hiện thực các giải thuật, khi dữ liệu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
12

giá trị của sản phẩm trên thị trường cho các công ty tài chính hay phân nhóm
các khách hàng tiềm năng,…
Ngoài ra, Khai phá dữ liệu còn được áp dụng cho các vấn đề xã hội như
phát hiện tội phạm hay tăng cường an ninh xã. Việc vận dụng thành công đã
mang lại những hiệu quả thiết thực cho các hoạt động diễn ra hàng ngày trong
đời sống.
1.2. Phân cụm tài liệu và phân cụm tài liệu Web
Phân cụm (Clustering) là quá trình nhóm một tập các đối tượng vật lý
hoặc trừu tượng thành các nhóm hay các lớp đối tượng tương tự nhau. Một
cụm (cluster) là một tập các đối tượng giống nhau hay là tương tự nhau,
chúng khác hoặc ít tương tự so với các đối tượng thuộc lớp khác. Không
giống như quá trình phân loại, ta thường biết trước tính chất hay đặc điểm của
các đối tượng trong cùng một lớp và dựa vào đó để ấn định một đối tượng vào
lớp của nó, trong quá trình chia lớp ta không hề biết trước tính chất của các
lớp và thường dựa vào mối quan hệ của các đối tượng để tìm ra sự giống nhau
giữa các đối tượng dựa vào một độ đo nào đó đặc trưng cho mỗi lớp.
Việc phân cụm không thực hiện độc lập mà thường sử dụng kết hợp với
các phương pháp khác. Một cách phân cụm được đưa ra cũng phải có một
phương pháp áp dụng trên các lớp đó để đưa ra được ý nghĩa của lớp đó.
Ở một mức cơ bản nhất, người ta đã đưa ra định nghĩa Phân cụm dữ liệu
như sau:
"Phân cụm dữ liệu là một kỹ thuật trong DATA MINING, nhằm tìm
kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn, quan tâm trong tập
dữ liệu lớn, từ đó cung cấp thông tin, tri thức hữu ích cho ra quyết định".
Hiện nay có rất nhiều vấn đề nghiên cứu về phân cụm trong các lĩnh
vực khác nhau như: Khai phá dữ liệu, thống kê, học máy, công nghệ dữ liệu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
14

không gian, sinh học... Do kích thước của các cơ sở dữ liệu tăng lên rất nhanh

từ nguồn đa phương tiện trực tuyến rộng lớn.
1.2.1.2 Khai phá văn bản Web
Khai phá văn bản Web là việc sử dụng kỹ thuật khai phá dữ liệu đối với
các tập văn bản để tìm ra tri thức có ý nghĩa tiềm ẩm trong nó [12]. Dữ liệu
của nó có là dữ liệu có cấu trúc hoặc không cấu trúc. Kết quả khai phá không
chỉ là trạng thái chung của mỗi tài liệu văn bản mà còn là sự phân loại, phân
cụm các tập văn bản phục vụ cho mục đích nào đó.

Hình 1.2: Quá trình khai phá văn bản Web
- Lựa chọn dữ liệu: Về cơ bản, văn bản văn bản cục bộ được định dạng
tích hợp thành các tài liệu theo mong muốn để khai phá và phân phối trong
nhiều dịch vụ Web bằng việc sử dụng kỹ thuật truy xuất thông tin.
- Tiền xử lý dữ liệu: Để có một kết quả khai phá tốt ta cần có dữ liệu rõ
ràng, chính xác và xoá bỏ dữ liệu hỗn độn và dư thừa. Sau bước tiền xử lý, tập
dữ liệu đạt được thường có các đặc điểm sau:
+ Dữ liệu thống nhất và hỗn hợp cưỡng bức.
+ Làm sạch dữ liệu không liên quan, nhiễu và dữ liệu rỗng. Dữ liệu
không bị mất mát và không bị lặp.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
16

+ Giảm bớt số chiều và làm tăng hiệu quả việc phát hiện tri thức bằng
việc chuyển đổi, quy nạp, cưỡng bức dữ liệu...
+ Làm sạch các thuộc tính không liên quan để giảm bớt số chiều của dữ liệu.
- Biểu diễn văn bản: Khai phá văn bản Web là khai phá các tập tài liệu
HTML. Do đó ta sẽ phải biến đổi và biểu diễn dữ liệu thích hợp cho quá trình
xử lý. Người ta thường dùng mô hình TF-IDF để vector hoá dữ liệu. Nhưng có
một vấn đề quan trọng là việc biểu diễn này sẽ dẫn đến số chiều vector khá lớn.
- Trích rút đặc trưng: Rút ra các đặc trưng là một phương pháp, nó có thể
giải quyết số chiều vector đặc trưng lớn được mang lại bởi khai phá văn bản.

bằng thuật toán nào đó. Khi đó các tài liệu có độ tương tự cao với nhau thì
nằm trong cùng một phân lớp. Độ tương tự sẽ được đo bằng hàm đánh giá xác
định trước. Nếu ít tài liệu tương tự nhau thì đưa nó về 0. Nếu nó không giống
với sự lựa chọn của phân lớp xác định trước thì xem như không phù hợp.
- Phân cụm văn bản: Chủ đề phân loại không cần xác định trước nhưng
ta phải phân loại các tài liệu vào nhiều cụm. Trong cùng một cụm thì độ
tương tự thấp hơn. Phương pháp sắp xếp liên kết và phương pháp phân cấp
thường được sử dụng trong văn bản phân cụm.
- Phân tích và dự đoán xu hướng: Thông qua việc phân tích các tài liệu
Web, ta có thể nhận được quan hệ phân phối của các dữ liệu đặc biệt trong
từng giai đoạn của nó và có thể dự đoán được tương lai phát triển.
- Đánh giá chất lượng mẫu: Khai phá dữ liệu Web có thể được xem như
quá trình của machine learning. Kết quả của machine learning là các mẫu tri
thức. Phần quan trọng của machine learning là đánh giá kết quả các mẫu. Ta
thường phân lớp các tập tài liệu vào tập huấn luyện và tập kiểm tra. Cuối
cùng, chất lượng trung bình được dung để đánh giá chất lượng mô hình.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
18

1.2.2. Bài toán phân cụm tài liệu Web
Nắm bắt những đặc tính của người dung Web là việc rất quan trọng đối
với người thiết kế Website. Thông qua việc khai phá lịch sử các mẫu truy xuất
của người dùng Web, không chỉ thông tin về Web được sử dụng như thế nào
mà còn nhiều đặc tính khác như các hành vi của người dùng có thể được xác
định. Sự điều hướng đường dẫn người dùng Web mang lại giá trị thông tin về
mức độ quan tâm của người dùng đến các Website đó.
Khai phá Web theo sử dụng Web là khai phá truy cập Web để khám phá
các mẫu người dùng truy cập vào Website.
Kiến trúc tổng quát của quá trình khai phá theo sử dụng Web như sau:


Web thành các cụm, sao cho các trang trong cụm "tương tự" về nội dung với
nhau hơn các trang ngoài cụm.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
20 Hình 1.4: Các bước phân cụm kết quả tìm kiếm trên Web
- Tìm kiếm dữ liệu trên Web: Nhiệm vụ chủ yếu của giai đoạn này là dựa
vào tập từ khoá tìm kiếm để tìm kiếm và trả về tập gồm toàn văn tài liệu, tiêu
đề, mô tả tóm tắt, URL... tương ứng với các trang đó.
- Tiền xử lý dữ liệu: Quá trình làm sạch dữ liệu và chuyển dịch các tài
liệu thành các dạng biểu diễn dữ liệu thích hợp.
- Chuẩn hoá văn bản: Đây là giai đoạn chuyển hoá văn bản thô về dạng
văn bản sao cho việc xử lý sau này được dễ dàng, đơn giản, thuận tiện, chính
xác so với việc xử lý trực tiếp trên văn bản thô mà ảnh hưởng ít đến kết quả
xử lý.
- Xoá bỏ từ dừng: Trong văn bản có những từ mang ít thông tin quan
trọng trong quá trình xử lý, những từ có tần số xuất hiện thấp, những từ xuất
hiện với tần số lớn nhưng không quan trọng trong quá trình xử lý đều được
loại bỏ. Theo một số nghiên cứu gần đây cho thấy việc loại bỏ các từ dừng có
thể giảm bớt được khoảng 20 - 30% tổng số từ trong văn bản.
- Kết hợp các từ có cùng gốc: Hầu hết trong các ngôn ngữ đều có rất
nhiều các từ có chung nguồn gốc với nhau, chúng mang ý nghĩa tương tự
nhau, do đó để giảm bớt số chiều trong biểu diễn văn bản, ta sẽ kết hợp với
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
21

các từ có cùng gốc thành một từ. Ví dụ trong tiếng Anh từ user, users, used,
using có cùng từ gốc và sẽ được quy về use.
- Xây dựng từ điển: Việc xây dựng từ điển là một công việc rất quan

một phân hoạch mong muốn, thoả mãn ràng buộc cho trước. Các thuật toán
phân cụm phân hoạch cố gắng cải tiến tiêu chuẩn phân cụm, bằng cách tính
các giá trị đo độ tương tự giữa các đối tượng dữ liệu và sắp xếp các giá trị
này, sau đó thuật toán lựa chọn một giá trị trong dãy sắp xếp sao cho hàm tiêu
chuẩn đạt giá trị tối thiểu. Như vậy, ý tưởng chính của thuật toán phân cụm
phân hoạch tối ưu cục bộ là sử dụng chiến lược ăn tham (Greedy) để tìm kiếm
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
23

nghiệm. Một số thuật toán phân cụm phân hoạch điển hình như k-means,
PAM, CLARA, CLARANS… sẽ được trình bày chi tiết ở những chương sau.
2.1.2 Phân cụm dữ liệu phân cấp
Phân cụm phân cấp sắp xếp một tập dữ liệu đã cho thành một cấu trúc có
dạng hình cây, cây phân cấp này được xây dựng theo kỹ thuật đệ quy. Cây
phân cụm có thể được xây dựng theo hai phương pháp tổng quát: phương
pháp dưới lên (Bottom up) và phương pháp trên xuống (Top down) [5].
Phương pháp “dưới lên” (Bottom up): Phương pháp này bắt đầu với mỗi
đối tượng được khởi tạo tương ứng với các cụm riêng biệt, sau đó tiến hành
nhóm các đối tượng theo một độ đo tương tự (như khoảng cách giữa hai trung
tâm của hai nhóm), quá trình này được thực hiện cho đến khi tất cả các nhóm
được hòa nhập vào một nhóm (mức cao nhất của cây phân cấp) hoặc cho đến
khi các điều kiện kết thúc thỏa mãn. Như vậy, cách tiếp cận này sử dụng
chiến lược ăn tham trong quá trình phân cụm.
Ví dụ: Dùng phương pháp "dưới lên" để phân cụm cho tập dữ liệu
S= {a, b, c, d, e}. Các bước thực hiện phân cụm được diễn tả như sau :
Bước 0: Mỗi đối tượng dữ liệu được gán cho mỗi cụm tương ứng, đồng
thời xác định tâm D cho mỗi cụm, và tính độ tương tự cho các cặp cụm dữ
liệu trên bằng cách xác định độ tương tự giữa cặp tâm của chúng. Như vậy ta
sẽ có các cụm ban đầu là {a}, {b}, {c}, {d}, {e}.
Bước 1: Xác định ngưỡng µ, các cặp cụm có độ tương tự bé hơn hoặc