Chương 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 2
1.1 Giới thiệu về khám phá tri thức 2
1.2 Khái quát về khai phá dữ liệu 3
1.3 Các phương pháp trong khai phá dữ liệu 3
Chương 2 GOM CỤM DỮ LIỆU 5
2.1 Khái quát về gom cụm dữ liệu 5
2.2 Các độ đo dữ liệu 5
2.3 Phân loại các phương pháp gom cụm dữ liệu 7
Chương 3 THUẬT TOÁN GOM CỤM DỮ LIỆU K-MEANS
3.1 Giới thiệu thuật toán K-Means 10
3.2 Thảo luận về thuật toán K-Means 10
3.3 Cài đặt thuật toán K-Means 11
3.3.1 Bộ dữ liệu thử nghiệm 11
3.3.2 Tiền xử lý và biến đổi dữ liệu 13
3.3.3 Đánh giá kết quả sau khi cài đặt 14
3.3.4 Giao diện chương trình thử nghiệm 14
TÀI LIỆU THAM KHẢO 17
Thuật toán gom cụm dữ liệu K-Means
Chương 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1.1 Giới thiệu về khám phá tri thức
Với sự phát triển mạnh mẽ của công nghệ thông tin, dữ liệu trong đời sống, kinh tế,
xã hội liên tục gia tăng đã cung cấp cho con người nhưng tri thức mới, kiến thức được
phổ cập hơn đến với mọi người. Nhưng với sự gia tăng khối lượng kiến thức đến mức
khổng lồ đã đặt ra một vấn đề cấp bách. Vấn đề đó là làm sao để trích lọc những thông tin
quan trọng, cần thiết từ khối lượng dữ liệu khổng lồ và biến những thông tin kiến thức đó
thành các tri thức để nâng cao việc phục vụ cho cuộc sống. Từ đó, ngành khám phá tri
thức để phát triển để giải quyết vấn đề trên. Khám phá tri thức là một ngành bao hàm
nhiều lĩnh vực liên quan đến lĩnh vực nghiên cứu và xử lý dữ liệu khối lượng lớn như:
xác suất thống kê, máy học, tính toán song song… Tuy nhiên trong khám phá tri thức
được chia thành các bước chính sau đây: [1]
- Bước 1: Thu thập dữ liệu. Bước quan trọng vì để khám phá tri thức thì cần phải có

Môn: Khai phá dữ liệu Trang 3
Thuật toán gom cụm dữ liệu K-Means
- Học nữa giám sát (Semi-Supervised Learning): Quá trinh chia một tập dữ liệu
thành các lớp con dựa trên một số thông tin cho trước (thông tin về các lớp không
đầy đủ như học có giám sát).
Theo các lớp bài toán cần giải quyết, các phương pháp chính trong khai phá dữ liệu
được chia thành:
- Phân lớp và dự đoán (Classfication and Prediciton): Phân lớp một đối tượng vào
một trong các lớp đã biết trước. Đa phần bài toán thuộc dạng này còn được gọi là
phương pháp học có giám sát.
- Luật kết hợp (Association rules): Phương pháp tìm các luật biểu diễn tri thức ở
dạng luật điều kiện dựa trên xác suất (độ phổ biến và độ tin cậy) của luật.
- Phân tích chuỗi thời gian: Quá trình phân tích dữ liệu có thuộc tính biến đổi theo
thời gian. Bài toán phức tạp có nhiều ứng dụng trong thực tế như chứng khoán,
kinh tế, sinh học.
- Gom cụm dữ liệu: Gom nhóm các đối tượng trong dữ liệu thành các cụm dữ liệu.
Đây là phương pháp học không giám sát.
Chương 2 GOM CỤM DỮ LIỆU
2.1 Khái quát về gom cụm dữ liệu
Gom cụm dữ liệu là một phương pháp trong khai phá dữ liệu dùng để tìm kiếm, phát
hiện các cụm, các mẫu dữ liệu ẩn và quan trọng trong tập dữ liệu lớn để từ đó cung cấp
thông tin, tri thức cho việc ra quyết định. Thực tế hơn, gom cụm dữ liệu là quá trình phân
Môn: Khai phá dữ liệu Trang 4
Thuật toán gom cụm dữ liệu K-Means
chia tập dữ liệu ban đầu thành các cụm dữ liệu dựa trên độ tương tự hoặc độ không tương
tự giữa các đối tượng trong tập dữ liệu.
Sau khi xác định các đặc tính của dữ liệu ở các bước xử lý trước, bước tiếp theo trong
gom cụm dữ liệu cần lựa chọn phương pháp thích hợp để xác định khoảng cách giữa các
đối tượng, hay còn gọi là phép đo độ tương tự (hoặc độ không tương tự). Giá trị của hàm
tính độ đo tương tự càng lớn thì sự giống nhau giữa các đối tượng càng lớn và ngược lại

