Gom Văn bản bằng Thuật toán K-Means
MỤC LỤC
MỤC LỤC 1
1
CHƯƠNG I 3
GOM CỤM DỮ LIỆU 3
- Gom cụm Expectation-Maximization (EM) 11
Gom cụm với mạng neural 11
CHƯƠNG II 12
THUẬT TOÁN K-MEANS 12
CHƯƠNG III 17
DEMO THỰC HIỆN GOM VĂN BẢN 17
BẰNG THUẬT TOÁN K-MEANS 17
CHƯƠNG IV 27
KẾT LUẬN 27
TÀI LIỆU THAM KHẢO 28
Gom Văn bản bằng Thuật toán K-Means
LỜI NÓI ĐẦU
Khai phá dữ liệu (Data Mining) là quá trình khám phá các tri thức mới và
các tri thức có ích ở dạng tiềm năng trong nguồn dữ liệu lớn đã có (các kho dữ
liệu). Khai phá dữ liệu là một bước đặc biệt trong toàn bộ quá trình phát hiện các
tri thức có ích từ các tập dữ liệu lớn, sử dụng các giải thuật đặc biệt để chiết suất
ra các mẫu (pattern) (hay các mô hình) từ dữ liệu.
Với mục đích tìm hiểu để nâng cao khả năng Khai phá dữ liệu, tiểu luận
này là sự trình bày khái quát về gom cụm dữ liệu và thuật toán K-means, đồng
thời trình bày Demo thực hiện gom văn bản bằng thuật toán K-means.
Em xin chân thành cảm ơn PGS.TS. Đỗ Phúc-Giảng viên môn học Khai
phá dữ liệu đã truyền đạt những kiến thức vô cùng quý báu, em cũng xin cảm ơn
sự giúp đỡ, dạy bảo tận tình của các thầy cô giáo và những bạn học trong suốt
quá trình học tập cũng như thực hiện và hoàn thành luận văn.
Do thời gian và khả năng có hạn nên bài luận văn còn nhiều hạn chế trong

thời gian tới em sẽ tiếp tục nghiên cứu các vấn đề trong môn học mà trong bài
luận văn này chưa đề cập đến. em rất mong nhận được sự góp ý của các thầy cô
và các bạn quan tâm.

Em xin chân thành cảm ơn!
Trần Xuân Thái

2
Gom Văn bản bằng Thuật toán K-Means
CHƯƠNG I
GOM CỤM DỮ LIỆU
1. Khái niệm
Gom cụm là quá trình nhóm 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 khác nhau.
Một cụm là một tập các đối tượng dữ liệu trong đó các đối tượng ở trong
cùng một cụm thì giống nhau và khác với các đối tượng thuộc cụm khác.
2. Một số ứng dụng điển hình
- Kinh doanh: phát hiện ra nhóm khách hàng.
- Sinh học: phân loại động, thực vật, phân loại gen.
- Đị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à,…
- Phân chia tài liệu Web.
3. Thế nào là gom cụm tốt
- 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).
- Chất lượng của kết quả gom cụm phụ thuộc vào : độ đo tương tự sử
dụng và việc cài đặt độ đo tương tự.
- Chất lượng của phương pháp gom cụm cũng được đo bởi khả năng phát
hiện các mẫu bị che ( hidden patterns).
4. Các yêu cầu của gom cụm trong khai phá dữ liệu

