Bài giảng Khai phá dữ liệu - Chương 4: Phân cụm dữ liệu - Nguyễn Vương Thịnh

TR ƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM 
KHOA CÔNG NGHỆ THÔNG TIN 
BÀI G I ẢNG MÔN HỌC  KHAI PHÁ DỮ LIỆU 
Giảng viên : ThS. Nguyễn V ươ ng Thịnh 
Bộ môn : Hệ thống thông tin 
Hải Phòng, 2013 
CHƯƠNG 4: PHÂN CỤM DỮ LIỆU 
2 
Thông tin về giảng viên 
Họ và tên 
Nguyễn Vương Thịnh 
Đơn vị công tác 
Bộ môn Hệ thống thông tin – Khoa Công nghệ thông tin 
Học vị 
Thạc sỹ 
Chuyên ngành 
Hệ thống thông tin 
Cơ sở đào tạo 
Trường Đại học Công nghệ - Đại học Quốc Gia Hà Nội 
Năm tốt nghiệp 
2012 
Điện thoại 
0983283791 
Email 
thinhnv@vimaru.edu.vn 
Website cá nhân 
3 
Thông tin về học phần 
Tên học phần 
Khai phá dữ liệu 
Tên tiếng Anh 
Data Mining 
Mã học phần 
17409 
Số tín chỉ 
03 tín chỉ 
Số tiết lý thuyết 
39 tiết (13 tuần x 03 tiết/tuần) 
Số tiết thực hành 
10 tiết (05 tuần x 02 tiết/tuần) 
Bộ môn phụ trách 
Hệ thống thông tin 
PHƯƠNG PHÁP HỌC TẬP, NGHIÊN CỨU 
Nghe giảng, t hảo luận, trao đổi với giảng viên trên lớp. 
Tự n ghiên cứu tài liệu và làm bài tập ở nhà. 
PHƯƠNG PHÁP ĐÁNH GIÁ 
SV phải t ham dự ít nhất 75% thời gian . 
Có 02 bài kiểm tra viết giữa học phần (X = X 2 = (L 1 + L 2 )/2). 
Thi kết thúc học phần bằng hình thức trắc nghiệm khách quan trên máy tính (Z = 0.5X + 0.5Y). 
4 
Tài liệu tham khảo 
Jiawei Han and Micheline Kamber, Data Mining Concepts and Techniques , Elsevier Inc, 2006. 
Ian H. Witten, Eibe Frank , Data Mining – Practical Machine Learning Tools and Techniques (the second edition) , Elsevier Inc, 2005 ( sử dụng kèm với công cụ Weka ). 
Elmasri, Navathe, Somayajulu, Gupta, Fundamentals of Database Systems (the 4 th Edition) , Pearson Education Inc, 2004. 
Hà Quang Thụy, Phan Xuân Hiếu, Đoàn Sơn, Nguyễn Trí Thành, Nguyễn Thu Trang, Nguyễn Cẩm Tú, Giáo trình Khai phá dữ liệu Web , NXB Giáo dục, 2009 
5 
6 
Công cụ phần mềm hỗ trợ 
Phần mềm Weka được phát triển bởi nhóm nghiên cứu của trường Đại học Waikato (New Zealand) từ năm 1999. Có thể download về tại địa chỉ:  
CHƯƠNG 4: PHÂN CỤM DỮ LIỆU 
4 .1. KHÁI NIỆM VỀ PHÂN CỤM DỮ LIỆU 
4 .2. ĐỘ ĐO SỬ DỤNG TRONG PHÂN CỤM 
4 .3. PHÂN CỤM DỮ LIỆU VỚI GIẢI THUẬT K-MEANS 
(Phân cụm từ trên xuống) 
4 .4. PHÂN CỤM DỮ LIỆU VỚI GIẢI THUẬT HAC 
(Phân cụm từ dưới lên) 
4 .5. SO SÁNH GIẢI THUẬT K-MEANS VÀ HAC 
4 .6. PHÂN CỤM DỮ LIỆU VỚI PHẦN MỀM WEKA 
7 
8 
4 .1 . KHÁI NIỆM VỀ PHÂN CỤM DỮ LIỆU 
4 .1.1. Phân cụm dữ liệu (clustering) là gì? 
Phân cụm dữ liệu là quá trình phân chia các đối tượng dữ liệu (bản ghi) vào các nhóm (cụm) sao cho các đối tượng thuộc về cùng một cụm thì có các đặc điểm “tương tự” nhau (“gần” nhau) và các đối tượng thuộc về các cụm khác nhau thì có các đặc điểm “khác” nhau (“xa” nhau). 
Đại lượng nào xác định sự “tương tự” và “khác” nhau giữa các đối tượng? 
Khác với phân lớp, phân cụm được xem quá trình học không có giám sát (unsupervised learning). Dữ liệu được phân vào các cụm mà không cần có tập mẫu học (training sample). 
9 
4 .1.2. Ứng dụng của phân cụm dữ liệu 
Phân cụm dữ liệu có thể ứng dụng trong nhiều lĩnh vực: 
Nghiên cứu thị trường ( M arketing ) : Xác định các nhóm khách hàng (khách hàng tiềm năng, khách hàng lớn , phân loại và dự đoán hành vi khách hàng,) sử dụng sản phẩm hay dịch vụ của công ty để giúp công ty có chiến lược kinh doanh hiệu quả hơn . 
Sinh học ( B iology ) : Ph â n nhóm động vật và thực vật dựa vào các thuộc tính của chúng . 
Quản lý thư viện ( L ibraries ) : Theo dõi độc giả, sách, dự đoán nhu cầu của độc giả 
Tài chính, Bảo hiểm ( Finance and I nsurance ) : Phân nhóm các đối tượng sử dụng bảo hiểm và các dịch vụ tài chính, dự đoán xu hướng (trend) của khách hàng, phát hiện gian lận tài chính (identifying frauds) . 
Khai phá web ( Web Mining ) : Phân loại tài liệu (document classification) ,  phân loại người dùng web (clustering weblog) , 
10 
4 .2. ĐỘ ĐO SỬ DỤNG TRONG PHÂN CỤM 
Để xác định tính chất tương đồng giữa các đối tượng dữ liệu, người ta thường sử dụng khái niệm “khoảng cách” (distance). 
Hai đối tượng có “khoảng cách” càng nhỏ thì càng “tương tự” (giống) nhau và có “khoảng cách” càng lớn thì càng “khác” nhau. 
Xét hai đối tượng dữ liệu (bản ghi) r i và r j , mỗi đối tượng có n thuộc tính : 
Khoảng cách Euclid ( Euclidean Distance ): 
Khoảng cách Manhattan ( Manhattan Distance ): 
11 
4 .3. PHÂN CỤM VỚI GIẢI THUẬT K-MEANS 
4 .3.1. Khái niệm về trọng tâm cụm 
Xét cụm dữ liệu C j gồm m đối tượng thuộc cụm: 
Mỗi đối tượng có n thuộc tính: 
Trọng tâm cụm (mean/centroid) là đối tượng m j được xác định: 
Ví dụ: 
Cho cụm C 1 = {r 1 , r 2 , r 3 } với r 1 = (1, 2, 1), r 2 = (1, 3, 2), r 3 = (1, 1, 3). 
Trọng tâm cụm là: 
r 1 
r 2 
r 3 
m 1 
C 1 
12 
4 .3.2. Nội dung giải thuật K-means 
Input : 	Tập dữ liệu D gồm m đối tượng dữ liệu (bản ghi): r 1 , r 2 ,, r m . 
	Số lượng cụm k. 
