ĐẠI HỌC CÔNG NGHỆ

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRẦN THỊ KIM THUYẾN
MỘT SỐ THUẬT TOÁN PHÂN CỤM DỮ LIỆU

LUẬN VĂN THS CÔNG NGHỆ THÔNG TIN

Người hướng dẫn PGSTSKH : BÙI CÔNG CƯỜNG Hà nội: 2007


2.3.3 PHƢƠNG PHÁP PHÂN CỤM DỰA TRÊN MẬT ĐỘ 36
2.3.4 PHƢƠNG PHÁP PHÂN CỤM DỰA TRÊN LƢỚI 36
2.3.5 PHƢƠNG PHÁP PHÂN CỤM DỰA TRÊN MÔ HÌNH 37
2.3.6 PHƢƠNG PHÁP PHÂN CỤM CÓ DỮ LIỆU RÀNG BUỘC 38
CHƢƠNG 3. MỘT SỐ THUẬT TOÁN PHÂN CỤM DỮ LIỆU 40
3.1 THUẬT TOÁN PHÂN CỤM PHÂN HOẠCH 41
3.1.1 THUẬT TOÁN K-MEANS 41
3.1.2 THUẬT TOÁN PAM 46
3.1.3 THUẬT TOÁN CLARA 51
3.1.4 THUẬT TOÁN CLARANS 53
3.2 CÁC THUẬT TOÁN PHÂN CỤM PHÂN CẤP 54

2
3.2.1 THUẬT TOÁN HERACHICAL 54
3.2.2 THUẬT TOÁN BIRCH 62
3.2.3 THUẬT TOÁN CURE 66
3.3 CÁC THUẬT TOÁN PHÂN CỤM DỰA TRÊN MẬT ĐỘ 69
3.3.1 THUẬT TOÁN DBSCAN 70
3.3.2 THUẬT TOÁN OPTICS 76
3.4 CÁC THUẬT TOÁN PHÂN CỤM DỰA TRÊN LƢỚI 77
3.4.1 THUẬT TOÁN STING 78
3.4.2 THUẬT TOÁN CLIQUE 81
CHƢƠNG 4. PHÂN CỤM DỮ LIỆU MỜ 83
4.1 VẤN ĐỀ PHÂN CỤM MỜ 83
4.2 KHÁI NIỆM VỀ TẬP MỜ VÀ PHÂN CỤM MỜ 84
4.2.1 KHÁI NIỆM VỀ TẬP MỜ VÀ BIỂU DIỄN TẬP MỜ 84
4.2.2 KHÁI NIỆM PHÂN CỤM MỜ 85
4.3 THUẬT TOÁN PHÂN CỤM MỜ K-MEANS 86
4.3.1 MÔ TẢ THUÂT TOÁN 88
4.3.2 ĐỘ PHỨC TẠP CỦA THUẬT TOÁN 89
4
DANH MỤC HÌNH VẼ, ĐỒ THỊ

Hình 1.1: Quá trình khám phá tri thức
Hình 1.2. Các kỹ thuật khai phá dữ liệu
Hình 1.3. Quy trình phân cụm
Hình 1.4. Các phần tử ngoại lai trong dữ liệu
Hình 2.1. Mối quan hệ giữa tỷ lệ phép đo và sự phân cụm
Hình 2.2. Ví dụ về các phép đo khoảng cách
Hình 2.3. Một số loại khoảng cách giữa hai cụm
Hình 2.4. Các chiến lƣợc phân cụm phân cấp
Hình 2.5. Cấu trúc dữ liệu lƣới
Hình 3.1. Xác định ranh giới của các cụm khởi tạo
Hình 3.2. Tính toán trọng tâm của các cụm mới
Hình 3.3. Ví dụ của thuật toán K-MEANS với k=2
Hình 3.4. Một số dạng cụm đƣợc khám phá bởi k-means
Hình 3.5. Khởi tạo các đối tƣợng medoid
Hình 3.6. Trƣờng hợp C
jmp
không âm
Hình 3.7. Trƣờng hợp C
jmp
có thể âm hoặc dƣơng
Hình 3.8. Trƣờng hợp C
jmp
=0
Hình 3.9. Trƣờng hợp C
jmp

