K-Means và gom cụm văn bản
Vũ Công Tâm
K-MEANS - GOM NHÓM VĂN BẢN VÀ PHÂN LOẠI WEB
(Vũ Công Tâm, 11-2012)
Lời nói đầu
Từ ngày máy tính ra đời và đặc biệt là internet xuất hiện, tốc độ lưu truyền và dung lượng
của thông tin ngày một lớn, và thời gian để lượng thông tin tăng gấp đôi ngày càng ngắn lại, và
ngày càng ngắn lại một cách đáng kinh ngạc. Tốc độ lan truyền thông tin và khả năng kết nối
mọi người trở nên nhanh chóng và rất dễ dàng. Chỉ cần một nơi nào đó xảy ra tai nạn hoặc có sự
kiện nào đó, thì dường như ngay lập tức, thông tin đó đã được lan truyền một cách rộng rãi trên
mạng internet. Chúng ta không cần phải đợi đến tối để xem bản tin thời sự 19h mới có thể biết.
Tại một thời điểm, luồng thông tin và tin tức đến với chúng ta liên tục, từ các trang web tin tức
truyền thống tới những mạng xã hôi đã là những kênh truyển tải thông tin liên tục và cập nhật
dường như ngay sau khi sự kiện diễn ra chỉ vài phút.Thật là không sai khi mà có người đã nhận
đinh rằng, con người chết ngụp trong biển thông tin nhưng thiết kiến thức. Vì có quá nhiều dòng
tin trùng lặp nên con người khó khăn trong việc tổng kết và rút trích ra được những tri thức cần
thiết. Chính vì vậy, lĩnh vực khai phá dữ liệu (Data Mining) ra đời như một sự tất yếu để giúp
con người có thể tìm được kiến thức cũng như thông tin cần thiết nhu cầu của mình trước một
biển thông tin.
Bài báo cáo này gồm ba phần chính:
Phần một: Khái quát về khai phá dữ liệu và vai trò của khai thác dữ liệu trong thời
buổi hiện tại.
Phần hai: Khái quát về gom nhóm dữ liệu
Phần ba: Thuật toán K-Means.
Phần bốn: Chương trình gom cụm văn bản và phân loại web
Em xin chân thành cám ơn thầy Đỗ Phúc, PGS-TS của trường ĐH CNTT TPHCM đã rất
nhiệt tình lên lớp giảng dạy môn Khai Phá Dữ Liệu, sự thật tới thời điểm này. Có thể khẳng định
một điều là em đã rất định đúng đắn khi quyết định học cao học. Sau gần 1 năm học với các thầy
em đã học được rất điều hay, không chỉ kiến thức chuyên ngành mà mà một lượng kiến thức tổng
hợp rất lớn.
Một lần nữa em xin chân thành cảm ơn thầy Đỗ Phúc

Trang 1/36
K-Means và gom cụm văn bản
Vũ Công Tâm
TP.HCM Ngày 20 tháng 11 năm 2012
Vũ Công Tâm
ĐÁNH GIÁ CỦA GIÁO VIÊN HƯỚNG DẪN
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
………………………………………………………………………………………………………
Trang 2/36
K-Means và gom cụm văn bản
Vũ Công Tâm
MỤC LỤC
PHẦN MỘT
KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU VÀ VAI TRÒ CỦA NÓ TRONG
Trang 3/36
K-Means và gom cụm văn bản
Vũ Công Tâm
THỜI BUỔI HIỆN TẠI
I.1 Khai phá dữ liệu (Data mining) là gì?
Data mining là một quá trình trích xuất thông tin có mối quan hệ hoặc có mối tương quan
nhất định từ một kho dữ liệu lớn (cực lớn) nhằm mục đích dự đoán các xu thế, các hành vi trong
tương lai, hoặc tìm kiếm những tập thông tin hữu ích mà bình thường không thể nhận diện được.

Về bản chất, khai thác dữ liệu giúp các tổ chức phân tích lượng đáng kinh ngạc của dữ
liệu để phát hiện các mô hình chung hoặc tìm hiểu những điều mới.
I.2 Phương pháp tiếp cận
Có nhiều cách tiếp cận để khai phá dữ liệu, nhưng nhìn chung là những loại chính sau đây:
Gom cụm (clustering): Là phát hiện là một nhóm các đối tượng có nội dung gần giống nhau và
xếp chúng chung vào một nhóm giữa các tập dữ liệu lớn.
Phân lớp (classification): Đó là một sự sắp xếp một số lượng lớn các thông tin vào các mục
bằng cách sử dụng các mẫu xuất hiện trong quá trình phân tích dữ liệu.
Trang 4/36
K-Means và gom cụm văn bản
Vũ Công Tâm
Phát hiện dị thường (Anomaly detection alms): Nhằm mục đích để tìm ra những bất thường
trong dữ liệu. Điều này có thể được sử dụng trong nhiều lĩnh vực, chẳng hạn như phát hiện các
bất thường về thời tiết hoặc thậm chí máy tính pháp y.
Hồi quy (Regression): Hồi quy là một kỹ thuật nhằm mục đích để dự đoán các kết quả trong
tương lai bằng cách sử dụng bộ lớn của các biến hiện có. Điều này được sử dụng để dự đoán sự
tham gia của người sử dụng trong tương lai, duy trì khách hàng và thậm chí là giá bất động sản.
Tổng hợp (Summarization): Mô tả thông tin thu thập được trong một tập dữ liệu lớn.
Mô hình ràng buộc (Dependency modeling):Tìm hiểu và rút trích ra thông tin về sự ràng buộc
giữa các thành phần trong tập dữ liệu hoặc một phần trong tập dữ liệu
Dò tìm biến đổi và độ lệch (Change and Deviation Dectection): Khám phá những thay đổi quan
trọng nhất trong tập dữ liệu.
……………………………………………………………………………………………
Có nhiều cách tiếp cận khác để khai thác dữ liệu, tùy thuộc vào mục đích mà bạn sẽ chọn
kĩ thuật phù hợp
Ứng dụng của nó rất đa dạng và rộng tới, từ marketing, chống gian lận, giảm giá thành
sản xuất, tăng doanh thu, phân tích hành vi sử dung người dùng internet để target đúng nhu cầu,
đúng đối tượng hay ứng dụng hỗ trợ ra quyết định, nghiên cứu khoa học đến việc chống khủng
bố v.v
Các công cụ, kỹ thuật data mining có thể trả lời các câu hỏi mà các công cụ truyền thống