Output : k cụm dữ liệu. 
Begin 
	Chọn ngẫu nhiên k đối tượng làm trọng tâm cho k cụm; 
	 Repeat 
	Gán mỗi đối tượng r i cho cụm mà khoảng cách từ đối 	tượng đến trọng tâm cụm là nhỏ nhất trong số k cụm; 
	Xác định lại trọng tâm cho mỗi cụm dựa trên các đối 	tượng được gán cho cụm; 
	 Until (Không còn sự thay đổi); 
End; 
(xem “Fundamentals of Database Systems – 4 th Edition” trang 680) 
13 
m 1 
m 2 
m 3 
r 1 
r 2 
C 1 
C 2 
C 3 
d(r 1 ,m 1 ) < d(r 1 ,m 2 ) < d(r 1 ,m 3 ) → r 1 thuộc C 1 
d(r 2 ,m 3 ) < d(r 2 ,m 2 ) < d(r 2 ,m 1 ) → r 2 thuộc C 3 
14 
4 .3.3. Điều kiện dừng của giải thuật K-means 
Có hai kết cục có thể xảy ra đối với giải thuật K-means: 
Giải thuật hội tụ : không còn sự phân chia lại các đối tượng giữa các cụm, hay trọng tâm các cụm là không đổi . Lúc đó tổng các tổng khoảng cách nội tại từ các đối tượng thuộc cụm đến trọng tâm cụm là cực tiểu: 
Đây là điều kiện dừng “lý tưởng”. 
J 
n 
J min 
15 
Giải thuật không hội tụ : trọng tâm của các cụm cứ liên tục thay đổi. Lúc đó có 3 lựa chọn: 
Dừng giải thuật khi số lượng vòng lặp vượt quá một ngưỡng nào đó định trước . 
Dừng giải thuật khi giá trị J nhỏ hơn một ngưỡng nào đó định trước. 
Dừng giải thuật khi hiệu giá trị của J trong hai vòng lặp liên tiếp nhỏ hơn một ngưỡng nào đó định trước: |J n+1 – J n | < ε 
J 
n 
n min 
J min 
J H 
n H 
16 
BÀI TẬP ÁP DỤNG 
Bài tập số 1 : Cho tập dữ liệu D như sau: 
Hãy phân cụm tập dữ liệu D với k = 2. 
X 1 
X 2 
r 1 
1 
2 
r 2 
2 
2 
r 3 
2 
3 
r 4 
3 
3 
r 5 
3 
4 
r 6 
2 
4 
17 
Chọn m 1 = r 1 = (1, 2), m 2 = r 6 = (2, 4) . 
Lần lặp 1 : 
r 2 = (2, 2) 
d(r 2 , m 1 ) = |2 - 1| + |2 - 2| = 1, d(r 2 , m 2 ) = |2 - 2| + |2 - 4| = 2 ⟹ r 2 ∈ C 1 
r 3 = (2, 3) 
d(r 3 , m 1 ) = |2 - 1| + |3 - 2| = 2, d(r 3 , m 2 ) = |2 - 2| + |3 - 4| = 1 ⟹ r 3 ∈ C 2 
r 4 = (3, 3) 
d(r 4 , m 1 ) = |3 - 1| + |3 - 2| = 3, d(r 4 , m 2 ) = |3 - 2| + |3 - 4| = 2 ⟹ r 4 ∈ C 2 
r 5 = (3, 4) 
d(r 5 , m 1 ) = |3 - 1| + |4 - 2| = 4, d(r 5 , m 2 ) = |3 - 2| + |4 - 4| = 1 ⟹ r 5 ∈ C 2 
Ta thu được 2 cụm: C 1 = {r 1 , r 2 } và C 2 = {r 3 , r 4 , r 5 , r 6 } 
Cập nhật trọng tâm cụm: 
18 
Với m 1 = (1.5, 2), m 2 = (2.5, 3.5) 
Lần lặp 2 : 
r 1 = (1, 2) 
d(r 1 , m 1 ) = |1 - 1.5| + |2 - 2| = 0.5, d(r 1 , m 2 ) = |1 - 2.5| + |2 - 3.5| = 3 ⟹ r 1 ∈ C 1 
r 2 = (2, 2) 
d(r 2 , m 1 ) = |2 - 1.5| + |2 - 2| = 0.5, d(r 2 , m 2 ) = |2 - 2.5| + |2 - 3.5| = 2 ⟹ r 2 ∈ C 1 
r 3 = (2, 3) 
d(r 3 , m 1 ) = |2 - 1.5| + |3 - 2| = 1.5, d(r 3 , m 2 ) = |2 - 2.5| + |3 - 3.5| = 1 ⟹ r 3 ∈ C 2 
r 4 = (3, 3) 
d(r 4 , m 1 ) = |3 - 1.5| + |3 - 2| = 2.5, d(r 4 , m 2 ) = |3 - 2.5| + |3 - 3.5| = 1 ⟹ r 4 ∈ C 2 
r 5 = (3, 4) 
d(r 5 , m 1 ) = |3 - 1.5| + |4 - 2| = 3.5, d(r 5 , m 2 ) = |3 - 2.5| + |4 - 3.5| = 1 ⟹ r 5 ∈ C 2 
r 6 = (2, 4) 
d(r 6 , m 1 ) = |2 - 1.5| + |4 - 2| = 2.5, d(r 6 , m 2 ) = |2 - 2.5| + |4 - 3.5| = 1 ⟹ r 6 ∈ C 2 
Ta thu được hai cụm C 1 = {r 1 , r 2 } và C 2 = {r 3 , r 4 , r 5 , r 6 }. 
Sau lần lặp 2 không có sự phân bố lại các đối tượng giữa các cụm (điều kiện dừng lý tưởng). Giải thuật kết thúc và kết quả của quá trình phân cụm là: 
	C 1 = {r 1 , r 2 } và C 2 = {r 3 , r 4 , r 5 , r 6 }. 