đòi hỏi cao, cần có những hiểu biết, những tri thức để hỗ trợ cho việc ra quyết
định. Đến những năm 90 nhu cầu khám phá tri thức thực sự bùng nổ, theo đó
hàng loạt các lĩnh vực nghiên cứu về tổ chức các kho dữ liệu và kho thông tin,
các hệ trợ giúp quyết định, các thuật toán nhận dạng mẫu, phân cụm ra đời.
Phân cụm dữ liệu là quá trình tìm kiếm và phát hiện ra các cụm hoặc
các mẫu dữ liệu tự nhiên trong cơ sở dữ liệu lớn. Các kỹ thuật chính đƣợc áp
dụng trong phân cụm dữ liệu phần lớn đƣợc kế thừa từ lĩnh vực thống kê, học
máy, nhận dạng, lƣợng hoá, Có nhiều ứng dụng phân cụm dữ liệu cho việc
giải quyết các vấn đề trong các lĩnh vực nhƣ tài chính, ngân hàng, y học, xã
hội học, nhận dạng ảnh,
Nhờ sự phát triển mạnh mẽ của ngành công nghệ thông tin đã làm cho
khả năng thu thập và lƣu trữ dữ liệu của các hệ thống thông tin tăng một cách
vũ bão. Kho dữ liệu, nguồn tri thức của nhân loại cũng trở nên vô tận và làm
thế nào để khai thác đƣợc nguồn tri thức đó đang là một vấn đề nóng bỏng
của nền công nghệ thông tin thế giới. Vấn đề Khám phá tri thức trong Cơ sở
dữ liệu (Knowledge Discovery in Databases) đang đƣợc rất nhiều các nhà
khoa học quan tâm nghiên cứu. Khai phá dữ liệu là một bƣớc quan trọng
trong quá trình khám phá tri thức.

7
Khai phá dữ liệu có rất nhiều hƣớng tiếp cận, các kỹ thuật khai phá dữ
liệu liên quan đến rất nhiều ngành khoa học khác nhƣ: Hệ cơ sở dữ liệu, thống
kê, học máy, trực quan hoá,…Tuỳ vào từng cách tiếp cận cụ thể đƣợc sử
dụng, khai phá dữ liệu còn áp dụng một số kỹ thuật khác nhƣ mạng nơron, lý
thuyết tập mờ, biểu diễn tri thức,…
Phân cụm dữ liệu là một trong những kỹ thuật khai phá dữ liệu phổ
biến nhất, nằm trong nhóm kỹ thuật khai phá dữ liệu mô tả, có nhiệm vụ mô
tả về các tính chất hoặc các đặc tính chung của dữ liệu trong cơ sở dữ liệu
hiện có. Luận văn này tập trung trình bày một số vấn đề của phân cụm dữ
liệu, luận văn gồm bốn chƣơng, phần kết luận và phần phụ lục là chƣơng trình

đƣợc ứng dụng vào nhiều lớp bài toán thực tế khác nhau và thu đƣợc nhiều
thành quả to lớn.
Khám phá tri thức trong cơ sở dữ liệu là một quá trình nhận biết đúng
đắn, mới, hữu ích và cuối cùng là có thể hiểu đƣợc mẫu hoặc mô hình trong
dữ liệu. Quá trình khám phá tri thức có thể bao gồm các bƣớc nhƣ hình 1.1 [7]

Hình 1.1: Quá trình khám phá tri thức
- Trích chọn dữ liệu: Là bƣớc trích chọn những tập dữ liệu cần đƣợc
khai phá từ tập dữ liệu lớn ban đầu theo một tiêu chí nhất định. Đây là bƣớc
quan trọng để rút ra những tri thức hữu ích và chọn phƣơng pháp khai phá dữ
liệu phù hợp với mục đích ứng dụng và bản chất dữ liệu.
- Tiền xử lý dữ liệu: Là bƣớc làm sạch dữ liệu: lựa chọn dữ liệu nguồn,
loại bỏ các dữ liệu nhiễu hoặc ngoại lai, xử lý các giá trị không đầy đủ, biến
Dữ
liệu
thô
Trích chọn dữ
liệu
Tiền xử lý dữ
liệu
Biến đổi dữ
liệu
Khai phá dữ
liệu
Đánh giá và
giải thích
Tri thức