đòi hỏi rất nhiều thời gian cần thiết để có thể giải đáp được (thậm chí các cách truyền thống
không thể giải được). Nó có thể tìm thấy được những thông tin cực kỳ hữu ích mà rất dễ bị bỏ
qua hoặc không xem xét đến để có thể dự đoán những xu thế/hành động xảy ra trong tương lai.
Để có thể data mining một cách hiệu quả, điều đầu tiên cần phải thu thập dữ liệu và định
nghĩa lại theo các tiêu chí cần phân tích. Các kỹ thuật data mining có thể cài đặt rất nhanh chóng
trên các nền tảng phần mềm, phần cứng phổ thông mà không cần đòi hỏi quá phức tạp, tuy vậy
data mining thường gắn liền với việc phân tích một khối lượng dữ liệu cực lớn nên cần ứng dụng
các công nghệ high performance client/server hoặc xử lý song song (parallel programming).
Trang 5/36
K-Means và gom cụm văn bản
Vũ Công Tâm
I.3 Các bước thực hiện data mining
Thu thập, bóc tách, chuẩn hóa dữ liệu và nhập dữ liệu vào hệ thống kho dữ liệu
(Datawarehouse).
Lưu trữ và quản lý dữ liệu dưới dạng đa chiều.
Đưa ra các cơ chế truy xuất cho các ứng dụng phân tích dữ liệu .
Sử dụng các phần mềm phân tích để tính toán.
Kết xuất dữ liệu dưới dạng dễ hiểu, như biểu đồ hoặc dạng report.
Làm sạch dữliệu (data cleaning & preprocessing)s: Thu thập, bóc tách, chuẩn hóa dữ liệu loại
bỏ nhiễu và các dữ liệu không cần thiết.
Tích hợp dữliệu: (data integration): quá trình hợp nhất dữ liệu thành những kho dữliệu (data
warehouses & data marts) sau khi đã làm sạch và tiền xử lý (data cleaning & preprocessing).
Trích chọn dữliệu (data selection): trích chọn dữ liệu từ những kho dữ liệu và sau đó chuyển
đổi về dạng thích hợp cho quá trình khai thác tri thức. Quá trình này bao gồm cả việc xửlý với dữ
liệu nhiễu (noisy data), dữ liệu không đầy đủ (incomplete data), .v.v.
Chuyển đổi dữ liệu: Các dữ liệu được chuyển đổi sang các dạng phù hợp cho quá trình xử lý
Khai phá dữ liệu(data mining): Là một trong các bước quan trọng nhất,trong đó sử dụng
những phương pháp thông minh để chắt lọc ra những mẫu dữ liệu.
Ước lượng mẫu (knowledge evaluation): Quá trình đánh giá các kết quả tìm được thông qua
các độ đo nào đó.

Trang 6/36
K-Means và gom cụm văn bản
Vũ Công Tâm
Biểu diễn tri thức (knowledge presentation): Quá trình này sửdụng các kỹ thuật đểbiểu diễn
và thểhiện trực quan cho người dùng.
I.4 Một số công nghệ thường được dung trong Data Mining
Mạng trí tuệ nhân tạo (Artificial neural networks): Đây là mô hình mà hệ thống có thể tự
học thông qua đào tạo với tập dữ liệu ban đầu, từ đó suy đoán ra các tập kết quả từ tập dữ liệu mà
nó khai thác.
Cây quyết định (Decisions Trees): Một tập các decisions biểu diễn dưới dạng cây, các
decisions này tạo ra các luật cho việc phân loại tập dữ liệu. Nôm na là, nếu tập thông tin A thõa
mãn các luật B thì quyết định C.
Giải thuật di truyền (Generic Algorithms): Kỹ thuật này sử dụng trong các quá trình phối
hợp, biến đổi, chọn lọc tự nhiên kế thừa từ khái niệm tiến hóa.
Phương pháp ông hàng xóm gần nhất (Nearest neighbor method): Đây là kỹ thuật phân loại
từng bản ghi/thông tin trong tập dữ liệu dựa trên sự kết hợp của k records có độ giống nhau nhất
trong tập dữ liệu quá khứ.
Nguyên tắc suy diễn (Rule induction): Kỹ thuật bóc tác dữ liệu dựa trên nguyên tắc Nếu-
Thì từ các tập dữ liệu thống kê.
I.5 Lợi ích của khai thác dữ liệu
Trong tài chính, ngân hàng, khai thác dữ liệu được sử dụng để tạo ra các mô hình rủi ro
chính xác đối với các khoản vay và thế chấp. Họ cũng rất hữu ích khi phát hiện các giao dịch
gian lận.
Trong tiếp thị, kỹ thuật khai thác dữ liệu được sử dụng để cải thiện chuyển đổi, làm tăng sự
hài lòng của khách hàng và tạo ra các chiến dịch quảng cáo nhắm mục tiêu.Họ thậm chí có thể
được sử dụng khi phân tích các nhu cầu trên thị trường và đến với những ý tưởng cho các dòng
sản phẩm hoàn toàn mới. Điều này được thực hiện bằng cách nhìn vào doanh số bán hàng lịch sử
và dữ liệu khách hàng và tạo ra các mô hình dự báo mạnh mẽ.
Cửa hàng bán lẻ sử dụng thói quen mua sắm của khách hàng / chi tiết để tối ưu hóa bố trí
của các cửa hàng của họ để cải thiện trải nghiệm của khách hàng và tăng lợi nhuận.

Cơ quan thuế quản lý sử dụng các kỹ thuật khai thác dữ liệu để phát hiện các giao dịch
gian lận và duy nhất hiện khai thuế đáng ngờ hoặc các tài liệu kinh doanh khác.
Trong sản xuất, dữ liệu phát hiện được sử dụng để cải thiện an toàn sản phẩm, khả năng sử
dụng và thoải mái.
Các hạn chế của khai phá dữ liệu
Trang 7/36
K-Means và gom cụm văn bản
Vũ Công Tâm
Vẫn có các mối lo ngại về tính riêng tư gắn với việc khai thác dữ liệu. Ví dụ, nếu một ông
chủ có quyền truy xuất vào các hồ sơ y tế, họ có thể loại những người có bệnh tiểu đường hay
bệnh tim. Việc loại ra những nhân viên như vậy sẽ cắt giảm chi phí bảo hiểm, nhưng tạo ra các
vấn đề về tính hợp pháp và đạo đức.
Khai thác dữ liệu các tập dữ liệu thương mại hay chính phủ cho các mục đích áp đặt luật
pháp và an ninh quốc gia cũng là những mối lo ngại về tính riêng tư đang tăng cao. 5
Có nhiều cách sử dụng hợp lý với khai thác dữ liệu. Ví dụ, một CSDL các mô tả về thuốc
được thực hiện bởi một nhóm người có thể được dùng để tìm kiếm sự kết hợp của các loại thuốc
tạo ra các phản ứng (hóa học) khác nhau. Vì việc kết hợp có thể chỉ xảy ra trong 1 phần 1000
người, một trường hợp đơn lẻ là rất khó phát hiện. Một dự án liên quan đến y tế như vậy có thể
giúp giảm số lượng phản ứng của thuốc và có khả năng cứu sống con người. Không may mắn là,
vẫn có khả năng lạm dụng đối với một CSDL như vậy.
Về cơ bản, khai thác dữ liệu đưa ra các thông tin mà sẽ không có sẵn được. Nó phải được
chuyển đổi sang một dạng khác để trở nên có nghĩa. Khi dữ liệu thu thập được liên quan đến các
cá nhân, thì có nhiều câu hỏi đặt ra liên quan đến tính riêng tư, tính hợp pháp, và đạo đức.
Khai phá dữ liệu văn bản (textmining) và khai phá dữ liệu web (webmining)
TextMining (Khai phá dữliệu văn bản) và WebMining (Khai phá dữliệu Web) là một
trong những ứng dụng quan trọng của Datamining. Trong phần này ta sẽ đi sâu hơn vào bài toán
này.
I.6 Các bài toán trong khai phá dữ liệu văn bản
I.6.1 Tìm kiếm văn bản
Bài toán:

