ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
Bài thu hoạch môn:
Công Nghệ Tri Thức và Ứng Dụng
Đề tài:
Gom Cụm Văn Bản
Với Thuật Toán K-means
Giảng viên: GS. TSKH. Hoàng Văn Kiếm
Học viên: Trần Ngọc Trí
Mã số học viên: CH1301111
1
TP.HCM, Tháng 10 - 2014
MỤC LỤC
LỜI MỞ ĐẦU 3
PHẦN II : THUẬT TOÁN K-MEANS 8
2.1 – Giới thiệu về thuật toán K-means : 9
2.2 – Thuật toán K-means : 9
PHẦN III: ỨNG DỤNG THUẬT TOÁN K-MEANS 16
16
22
23
TÀI LIỆU THAM KHẢO 23
[2] Text Documents clustering using K Means Algorithm (Thiết kế Demo) 23
2
LỜI MỞ ĐẦU
Ngày nay, cùng với sự phát triển mạnh mẽ của công nghệ phần cứng
và truyền thông, các hệ thống dữ liệu phục vụ cho các lĩnh vực kinh tế - xã hội
cũng không ngừng tăng lên, lượng dữ liệu được tạo ra ngày càng lớn. Sự
phong phú về dữ liệu, thông tin cùng với khả năng kịp thời khai thác chúng đã
mang đến những năng suất và chất lượng mới cho công tác quản lý, hoạt
động kinh doanh,…Nhưng rồi các yêu cầu về thông tin trong các lĩnh vực hoạt

câu hỏi, chúng ta phân nhóm dựa trên yếu tố nào? Hoặc chúng ta định
phân thành bao nhiêu nhóm?
Ví dụ về gom cụm ảnh
Hay trường hợp tổng quát
Ta phân hoạch các nhóm phần tử trong 1 tập hợp xác định vào các cụm
khác nhau theo thuộc tính chung của các phần tử.
4
B. Quá trình gom cụm
- Là quá trình ta phân hoạch các đối tượng vào các cụm hoặc
nhóm.
- Các đối tượng trong một cụm,nhóm có đặc điểm giống nhau
nhất so với các phần tử của nhóm,cụm khác
Trước khi thực hiện một quá trình gom cụm thì ta cần phải trả lời những
câu hỏi sau
- Mỗi cụm nên có bao nhiêu phần tử.
- Các phần tử nên được gom vào bao nhiêu cụm.
- Bao nhiêu cụm nên được tạo ra.
5
Quá trình gom cụm có thể được minh họa qua sơ đồ sau :
1.2 Các phương pháp gom cụm
A. Các yêu cầu tiêu biểu về việc gom cụm dữ liệu
- Khả năng co giãn về tập dữ liệu (scalability)
- Khả năng xử lý nhiều kiểu thuộc tính khác nhau (different types of
attributes)
- Khả năng khám phá các cụm với hình dạng tùy ý (clusters with
arbitrary shape)
- Tối thiểu hóa yêu cầu về tri thức miền trong việc xác định các thông
số nhập (domain knowledge for input parameters)
- Khả năng xử lý dữ liệu có nhiễu (noisy data)
6

mẫu, mỗi mẫu này coi như biểu diễn 1 cụm, như vậy lúc này trong mỗi cụm
thì đối mẫu đó cũng là tâm của cụm (hay còn gọi là nhân). Các mẫu còn lại
được gán vào một nhóm nào đó trong K nhóm đã có sao cho tổng khoảng
cách từ nhóm mẫu đó đến tâm của nhóm là nhỏ nhất. Sau đó tính lại tâm cho
các nhóm và lặp lại quá trình đó cho đến khi hàm tiêu chuẩn hội tụ. Hàm tiêu
chuẩn hay được dùng nhất là hàm tiêu chuẩn sai-số vuông. Thuật toán này có
thể áp dụng được đối với CSDL đa chiều, nhưng để dễ minh họa chúng tôi mô
tả thuật toán trên dữ liệu hai chiều.
2.2 – Thuật toán K-means :
Thuật toán k-means được mô tả cụ thể như sau:
Input: K, và dữ liệu về n mẫu của 1 CSDL.
Output: Một tập gồm K cluster sao cho cực tiểu về tổng sai-số vuông.
Thuật toán:
Bước 1: Chọn ngẫu nhiên K mẫu vào K cluster. Coi tâm của cluster
chính là mẫu có trong cluster.
Bước 2: Tìm tâm mới của cluster.
Bước 3: Gán (gán lại) các mẫu vào từng cluster sao cho khoảng cách
từ mẫu đó đến tâm của cluster đó là nhỏ nhất.
Bước 4: Nếu các cluster không có sự thay đổi nào sau khi thực hiện
bước 3 thì chuyển sang bước 5, ngược lại sang bước 2.
Bước 5: Dừng thuật toán.
9
Mô tả của thuật toán K-Means
Ví dụ: Giả sử trong không gian hai chiều, cho 12 điểm (n = 12) cần phân 12
điểm này thành hai cluster (k=2).
Đầu tiên chọn hai điểm ngẫu nhiên vào hai cluster, giả sử chọn điểm (1,3) và
điểm (9,4) (điểm có màu đỏ trên hình 9.a).
Coi điểm (1,3) là tâm của cluster 1 và điểm (9,4) là tâm của cluster hai. Tính
toán khoảng cách từ các điểm khác đến hai điểm này và ta gán được các
điểm còn lại này vào một trong hai cluster, những điểm có màu xanh lơ vào