- Ứng dụng tri thức được khám phá: Củng cố các tri thức đã khám phá,
kết hợp các tri thức thành một hệ thống máy tính. Giải quyết các xung đột
tiềm năng trong tri thức khai thác đƣợc. Đƣa kết quả vào thực tiễn là mục đích
cuối cùng của khám phá tri thức.
Khai phá dữ liệu là một giai đoạn quan trọng nhất của quá trình khám
phá tri thức. Bản chất của quá trình khám phá tri thức là rút ra đƣợc tri thức
phù hợp từ cơ sở dữ liệu.
1.2 KHAI PHÁ DỮ LIỆU
1.2.1 KHÁI NIỆM VỀ KHAI PHÁ DỮ LIỆU
Khai phá dữ liệu (Data mining) là quá trình tìm kiếm, phát hiện các tri
thức mới, tiềm ẩn, hữu dụng trong các cơ sở dữ liệu lớn, các kho dữ
liệu…Các kết quả khoa học cùng những thành công trong khám phá tri thức
cho thấy khai phá dữ liệu là một lĩnh vực mang lại nhiều lợi ích và có triển
vọng, có ƣu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống.
Khai phá dữ liệu là một lĩnh vực có liên quan đến rất nhiều ngành khoa học
khác nhƣ: Hệ cơ sở dữ liệu, thống kê, học máy, trực quan hoá…Tuỳ vào cách
tiếp cận đƣợc sử dụng thì khai phá dữ liệu còn áp dụng một số kỹ thuật khác
nhƣ mạng nơron, lý thuyết tập thô hoặc tập mờ, biểu diễn tri thức…So với các
phƣơng pháp này, khai phá dữ liệu có một số ƣu thế rõ rệt.
So với phƣơng pháp học máy, khai phá dữ liệu có thể sử dụng dữ liệu
có nhiều nhiễu, dữ liệu không đầy đủ hoặc biến đổi liên tục. Trong khi đó,
phƣơng pháp học máy đòi hỏi tập dữ liệu phải đầy đủ, ít biến động và không
quá lớn.
Phƣơng pháp hệ chuyên gia, các ví dụ của chuyên gia thƣờng phải đòi
hỏi chất lƣợng cao hơn nhiều so với dữ liệu trong cơ sở dữ liệu.

12
Phƣơng pháp thống kê là một trong những nền tảng lý thuyết của khai
phá dữ liệu nhƣng khai phá dữ liệu đã khắc phục đƣợc một số tồn tại của
phƣơng pháp thống kê nhƣ: Các phƣơng pháp thống kê chuẩn không phù hợp

mà chƣa biết trƣớc các thông tin về lớp một phƣơng pháp của ngành học máy
nhằm tìm ra một mô hình mà phù hợp với các quan sát. Nó khác biệt với học
có giám sát ở chỗ là đầu ra đúng tƣơng ứng cho mỗi đầu vào là không biết
trƣớc. Trong học không có giám sát, một tập dữ liệu đầu vào đƣợc thu thập.
Học không có giám sát thƣờng đối xử với các đối tƣợng đầu vào nhƣ là một
tập các biến ngẫu nhiên. Sau đó, một mô hình mật độ kết hợp sẽ đƣợc xây
dựng cho tập dữ liệu đó [4].
- Học nửa giám sát (semi-supervised learning) là quá trình phân chia
một tập dữ liệu thành các lớp dựa trên một tập dữ liệu nhỏ các ví dụ huấn
luyện và một số các thông tin về một số nhãn lớp đã biết trƣớc.
Nếu căn cứ vào lớp các bài toán cần giải quyết thì kỹ thuật khai phá dữ
liệu gồm các kỹ thuật sau:
- Kỹ thuật khai phá dữ liệu mô tả: Có nhiệm vụ mô tả về các tính chất
hoặc các đặc tính chung của dữ liệu trong cơ sở dữ liệu hiện có. Các kỹ thuật
loại này gồm có: Phân cụm (Clustering), tóm tắt (Summarization), trực quan
hoá (Visualization), phân tích sự phát triển và độ lệch (Evolution and
deviation analysis), phân tích luật kết hợp (Association rules),…
- Kỹ thuật khai phá dữ liệu dự đoán: Có nhiệm vụ đƣa ra các dự đoán
dựa vào các suy diễn trên dữ liệu hiện tại. Các kỹ thuật loại này gồm có: Phân
lớp (Classification), hồi quy (Regression),…

14
Trong luận văn này, tôi tập trung trình bày về một trong những phƣơng
pháp thông dụng nhất thuộc kỹ thuật khai phá dữ liệu mô tả là “Phân cụm dữ
liệu”.

15
- Các đối tƣợng trong cùng một cụm là giống nhau hoặc gần giống
nhau đƣợc xác định bằng độ tương tự. Hay nói một cách khác, các đối tƣợng
trong cùng một cụm là tương tự với nhau.
- Các đối tƣợng thuộc các cụm khác nhau sẽ không tương tự (phi
tương tự) với nhau.
Vậy có thể hiểu một cách đơn giản là “Phân cụm là qúa trình tổ chức
các đối tượng thành các nhóm sao cho các đối tượng trong cùng một nhóm
là tương tự với nhau”. Quy trình này đƣợc thể hiện nhƣ hình 1.3.
Hình 1.3. Quy trình phân cụm
Phân cụm tối ƣu thuộc lớp bài toán NP-Hard, số cách để phân chia n
đối tƣợng thành k cụm đƣợc tính theo công thức:

Số các cụm đƣợc xác định tuỳ thuộc vào phƣơng pháp phân cụm. Các
thuật toán phân cụm tìm các nhóm chứa đối tƣợng tƣơng tự nhau. Hai hay
nhiều đối tƣợng đƣợc xếp vào cùng một cụm nếu chúng có chung một định

Thuật toán
Phân cụm
N đối tƣợng
K nhóm

16

quyết nhiều vấn đề cơ bản nhƣ: Xây dựng hàm tính độ tƣơng tự, xây dựng các
tiêu chuẩn phân cụm, xây dựng mô hình cho cấu trúc dữ liệu, xây dựng các
thuật toán phân cụm và xác lập các điều kiện khởi tạo, xây dựng các thủ tục
biểu diễn và đánh giá kết quả phân cụm. Hiện nay, chưa có một phương
pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng
cấu trúc dữ liệu. Với những loại dữ liệu hỗn hợp thì việc phân cụm càng trở
nên khó khăn và đây đang là một trong những thách thức lớn trong lĩnh vực
khai phá dữ liệu.
1.3.3 MỤC TIÊU CỦA PHÂN CỤM
Mục tiêu của phân cụm là xác định đƣợc bản chất nhóm trong tập dữ
liệu chƣa có nhãn. Nhƣng để có thể quyết định đƣợc cái gì tạo thành một cụm
tốt. Nó đòi hỏi ngƣời sử dụng phải đƣa ra một số tiêu chuẩn mà theo cách đó
kết quả phân cụm sẽ đáp ứng đƣợc yêu cầu. Ví dụ nhƣ quan tâm đến việc tìm
đại diện cho các nhóm đồng nhất (rút gọn dữ liệu), tìm kiếm các nhóm hữu
ích và phù hợp (các lớp dữ liệu hữu ích), tìm kiếm các đối tƣợng khác thƣờng
(dò tìm phần tử ngoại lai),…

18
1.3.4 CÁC BƢỚC CƠ BẢN TRONG PHÂN CỤM
- Chọn lựa đặc trưng: các đặc trƣng phải đƣợc chọn lựa một cách hợp
lý để có thể mã hoá nhiều nhất thông tin liên quan đến công việc quan tâm.
Mục tiêu chính là phải giảm thiểu sự dƣ thừa thông tin giữa các đặc trƣng.
Các đặc trƣng cần đƣợc tiền xử lý trƣớc khi dùng chúng trong các bƣớc sau.
- Chọn độ đo gần gũi: đây là một độ đo chỉ ra mức độ tƣơng tự hay
không tƣơng tự giữa hai vectơ đặc trƣng. Phải đảm bảo rằng tất cả các vectơ
đặc trƣng góp phần nhƣ nhau trong việc tính toán độ đo gần gũi và không có
đặc trƣng nào át hẳn đặc trƣng nào, điều này đƣợc đảm bảo bởi quá trình tiền
xử lý.
- Tiêu chuẩn phân cụm: điều này phụ thuộc vào sự giải thích của
chuyên gia cho thuật ngữ “dễ nhận thấy” dựa vào loại của các cụm đƣợc

để xác định các giá trị đầu vào thích hợp đối với các cơ sở dữ liệu lớn.
- Khả năng thích nghi với các dữ liệu nhiễu hoặc ngoại lai.
- Ít nhạy cảm với thứ tự của dữ liệu vào: Cùng một tập dữ liệu khi đƣa
vào phân nhóm với các thứ tự khác nhau thì không ảnh hƣởng đến kết quả
phân cụm.
- Thích nghi với dữ liệu đa chiều: Thuật toán áp dụng hiệu quả cho dữ
liệu với số chiều khác nhau.
- Dễ hiểu và dễ sử dụng.