Tìm kiếm văn bản là quá trình tìm kiếm văn bản theo yêu cầu của người dùng.Các yêu
cầu được thểhiện dưới dạng các câu hỏi (query), dạng câu hỏi đơn giản nhất là các từkhóa. Có
thểhình dung hệtìm kiếm văn bản sắp xếp văn bản thành hai lớp: Một lớp cho ra những các văn
bản thỏa mãn với câu hỏi đưa ra và một lớp không hiển thịnhững văn bản không được thỏa mãn.
Các hệthống thực tếhiện nay không hiển thị nhưvậy mà đưa ra các danh sách văn bản theo
độquan trọng của văn bản tuỳtheo các câu hỏi đưa vào, ví dụ điển hình là các máy tìm tin
nhưGoogle, Altavista,…
Quá trình
Quá trình tìm tin được chia thành bốn quá trình chính :
Trang 8/36
K-Means và gom cụm văn bản
Vũ Công Tâm
Đánh chỉ số(indexing): Các văn bản ởdạng thô cần được chuyển sang một dạng biểu diễn
nào đó đểxửlý. Quá trình này còn được gọi là quá trình biểu diễn văn bản, dạng biểu diễn phải có
cấu trúc và dẽdàng khi xử lý.
Định dạng câu hỏi: Người dùng phải mô tảnhững yêu cầu vềlấy thông tin cần thiết dưới
dạng câu hỏi. Các câu hỏi này phải được biểu diễn dưới dạng phổbiến cho các hệtìm kiếm
nhưnhập vào các từkhóa cần tìm. Ngoài ra còn có các phương pháp định dạng câu hỏi dưới dạng
ngôn ngữtựnhiên hoặc dưới dạng các ví dụ, đối với các dạngnày thì cần có các kỹthuật xửlý phức
tạp hơn. Trong các hệtìm tin hiện nay thì đại đa sốlà dùng câu hỏi dưới dạng các từkhóa.
So sánh: Hệthống phải có sựso sánh rõ ràng và hoàn toàn câu hỏi các câu hỏi của người
dùng với các văn bản đượcl ưu trữtrong CSDL. Cuối cùng hệ đưa ra một quyết định phân loại
các văn bản có độliên quan gầnvới câu hỏi đưa vào và thứ tự của nó. Hệ sẽ hiển thịtoàn bộvăn
bản hoặc chỉmột phần văn bản.
Phản hồi: Nhiều khi kết quả được trảvềban đầu không thỏa mãn yêu cầu của người dùng,
do đó cần phải có qua trình phản hồi đểngười dùng có thểt hay đổi lại hoặc nhập mới các yêu cầu
của mình. Mặt khác, người dùng có thểtương tác với các hệvềcác văn bản thỏa mãn yêu cầu của
mình và hệcó chức năng cập nhậu các văn bản đó. Quá trình này được gọi là quá trình phản hồi
liên quan (Relevance feeback).
Các công cụ tìm kiếm hiện nay chủyếu tập trung nhiều vào ba quá trình đầu,còn phần lớn chưa

có quá trình phản hồi hay xửlý tương tác người dùng và máy. Quá trình phản hồi hiện nay đang
được nghiên cứu rộng rãi và riêng trong quá trình tương tác giao diện người máy đã xuất hiện
hướng nghiên cứu là interface agent.
I.6.2 Phân lớp văn bản(Text Categoization)
Bài toán:
Phân lớp văn bản được xem nhưlà quá trình gán các văn bản vào một hay nhiều văn bản
đã xác định từtrước. Người ta có thểphân lớp các văn bản mộtc ách thủ công, tức là đọc từng văn
bản một và gán nó vào một lớp nào đó. Cách này sẽtốn rất nhiều thời gian và công sức đối với
nhiều văn bản và do đó không khảthi. Do vậy mà phải có các phương pháp phân lớp tự động.
Đểphân lớp tự động người ta sửdụng các phương pháp học máy trong trí tuệnhân tạo (Cây quyết
định, Bayes, k người láng giềng gần nhất)
Một trong những ứng dụng quan trọng nhất của phân lớp văn bản là trong tìm kiếm văn
bản. Từmột tập dữliệu đã phân lớp các văn bản sẽ được đánh chỉsố đôí với từng lớp tương ứng.
Người dùng có thểxác định chủ đềhoặc phân lớp văn bản mà mình mong muốn tìm kiếm thông
qua các câu hỏi. Một ứng dụng khác của phân lớp văn bản là trong lĩnh vực tìm hiểu văn bản.
Trang 9/36
K-Means và gom cụm văn bản
Vũ Công Tâm
Phân lớp văn bản có thể được sửdụng đểlọc các văn bản hoặc một phần các văn bản chứa dữliệu
cần tìm mà không làm mất đi tính phức tạp của ngôn ngữtựnhiên. Trong phân lớp văn bản, một
lớp có thể được gán giá trị đúng sai (True hay False hoặc văn bản thuộc hay không thuộc lớp)
hoặc được tính theo mức độ phụ thuộc (văn bản có môt mức độphụthuộc vào lớp). Trong trương
hợp có nhiều lớp thì phân loại đúng sai sẽlà việc xem một văn bản có thuộc vào một lớp duy nhất
nào đó hay không
Quá trình:
Đánh chỉ số(Indexing): Quá trình đánh chỉsốvăn bản cũng giống như trong quá trình đánh
chỉsốcủa tìm kiếm văn bản. Trong phần này thì tốc độ đánh chỉ số đóng vai trò quan trọng vì một
sốcác văn bản mới có thể cần đươc xửlý trong thời gían thực
Xác định độphân lớp:Cũng giống nhưtrong tìm kiếm văn bản, phân lớp văn bản yêu cầu quá
trình diễn tảviệc xác định văn bản đó thuộc lớp nào đó nhưthếnào, dựa trên cấu trúc biểu diễn