o Khoảng cách Minkowski:
1/ *
1
( , ) ( ) ,
n
q
q
i i
i
d x y x y q N
=
= − ∈
∑
o Khoảng cách Euclide:
2
1/ 2
1
( , ) ( )
n
i i
i
d x y x y
=
= −
∑
, trường hợp đặc biệt
của khoảng cách Minkowski với q = 2. Càng giống nhau thì khoảng cách
càng nhỏ.
o Tương tự Cosine (Cosine Similarity): [2]
A

hoạch điển hình như k-Means, k-Medoids …
- Gom cụm dữ liệu phân cấp
Gom cụm dữ liệu phân cấp là 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 gom cụm có thể được xây dựng theo hai phương pháp tổng quát:
phương pháp xây dựng từ trên xuống (Top Down) và phương pháp xây dựng từ dưới lên
(Bottom Up).
• Phương pháp xây dựng từ trên xuống: bắt đầu với trạng thái là tất cả các đối tượng
được xếp trong cùng một cụm. Qua mỗi bước, một cụm sẽ được tách những cụm
nhỏ hơn theo giá trị của một phép đo độ tương tự (khoảng cách) xác định cho đến
khi mỗi đối tượng là một cụm, hoặc cho đến khi điều kiện dừng thỏa mãn.
• Phương pháp xây dựng từ dưới lên: 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. Qua mỗi bước, tiến hành gom nhóm các đối
tượng theo một phép đo tương tự (khoảng cách) thành một nhóm lớn hơn. Quá
trình kết thúc khi tất cả các nhóm được gom vào thành một nhóm duy nhất hoặc
gặp phải điều kiện kết thúc.
Trong thực tế, 2 phương pháp gom cụm dữ liệu phân cấp và gom cụm dữ liệu phân
hoạch thường được sử dụng của với nhau. Kết quả của gom cụm phân hoạch là kết quả
của mỗi bước của gom cụm phân cấp. Qua mỗi cấp của gom cụm phân cấp, các ràng
buộc sẽ thay đổi để tiến hành ở các mức khác nhau của gom cụm dữ liệu phân hoạch.
- Gom cụm dữ liệu dựa trên mật độ
Mật độ ở đây được định nghĩa như là số đối tượng gần với một đối tượng dữ liệu dựa
trên một ngưỡng cho trước. Khi xác định được một cụm dữ liệu thì cụm đó sẽ liên tục
phát triển thêm các đối tượng dữ liệu mới thỏa điều kiện về mật độ. Phương pháp gom
cụm dựa vào mật độ của các đối tượng có thể phát hiện ra các cụm dữ liệu với hình thù
bất kỳ. Tuy nhiên, việc việc xác định các tham số mật độ của thuật toán rất phức tạp vì
các tham số này có tác động rất lớn đến kết quả nhận được.
Môn: Khai phá dữ liệu Trang 7
Thuật toán gom cụm dữ liệu K-Means
- Gom cụm dữ liệu dựa trên dạng lưới
Phương pháp gom cụm dữ liệu dựa trên dạng lưới phù hợp với các dữ liệu nhiều

nơron của đầu ra. Mỗi liên kết được gắn liền với một trọng số nhằm xác định vị trí
của nơron ra tương ứng. Quá trình gom cụm này tương tự như mạng nơron sẽ cho
học tập mẫu huấn luyện đã được gom cụm trước để điều chỉnh các trọng số để
qua đó khi sử dụng vào thực tế sẽ gom cụm sẽ trên các trọng số đã được điều
chỉnh nhờ vào tập mẫu huấn luyện.
Tóm lại, các phương pháp gom cụm dữ liệu đã được áp dụng rộng rãi trong thực tế.
Như trong thương mại, gom cụm sẽ cho phép các công ty tìm kiếm ra được các nhóm
khác hàng. Trong sinh học – hóa học, gom cụm dữ liệu cho phép thành lập các nhóm
gene, cấu trúc hóa học tương tự để trù bị các biến đổi, tương tác với nhau
Chương 3 THUẬT TOÁN GOM CỤM DỮ LIỆU K-MEANS
3.1 Giới thiệu về thuật toán K-Means
Thuật toán gom cụm dữ liệu K-Means là thuật toán gom cụm thuộc dạng không giám
sát và thuộc lớp bài toán gom cụm dữ liệu phân hoạch. Thuật toán K-Means được phát
triển từ lâu nhưng đến năm 1953 mới được Lloy phát triển hoàn chỉnh (thông qua các
nghiên cứu chứng minh tính đúng đắn của thuật toán) thì thuật toán gom cụm K-Means
mới được phổ biến rộng rãi. Thuật toán K-Means là một thuật toán đơn giản nhưng vẫn tỏ
ra hiệu quả trong việc gom cụm dữ liệu và vẫn được áp dụng rộng rãi trong ngày nay.
Các bước của thuật toán K-Means [3]
- Input: số lượng các cụm dữ liệu (số K) và tập dữ liệu có n điểm (đối tượng)
Môn: Khai phá dữ liệu Trang 9
Thuật toán gom cụm dữ liệu K-Means
- Output: các cụm dữ liệu chứa các đối tượng.
Bước 1: Phân hoạch đối tượn thành k tập con/ cụm khác rỗng.
Bước 2: Tính các điểm hạt giống làm centroid (trung bình của các đối tượng của cụm)
cho từng cụm trong cụm hiện hành
Bước 3: Gán từng đối tượng vào cụm có centroid gần nhất
Bước 4: Quay về bước 2, kết thúc khi không còn gán mới.
Các phép khoảng cách thường được dùng trong thuật toán gom cụm K-Means là
khoảng cách Minkowski và các biến thể của Minkowski là Euclide và Manhattan (đề cập
ở phần 2.2).