19 
0 1 2 3 4 5 
5 
4 
3 
2 
1 
X 1 
X 2 
r 1 
r 2 
r 3 
r 4 
r 5 
r 6 
0 1 2 3 4 5 
5 
4 
3 
2 
1 
X 1 
X 2 
r 1 
r 2 
r 3 
r 4 
r 5 
r 6 
20 
Bài tập số 2 : Cho tập dữ liệu D như sau: 
Hãy phân cụm tập dữ liệu D với k = 2. 
X 1 
X 2 
A 
1 
1 
B 
2 
1 
C 
4 
3 
D 
5 
4 
21 
Chọn m 1 = A = (1, 1), m 2 = C = (4, 3) . 
Lần lặp 1 : 
B = (2, 1) 
d(B, m 1 ) = |2 - 1| + |1 - 1| = 1, d(B, m 2 ) = |2 - 4| + |1 - 3| = 4 ⟹ B ∈ C 1 
D = (5, 4) 
d(D, m 1 ) = |5 - 1| + |4 - 1| = 7, d(D, m 2 ) = |5 - 4| + |4 - 3| = 2 ⟹ D ∈ C 2 
Ta thu được 2 cụm: C 1 = {A, B} và C 2 = {C, D} 
Cập nhật trọng tâm cụm: 
Lần lặp 2 : m 1 = (1.5,1), m 2 = (4,5, 3.5) 
A = (1, 1) 
d(A, m 1 ) = |1 - 1.5| + |1 - 1| = 0.5, d(A, m 2 ) = |1 - 4.5| + |1 - 3.5| = 6 ⟹ A ∈ C 1 
B = (2, 1) 
d(B, m 1 ) = |2 - 1.5| + |1 - 1| = 0.5, d(B, m 2 ) = |2 - 4.5| + |1 - 3.5| = 5 ⟹ B ∈ C 1 
22 
C = (4, 3) 
d(C, m 1 ) = |4 - 1.5| + |3 - 1| = 4.5, d(C, m 2 ) = |4 - 4.5| + |3 - 3.5| = 1 ⟹ C ∈ C 2 
D = (5, 4) 
d(D, m 1 ) = |5 – 1.5| + |4 - 1| = 6.5, d(D, m 2 ) = |5 - 4.5| + |4 - 3.5| = 1 ⟹ D ∈ C 2 
Ta thu được 2 cụm: C 1 = {A, B} và C 2 = {C, D} 
Sau lần lặp 2 không có sự phân bố lại các đối tượng giữa các cụm (điều kiện dừng lý tưởng). Giải thuật kết thúc và kết quả của quá trình phân cụm là: 
	C 1 = {A, B} và C 2 = {C, D} 