của nó. Đối với hệphân lớp văn bản, chúng ta gọi quá trình này là bộphân lớp (Categorization
hoặc classifier). Nó đóng vai trò nhưnhững câu hỏi trong hệtìm kiếm. Nhưng trong khi những
câu hỏi mang tính nhất thời, thì bộphân loại được sửdụng một cách ổn định và lâu dài cho quá
trình phân loại.
So sánh:Trong hầu hết các bộphân loại, mỗi văn bản đều được yêu cầu gán đúng sai vào một
lớp nào đó. Sựkhác nhau lớn nhất đối với quá trình so sánh trong hệtìm kiếm văn bản là mỗi văn
bản chỉ được so sánh với một sốlượng các lớp một lần và việcc họn quyết đnịh phù hợp còn
phụthuộc vào mối quan hệgiữa các lớp văn bản.
Phản hồi (Hay thích nghi):Quá trình phản hồi đóng vai trò trong hệphân lớp văn bản.
Thứnhất là khi phân loại thì phải có môt sốlượng lớn các văn bản đã được xếp loại bằng tay
trước đó, các văn bản này được sửdụng làm mẫu huấn luyện đểhỗtrợxây dựng bộphân loại.
Thứhai là đối với việc phân loại văn bản này không dễdàng thay đổi các yêu cầu nhưtrong quá
trình phản hồi của tìm kiếm văn bản , người dùng có thểthông tin cho người bảo trì hệthống về
việc xóa bỏ, thêm vào hoặc thay đổi các phân lớp văn bản nào đó mà mình yêu cầu.
I.6.3 Khai phá dữ liệu Web
Nhu cầu
Sự phát triển nhanh chóng của mạng Internet và Intranet đã sinh ra một khối lượng khổng
lồcác dữliệu dạng siêu văn bản(dữliệu Web). Cùng với sựthay đổi và phát triển hàng ngaỳhàng
giờvềnội dung cũng nhưsốlượng của các trang Web trên Internet thì vấn đềtìm kiếm thôn g tin
đối với người sửdụng lại ngày càng khó khăn.Có thểnói nhu cầu tìm kiếm thông tin trên môt
CSDL phi cấu trúc đã được phát triển chủyếu cùng với sựphát triển của Internet. Thực vậy với
Internet con người đã làm quen với các trang Web cùng với vô vàn các thông tin. Trong những
năm gần đây Intrnet đã trởthành một trong những kênh vềkhoa học, thông tin kinh tế, thương mại
Trang 10/36
K-Means và gom cụm văn bản
Vũ Công Tâm
và quảng cáo. Một trong những lý do cho sựphát triển này là sựthấp vềgiá cảtiêu tốn khi công
khai một trang Web trên Internet. So sánh với những dịch vụkhác như mua bản hay quảng cáo
trên một tờbáo hay tạp chí, thì một trang Web "đòi" rẻ hơn rất nhiều và cập nhật nhanh chóng
hơn tới hàng triệu người dùng khắp mọi nơi trên thế giới. Có thểnói trang Web nhưlà cuốn từ

điển Bách khoa toàn thư. Thông tin trên các trang Web đa dạng vềmặt nội dung cũng nhưhình
thức. Có thểnói Internet như một xã hội ảo, nó bao gồm các thông tin vềmọi mặt của đời sống
kinh tế, xã hội được trình bày dưới dạng văn bản, hình ảnh, âm thanh, Tuy nhiên cùng với sự
đa dạng và sốlượng lớn thông tin nhưvậy đã nảy sinh vấn đềquá tải thông tin. Người ta không
thểtìm tựkiếm địa chỉtrang Web chứa thông tin mà mình cần, do vậy đòi hỏi cần phải có một
trình tiện ích quản lý nội dung của các trang Web và cho phép tìm thấy các địa chỉtrang Web có
nội dung giống với yêu cầu của người tìm kiếm. Các tiện ích này quản lý dữliệu nhưcác đối
tượng phi cấu trúc. Hiện nay chúng ta đã làm quen với một sốcác tiện ích nhưvậy đó là: Yahoo,
goolel, Alvista, Mặt khác, giảsửchúng ta có các trang Web vềcác vấn đềTin học, Thể thao,
Kinh tể-Xã hội và xây dựng Căn cứvào nội dung của các tài liệu mà khách hàng xem hoặc
download về, sau khi phân lớp chúng ta sẽbiết khách hàng hay tập trung vào nội dung gì trên
trang Web của chúng ta, từ đó chúng ta sẽbổsung thêm nhiều các tài liệu vềcác nội dung mà
khách hàng quan tâm và ngược lại. Còn vềphía khách hàng sau khi phân tích chúng ta cũng biết
được khách hàng hay tập trung vềvấn đềgì, đểtừ đó có thể đưa ra những hỗtrợthêm cho khách
hàng đó. Từnhững nhu cầu thực tế trên, phân lớp và tìm kiếm trang Web vẫn là bài toán hay và
cần phát triển nghiên cứu hiện nay.
Khó khăn
Hệthống phục vụWorld Wide Web nhưlà một hệthống trung tâm rất lớn phân bốrộng cung
cấp thông tin trên mọi lĩnh vực khoa học, xã hội, thương mại, văn hóa, Web là một nguồn tài
nguyên giàu có cho Khai phá dữliệu. Những quan sát sau đây cho thấy Web đã đưa ra sựthách
thức lớn cho công nghệKhai phá dữ liệu
Web dường nhưquá lớn đểtổchức thành một kho dữliệu phục vụ Dataming Các CSDL truyền
thống thì có kích thước không lớn lắm và thường được lưu trữ ởmột nơi, , Trong khi đó kích
thước Web rất lớn, tới hàng terabytes và thay đổi liên tục, không những thếcòn phân tán trên rất
nhiều máy tính khắp nơi trên thếgiới. Một vài nghiên cứu vềkích thước của Web đã đưa ra các
sốliệu nhưsau: Hiện nay trên Internet có khoảng hơn một tỷcác trang Web được cung cấp cho
người sửdụng., giảsửkích thước trung bình của mỗi trang là 5-10Kb thì tổng kích thước của nó ít
nhất là khoảng 10 terabyte. Còn tỷlệt ăng của các trang Web thì thật sựgây ấn tượng. Hai năm
gần đây sốcác trang Web tăng gấp đôi và còng tiếp tục tăng trong hai năm tới.Nhiều tổchức và xã
hội đặt hầu hết những thông tin công cộng của họlên Web. Như vậy việc xây dựng một kho