- Scalability: Có thể thay đổi kích cỡ.
- Khả năng làm việc với các loại thuộc tính khác nhau.
- Khám phá ra các cụm có hình dạng bất kì.
- Các yêu cầu tối thiểu cho tri thức lĩnh vực nhằm xác định các tham
biến nhập
- Khả năng làm việc với dữ liệu có chứa nhiễu ( outliers).
- Không nhạy cảm với thứ tự các bản ghi nhập vào.
- Khả năng làm việc với dữ liệu nhiều chiều.
- Có thể diễn dịch và khả dụng
5. Các kiểu dữ liệu trong gom cụm dữ liệu
5.1. Cấu trúc dữ liệu
Các thuật toán gom cụm hầu hết sử dụng hai cấu trúc dữ liệu điển hình sau:
- Ma trận dữ liệu ( two modes )
3
Gom Văn bản bằng Thuật toán K-Means
Biểu diễn n đối tượng và p biến ( là các phép đo hoặc các thuộc tính ) của
đối tượng, có dạng ma trận nxp.
Ma trận bất tương tự ( One modes): Lưu trữ một tập các trạng thái ở gần
nhau mà chúng sẵn có ở tất cả các cặp n đối tượng. Được biểu thị bởi một
bảng n x n.
Với d(i,j) là sự khác nhau hoặc sự bất tương tự giữa các đối tượng i và j.
Nói chung, d(i,j) là số không âm và gần bằng 0 khi đối tượng i và j là tương tự
nhau mức cao hoặc “gần” với đối tượng khác. Khi d(i,j) = d(j,i) và d(i,i) = 0,
chúng ta có ma trận một chiều.
Ma trận dữ liệu thường được gọi là ma trận dạng 2, trái lại ma trận bất
tương tự được gọi là ma trận dạng 1, khi đó các dòng và các cột biểu diễn các
thực thể khác nhau trước, các thực thể giống nhau biểu diễn sau. Nhiều thuật
toán gom cụm hoạt đông trên ma trận bất tương tự. Nếu dữ liệu được trình bầy
dưới dạng một ma trận dữ liệu, đầu tiên nó có thể được chuyển vào ma trận bất
tương tự trước khi áp dụng các thuật toán gom cụm như vậy.

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 mà định nghĩa này tuỳ thuộc vào loại dữ liệu khảo sát, loại tương
tự cần thiết.“Sự tương tự / bất tương tự được đánh giá như thế nào?”. Thông
thường được biểu diễn qua độ đo khoảng cách d(i,j). Lý tưởng, mọi độ đo
khoảng cách phải thoả mãn các điều kiện sau:
4
Gom Văn bản bằng Thuật toán K-Means
- d(i,j)>=0
- d(i,j)=0 nếu i=j
- d(i,j)=d(j,i)
- d(x,z)<=d(x,y) + d(y,z)
5.2. Các kiểu dữ liệu
5.2.1. Các biến trị khoảng ( interval- valued variables)
Định nghĩa: 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.
Các đơn vị đo có thể ảnh hưởng đến phân tích cụm. Vì vậy để tránh sự
phụ thuộc vào đơn vị đo, cần chuẩn hoá dữ liệu.
Các bước chuẩn hoá dữ liệu
- Tính sai số tuyệt đối trung bình:
|)| |||(|
1
21 fnffffff
mxmxmx
h
x −++−+−=
với
) (
1
21 nffff

xxx
h
m +++=
- Tính độ đo chuẩn:
f
fif
if
s
mx
z
−
=
Một nhóm các độ đo khoảng cách phổ biến cho tỉ lệ theo khoảng là
khoảng cách Minkowski.
)|| |||(|),(
2211
q
q
jpip
q
ji
q
ji
xxxxxxjid −++−+−=
với i = (x
i1
, x
i2
, x
ip

) và j=(x
j1
, x
j2
, ,x
jp
) là các đối tượng dữ liệu p- chiều
và q là số nguyên dương.
+ Nếu q = 1, độ đo khoảng cách là Mahattan
|| ||||),(
2211 jpipjiji
xxxxxxjid −++−+−=
+ Nếu q = 2, độ đo khoảng cách là khoảng cách Euclidean.
22
22
2
11
|| |||(|),(
jpipjiji
xxxxxxjid −++−+−=
5
Gom Văn bản bằng Thuật toán K-Means
5.2.2. Các biến nhị phân ( binary variables )
Định nghĩa: Biến nhị phân là biến chỉ có hai trạng thái là 0 hoặc 1. Các
biến nhị phân được mô tả là đối xứng và bất đối xứng. Việc xử lý các biến nhị
phân giống như các biến tỉ lệ khoảng có thể dẫn đến không đưa ra được kết quả
phân cụm. Vì vậy phải có phương pháp tính toán khác.
Giả sử ta có bảng dữ liệu nhị phân sau:
Object j
Object i

1 0 Sum
1 a b a+b
0 c d c+d
Sum a+c b+d p
Biến nhị phân đối xứng và bất đối xứng
- 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). Trong hai biến nhị phân được đưa ra, việc chấp nhận biến
giá trị 1(khẳng định) được xem như “monary” (như là có một trạng thái). 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.
6

Gom Văn bản bằng Thuật toán K-Means
cba
cb
jid
++
+
=),(
Ví dụ: Bảng hồ sơ bệnh nhân
Name Gender Fever Cough 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 đó:
- Gender là thuộc tính nhị phân đối xứng
- 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ó:
75.0
211
21
),(
67.0
111
11
),(
33.0
102
10
),(

=
++
+
=
=
++
+
=
=
++
+
=
marryjimd
jimjackd
marryjackd
Như vậy, theo tính toán trên Jim và Marry có khả năng mắc bệnh giống
nhau nhiều nhất vì
d(jim, marry)=0.75 là lớn nhất.
5.2.3. Các biến định danh ( nominal variables)
Định nghĩa: Biến định danh là mở rộng của biến nhị phân với nhiều hơn
hai trạng thái. Ví dụ: thuộc tính màu sắc: đỏ, vàng, xanh, lục.
Có hai phương pháp để tính toán sự tương tự giữa hai đối tượng:
- Phương pháp 1: Đối sánh đơn giản với m là số lần đối sáng, p là tổng số
các biến
p
mp
jid
−
=),(
- Phương pháp 2: Dùng một số lượng lớn các biến nhị phân.

+ Tạo biến nhị phân mới cho từng trạng thái định danh.
7
Gom Văn bản bằng Thuật toán K-Means
+ Các biến thứ tự có thể là liên tục hay rời rạc
+ Thứ tự của các trị là quan trọng, ví dụ hạng.
+ Có thể xử lý như tỉ lệ khoảng như sau:
Thay thế x
if
bởi hạng của chúng ánh xạ phạm vi của từng biến vào đoạn
[0,1] bằng cách thay thế đối tượng i trong biến thứ f bởi
}, ,1{
fif
Mr ∈
Tính sự khác nhau dùng các phương pháp cho biến tỉ lệ theo khoảng
1
1
−
−
=
f
if
if
M
r
z
5.2.4. Các biến thang đo tỉ lệ
Định nghĩa: Là các biến có độ đo dương trên thang phi tuyến, xấp xỉ
thang đo mũ. Ví dụ: Ae
Bt
hay Ae

-Bt
.
Các phương pháp tính độ tương tự:
- Xử lý chúng như các biến thang đo khoảng
- áp dụng các biến đổi logarithmic
- Xử lý chúng như dữ liệu thứ tự liên tục
- Xử lý chúng theo hạng như thang đo khoảng.
5.2.5. Các biến có kiểu hỗn hợp
Một cơ sở dữ liệu có thể chứa đồng thời cả sáu loại biến. Khi đó có thể
dùng công thức được gán trọng để kết hợp các hiệu quả:
∑
∑
=
=
=
p
f
f
ij
p
f
f
ij
f
ij
d
jid
1
)(
1

)()(
),(
δ
δ
với
0=
f
ij
δ
nếu x
if
hoặc x
jf
missing
hoặc x
if
=x
jf
=0
trường hợp khác
1=
f
ij
δ
Đóng góp của biến f vào khoảng cách d(i,j):
- Nếu f là biến nhị phân hay định danh:
0
)(
=
f

ij
d
nếu x
if
=x
jf
các trường hợp khác
1
)(
=
f
ij
d
- Nếu f là dựa trên khoảng cách: dùng khoảng cách được chuẩn hoá.
8
Gom Văn bản bằng Thuật toán K-Means
- Nếu f là thứ tự thang đo tỉ số tính các hạng r
if
và xử lý z
if
như thang đo
khoảng
1
1
−
−
=
f
if
if

M
r
z
6. Các phương pháp gom cụm
Có rất nhiều các phương pháp gom cụm khác nhau. Việc lựa chọn phương
pháp nào tuỳ thuộc vào kiểu dữ liệu, mục tiêu và trình ứng dụng cụ thể. Nhìn
chung, có thể chia thành các phương pháp sau:
6.1. Phương pháp phân hoạch
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.
Các phương pháp phân hoạch
Phương pháp heuristic điển hình được biết đến là k-means và k-medoids
6.1.1. Phương pháp gom cụm k-means ( MacQueen’67)
Input: Số các cụm k và cơ sở dữ liệu chứa n đối tượng
Thuật giải: gồm 4 bước
- Phân hoạch đối tượng thành k tập con ( cụm).
- Tính các điểm hạt giống centroid ( trung bình của các đối tượng trong
cụm ) cho từng cụm trong phân hoạch hiện hành.
- Gán mỗi đối tượng cho cụm centroid gần nhất
- Quay về bước 2, chấm dứt khi không còn phép gán mới.
Điểm mạnh của phương pháp gom cụm k- means
- Có thể scalable trong khi xử lý dữ liệu lớn
- Hiệu suất tương đối: O(nkt) với n là số đối tượng, k là số cụm, t là số lần
lặp. Thông thường k, t << n.
- Thường kết thúc ở tối ưu cục bộ; có thể tìm được tối ưu toàn cục, dùng
kĩ thuật thuật giải di truyền.

Điểm yếu của phương pháp k- means
- Có thể áp dụng chỉ khi xác định được trị trung bình
- Cần chỉ định trước số các cụm- k.
- Không thể xử lý nhiễu và outliers.
9
Gom Văn bản bằng Thuật toán K-Means
- Không thích hợp đối với các cụm có dạng nồi hay các cụm có kích
thước khác nhau.
- Các biến đổi của phương pháp k- means
- Các biến thể của phương pháp k- means khác nhau ở việc chọn k
centroids đầu tiên, tính toán sự khác nhau và ở chiến lược tính centroids của
cụm.
6.1.2. Phương pháp k- medoids
Input: Một cơ sở dữ liệu n đối tượng và số các cụm k.
Thuật toán: Gồm 4 bước:
- Chọn bất kì k đối tượng làm medoids ban đầu để đại diện cho các đối
tượng
- Gán từng đối tượng cho cụm có medoid gần nhất.
- Chọn nonmedoid và thay thế các medoids nếu cải thiện được tình trạng
gom cụm.
- Quay về bước 2, dừng khi không còn phép gán mới.
6.2. 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ác cụm và được gọi
là dendrogram. 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: top-down và bottom- up
- Phương pháp Bottom up ( từ dưới lên): Thay thế từng đối tượng trong
cụm của nó. Trộn theo từng bước hai cụm giống nhau nhất cho đến khi chỉ còn
một cụm hay thoả mãn điều kiện thì dừng.
- Phương pháp Top- down ( 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.
Đo khoảng cách: Có 3 cách được dùng để đo khoảng cách là:
- Phương pháp liên kết đơn ( người láng giềng gần nhất)
)},({min),(
,
yxdjid
þCi
CyCx ∈∈
=
10
Gom Văn bản bằng Thuật toán K-Means
- Phương pháp liên kết hoàn toàn ( người láng giềng xa nhất )
)},({max),(
,
yxdjid
þCi
CyCx ∈∈
=
- Phương pháp liên kết trung bình ( trung bình cặp nhóm không có trọng )
)},({),(
,
yxdavgjid
þCi

CyCx ∈∈
=
Đá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.
- Đ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.
6.3. Phương pháp dựa vào mật độ (Density based Methods)
Gom cụm dựa trên sự liên thông địa phương và hàm mật độ. Theo phương
pháp này các điểm có mật độ cao hơn sẽ ở cùng một cụm.
Đặc trưng của phương pháp:
- Phát hiện ra các cụm có hình dạng bất kì.
- Phát hiện nhiễu.
6.4. Phương pháp dựa trên mô hình (gom cụm khái niệm, mạng
neural).
- Gom cụm Expectation-Maximization (EM)
Giải thuật tinh chỉnh để gán các đối tượng vào các cụm (bước kỳ vọng) và
ước lượng thông số (bước cực đai)
- Gom cụm ý niệm (Conceptual clustering)
Tạo ra cách phân lớp các đối tượng chưa được gán nhãn dựa vào các mô
tả đặc trưng cho mỗi nhóm đối tượng ứng với mỗi khái niệm (Concept)
- Gom cụm với mạng neural
+ Biểu diễn mỗi cụm là một ví dụ tiêu biểu (Exemplar)
+ Exemplar đóng vai trò của một Prototype của cụm
+ Các đối tượng mới được phân bố vào một cụm nếu tương tự với
Exemplar của cụm đó nhất dựa trên độ đo khoảng cách.
11
Gom Văn bản bằng Thuật toán K-Means

CHƯƠNG II
THUẬT TOÁN K-MEANS
1. Khái niệm
K-means là thuật toán gom cụm theo phương pháp phân hoạch và đã
được sử dụng rộng rãi. Cho tập các đối tượng, mục tiêu gom cụm hay phân
mảnh là chia tập đối tượng này thành nhiều nhóm hay “cụm” sao cho các đối
tượng trong một cụm có khuynh khuynh hướng tương tự nhau hơn so với đối
tượng khác nhóm. Nói cách khác, các thuật toán gom cụm đặt các điểm tượng
tự trong cùng một cụm trong khi các điểm không tương tự đặt trong nhóm khác.
Lưu ý, ngược với các tác vụ có giám sát như hồi qui hay phân lớp, ở đó có khái
niệm giá trị mục tiêu hay nhãn lớp, các đối tượng là đầu vào cho một thủ tục
gom cụm không cần một mục tiêu. Vì vậy, gom cụm thường được xem là học
không có giám sát. Do không cần dữ liệu nhãn, các thuật toán không giám sát
thích hợp với nhiều ứng dụng không có dữ liệu được gán nhãn. Các tác vụ
không giám sát như gom cụm thường dược dùng để khám phá và mô tả tập dữ
liệu trước khi thực hiện công việc học có giám sát. Do gom cụm không dùng
các nhãn lớp, khái niệmthức mà ở đó các điểm được gom cụm khác nhau dựa
trên thuật toán gom cụm được áp dụng. Các thuật toán gom cụm khác nhau
thích hợp với các kiểu khác nhau về tập dữ liệu và các mục tiêu khác nhau. Vì
vậy thuật toán gom cụm “tốt nhất” để sử dụng tùy thuộc vào ứng dụng.
Thuật toán k-means là thuật toán gom cụm lặp đơn giản. Nó phân mảnh
tập dữ liệu cho trước thành k cụm, giá trị k do người dùng xác định. Thuật toán
dễ thực hiện, thi hành nhanh, dễ thích nghi và phổ biến trong thực tế. Đây là một
trong những thuậttoán kinh điển trong khai thác dữ liệu.
K-means được nhiều nhà nghiên cứu khám phá thông qua nhiều cách khác
nhau, đángchú ý nhất là Lloyd (1957, 1982), Forgey (1965), Friedman và Rubin
(1967) vàMcQueen (1967). Jain và Dubes mô tả lịch sử k-means theo nhiều biến
thể. Gray vàNeuhoff cung cấp nền tảng cho k-means diễn ra trong ngữ cảnh lớn
hơn trên các thuậttoán leo đồi.
2. Thuật toán

Thuật toán k-means áp dụng cho các đối tượng được biểu diễn bởi các
điểm trong không gian vectơ d chiều U {x | i 1, , N} i = = , với di x ∈ R biểu thị
đối tượng (hay điểm dữ liệu) thứ i. Thuật toán k-means gom cụm toàn bộ các
điểm dữ liệu trong U thành k cụm C ={C1, C2, … , Ck }, sao cho mỗi điểm dữ
liệu xi nằm trong một cụm duy nhất. Để biết điểm dữ liệu thuộc cụm nào người
12
Gom Văn bản bằng Thuật toán K-Means
ta gán cho nó một mã cụm. Các điểm có cùng mã cụm thì ở cùng cụm, trong khi
các điểm khác mã cụm thì ở trong các cụm khác nhau. Một cụm có thể biểu thị
bằng vectơ liên thuộc cụm v có độ dài N, với vi là mã cụm của xi.
Giá trị k là đầu vào của thuật toán. Giá trị k dựa trên tiêu chuẩn tri thức
trước đó. Sẽ có bao nhiêu cụm thực sự xuất hiện trong U, bao nhiêu cụm được
đề nghị cho ứng dụng hiện hành, hay các kiểu cụm được tìm thấy bằng cách dựa
vào thực nghiệm với nhiều giá trị k khác nhau. Không cần thiết phải hiểu k
được chọn như thế nào khi k-means phân mảnh tập dữ liệu U, việc chọn giá trị k
như thế nào sẽ được thảo luận trong phần kế tiếp.
Trong các thuật toán gom cụm, các điểm được nhóm theo khái niệm “độ
gần” hay “độ tương tự”. Với k-means, phép đo mặc định cho “độ tương tự” là
khoảng cách Euclide.Đặc biệt, có thể thấy k-means cố gắng cực tiểu hóa hàm
giá trị không âm sau:
Nói cách khác, k-means cố gắng cực tiểu khoảng cách Euclide tổng bình
phương giữamỗi điểm xi và thể hiện cụm gần nhất của nó Cj. Biểu thức trên
thường được xem làhàm mục tiêu k-means.
Thuật toán k-means, thay đổi giữa 2 bước: (1) gán lại mã cụm của tất cả
điểm trong U và (2) cập nhật các thể hiện cụm dựa trên các điểm dữ liệu trong
mỗi cụm.
Thuật toán làm việc như sau: đầu tiên, các thể hiện nhóm được khởi tạo
bằng cách chọn k điểm trong Rd . Các k thuật để chọn các hạt giống khởi tạo
bao gồm lấy mẫu ngẫu nhiên từ tập dữ liệu, xem chúng như giải pháp gom cụm
tập con nhỏ dữ liệu, hay làm thay đổi giá trị trung bình toàn cục của k lần dữ

liệu. Trongthuật toán 2.1, ta khởi tạo k điểm ngẫu nhiên. Sau đó thuật toán lặp 2
bước cho đến khi hội tụ.
Bước 1. [Gán dữ liệu] Mỗi điểm được gán vào trọng tâm gần nhất.
Bước 2. Tái định vị “độ trung bình”. Mỗi thể hiện nhóm được tái định vị
vàotâm của tất cả các điểm được gán cho nó. Cho trước tập các điểm, thể hiện
tốt nhất đốivới tập này (theo ý nghĩa tối thiểu tổng khoảng cách Euclide giữa
mỗi điểm và thểhiện) thì không là gì cả ngoài độ trung bình của các điểm dữ
liệu. Đó là lý do tại sao thể hiện nhóm (hay còn gọi là tâm của nhóm) thường
được tính là trung bình nhóm vàđó là cách thuật toán mang tên.
13
Gom Văn bản bằng Thuật toán K-Means
Thuật toán hội tụ khi việc gán không còn thay đổi. Người ta có thể thấy
rằng hàm mục tiêu k-means được định nghĩa trong biểu thức 2.1 sẽ giảm bất cứ
khi nào có một thayđổi trong bướcc gán hay bước tái định vị và sự hội tụ được
đảm bảo sau hữu hạn bước lặp. Lưu ý, mỗi bước lặp cần Nk phép so sánh. Đây
là độ phức tạp thời gian trong mỗi bước lặp. Số bước lặp cần cho sự hội tụ thay
đổi và có thể tùy thuộc vào N, nhưng ở lần cắt đầu tiên, k-means có thể được
xem là tuyến tính với kích thước tập dữ liệu.
Hơn nữa, do thao tác so sánh là tuyến tính với d nên thuật toán cũng
tuyến tính theo chiều dữ liệu.
Thuật toán k-means
3. Thời gian và độ phức tạp của thuật toán K-means.
- Độ phức tạp của việc chọn k cụm ban đầu là O(k).
- Tính khoảng cách của n đối tượng với trọng tâm của từng cụm là O(kn).
- Thời gian cập nhật lại centriods là O(n).
- Thời gian của bước 4 là O(n)
Vậy độ phức tạp của thuật toán K-means là:
O(k) + t(O(kn) + O(n) + O(n)) = O(tkn)
4. Ưu điểm
- Hiệu suất tượng đối: do t, k << n (t là số lần lặp, k là số cụm, n là tập

văn bản) cho nên có sự thực thi rất tốt trong hầu hết các ứng dụng.
- Scalable tượng đối: trong khi xử lý các tập dữ liệu lớn.
- Kết thúc ở điểm tối ưu cục bộ, có thể dùng thuật toán di truyền để tìm tối
ưu toàn cục.
14
Gom Văn bản bằng Thuật toán K-Means
5. Một số hạn chế của thuật toán k-means
Sự hội tụ chỉ là tối ưu cục bộ và thuật toán khá nhạy cảm với các định vị
tâm khởi tạo.Nói cách khác, việc khởi tạo tâm các thể hiện cụm C khác nhau có
thể dẫn đến rất nhiều cụm, thậm chí trên cùng tập dữ liệu U. Việc khởi tạo
nghèo nàn có thể dẫn đến các cụm rất nghèo nàn.
Như đã đề cập, việc chọn giá trị tối ưu của k có thể khó. Nếu hiểu rõ về
tập dữ liệu, như là số mảnh tự nhiên có trong tập dữ liệu thì sự hiểu biết đó là cơ
sở để chọn k. Ngược lại, ta phải dùng một chuẩn khác để chọn k. Một giải pháp
là thử nhiều giá trị khác nhau của k và chọn cụm mà nó cực tiểu hàm mục tiêu k-
means. Giá trị hàm mục tiêu không giống thông tin như mong muốn. Điều này
làm bài toán khó hơn khi dùng hàm mục tiêu cho (a) các giải pháp so sánh trực
tiếp với nhiều số cụm khác nhau và (b) tìm giá trị tối ưu của k. Vì vậy, nếu
không biết được giá trị k mong chờ, người ta sẽ chạy k-means với các giá trị k
khác nhau rồi chọn ra một trong những giá trị tốt nhất.
Người ta có thể tăng dần số cụm, kết hợp với chuẩn dừng thích hợp. Chia
k-mean làm 2, đầu tiên cho tất cả dữ liệu vào trong một cụm, sau đó chia một
cách đệ quy cụm ít bền vững nhất thành 2 cụm dùng 2-means. Thuật toán LBG
dùng cho lượng tử hóa vec-tơ gấp đôi số cụm cho đến khi có kích thước hợp lý.
Cả hai hướng tiếp cận trên làm nhẹ bớt nhu cầu biết trước k. Nhiều nhà nghiên
cứu khác vẫn tiếp tục nghiên cứu vấn đề này.
Với các giới hạn trên, k-means kém chất lượng do nhiều vấn đề khác. Đầu
tiên có thể được hiểu bằng bài toán khớp dữ liệu dùng cách trộn k Gaussian với
các ma trận thống kê Σ=σ 2 I (isotropic convariance matrices), với I là ma trận
xác định, các kết quả trong phiên bản “mềm” của k-means. Chính xác hơn, nếu

các phép gán mềm của các điểm dữ liệu cho những thành phần trộn của một mô
hình như vậy trở nên khó, sao cho mỗi điểm dữ liệu được định vị đơn độc cho
thành phần giống nhất, đó là thuật toánk-means. Từ đó có thể thấy, k-means sẽ
gặp khó khăn bất cứlúc nào khi dữ liệu không được mô tả tốt theo vị trí của các
phân bố Gaussian. Ví dụ, k-means sẽ có vấn đề nếu có các nhóm có hình dạng
không lồi.
Phương pháp khác để làm việc với các cụm không lồi bằng cách bắt cặp
k-means với thuật toán khác. Ví dụ, đầu tiên ta có thể gom cụm dữ liệu thành số
lượng lớn các nhóm dùng k-means. Sau đó tích tụ các nhóm này thành các cụm
lớn hơn dùng cụmphân cấp liên kết đơn, có thể dò tìm ra hình dạng phức tạp.
Hướng tiếp cận này cũng là giải pháp ít nhạy cảm hơn so với khởi tạo. Do
phương pháp phân cấp cho ra nhiều kết quả trong nhiều giải pháp, ta không cần
15
Gom Văn bản bằng Thuật toán K-Means
lo lắng về việc chọn k chính xác; thay vì, ta có thể dùng giá trị lớn cho k khi tạo
các cụm khởi tạo.
Thuật toán cũng nhạy cảm với sự hiện diện của những phần nằm ngoài,
do sử dụng độ đo trung bình. Để xử lý vấn đề này, đầu tiên là tiền xử lý loại bỏ
những phần nằm ngoài có thể hữu ích. Sau đó hậu xử lý kết quả, ví dụ để loại bỏ
các cụm nhỏ hay trộncác cụm gần nhau thành cụm lớn hơn cũng cần thiết. Thuật
toán ISOD T năm 1967sử dụng hiệu quả cho cả tiền và hậu xử lý trên k-means.
16
Gom Văn bản bằng Thuật toán K-Means
CHƯƠNG III
DEMO THỰC HIỆN GOM VĂN BẢN
BẰNG THUẬT TOÁN K-MEANS
1. Cụ thể thuật toán K-Means
1.1. Phát biểu bài toán phân lớp với K-means
Input
Tập các đối tượng X = {xi| i = 1, 2, …, N},

Số cụm: K
Output
Các cụm Ci( i = 1 ÷ K) tách rời và hàm tiêu chuẩn E đạt giá trị tối thiểu.
Thuật toán hoạt động trên 1 tập vectơ d chiều, tập dữ liệu X gồm N phần tử:
X = {xi | i = 1, 2, …, N}
K-Mean lặp lại nhiều lần quá trình:
- Gán dữ liệu.
- Cập nhật lại vị trí trọng tâm.
- Quá trình lặp dừng lại khi trọng tâm hội tụ và mỗi đối tượng là 1 bộ
phận của 1 cụm.
- Hàm đo độ tương tự sử dụng khoảng cách Euclidean, trong đó cj là trọng
tâm của cụm Cj.
Hàm trên không âm, giảm khi có 1 sự thay đổi trong 1 trong 2 bước: gán
dữ liệu và định lại vị trí tâm.
Thuật toán:
- Bước 1 - Khởi tạo
Chọn K trọng tâm {ci} (i = 1÷K).
- Bước 2 - Tính toán khoảng cách
- Bước 3 - Cập nhật lại trọng tâm
17
Gom Văn bản bằng Thuật toán K-Means
- Bước 4 – Điều kiện dừng: lặp lại các bước 2 và 3 cho tới khi không có
sự thay đổi trọng tâm của cụm.
Hình 3. Sơ đồ khối chương trình
1.2. Ví dụ hiện thực:
Thực hiện thuật toán K-means phân thành 3 cụm cho tập vector A(x,y)
như sau:
A1(2, 10) A2(2, 5) A3(8, 4) A4(5, 8) A5(7, 5) A6(6, 4) A7(1, 2) A8(4, 9)
Khoản cách 2 vector:a=(x1, y1),b=(x2, y2) được định nghĩa: ρ(a, b) = |x2
– x1| +|y2 – y1|. (trong ví dụ này chúng ta dùng công thức tính khoản cách này

thay vì khoản cách Euclid)
Áp dụng thuật toán:
Bước 1: ChọnVector trọng tâm ban đầu của từng cụm: A1(2, 10), A4(5,
8) và A7(1, 2).
Bước 2: tính toán khoản cách
(2, 10) (5, 8) (1, 2)
Vector Khoản cách 1 Khoản cách 2 Khoản cách 3 Cluster
A1 (2, 10)
A2 (2, 5)
A3 (8, 4)
A4 (5, 8)
A5 (7, 5)
A6 (6, 4)
A7 (1, 2)
A8 (4, 9)
Chúng ta tính khoản cách từ các vector còn lại so với các vector trọng tâm.
18
Gom Văn bản bằng Thuật toán K-Means
vector trọng tâm cụm 1
x1, y1 x2, y2
(2, 10) (2, 10)
p (a, b) = |x2 – x1| + |y2 – y1|
p(vector, trọng tâm cụm 1) = |x2 – x1| + |y2 – y1|
= |2 – 2| + |10 – 10|
= 0 + 0
= 0
vector trọng tâm cụm 2
x1, y1 x2, y2
(2, 10) (5, 8)
p (a, b) = |x2 – x1| + |y2 – y1|

p (vector, trọng tâm cụm 2) = |x2 – x1| + |y2 – y1|
= |5 – 2| + |8 – 10|
= 3 + 2
= 5
vector trọng tâm cụm 3
x1, y1 x2, y2
(2, 10) (1, 2)
p (a, b) = |x2 – x1| + |y2 – y1|
p (vector, trọng tâm cụm 2) = |x2 – x1| + |y2 – y1|
= |1 – 2| + |2 – 10|
= 1 + 8
= 9
Cập nhật khoản các của vector A tới các vector trọng tâm trong từng cụm:
(2, 10) (5, 8) (1, 2)
Vector Khoản cách 1 Khoản cách 2 Khoản cách 3 Cluster
A1 (2, 10) 0 5 9 1
A2 (2, 5)
A3 (8, 4)
A4 (5, 8)
A5 (7, 5)
A6 (6, 4)
A7 (1, 2)
A8 (4, 9)
Khoản các từ vetor A1 tới các cụm (dựa vào vector trọng tâm của từng
cụm) là: 0, 5, 9
Như vậy khoảng cách từ A1 tới cụm 1 là ngắn nhât à A1 thuộc cụm 1.
19
Gom Văn bản bằng Thuật toán K-Means
Cluster 1 Cluster 2 Cluster 3
(2, 10)

Tương tự cho vector A2 (2, 5)
vector trọng tâm cụm 1
x1, y1 x2, y2
(2, 5) (2, 10)
p (a, b) = |x2 – x1| + |y2 – y1|
p(vector, trọng tâm cụm 1) = |x2 – x1| + |y2 – y1|
= |2 – 2| + |10 – 5|
= 0 + 5
= 5
vector trọng tâm cụm 2
x1, y1 x2, y2
(2, 5) (5, 8)
p (a, b) = |x2 – x1| + |y2 – y1|
p (vector, trọng tâm cụm 2) = |x2 – x1| + |y2 – y1|
= |5 – 2| + |8 – 5|
= 3 + 3
= 6
vector trọng tâm cụm 3
x1, y1 x2, y2
(2, 5) (1, 2)
p (a, b) = |x2 – x1| + |y2 – y1|
p (vector, trọng tâm cụm 2) = |x2 – x1| + |y2 – y1|
= |1 – 2| + |2 – 5|
= 1 + 3
= 4
Khoản các từ vetor A2 tới các cụm (dựa vào vector trọng tâm của từng
cụm) là: 5, 6, 4
Iteration 1
(2, 10) (5, 8) (1, 2)
Vector Khoản cách 1 Khoản cách 2 Khoản cách 3 Cluster

A1 (2, 10) 0 5 9 1
20
Gom Văn bản bằng Thuật toán K-Means
A2 (2, 5) 5 6 4 3
A3 (8, 4)
A4 (5, 8)
A5 (7, 5)
A6 (6, 4)
A7 (1, 2)
A8 (4, 9)
Như vậy khoảng cách từ A2 tới cụm 3 là ngắn nhât là A1 thuộc cụm 3.
Cluster 1 Cluster 2 Cluster 3
(2, 10) (2, 5)
Tương tự cho các vector khác ta được bảng sau:
Iteration 1
(2, 10) (5, 8) (1, 2)
Vector Khoản cách 1 Khoản cách 2 Khoản cách 3 Cluster
A1 (2, 10) 0 5 9 1
A2 (2, 5) 5 6 4 3
A3 (8, 4) 12 7 9 2
A4 (5, 8) 5 0 10 2
A5 (7, 5) 10 5 9 2
A6 (6, 4) 10 5 7 2
A7 (1, 2) 9 10 0 3
A8 (4, 9) 3 2 10 2
Cluster 1 Cluster 2 Cluster 3
(2, 10) (8, 4) (2, 5)
(5, 8) (1, 2)
(7, 5)
(6, 4)

(4, 9)
Bước 3: Cập nhật lại trọng tâm
Cụm1: có 1 vector A1(2, 10) nên trọng tâm không đổi
Cụm 2: ( (8+5+7+6+4)/5, (4+8+5+4+9)/5 ) = (6, 6)
Cụm 3: ( (2+1)/2, (5+2)/2 ) = (1.5, 3.5)
C1 = (2, 10),
C2 ((8+5+7+6+4)/5, (4+8+5+4+9)/5) = (6,6)
C3 ((2+1)/2, (5+2)/2) = (1.5, 3.5)
Các cụm mới sau lần phân đầu tiên:
Cụm 1; A1
21
Gom Văn bản bằng Thuật toán K-Means
Cụm 2: A3, A4, A5, A6, A8
Cụm 3: A2, A7
Các vector trọng tâm ban đầu của từ cụm được biểu diễn bằng chấm đỏ
Trọng tâm sau khi cậpnhật được biẻu diễn bằng dấu x
Bước 4: Lặp lại bước 2 và bước 3 tới khi không có sự thay đổi trọng tâm
trong cụm.
Lần lặp thứ 2:
Ta được:
cụm 1: A1, A8
cụm 2: A3, A4, A5, A6
cụm 3: A2, A7
Trọng tâm mới: C1(3, 9.5); C2 (6.5, 5.25); C3 (1.5, 3.5)
Lần lặp thứ 3:
Ta có:
cụm 1: A1, A4, A8
cụm 2: A3, A5, A6
cụm 3: A2, A7
22

Gom Văn bản bằng Thuật toán K-Means
Trọng tâm mới: C1(3.66, 9); C2(7, 4.33); C3 (1.5, 3.5)
Cập nhật trọng tâm sau lần lặp thứ 2 và thứ 3
2. Áp dụng thuật toán K-means vào phân lớp văn bản
2.1. Giới thiệu:
Để áp dụng thuật toán K-mean vào phân lớp văn bản ta cần phải thực hiện
vector hóa văn bản mỗi văn bản được biểu diễn dưới dạng vector
, việc vector hóa văn bản sử dụng mô hình vector
không gian. Sau khi có tập các vector ta có thể áp dụng thuật toán K-mean vào
tách văn bản.
2.2. Mô hình vector không gian
Mô hình vector không gian hay mô hình vector hạn là một mô hình đại số
cho đại diện các tài liệu văn bản (và bất kỳ đối tượng nào, nói chung) là vector
định danh, chẳng hạn như, ví dụ về chỉ số. Nó được sử dụng trong lọc thông tin,
thu hồi thông tin, lập chỉ mục và bảng xếp hạng liên quan. Sử dụng đầu tiên của
nó là hệ thống truy hồi thông tin SMART.
Tài liệu và các truy vấn được biểu diễn như là vectơ
Mỗi kích thước tương ứng với một thuật ngữ riêng biệt.Nếu hạn xảy ra
trong tài liệu, giá trị của nó trong vector là không.Một số cách khác nhau tính
toán các giá trị này, còn được gọi là trọng lượng (hạn), đã được phát triển. Một
23
Gom Văn bản bằng Thuật toán K-Means
trong những phương án tốt nhất được biết đến là tf-idf trọng (xem ví dụ dưới
đây). Định nghĩa của thuật ngữ phụ thuộc vào ứng dụng. Thông thường điều
kiện là những từ đơn, từ khoá hoặc cụm từ dài. Nếu được lựa chọn là các điều
khoản, số chiều của vector là số từ trong từ vựng (số lượng các từ riêng biệt xảy
ra trong ngữ liệu).Vector hoạt động có thể được sử dụng để so sánh các tài liệu
với các truy vấn.
Thứ hai quá trình chọn vector trọng tâm ban đầu rất quan trọng, nếu ta tìm
được các trọng tâm trong từng nhóm phân biệt đầu tiên thì là rất tốt, tuy nhiên

điều này khó thực hiện được. Trong chương trình, chúng em chỉ thực hiện
Random trọng tâm ban đầu. Số nhóm ban đầu cũng là một vấn đề, chúng ta cần
phải xác định được từ đầu số nhóm, trong khi các ứng dụng thực tế thì số nhóm
này cần rút ra
được từ tập dữ liệu.
2.3. Xác định trọng số (tọa độ) của hạn (term) trong văn bản
Trong mô hình vector không gian cổ điển, trọng lượng cụ thể hạn trong
các vectơ tài liệu văn bản là tích của các biến số địa phương và toàn cục. Mô
hình này được biết đến như là nghịch đảo tần số của hạn tần số tài liệu mô hình.
Vector trọng
lượng cho tài liệu d là vector
Trong đó tọa độ wt,d được tính bởi công thức:
Trong đó, tft,d là tần số xuất hiện của hạn t tromg tài liệu d.
là nghịch đảo tần số tài liệu. |D| là tổng tài liệu
trongtập. số tài liệu chứa hạn t. trong demo nhỏ này chúng em xem trọng số của
các hạn là tần số xuất hiện của hạn đó trong văn bản.
2.4. Xác định các hạn (term) trong văn bản
Xác định các hạn trong văn bản chính là việc xác định các từ trong văn
bản.Tách từ trong văn bản là một bải toán khó, đặc biệt trong tiếng Việt. Đối với
24
Gom Văn bản bằng Thuật toán K-Means
việc xácđịnh các hạn trong văn bản thì các từ tối nghĩa sẽ được loại bỏ đầu tiên,
các từ tối
nghĩa thường là các giới từ, mạo từ như: “thì”, “là”, “và”, “sẽ”,… Các từ này
được gọi là stopwords.
Đối với văn bản tiếng anh việc tách từ tương đối dễ vì hầu hết các từ trong
tiếng Anh là từ đơn chúng ta có thể áp dụng việc tách các khoảng trắng và ký tự
đặc biệt. Tuy nhiên hầu hết các từ trong tiếng việt là các từ ghép việc tách các từ
đơn như vậy sẽ làm cho việc gom nhóm không chính xác.
Ví dụ: “Bác sĩ”, “ca sĩ”, “nhạc sĩ”, “nha sĩ”,… thì việc tách thành từ đơn

có thể
làm cho việc gom nhóm không chính xác.
Trong ứng dụng nhỏ này chúng em sử dụng việc tách từ theo từ điển. Một
từ điển gồm các từ ghép phổ biến trong tiếng Việt được chọn lọc gồm các từ
thường dùng hầu hết là các danh từ. Từ điển được sắp xếp theo thứ tự giảm dần
của số âm tiết.
Việc sắp xếp giảm dần số âm tiết sẽ giúp việc tách từ chính xác hơn.Việc
tách từ sẽ đươc thực hiện lần lượt từ các từ nhiều âm tiết tới các từ ít âm tiết.
Ví dụ:
“Công nghệ thông tin ngày càng phát triển”
Mẫu từ điển: “Công nghệ thông tin”, “Công nghệ”, “Thông tin”
3. Chương trình demo
3.1. Giao diện
25