không đổi, c1(1,1). Tâm nhóm 2 được tính như sau:
13
Bước 5. Tính lại khoảng cách từ các đối tượng đến tâm mới
Bước 6. Nhóm các đối tượng vào nhóm
14
Bước 7. Tính lại tâm cho nhóm mới
Bước 9. Tính lại khoảng cách từ các đối tượng đến tâm mới
Bước 10. Nhóm các đối tượng vào nhóm
15
Ta thấy G
2
= G
1
(Không có sự thay đổi nhóm nào của các đối tượng) nên thuật
toán dừng và kết quả phân nhóm như sau:

Ưu điểm : - Dễ hiểu và cài đặt.
Hạn chế : - Phụ thuộc vào số nhóm K chọn ban đầu
- Chi phí cho thực hiện vòng lặp tính toán khoảng cách lớn khi số
cụm K và dữ liệu phân cụm lớn.
PHẦN III: ỨNG DỤNG THUẬT TOÁN K-MEANS
16
Biểu diễn văn bản
Mỗi văn bản sẽ được biểu diễn dưới dạng mô hình không gian Vector.
public class DocumentVector
{
//Content represents the document(or any other object) to be clustered
public string Content { get; set; }
//represents the tf*idf of each document
public float[] VectorSpace { get; set; }

{
float tf = FindTermFrequency(document, term);
float idf = FindInverseDocumentFrequency(term);
return tf * idf;
}

private static float FindTermFrequency(string document, string term)
{
int count = r.Split(document).Where(s => s.ToUpper() ==
term.ToUpper()).Count();
//ratio of no of occurance of term t in document d to the total no of terms in
the document
return (float)((float)count / (float)(r.Split(document).Count()));
}

private static float FindInverseDocumentFrequency(string term)
{
//find the no. of document that contains the term in whole document
collection
int count = documentCollection.ToArray().Where(s => r.Split(
s.ToUpper()).ToArray().Contains(term.ToUpper())).Count();
/*
* log of the ratio of total no of document in the collection to the no. of
document containing the term
* we can also use Math.Log(count/(1+documentCollection.Count)) to deal
with divide by zero case;
*/
return (float)Math.Log((float)documentCollection.Count() / (float)count);
}
Trọng số giống nhau

* more than once same document is added to the next cluster
* so avoid it using HasSet collection
*/
HashSet<int> uniqRand = new HashSet<int>();
GenerateRandomNumber(ref uniqRand,k,documentCollection.Count);

foreach(int pos in uniqRand)
{
c = new Centroid();
c.GroupedDocument = new List<DocumentVector>();
c.GroupedDocument.Add(documentCollection[pos]);
centroidCollection.Add(c);
}
Boolean stoppingCriteria;
List<Centroid> resultSet;
19
List<Centroid> prevClusterCenter;

InitializeClusterCentroid(out resultSet, centroidCollection.Count);
do
{
prevClusterCenter = centroidCollection;
foreach (DocumentVector obj in documentCollection)
{
int index = FindClosestClusterCenter(centroidCollection, obj);
resultSet[index].GroupedDocument.Add(obj);
}
InitializeClusterCentroid(out centroidCollection,
centroidCollection.Count());
centroidCollection = CalculateMeanPoints(resultSet);

similarityMeasure[i] =
SimilarityMatrics.FindCosineSimilarity(
clusterCenter[i].GroupedDocument[0].VectorSpace, obj.VectorSpace);
}
int index = 0;
float maxValue = similarityMeasure[0];
for (int i = 0; i < similarityMeasure.Count(); i++)
{
//if document is similar assign the document
//to the lowest index cluster center to avoid the long loop
if (similarityMeasure[i] >maxValue)
{
maxValue = similarityMeasure[i];
index = i;
}
}
return index;
}
private static List<Centroid> CalculateMeanPoints(List<Centroid>
_clusterCenter)
{
for (int i = 0; i < _clusterCenter.Count(); i++)
{
if (_clusterCenter[i].GroupedDocument.Count() > 0)
{
for (int j = 0; j <
_clusterCenter[i].GroupedDocument[0].VectorSpace.Count(); j++)
{
float total = 0;