dữliệu (datawarehouse) đểlưu trữ, sao chép hay tích hợp các dữliệu trên Web là gần nhưkhông
thể.
Trang 11/36
K-Means và gom cụm văn bản
Vũ Công Tâm
Độ phức tạp của trang Web lớn hơn rất nhiều so với những tài liệu văn bản truyền thống
khác: Các dữliệu trong các CSDL truyền thống thì thường là loại dữliệu đồng nhất (vềngôn ngữ,
định dạng,…), còn dữliệu Web thì hoàn toàn không đồng nhất. Ví dụ về ngôn ngữ dữ liệu Web
bao gồm rất nhiều loại ngôn ngữ khác nhau (Cả ngôn ngữ diễn tả nội dung lẫn ngôn ngữ lập
trình), nhiều loại định dạng khác nhau (Text, HTML, PDF, hình ảnh âm thanh,…), nhiều loại
từvựng khác nhau (Địa chỉEmail, các liên kết (links), các mã nén (zipcode), số điện thoại) Nói
cách khác, trang Web thiếu một cấu trúc thống nhất. Chúng được coi như một thưviện kỹthuật
sốrộng lớn, tuy nhiên con sốkhổng lồcác tài liệu trong thư viện thì không được sắp xếp tuân theo
một tiêu chuẩn đặc biệt nào, không theo phạm trù, tiêu đề, tác giả, sốtrang hay nội dung, Điều
này là một thửthách rất lớn cho việc tìm kiếm thông tin cần thiết trong một thưviện như thế.
Web là một nguồn tài nguyên thông tin có độthay đổi cao: Web không chỉcó thay đổi về
độlớn mà thông tin trong chính các trang Web cũng được cập nhật liên tục. Theo kết quảnghiên
cứu , hơn 500.000 trang Web trong hơn 4 tháng thì 23% các trang thay đổi hàng ngày, và khoảng
hơn 10 ngày thì 50% các trang trong tên miền đó biến mất, nghĩa là địa chỉURL của nó không
còn tồn tại nữa.Tin tức, thịtrường chứng khoán, các công ty quản cáo và trung tâm phục vụWeb
thường xuyên cập nhật trang Web của họ.s Thêm vào đó sựkết nối thông tin và sự truy cập bản
ghi cũng được cập nhật
Web phục vụmột cộng đồng người dùng rộng lớn và đa dạng: Internet hiện nay nối với
khoảng 50 trạm làm việc, và cộng đồng người dùng vẫn đang nhanh chóng lan rộng. Mỗi người
dùng có một kiến thức, mối quan tâm, sở thích khác nhau. Nhưng hầu hết người dùng không có
kiến thức tốt vềcấu trúc mạng thông tin, hoặc không có ý thức cho những tìm kiếm, rất dễbị"lạc"
khi đang "mò mẫm"trong "bóng tối" của mạng hoặc sẽchán khi tìm kiếm mà chỉnhận những
mảng thông tin không mấy hữu ích
Chỉ một phần rất nhỏ của thông tin trên Web là thực sự hữu ích: Theo thống kê, 99% của
thông tin Web là vô ích với 99% người dùng Web. Trong khi những phần Web không được quan

tâm lại bịbúi vào kết quảnhận được trong khi tìm kiếm. Vậy thì ta cần phải khai phá Web
nhưthếnào đểnhận được trang web chất lượng cao nhất theo tiêu chuẩn của người dùng? Nhưvậy
chúng ta có thểthấy các điểm khác nhau giữa việc tìm kiếm trong một CSDL truyền thống với
vviệc tìm kiếm trên Internet. Những thách thức trên đã đẩy mạnh việc nghiên cứu khai phá và
sửdụng tài nguyên trên Internet
Thuận lợi:
Bên cạnh những thửthách trên, còn một sốlợi thếcủa trang Web cung cấp cho công việc khai
phá Web.
Web bao gồm không chỉcó các trang mà còn có cảcác hyperlink trỏ từ trang này tới trang
khác. Khi một tác giảtạo một hyperlink từtrang của ông ta tới một trang A có nghĩa là A là trang
có hữu ích với vấn đề đang bàn luận. Nếu trang A càng nhiều Hyperlink từtrang khác trỏ đến
Trang 12/36
K-Means và gom cụm văn bản
Vũ Công Tâm
chứng tỏtrang A quan trọng. Vì vậy sốlượng lớn các thông tin liên kết trang sẽcung cấp một
lượng thông tin giàu có vềmối liên quan, chất lượng, và cấu trúc của nội dung trang Web, và vì
thếlà một nguồn tài nguyên lớn cho khai phá Web.
Một máy chủWeb thường đăng ký một bản ghi đầu vào (Weblog entry) cho mọi lần truy
cập trang Web. Nó bao gồm địa chỉURL, địa chỉIP, timestamp. Dữliệu Weblog cung cấp lượng
thông tin giàu có vềnhững trang Web động. Với những thông tin về địa chỉURL, địa chỉIP,… một
cách hiển thị đa chiều có thể được cấu trúc nên dựa trên CSDL Weblog. Thực hiện phân tích
OLAP đa chiều có thể đưa ra N người dùng cao nhất, N trang Web truy cập nhiều nhất, và
khoảng thời gian nhiều người truy cập nhất, xu hướng truy cập Web
Các nội dung trong Webmining:
Như đã phân tích về đặc điểm và nội dung các văn bản HyperText ở trên, từđó khai phá
dữ liệu Web cũng sẽtập trung vào các thành phần có trong trang Web. Đó chính là:
Khai phá nội dung trang Web (WebContent mining):
Web Page Content:
Nghĩa là sẽsửdụng chỉcác từtrong văn bản mà không tính đến các liên kết giữa các văn
bản. Đây chính là khai phá dữliệu Text (Textmining)

Search Result: Tìm kiếm theo kết quả. Trong các máy tìm kiếm, sau khi đã tìm ra những
trang Web thoảmãn yêu cầu người dùng, còn một công việc không kém phần quan trọng, đó là
phải sắp xếp kết quảtheo thứtựdộgần nhau với nội dung cần tìm kiếm. Đây cũng chính là khai
phá nội dung trang Web.
Web Structure Mining: Khai phá dựa trên các siêu liên kết giữa các văn bản có liên quan.
Web Usage Mining: Phân tích các Web log đểkhám phá ra các mẫu truy cập của người
dùng trong trang Web.
Customize Usage Tracking: Phân tích các mẫu truy cập của người dùng tại mỗi thời điểm
để biết xu hướng truy cập trang Web của từng đối tượng người dùng tại mỗi thời điểm khác nhau