20
1.3.6 ỨNG DỤNG CỦA PHÂN CỤM
Phân cụm là một công cụ quan trọng trong một số ứng dụng sau:
- Giảm dữ liệu: Từ một số lƣợng lớn dữ liệu, phân cụm sẽ nhóm các dữ
liệu này thành cụm dữ liệu nhỏ dễ nhận thấy sau đó xử lý mỗi cụm nhƣ một
đối tƣợng đơn.
- Rút ra các giả thuyết: Các giả thuyết này có liên quan đến tính tự
nhiên của dữ liệu phải đƣợc kiểm tra bởi việc dùng một số tập dữ liệu khác.
- Kiểm định giả thuyết: Phân cụm để xét xem có tồn tại một cụm nào
đó trong tập dữ liệu thoả mãn các giả thiết đã cho hay không.
- Dự đoán dựa trên các cụm: Trƣớc hết ta phải phân cụm một tập dữ
liệu thành các cụm mang đặc điểm của các dạng mà nó chứa. Sau đó, khi có
một dạng mới chƣa biết xác định xem nó có khả năng thuộc về cụm nào nhất
và dự đoán đƣợc một số đặc điểm của dạng này nhờ các đặc trƣng chung của
cả cụm.
Trong thực tế, phân cụm đƣợc áp dụng vào nhiều lĩnh vực khác nhau nhƣ:
- Tìm kiếm dữ liệu trên mạng: kết quả đƣợc phân thành các cụm tuỳ
theo độ tƣơng tự với dữ liệu cần tìm.
- Marketing: trợ giúp cán bộ thị trƣờng phát hiện đƣợc những phân
đoạn thị trƣờng để có chiến lƣợc, sản phẩm hợp lý đối với các phân đoạn đó.
- Phân loại khách hàng sử dụng các sản phẩm của Ngân hàng và các

, x
2
,…,x
k
); y=(y
1
, y
2
,…,y
k
); z=(z
1
,z
2
,…,z
k
)
Trong đó x
i
, y
i
, z
i
với i=1÷k là các đặc trƣng hoặc thuộc tính tƣơng ứng
của các đối tƣợng x, y, z. Nhƣ vậy ta sẽ có các kiểu dữ liệu nhƣ sau [2][3][7].
2.1.1 PHÂN LOẠI KIỂU DỮ LIỆU DỰA TRÊN KÍCH THƢỚC MIỀN
 Thuộc tính liên tục: Nếu miền giá trị của nó là vô hạn không đếm
đƣợc, nghĩa là giữa hai giá trị tồn tại vô số giá trị khác. Ví dụ nhƣ các thuộc
tính về nhiệt độ, hoặc cƣờng độ âm thanh,…
 Thuôc tính rời rạc: Nếu miền giá trị của nó là tập hữu hạn, đếm đƣợc.

tƣơng ứng với thuộc tính thứ i.
- Thuộc tính tỷ lệ: Là thuộc tính khoảng nhƣng đƣợc xác định một cách
tƣơng đối so với điểm mốc có nghĩa nào đó.
Trong các loại thuộc tính đề cập đến ở trên thì thuộc tính định danh và
thuộc tính có thứ tự đƣợc gọi chung là thuộc tính có hạng mục, còn thuộc tính
khoảng và thuộc tính tỷ lệ đƣợc gọi chung là thuộc tính số.
Đặc biệt còn có dữ liệu không gian là loại dữ liệu có thuộc tính số khái
quát trong không gian nhiều chiều, dữ liệu không gian mô tả các thông tin liên
quan đến không gian chứa đựng các đối tƣợng. Ví dụ nhƣ thông tin về hình
học,…Dữ liệu không gian có thể là dữ liệu liên tục hoặc rời rạc.
 Dữ liệu không gian liên tục: Bao chứa một vùng không gian.

24
 Dữ liệu không gian rời rạc: Có thể là một điểm trong không gian nhiều
chiều và cho phép xác định khoảng cách giữa các đối tƣợng dữ liệu trong
không gian.
Thông thƣờng, các thuộc tính số đƣợc đo bằng các đơn vị xác định nhƣ
kilogams hay centimeters. Tuy nhiên, việc thay đổi các đơn vị đo cũng ảnh
hƣởng đến kết quả phân cụm. Để khắc phục điều này phải chuẩn hoá dữ liệu
đƣợc thực hiện bằng cách thay thế mỗi một thuộc tính bằng thuộc tính số hoặc
thêm các trọng số cho các thuộc tính.
2.2 PHÉP ĐO ĐỘ TƢƠNG TỰ VÀ PHÉP ĐO KHOẢNG CÁCH
2.2.1 KHÁI NIỆM TƢƠNG TỰ VÀ PHI TƢƠNG TỰ
Khi các đặc tính của dữ liệu đƣợc xác định, ta phải tìm cách thích hợp
để xác định “khoảng cách” giữa các đối tƣợng, hay là phép đo tƣơng tự dữ
liệu. Đây là các hàm để đo sự giống nhau giữa các cặp đối tƣợng dữ liệu,
thông thƣờng các hàm này hoặc là để tính độ tƣơng tự hoặc là để tính độ phi
tƣơng tự giữa các đối tƣợng dữ liệu. 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, còn hàm tính
độ phi tƣơng tự tỷ lệ nghịch với hàm tính độ tƣơng tự. Độ tƣơng tự hoặc phi