Bộ dữ liệu được sử dụng ở đây là bộ dữ liệu của tổ chức MovieLens chuyên thu thập
việc đánh giá những bộ phim từ những người dùng.
Thử nghiệm sử dụng 2 bộ dữ liệu:
- Bộ 1: có 100 ngàn đánh giá từ 943 người dùng đối với 1682 bộ phim.
- Bộ 2: có 1 triệu đánh giá từ 6040 người dùng đối với 3952 bộ phim.
Các thông tin chi tiết khác:
- Thông tin về mỗi người dùng {Id, Tuổi, Giới Tính, Công Việc}
- Thông tin về mỗi bộ phim {Id, tên phim, các thể loại}
- Thông tin về đánh giá {Id người dùng, Id Phim, Đánh giá}
Trong đó:
- Giới tính được xét là nam hay nữ.
- Tuổi có giá trị và thể hiện của giá trị đó:
 1: tuổi dưới 18
 18: tuổi từ 18 đến 24
 25: tuổi từ 25 đến 34
 35: tuổi từ 35 đến 44
 45: tuổi từ 45 đến 49
 50: tuổi từ 50 đến 55
 56: trên 56 tuổi.
- Công việc có giá trị và thể hiện của giá trị (theo tiếng Anh) đó:
 0: other
 1: academic/educator
 2: artist
 3: clerical/admin
 4: college/grad student
 5: customer service
 6: doctor/health care
 7: executive/managerial
 8: farmer
Môn: Khai phá dữ liệu Trang 11

 16: War
 17: Western
- Đánh giá của người dùng đối với bộ phim nằm trong khoảng từ 1 đến 5. Trong đó,
5 là mức độ đánh giá cao nhất và 1 là mức độ đánh giá hài lòng thấp nhất.
3.3.2 Tiền xử lý và biến đổi dữ liệu
Do việc gom cụm chỉ dựa trên tiêu chí đánh giá của người dùng đối với bộ phim nên
các thuộc tính như tuổi và giới tính, công việc của người được bỏ qua trong việc gom
cụm do không ảnh hưởng đến việc gom cụm.
Như trên có số lượng bộ phim rất lớn nên nếu gom cụm dữ liệu dựa trực tiếp theo số
lượng bộ phim thì khi đó chi phí tính toán giá trị trọng tâm và khoảng cách (khoảng cách
Môn: Khai phá dữ liệu Trang 12
Thuật toán gom cụm dữ liệu K-Means
euclid được dùng ở đây) giữa các đối tượng đến trọng tâm là rất lớn. Nên ở đây sẽ biến
đỗi dữ liệu thay vì tính trực tiếp theo đánh giá từng bộ phim, sẽ tính trên đánh giá của
người dùng đối với từng thể loại.
Các bước biến đổi thống kê trung bình đánh giá của mỗi người dùng đối với từng thể
loại phim:
Bước 1: với mỗi người dùng  vectorA, vectorB có chiều dài là số thể loại phim
VectorA đếm tổng đánh giá của người dùng đối với các thể loại phim, vectorB đếm số
lượng phim tương ứng với từng thể loại mà người dùng đó xem.
Bước 2: với mỗi bộ phim sẽ có thể loại tương ứng và đánh giá tương ứng. Từ đó, cập
nhật vào vectorA và vectorB.
Bước 3: với phần tử x là thể loại tiến hành cập nhật : A[x] = A[x] / B[x].
3.3.3 Đánh giá kết quả sau khi cài đặt
Chương trình được viết trên ngôn ngữ C# (Visual Studio 2010)
Cấu hình máy thử nghiệm: Intel Core i5 2.4Ghz – Ram 4GB.
Thời gian trung bình chạy (tính theo milisecond)
30 cụm 50 cụm
Bộ dữ liệu
1

đánh giá của IDUser đó.
TÀI LIỆU THAM KHẢO
Môn: Khai phá dữ liệu Trang 15
Thuật toán gom cụm dữ liệu K-Means
[1] Lưu Tuấn Lâm, “Phương pháp gom cụm nữa giám sát”, Đồ án tốt nghiệp đại học,
2007, trang 6 – 10.
[2] Cosine Similarity – wikipedia. http://en.wikipedia.org/wiki/Cosine_similarity
[3] PGS.TS Đỗ Phúc, Bài giảng gom cụm (clustering), trang 29 – 46.
Môn: Khai phá dữ liệu Trang 16