PHẦN HAI:
Trang 13/36
K-Means và gom cụm văn bản
Vũ Công Tâm
CÁC THUẬT TOÁN PHỤC VỤ CHO VIỆC PHÂN NHÓM DỮ LIỆU VÀ
TRÌNH BÀY CHI TIẾT THUẬT TOÁN K-MEANS
II.1 Khái niệm gom cụm (Clustering)
II.1.1 Gom cụm là gì?
Công cụ tìm kiếm đã trở thành phổ biến nhất để sử dụng tìm kiếm thông tin. Khi một
người dùng thực hiện một truy vấn, họ sẽ được đưa ra một danh sách các hàng triệu bài báo, có
thể làm họ bị bối rối vì lượng kết quả nhiều. Thông thường người dùng tìm thấy những gì họ
muốn trong một hoặc hai trang. Đối với các truy vấn không chính xác như Apple, Jaguar, đồ thị,
Obama Thì kết quả có thể không phải luôn luôn có giá trị. Điều này dẫn đến người sử dụng
chỉnh sửa câu truy vấn của mình và quá trình lặp đi lặp lại cho đến khi người dùng nhận được kết
quả mong muốn hoặc là thất vọng. Lý do là các công cụ tìm kiếm trả về kết quả xếp hạng dựa
trên thuật toán nội bộ của mình mà không có liên quan đến ngữ nghĩa ý định của người sử dụng.
Nói cách khác, dữ liệu trả về của công cụ tìm kiếm là phi cấu trúc…
Ví dụ: Khi một người sử dụng truy vấn cho Jaguar, ông có thể tìm kiếm Jaguar, động vật hoặc
Jaguar xe, hoặc Jaguar phần mềm. Vì vậy, danh sách cho một căn hộ là không thích hợp ở đây.
Các giải pháp phổ biến nhất cho vấn đề này là gom cụm (clustering) của kết quả tìm

kiếm. Clustering giải quyết vấn đề bằng cách tạo ra các nhóm tài liệu trong kết quả tìm kiếm dựa
trên các chủ đề tương tự, và nhãn mỗi cụm dựa trên khái niệm trung tâm của nó. Điều này cho
phép người sử dụng xem khái niệm ý chính của văn bản nhiều hơn nữa (thường là 100 hoặc 200)
và người sử dụng có thể đi tới ngay với khái niệm gần gũi nhất với những gì anh / cô ấy có trong
tâm trí. Danh sách các cụm có thể được coi như là một bản tóm tắt ngắn gọn các kết quả tìm
kiếm truy vấn. Tiếp tục ví dụ trên, có thể là xe hơi, Animal và Phần mềm.
Nói cách khác, gom cụm nhìn từ góc độ tự nhiên là một việc hết sức bình thường mà
chúng ta vẫn làm và thực hiện hàng ngày ví dụ như phân loại học sinh khá, giỏi trong lớp, phân
loại đất đai, phân loại tài sản, phân loại sách trong thư viện…
Gom cụm:
Tương tự với cùng một đối tượng khác trong cùng một cụm Không tương tự với các đối
tượng trong các cụm khác (tức là thực hiện gom các đối tượng có cùng tính chất hay có các tính
chất gần giống nhau thành nhóm)
Trang 14/36
K-Means và gom cụm văn bản
Vũ Công Tâm
Ví dụ: Phân loại học sinh trong một lớp theo điểm số thành 5 nhóm giỏi, khá, trung bình khá,
trung bình, yếu. Những học sinh có điểm từ 8-10 phân vào nhóm giỏi, từ 7-8 phân vào nhóm
khá, 6-7 phân vào nhóm trung bình khá, 5-6 nhóm TB, 5 trở xuống vào nhóm yếu
II.1.2 Mục tiêu của gom cụm:
Mục tiêu chính của phương pháp phân cụm dữ liệu là nhóm các đối tượng tương tự nhau
trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một lớp là tương đồng còn các
đối tượng thuộc các cụm khác nhau sẽ không tương đồng.
II.1.3 Ứng dụng của gom cụm:
o Kinh doanh: phát hiện ra nhóm khách hàng. Ví dụ Trong tiếp thị mỹ phẩm có thể
phân nhóm khách hang ưa chuộng mỹ phẩm Hàn Quốc, nhóm khách hang ưa chuộng
Mỹ phẩm pháp…
o Sinh học: phân loại động, thực vật, phân loại gen.
o Địa lí: nhận ra các vùng đất giống nhau dựa vào CSDL quan sát trên trái đất, phân
nhóm nhà,

o Bảo hiểm: nhận dạng các nhóm công ty có chính sách bảo hiểm mô tô với chi phí đền
bù trung bình cao
o Hoạch định thành phố: nhận dạng các nhóm nhà cửa theo loại nhà, giá trị và vị trí địa
lý.
o Một công cụ độc lập để xem xét phân bố dữ liệu
o Làm bước tiền xử lý cho các thuật toán khác
II.1.4 Thế nào là gom cụm tốt
o Một phương pháp tốt sẽ tạo ra các cụm có chất lượng cao với:
• Tương tự cao cho trong lớp (intra-class)
• Tương tự thấp giữa các lớp (inter-class)
• Tức là những đối tượng cùng một nhóm có sự giống nhau hoặc gần giống nhau
càng nhiều thì chất lượng gom cụm sẽ càng cao
o Chất lượng của kết quả gom cụm phụ thuộc vào:
• Độ đo tương tự sử dụng
• Cài đặt độ đo tương tự
Trang 15/36
K-Means và gom cụm văn bản
Vũ Công Tâm
II.1.5 Các yêu cầu của gom cụm trong khai phá dữ liệu.
o Scalability: Có thể thay đổi kích cỡ.
o Khả năng làm việc với các loại thuộc tính khác nhau.
o Khám phá ra các cụm có hình dạng bất kì.
o Khả năng làm việc với dữ liệu có chứa nhiễu ( outliers)
II.1.6 Tương tự và bất tương tự giữa hai đối tượng
o Không có định nghĩa duy nhất về sự tương tự và bất tương tự giữa các đối tượng dữ
liệu
o Định nghĩa về tương tự và bất tượng tự giữa các đối tượng tùy thuộc vào
• Loại dữ liệu khảo sát
• Loại tương tự cần thiết
o Tương tự /Bất tượng tự giữa đối tượng thường được biểu diễn qua độ đo khoảng cách