0 1 2 3 4 5 
5 
4 
3 
2 
1 
X 1 
X 2 
A 
B 
D 
C 
0 1 2 3 4 5 
5 
4 
3 
2 
1 
X 1 
X 2 
A 
B 
D 
C 
23 
4 .4. PHÂN CỤM VỚI GIẢI THUẬT HAC 
(HAC - Hierarchical Agglomerative Clustering) 
4 .4.1. Nội dung giải thuật HAC 
Tích tụ dần “từ dưới lên” (Bottom-Up) 
Tư tưởng giải thuật : 
Ban đầu, mỗi đối tượng (bản ghi) dữ liệu được coi là một cụm. 
Từng bước kết hợp các cụm đã có thành các cụm lớn hơn với yêu cầu là khoảng cách giữa các đối tượng trong nội bộ cụm là nhỏ. 
Dừng thuật toán khi đã đạt số lượng cụm mong muốn, hoặc chỉ còn một cụm duy nhất chứa tất cả các đối tượng hoặc thỏa mãn điều kiện dừng nào đó. 
24 
G = {{r} | r ∈ D}; //Khởi tạo G là tập các cụm chỉ gồm 1 đối tượng 
Nếu |G| = k thì dừng thuật toán; //Đã đạt số lượng cụm mong muốn 
Tìm hai cụm S i , S j ∈ G có khoảng cách d(S i , S j ) là nhỏ nhất; 
Nếu d(S i , S j ) > d o thì dừng thuật toán; //Khoảng cách 2 cụm gần nhất đã lớn hơn ngưỡng cho phép 
G = G\{S i , S j }; //Loại bỏ 2 cụm S i ,S j khỏi tập các cụm 
S = S i ∪ S j ; //Ghép S i , S j thành cụm mới S 
G = G ∪ {S}; //Kết nạp cụm mới vào G 
Nhảy về bước 2. 
G: tập các cụm. 
D: tập các đối tượng (bản ghi) dữ liệu cần phân cụm. 
k: số lượng cụm mong muốn. 
d o : ngưỡng khoảng cách giữa 2 cụm. 
25 
4 .4.2. Độ đo “khoảng cách” giữa 02 cụm 
A. Độ đo khoảng cách gần nhất (single-link) 
Khoảng cách giữa 02 cụm được xác định là khoảng cách giữa 02 phần tử “gần” nhau nhất của 02 cụm đó: 
S 1 
S 2 
26 
4 .4.2. Độ đo “khoảng cách” giữa 02 cụm 
B. Độ đo khoảng cách xa nhất (complete-link) 
Khoảng cách giữa 02 cụm được xác định là khoảng cách giữa 02 phần tử “xa” nhau nhất của 02 cụm đó: 
S 1 
S 2 
27 
4 .4.2. Độ đo “khoảng cách” giữa 02 cụm 
C. Độ đo khoảng cách trọng tâm (centroid-link) 
Khoảng cách giữa 02 cụm được xác định là khoảng cách giữa 02 trọng tâm của 02 cụm đó: 
S 1 
S 2 
m 1 
m 2 
28 
4 .4.2. Độ đo “khoảng cách” giữa 02 cụm 
D. Độ đo khoảng cách trung bình nhóm (group-average) 
Khoảng cách giữa 02 cụm được xác định là khoảng cách trung bình giữa các phần tử thuộc về 02 cụm đó: 
S 1 
S 2 
29 
r 
X 1 
X 2 
1 
1 
1 
2 
2 
1 
3 
3 
3 
4 
3 
2 
5 
4 
2 
Ví dụ : Cho tập dữ liệu D gồm các bản ghi: 
Xét 2 cụm dữ liệu C 1 = {r 1 , r 2 }, C 2 = {r 3 , r 4 , r 5 }. Xác định khoảng cách d(C 1 ,C 2 ) giữa 2 cụm dựa trên các độ đo khác nhau. 
30 
0 1 2 3 4 5 
4 
3 
2 
1 
X 1 
X 2 
r 1 
r 2 
r 3 
r 4 
r 5 
r 3 
r 4 
r 5 
r 1 
4 
3 
4 
r 2 
3 
2 
3 
Ma trận khoảng cách: 
Nếu sử dụng single-link: 
d(C 1 , C 2 ) = d(r 2 , r 4 ) = 2 
Nếu sử dụng c omplete-link : 
d(C 1 , C 2 ) = d(r 1 , r 3 ) = d(r 1 ,r 5 ) = 4 
Nếu sử dụng group-average-link : 
d(C 1 , C 2 ) = 19/6 = 3.17 
Nếu sử dụng centroid-link: 
31 
4 .4.2. Độ đo “khoảng cách” giữa 02 cụm 
E. Nhận xét về các độ đo 
Với độ đo single-link : 
Mang tính chất cục bộ: Chỉ quan tâm đến những vùng mà ở đó có phần tử của 2 cụm gần nhau nhất, không quan tâm đến các phần tử khác trong cụm cũng như cấu trúc tổng thể của các cụm. 
Chất lượng phân cụm kém khi chỉ có 2 phân tử trong 2 cụm là rất gần nhau trong khi các phần tử khác ở phân tán rất xa nhau. 
Với độ đo complete-link : 
Khoảng cách 2 cụm dựa trên khoảng cách 2 phần tử xa nhau nhất ⟹ Việc ghép 2 cụm sẽ tạo ra cụm mới có đường kính nhỏ nhất. 
Chất lượng phân cụm kém khi 2 phần tử trong 2 cụm ở rất xa nhau nhưng thực tế trọng tâm 2 cụm lại ở rất gần nhau. 
32 
Với độ đo group-average : 
Tính toán khoảng cách của 2 cụm dựa trên khoảng cách của toàn bộ các cặp phần tử trong 2 cụm chứ không chỉ dựa trên một cặp phần tử duy nhất ⟹ tránh được nhược điểm của single-link và complete-link. 
Với độ đo centroid-link : 
Khắc phục được nhược điểm của single/complete-link. 
Vẫn có nhược điểm là khoảng cách giữa các cụm khi từ đi mức dưới lên mức trên của cây phân cấp có thể là không tăng dần (do trong tâm các cụm ở mức cao nhiều khi gần nhau hơn các cụm ở mức dưới) ⟹ Trái với giả thiết về độ kết dính “Các cụm nhỏ thường có độ kết dính cao hơn các cụm có kích thước lớn hơn” . 
33 
Ví dụ : Cho tập dữ liệu gồm các đối tượng với 02 thuộc tính X 1 , X 2 như sau : 
r 
X 1 
X 2 
1 
1 
1 
2 
2 
1 
3 
3 
3 
4 
3 
2 
5 
4 
2 
Áp dụng giải thuật HAC hãy phân chia tập dữ liệu trên thành 02 cụm. Biết khoảng cách giữa 02 đối tượng được đo bằng độ đo Manhattan và khoảng cách giữa 02 cụm sử dụng độ đo single-link. 
0 1 2 3 4 5 
4 
3 
2 
1 
X 1 
X 2 
r 1 
r 2 
r 3 
r 4 
r 5 
34 
1 
2 
3 
4 
5 
1 
0 
1 
4 
3 
4 
2 
0 
3 
2 
3 
3 
0 
1 
2 
4 
0 
1 
5 
0 
{1,2} 
3 
4 
5 
{1,2} 
0 
3 
2 
3 
3 
0 
1 
2 
4 
0 
1 
5 
0 
{1,2} 
{3,4} 
5 
{1,2} 
0 
2 
3 
{3,4} 
0 
1 
5 
0 
Ghép {3,4} với {5} thu được 02 cụm là {1,2} và {3,4,5} 
Đã đạt số lượng cụm cần thiết. Kết thúc thuật toán 
0 1 2 3 4 5 
4 
3 
2 
1 
X 1 
X 2 
r 1 
r 2 
r 3 
r 4 
r 5 
35 
0 1 2 3 4 5 
4 
3 
2 
1 
X 1 
X 2 
r 1 
r 2 
r 3 
r 4 
r 5 
1 
2 
3 
4 
5 
{3, 4} 
{3, 4, 5} 
{1, 2} 
36 
4 .5. SO SÁNH GIẢI THUẬT K-MEANS VÀ HAC 
GIẢI THUẬT HAC 
GiẢI THUẬT K-MEANS 
Độ phức tạp thuật toán 
Độ phức tạp thuật toán là O(N 2 ) trong đó N là số đối tượng được phân cụm. 
Ưu, nhược điểm 
Ưu điểm : 
Khái niệm đơn giản . 
Lý thuyết tốt . 
Khi cụm được trộn hay tách thì quyết định là vĩnh cửu vì thế các phương pháp khác nhau cần được xem xét được rút giảm . 
Nhược điểm : 
Quyết định trộn tách các cụm là vĩnh cửu nên thuật toán không có tính quay lui, nếu có quyết định sai thì không thể khắc phục lại. 
Độ phức tạp thuật toán cao, thời gian thực hiện phân cụm lâu. 
Áp dụng tạo cây phân cấp 
Thuật toán tạo ra cây phân cấp ngay trong quá trình phân cụm. 
Độ phức tạp thuật toán 
Độ phức tạp thuật toán O(NkT) trong đó N là số đối tượng được phân cụm, k số cụm và T là số vòng lặp trong quá trình phân cụm. 
Thường T, k << N nên ta có thể coi độ phức tạp của thuật toán là O(N). 
Ưu, nhược điểm 
Ưu điểm : 
Tính mở rộng cao, phù hợp với lượng dữ liệu lớn . 
T hời gian thực hiện thuật toán ít . 
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. 
Nhược điểm : 
Cần chỉ định trước k cụm . 
Không thể xử lý dữ liệu chuỗi và ngoại lệ. 
Không phù hợp với miền dữ liệu không lồi hay cụm có kích thước khác nhau. 
Chỉ thực hiện tốt khi xác định được trị số trung bình của các đối tượng. 
Áp dụng tạo cây phân cấp 
Tạo ra cây phân cấp từng bước một. 
Tạo cây phân cấp ở mức một sau khi tiến hành phân cụm lần một bộ dữ liệu lớn. 
Tiếp tục tạo chủ đề mức hai và các mức sau sau khi tiếp tục tiến hành phân cụm cho bộ dữ liệu thuộc từng chủ đề con. 
Cây phân cấp được tạo ra bằng cách kết hợp các lần tiến hành phân cụm. 
37 
4 .6. PHÂN CỤM DỮ LIỆU VỚI PHẦN MỀM WEKA 
Khởi động phần mềm Weka, chọn Explorer: 
38 
Chọn tập tin dữ liệu sử dụng 
39 
Chọn loại tập tin dữ liệu sử dụng (định dạng .csv hoặc .Arff) 
Chọn tên tập tin và nạp dữ liệu vào hệ thống 
40 
0 1 2 3 4 5 
5 
4 
3 
2 
1 
X 1 
X 2 
r 1 
r 2 
r 3 
r 4 
r 5 
r 6 
X 1 
X 2 
r 
1 
2 
1 
2 
2 
2 
2 
3 
3 
3 
3 
4 
3 
4 
5 
2 
4 
6 
41 
Chọn chức năng “Phân cụm dữ liệu” (cluster) 
42 
Chọn giải thuật sử dụng để phân cụm 
(K-Means hoặc HAC) 
Click để thiết lập các thông số 
c ho giải thuật 
43 
Nếu lựa chọn giải thuật K-Means: 
Chọn độ đo khoảng cách 
(độ đo Euclide hoặc Mahattant) 
Có cho phép thay thế các giá trị thiếu vắng bằng giá trị trung bình hay không 
Số lần lặp tối đa 
(Điều kiện dừng) 
Số lượng cụm mong muốn 
Giá trị cho phép khởi tạo ngẫu nhiên các trọng tâm ban đầu của các cụm 
44 
Nếu lựa chọn giải thuật HAC (Hierarchical Clustering): 
Chọn độ đo khoảng cách đối tượng (độ đo Euclide hoặc Mahattant) 
Chọn độ đo khoảng cách cụm (Single, Complete, Group-average, Centroid) 
Số lượng cụm mong muốn 
45 
Kết quả phân cụm n ếu lựa chọn giải thuật K-Means: 
Tọa độ trọng tâm các cụm sau khi hoàn thành phân cụm 
Phân bố số lượng phần tử trong các cụm 
46 
Kết quả phân cụm n ếu lựa chọn giải thuật HAC: 
Kết quả phân cụm 
Phân bố số lượng phần tử trong các cụm 
Q & A 
47