d(x,y)
o
),(),(),( 4.
),(),( 3.
iff 0),( 2.
0),( 1.
zydyxdzxd
xydyxd
yxyxd
yxd
+≤
=
==
≥
Lý tưởng, mọi độ đo khoảng cách phải là một và phải
thỏa các điều kiện sau:
II.1.7 Các dữ liệu trong phân tích cụm
o Các biến khoảng tỉ lệ
o Biến nhị phân
o Các biến định danh, thứ tự, tỉ lệ
o Các biến có kiểu hổn hợp
o Các kiểu dữ liệu phức tạp
II.1.8 Các biến trị khoảng
Trang 16/36
K-Means và gom cụm văn bản
Vũ Công Tâm
Biến trị khoảng là các phép đo liên tục của các thang đo tuyến tính, thô. Ví dụ: trọng lượng,
chiều cao, chiều ngang, chiều dọc, tuổi, nhiệt độ thời tiết.
o Một nhóm các độ đo khoảng cách phổ biến cho biến tỉ lệ theo khoảng là khoảng cách
Minkowski.

)|| |||(|),(
2211
q
q
jpip
q
ji
q
ji
xxxxxxjid
−++−+−=
Với i = (xi1, xi2, …, xip) và j = (xj1, xj2, …, xjp) là các đối tượng dữ liệu p-chiều và q là số
nguên dương
o Nếu q = 1, độ đo khoảng cách là Manhattan
|| ||||),(
2211 pp
j
x
i
x
j
x
i
x
j
x
i
xjid
−++−+−=
o Nếu q = 2, độ đo khoảng cách là khoảng cách Euclidean

)|| |||(|),(
22
22
2
11 pp
j
x
i
x
j
x
i
x
j
x
i
xjid −++−+−=

II.1.9 Các biến nhị phân
o Biến nhị phân chỉ có hai trạng thái là 0 hay 1
o Bảng contingency table cho dữ liệu nhị phân:
pdbcasum
dcdc
baba
sum
++
+
+
0
1

01
Subject i
o Hệ số Jaccard coefficient (tương tự không bất biến, nếu biến nhị phân là bất đối
xứng):
 Biến nhị phân đối xứng và bất đối xứng
Trang 17/36
K-Means và gom cụm văn bản
Vũ Công Tâm
Một biến nhị phân là đối xứng nếu đồng thời các trạng thái của nó có tầm quan trọng
như nhau và mang cùng một trọng số. Do đó, không có sự ưu tiên khi kết quả đưa ra phải
được mã hoá là 0 hoặc 1. Ví dụ thuộc tính giới tính có 2 trạng thái là male và female.
Tính tương tự giữa các biến nhị phân đối xứng được gọi là tính tương tự bất biến, trong
đó kết quả không thay đổi khi 1 hoặc tất cả các biến nhị phân được mã hoá khác nhau.
Với các tính giống nhau bất biến, một hệ số được biết đến nhiều nhất để xác định sự khác
nhau giữa đối tượng i và j là hệ số đối sánh đơn giản, được định nghĩa như sau:
dcba
cb
jid
+++
+
=
),(
- Một biến nhị phân là không đối xứng nếu các kết quả của các trạng
thái không có tầm quan trọng như nhau. Chẳng hạn kết quả âm tính và dương tính khi khám
bệnh. Theo thói quen, chúng ta sẽ mã hoá kết quả quan trọng nhất, thường là kết quả ít xẩy ra
bằng 1 (HIV dương tính) và bằng 0 cho kết quả khác (HIV âm tính). Tính tương tự giữa các biến
này được gọi là tương tự không bất biến. Với sự tương tự không bất biến, hệ số được biết đến
nhiều nhất là hệ số Jaccard trong đó số phép so sánh phủ định coi như không quan trọng và do đó
được bỏ qua khi tính toán.
cba

cb
jid
++
+
=
),(
Ví dụ: Bảng hồ sơ bệnh nhân
Name(tên) Gender(giới
tính)
Fever(ho) Cough(sốt) Test-1 Test-2 Test-3 Test-4
Jack M Y N P N N N
Mary F Y N P N P N
Jim M Y P N N N N
Có 8 thuộc tính Name, Gender, Fever, Cough, Test-1, Test-2, Test-3, Test-4 trong đó:
o Gender là thuộc tính nhị phân đối xứng
Trang 18/36
K-Means và gom cụm văn bản
Vũ Công Tâm
o Các thuộc tính còn lại là nhị phân bất đối xứng
Ta gán các trị Y và P bằng 1 và trị N được gán bằng 0. Tính khoảng cách giữa các bệnh nhân
dựa vào các bất đối xứng dùng hệ số Jacard ta có bảng giá trị như sau:
name Fever Cough Test-1 Test-2 Test-3 Test-4
Jack 1 0 1 0 0 0
Marry 1 0 1 0 1 0
Jim 1 1 0 0 0 0
Tính d(Jack,Marry):
• Bảng dữ liệu dạng nhị phân:
Marry
Jack
1 0

sum
1 2 0 2
0 1 3 4
sum 3 3 6
Từ bảng ta có:a=2, b=0, c=1, d=3
Trang 19/36
K-Means và gom cụm văn bản
Vũ Công Tâm
D(Jack,Marry):
102
10
++
+
=0.33
II.2 Các phương pháp gom cụm (clustering) chính yếu
o Các phương pháp phân cấp
o Các phương pháp dựa trên phân hoạch
II.2.1 Phương pháp phân cấp ( Hierachical methods):
Phân cấp: Tạo phân cấp cụm chứ không phải phân hoạch các đối tượng. Khác với phân hoạch,
phân cấp không cần số cụm k ở đầu vào và dùng ma trận khoảng cách làm tiêu chuẩn gom cụm.
Trong phương pháp phân cấp có thể dùng điều kiện dừng. Ví dụ: số cụm.
Cây các cụm: Phân cấp cụm thường được biểu diễn dưới dạng cây của các cụm. Trong đó:
- Các lá của cây biểu diễn từng đối tượng
- Các nút trong biểu diễn các cụm
Có hai phương pháp tạo cây phân cấp: từ trên xuống và tù dưới lên:
Phương pháp phân cấp từ trên xuống:
Bắt đầu từ cụm lớn nhất chứa tất cả các đối tượng. Chia cụm phân biệt nhất thành các cụm
nhỏ hơn và tiếp diễn cho đến khi có n cụm thoả mãn điều kiện dừng.
b
d

c
e
a
a b
Trang 20/36
K-Means và gom cụm văn bản
Vũ Công Tâm
d e
c d e
a b c d e
Step 4
Step 3
Step 2
Step 1
Step 0
Ph
Ph
ân chia-
ân chia-
divisive
divisive
Phương pháp từ dưới lên:
Các bước thực hiện:
B1: Tạo n nhóm, mỗi nhóm gồm một đối tượng và lập ma trận khoảng cách cấp n.
B2:Tìm 2 nhóm u,v có khoảng cách nhỏ nhất (duv)
B3: Gộp nhóm u với nhóm v. Ký hiệu nhóm mới là (uv). Lập ma trận khoảng cách mới bằng
cách:
+ Loại các hàng và cột tương ứng với các nhóm u,v
+Thêm một hàng và một cột để lưu khoảng cách của nhóm uv với các nhóm còn lại
B4: Lặp lại các bước 2 và bước 3 cho đến khi chọn được k nhóm thích hợp nhất cho bài toán

hoặc chỉ có một nhóm duy nhất.
Phương pháp này đưa tới bài toán nhỏ hơn : Tìm khoảng cách giữa hai nhóm
 Các phương pháp tính khoảng cách giữa hai nhóm là:
Trang 21/36
K-Means và gom cụm văn bản
Vũ Công Tâm
1. Phương pháp kết nối đơn: Trong phương pháp kết nối đơn điều kiện ở đây là khoảng
cách giữa hai cụm là khoảng cách ngắn nhất từ một thành viên của nhóm tới thành viên của
nhóm khác.
d(C1,C2) = min(drs), với r thuộc C1; s thuộc C2 (*)
Ví dụ: Cho 5 đối tượng.Với khoảng cách giữa các đối tượng được cho như sau: d(1,2) =2,
d(1,3)=6, d(1,4)=10, d(1,5)=9, d(2,3)=5, d(2,4)=9, d(2,5)=8,
d(3,4)=4, d(3,5)=5, d(4,5)=3.
ma trận khoảng cách của 5 đối tưọng là D như sau:
0 2 6 10 9
D = 2 0 5 9 8
6 5 0 4 5
10 9 4 0 3
9 8 5 3 0
B1: Ta xây dựng 5 nhóm và lập ma trận khoảng cách giữa 5 nhóm này là D=D1
B2: Khoảng cách giữa 2 nhóm 1 và 2 nhỏ nhất là 2.
B3: Ta sẽ gộp nhóm 1 và 2 thành một nhóm Khi đó ta sẽ cập nhật lại ma trận khoảng
cách mới là D1
+ xoá cột 1 và dòng 1 của nhóm 1. Xoá cột 2 và dòng 2 của nhóm 2.
+ Để thêm một cột và một dòng đẻ lưư khoảng cách của nhom (12) đến các nhóm còn
lại ta tính theo công thức (*) .
D(12,3)= min(drs) với r thuộc nhóm (12), và s thuộc nhóm 3.
D(1,3)=6, d(2,3)=5. vậy nên d(12,3)=5.
Hoàn toàn tương tự ta tính được d(12,5)=8, d(12,4)=9.
Khi đó ta thu được ma trận khoảng cách mới D1 là

0 5 9 8
D1= 5 0 4 5
9 4 0 3
Trang 22/36
K-Means và gom cụm văn bản
Vũ Công Tâm
8 5 3 0
B4:
- Lặp lại bước 2, khoảng cách của nhóm 5 và nhóm 4 là nhỏ nhất d(5,4)=3
- Lặp lại bước 3, Ta sẽ gộp nhóm 4 và 5 thành một nhóm Khi đó ta sẽ cập nhật lại ma trận
khoảng cách mới là D2
+ xoá cột 4 và dòng 4 của nhóm 4. Xoá cột 5 và dòng 5 của nhóm 5
+ Thêm một dòng và một cột để lưư khoảng cách của nhóm (45) tớ các nhóm khác.
Ta tính theo công thức (*)
D(45, 12)=min(drs) với r thuộc (45), s thuộc (12)
D(4,1)=10, d(4,2)=9, d(5,1)=9, d(5,2)=8.
vậy d(45,12)=8.
Hoàn toàn tương tự ta tính đựoc d(45,3)=4.
Khi đó ta thu được ma trận khoảng cách mới D2 là:
0 5 8
D2 = 5 0 4
8 4 0
- Lặp lại bước 2: d (45,3)= 4 là nhỏ nhất
- Lặp lại bước 3: ta gộp nhóm (45) và nhóm 3 thành một nhóm. Cập nhật ma trận khoảng cách
mới là D3.
+ Xoá dòng và cột của nhóm (45), xoá dòng và cột của nhóm 3
+ Thêm một dong f và một cột đẻ lưư khoảng cách của nhóm mơid này đến các nhóm khác ta
sẽ tính khoảng cách theo công thức (*)
D(345,12)= min( drs) với r thuộc (345) và s thuộc(12).
D(3,1)=6, d(3,2)=5, d(4,1)=10, d(4,2)=9, d(5,1)=9, d(5,2)=8.

vậy d(345,12)=5.
Ta thu được khoảng cách mới là D3 là:

Trang 23/36
K-Means và gom cụm văn bản
Vũ Công Tâm
0 5
D3= 5 0
Cuối cùng nhóm thu đựoc sẽ là nhóm (12543)
Sơ đồ mô tả các bước:
B0 B1 B2 B3 B4


II.2.2 Phương pháp kết nối đầy đủ:
d(C1,C2) = max(drs), với r thuộc C1; s thuộc C2.
II.2.3 Phương pháp kết nối trung bình
Khoảng cách giữa một cluster này và một cluster khác là tương đương khoảng cách trung
bình từ một vài thành viên của một nhóm này đến một vài thành viên của nhóm khác.
)(
21
1
)2,1(
2
1
1
1
drs
nn
CCD
n

s
n
r
∑∑
==
=
Với r thuộc C1, s thuộc C2.
Đánh giá:
- Các phương pháp phân cấp có ưu điểm lớn là: khái niệm đơn giản, lý thuyết tốt. Khi cụm
được trộn tách, quyết định là vĩnh cửu, vì vậy số các phương án khác cần xem xét bị rút
giảm.
Trang 24/36
1
2
3
12
345
12345
45
5
4
K-Means và gom cụm văn bản
Vũ Công Tâm
- Điểm yếu của phương pháp phân cấp: Do việc trộn tách các cụm là vĩnh cửu nên quyết
định sai là không thể khắc phục được. Các phương pháp phân chia cần thời gian tính toán và
không thể scalable cho tập dữ liệu lớn
II.2.4 Các phương pháp dựa trên phân hoạch
II.2.4.1 Mô tả phương pháp
Cho một cơ sở dữ liệu D chứa n đối tượng, tạo phân hoạch thành tập có k cụm sao cho:
- Mỗi cụm chứa ít nhất một đối tượng

- Mỗi đối tượng thuộc về một cụm duy nhất
- Cho trị k, tìm phân hoạch có k cụm sao cho tối ưu hoá tiêu chuẩn phân hoạch được chọn.
II.2.4.2 Các phương pháp
Phương pháp gom cụm K-Means
Thuật toán K-Medoid
Thuật toán Dendrogram
Thuật toán SOM
Thuật toán EM
………………………………………………………
Trang 25/36