ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG
TRẦN HÀ PHƯƠNG
PHÂN CỤM ĐỒ THỊ DỮ LIỆU VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
THÁI NGUYÊN - 2016
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG
TRẦN HÀ PHƯƠNG
PHÂN CỤM ĐỒ THỊ DỮ LIỆU VÀ ỨNG DỤNG
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01 01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Người hướng dẫn khoa học: PGS. TS. ĐOÀN VĂN BAN
THÁI NGUYÊN - 2016
i
LỜI CAM ĐOAN
Tên tôi là: Trần Hà Phương
Sinh ngày:
Học viên lớp cao học CHK13 - Trường Đại học Công nghệ thông tin và Truyền
thông - Đại học Thái Nguyên.
Hiện đang công tác tại:
Xin cam đoan: Đề tài “Phân cụm đồ thị dữ liệu và ứng dụng” do Thầy giáo
PGS.TS Đoàn Văn Ban hướng dẫn là công trình nghiên cứu của riêng tôi. Tất cả tài
liệu tham khảo đều có nguồn gốc, xuất xứ rõ ràng.
Tác giả xin cam đoan tất cả những nội dung trong luận văn đúng như nội dung
trong đề cương và yêu cầu của thầy giáo hướng dẫn. Nếu sai tôi hoàn toàn chịu trách
nhiệm trước hội đồng khoa học và trước pháp luật.
Thái Nguyên, ngày 14 tháng 4 năm 2016
Tác giả luận văn
Trần Hà Phương
ii
LỜI CẢM ƠN
Sau một thời gian nghiên cứu và làm việc nghiêm túc, được sự động viên, giúp
đỡ và hướng dẫn tận tình của Thầy giáo hướng dẫn PGS.TS Đoàn Văn Ban, luận văn
với đề tài “Phân cụm đồ thị dữ liệu và ứng dụng”đã hoàn thành.
Tôi xin bày tỏ lòng biết ơn sâu sắc đến:
Thầy giáo hướng dẫn PGS.TS Đoàn Văn Ban đã tận tình chỉ dẫn, giúp đỡ tôi
hoàn thành luận văn này.
Khoa sau Đại học Trường Đại học công nghệ thông tin và truyền thông đã
giúp đỡ tôi trong quá trình học tập cũng như thực hiện luận văn.
Tôi xin chân thành cảm ơn bạn bè, đồng nghiệp và gia đình đã động viên,
khích lệ, tạo điều kiện giúp đỡ tôi trong suốt quá trình học tập, thực hiện và hoàn
thành luận văn này.
Thái Nguyên, ngày 16 tháng 6 năm 2016
Tác giả luận văn
Trần Hà Phương
iii
MỤC LỤC
LỜI CAM ĐOAN ...................................................................................................... i
LỜI CẢM ƠN ........................................................................................................... ii
MỤC LỤC ................................................................................................................ iii
DANH MỤC CÁC TỪ VIẾT TẮT ..........................................................................v
DANH MỤC BẢNG ................................................................................................ vi
DANH MỤC CÁC HÌNH ẢNH ............................................................................ vii
MỞ ĐẦU ....................................................................................................................1
1. Tính khoa học và cấp thiết của đề tài ......................................................................1
2. Mục tiêu, đối tượng và phạm vi nghiên cứu của đề tài ...........................................2
3. Phương pháp luận nghiên cứu .................................................................................2
4. Nội dung và bố cục của luận văn ............................................................................2
CHƯƠNG 1TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU .......................................4
1.1 Khái niệm, mục tiêu và các bước cơ bản của phân cụm dữ liệu ......................4
1.1.1 Phân cụm dữ liệu là gì? .............................................................................4
1.1.2 Các mục tiêu của phân cụm dữ liệu ...........................................................5
1.1.3 Các bước cơ bản để phân cụm ...................................................................7
1.2 Một số khái niệm cần thiết khi tiếp cận phân cụm dữ liệu ..............................8
1.2.1 Phân loại các kiểu dữ liệu ..........................................................................8
1.2.2 Độ đo tương tự và phi tương tự .................................................................9
1.3 Những kỹ thuật tiếp cận trong phân cụm dữ liệu ...........................................11
1.3.1 Phương pháp phân cụm phân hoạch ........................................................12
1.3.2 Phương pháp phân cụm phân cấp ............................................................12
1.3.3 Phương pháp phân cụm dựa trên mật độ .................................................13
1.3.4 Phương pháp phân cụm dựa trên lưới ......................................................14
1.3.5 Phương pháp phân cụm dựa trên mô hình ...............................................15
1.3.6 Phương pháp phân cụm dữ liệu có liên kết .............................................15
1.4 Các ứng dụng của phân cụm dữ liệu ..............................................................16
1.5 Các yêu cầu và những vấn đề còn tồn tại trong phân cụm dữ liệu ................18
1.5.1 Các yêu cầu của phân cụm dữ liệu ..........................................................18
1.5.2 Những vấn đề còn tồn tại trong phân cụm dữ liệu ..................................19
1.6 Tổng kết chương ............................................................................................20
iv
CHƯƠNG 2 THUẬT TOÁN PHÂN CỤM ĐỒ THỊ DỮ LIỆU ........................22
2.1 Tổng quan về lý thuyết đồ thị ........................................................................22
2.1.1 Giới thiệu chung ......................................................................................22
2.1.2 Biểu diễn đồ thị trên máy tính .................................................................23
2.2 Mô hình đồ thị dữ liệu ....................................................................................27
2.3 Độ đo trong phân cụm đồ thị dữ liệu .............................................................28
2.3.1 Độ đo cho phân cụm dữ liệu nói chung ...................................................28
2.3.2 Độ đo cho phân cụm đồ thị ......................................................................30
2.4 Một số thuật toán phân cụm dữ liệu dựa trên đồ thị ......................................31
2.4.1 Thuật toán CHAMELEON ......................................................................31
2.4.2 Thuật toán phân cụm quang phổ ..............................................................33
2.4.3 Thuật toán phân cụm phân cấp ................................................................35
2.5 Kết luận chương .............................................................................................46
CHƯƠNG 3. ỨNG DỤNG THUẬT TOÁN ĐỒ THỊ QUANG PHỔ TRONG
VIỆC PHÂN LOẠI KẾT QUẢ HỌC TẬP CỦA HỌC SINH ............................47
3.1 Đặt vấn đề.......................................................................................................47
3.2 Xây dựng chương trình ứng dụng ..................................................................49
3.2.1 Mục đích chương trình ............................................................................49
3.2.2 Cơ sở dữ liệu ............................................................................................49
3.2.3 Các bước thực hiện ..................................................................................49
3.2.4 Môi trường cài đặt ...................................................................................50
3.2.5 Cài đặt ......................................................................................................50
3.3 Các chức năng chính của chương trình ..........................................................51
3.3.1 Chương trình chính ..................................................................................51
3.3.2 Biểu diễn dữ liệu theo đồ thị....................................................................52
3.3.3 Phân cụm dữ liệu đồ thị quang phổ .........................................................52
3.4 Đánh giá hiệu quả của thuật toán phân cụm dữ liệu đồ thị quang phổ ..........54
3.5 Kết luận chương .............................................................................................58
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .............................................................59
TÀI LIỆU THAM KHẢO ......................................................................................61
v
DANH MỤC CÁC TỪ VIẾT TẮT
Từ hoặc
cụm từ
BDCM
CA
Từ tiếng Anh
Binding
data
Từ tiếng Việt
Clustering Phương pháp phân cụm dữ liệu
Methods
có liên kết
Continuous Attribute
Thuộc tính liên tục
Cơ sở dữ liệu
CSDL
Discrette Attribute
Thuộc tính rời rạc
DBM
Density-Based Methods
Phương pháp dựa trên mật độ
GBM
Grid-Based Methods
Phương pháp dựa trên lưới
HM
Hierarchical Methods
Phương pháp phân cấp
DA
MBCM
Model-Based
Clustering Phương pháp dựa trên mô hình
Methods
phân cụm
MC
Markov Clustering
Phân cụm theo mô hình Markov
MST
Minimum Spanning Tree
Cây khung nhỏ nhất
Partitioning Methods
Phương pháp phân họach
Random Walk Algorithm
Thuật toán bước đi ngẫu nhiên
Star Clustering
Phân cụm hình sao
PM
RWA
SC
SCA
Spectral Clustering Algorithm Thuật toán phân cụm quang phổ
SOM
Self-Organizing Map
Mạng tự tổ chức
vi
DANH MỤC BẢNG
Bảng 3.1. Các module chính của chương trình .........................................................51
vii
DANH MỤC CÁC HÌNH ẢNH
Hình 1.1. Ví dụ về phân cụm dữ liệu [7] ....................................................................5
Hình 1.2. Ví dụ phân cụm các đối tượng dựa trên khoảng cách [7] ...........................5
Hình 1.3. Ví dụ phân cụm các đối tượng dựa trên kích cỡ [7] ...................................6
Hình 1.4. Các bước trong quá trình phân cụm ............................................................8
Hình 1.5. Các chiến lược phân cụm phân cấp [11] ...................................................13
Hình 1.6. Cấu trúc phân cụm dữ liệu dựa trên lưới ..................................................14
Hình 2.1. Ví dụ về mô hình đồ thị.............................................................................22
Hình 2.2. Phân loại đồ thị..........................................................................................23
Hình 2.3. Ma trận kề vô hướng (trên) và có hướng (dưới) .......................................25
Hình 2.4. Ma trận trọng số vô hướng (trên) và có hướng (dưới) ..............................26
Hình 2.5. Ma trận liên thuộc vô hướng (trên) và có hướng (dưới) ...........................27
Hình 2.6. Minh họa thuật toán CHAMELEON ........................................................32
Hình 2.7. Nguyên lý chung của AntTree ..................................................................36
Hình 2.8. Kiến trúc khác nhau giữa SOM và SOMTree ...........................................41
Hình 2.9. Phân việc từ cây
treec
old
cho treec ...............................................................44
tree
c
Hình 2.10. Tách subtreex khỏi cây
và đưa vào list .........................................45
Hình 2.11. Tái liên kết subtreex vào treec ................................................................45
old
Hình 3.1. Màn hình chính của chương trình .............................................................51
Hình 3.2. Biểu diễn dữ liệu theo đồ thị .....................................................................52
Hình 3.3. Phân cụm dữ liệu đồ thị quang phổ với dữ liệu vào là dữ liệu kiểm tra ...53
Hình 3.4. Phân cụm dữ liệu đồ thị quang phổ với dữ liệu vào là điểm học sinh ......54
Hình 3.5. Kết quả phân cụm dữ liệu dạng ba cụm Gaussian với 1000 mẫu dữ liệu .55
Hình 3.6. Kết quả phân cụm dữ liệu dạng ba cụm Gaussian với độ lớn lần lượt là 100,
1000, 3000 mẫu dữ liệu .............................................................................................55
Hình 3.7. Kết quả phân cụm dữ liệu dạng hai nửa vầng trăng với kích thước dữ liệu
là ba cụm Gaussian với độ lớn lần lượt là 7500 mẫu dữ liệu ....................................56
Hình 3.8. Kết quả phân cụm dữ liệu dạng hai nửa vầng trăng với hai thuật toán K
mean (trái) và đồ thị quang phổ (phải) ......................................................................56
Hình 3.9. Kết quả phân cụm dữ liệu điểm học sinh với số cụm khác nhau ..............57
1
MỞ ĐẦU
1. Tính khoa học và cấp thiết của đề tài
Phân cụm là một trong những vấn đề cơ bản phổ biến trong các lĩnh vực nhận
dạng mẫu, học máy và khai thác dữ liệu. Hiện tại, trên thực tế có rất nhiều thuật toán
phân cụm được công bố. Tuy nhiên, do không tồn tại một thuật toán phân cụm duy
nhất cho tất cả các loại bộ dữ liệu, những thuật toán phân cụm mới vẫn liên tục được
đề xuất. Kết quả là, người dùng phải chọn thuật toán thích hợp nhất từ nhiều ứng viên
để đạt được kết quả chính xác.
Trong thực tế, việc lựa chọn thuật toán phân cụm dữ liệu phù hợp là rất khó
khăn do người sử dụng thường không có một kiến thức tiên nghiệm về sự đa dạng và
phức tạp của dữ liệu. Để phần nào giảm bớt nhược điểm trên, các thuật toán phân
cụm dựa trên đồ thị được đề xuất do ưu điểm ở khả năng xử lý các bộ dữ liệu đa dạng
và có cấu trúc. Bản chất của các thuật toán này là biểu diễn dữ liệu dựa trên đồ thị và
phân cụm các thành phần theo các thuật toán thiết kế riêng.
Đồ thị là những cấu trúc toán học được sử dụng để đại diện cho mối quan hệ
giữa cặp đối tượng từ một tập hợp xác định. Đồ thị chứa đỉnh (đại diện cho các đối
tượng) và các cạnh nối các đỉnh (đại diện cho mối quan hệ giữa các đối tượng cặp).
Đây là phương pháp cấu trúc dữ liệu quan trọng được sử dụng trong rất nhiều lĩnh
vực như khai thác dữ liệu, xử lý ngôn ngữ tự nhiên, tìm kiếm thông tin và khai thác
thông tin. Trong phân cụm, sự tương đồng giữa các đối tượng được phân cụm có thể
được diễn tả như một đồ thị có trọng số. Trong đó, các đối tượng là các đỉnh và sự
tương đồng là trọng số của các cạnh. Bài toán phân cụm sẽ được đơn giản hóa về bài
toán phân cụm đồ thị mà nhiệm vụ chính là tách các đồ thị phụ dày đặc và kết nối
thưa thớt khỏi nhau dựa trên khái niệm của mật độ nội cụm so với khoảng cách liên
cụm.
Với những lý do trên, tác giả đã chọn đề tài “Phân cụm đồ thị dữ liệu và
ứng dụng” làm đề tài nghiên cứu luận văn tốt nghiệp thạc sĩ chuyên ngành Khoa
học máy tính.
2
2. Mục tiêu, đối tượng và phạm vi nghiên cứu của đề tài
Đề tài nhằm thực hiện các mục tiêu sau:
- Nghiên cứu tổng quan và đánh giá các phương pháp phân cụm, nghiên cứu
sâu về phương pháp phân cụm dữ liệu dựa trên đồ thị.
- Nghiên cứu một số thuật toán của phương pháp phân cụm dựa trên đồ thị
như: Chameleon, phân cụm đồ thị quang phổ (Spectral Clustering), phân cụm phân
cấp theo đồ thị (thuật toán AntTree và SOMTree). Đánh giá các ưu và nhược điểm
của mỗi thuật toán.
- Cài đặt phần mềm thử nghiệm mô phỏng chương trình phân loại kết quả học
tập của học sinh theo thuật toán phân cụm đồ thị quang phổ, đánh giá hiệu quả hoạt
động của thuật toán này.
Chính vì vậy, đối tượng của luận văn là: Các thuật toán phân cụm dữ liệu dựa
trên đồ thị. Luận văn sẽ khảo sát và đánh giá một số ứng dụng thực tế của một số
phương pháp phân cụm dữ liệu dựa trên đồ thị.Tập trung sâu vào cài đặt thử nghiệm
thuật toán phân cụm dựa trên đồ thị quang phổ ứng dụng trong phân tích đánh giá kết
quả học tập của học sinh.
3. Phương pháp luận nghiên cứu
- Phương pháp nghiên cứu lý thuyết: Tổng hợp, nghiên cứu các tài liệu về
phân cụm dữ liệu, tập trung sâu vào các phương pháp, thuật toán phân cụm dữ liệu
bằng đồ thị; Tìm hiểu các kiến thức liên quan.
- Phương pháp nghiên cứu thực nghiệm: Sau khi nghiên cứu lý thuyết,
phát biểu bài toán phân tích đánh giá kết quả học tập của học sinh, đưa ra giải
pháp xử lý; Mô phỏng thử nghiệm chương trình phần mềm; Đánh giá các kết quả
đạt được.
- Phương pháp trao đổi khoa học: Thảo luận, xemina, và trao đổi ý kiến với
các chuyên gia.
4. Nội dung và bố cục của luận văn
Ngoài phần mở đầu trình bày lý do chọn đề tài và phần kết luận trình bày các
kết quả đạt được cũng như hướng phát triển tiếp theo của luận văn này, nội dung
nghiên cứu chính được trình bày trong ba chương như sau:
3
Chương 1: Tổng quan về phân cụm dữ liệu.
- Nghiên cứu về bài toán phân cụm dữ liệu; Giới thiệu một số phương pháp
phân cụm dữ liệu phổ biến như: phân cụm phân hoạch, phân cụm phân cấp, phân cụm
dựa trên mật độ, phân cụm dựa trên lưới, phân cụm dựa trên mô hình, phân cụm có
dữ liệu ràng buộc và đánh giá các ưu và nhược điểm của mỗi phương pháp.
Chương 2: Thuật toán phân cụm đồ thị dữ liệu.
Trình bày phương pháp phân cụm dữ liệu dựa trên đồ thị và một số thuật toán
như: Thuật toán Chameleon, thuật toán phân cụm quang phổ, thuật toán Ant Tree,
thuật toán SOM Tree.
Chương 3: Ứng dụng thuật toán đồ thị quang phổ trong việc phân loại
kết quả học tập của học sinh.
- Phát biểu bài toán, xây dựng chương trình phân loại kết quả học tập của học
sinh theo thuật toán phân cụm dữ liệu quang phổ.
4
CHƯƠNG 1
TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU
1.1 Khái niệm, mục tiêu và các bước cơ bản của phân cụm dữ liệu
1.1.1 Phân cụm dữ liệu là gì?
Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu (Data mining) nhằm
tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩ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 [6], [14].
Phân cụm dữ liệu là sự phân chia một cơ sở dữ liệu lớn thành các nhóm dữ
liệu trong đó các đối tượng tương tự nhau trong một nhóm. Trong mỗi nhóm, một số
chi tiết có thể không quan tâm đến để đổi lấy dữ liệu đơn giản hóa. Hay ta có thể hiểu
“Phân cụm dữ liệu là quá trình tổ chức các đối tượng thành từng nhóm sao cho mỗi
nhóm đều tương tự nhau theo một tính chất nào đó và những đối tượng ở nhóm khác
sẽ không tương tự như nhau” [1].
Như vậy, bản chất của phân cụm dữ liệu là quá trình nhóm một tập các đối
tượng tương tự nhau trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng
một cụm là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương
đồng. Số các cụm dữ liệu được phân ở đây có thể được xác định trước theo kinh
nghiệm hoặc có thể được tự động xác định. Phân cụm dữ liệu là một ví dụ của phương
pháp học không giám sát. Không giống như phân lớp dữ liệu, phân cụm dữ liệu không
đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm
dữ liệu là một cách học bằng quan sát, trong khi phân lớp dữ liệu là học bằng ví
dụ...Ngoài ra phân cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lí cho
các thuật toán khai phá dữ liệu khác như là phân loại và mô tả đặc điểm, có tác dụng
trong việc phát hiện ra các cụm.
Chúng ta có thể thấy điều này với một ví dụ đơn giản như Hình 1.1. Trong
trường hợp này, chúng ta dễ dàng xác định được 4 cụm dựa vào các dữ liệu đã cho;
các tiêu chí “tương tự” để phân cụm trong trường hợp này là khoảng cách: hai hoặc
nhiều đối tượng thuộc nhóm của chúng được “nhóm” theo một khoảng cách nhất
định. Điều này được gọi là phân cụm dựa trên khoảng cách.
Một kiểu khác của phân cụm dữ liệu là phân cụm dữ liệu dựa vào khái niệm:
hai hay nhiều đối tượng thuộc cùng nhóm nếu có một định nghĩa khái niệm chung
5
cho tất cả các đối tượng trong đó. Nói cách khác, đối tượng của nhóm phải phù hợp
với nhau theo các khái niệm miêu tả đã được định nghĩa, không phải theo những biện
pháp đơn giản tương tự.
Hình 1.1. Ví dụ về phân cụm dữ liệu [7]
1.1.2 Các mục tiêu của phân cụm dữ liệu
Mục tiêu của phân cụm dữ liệu là để xác định các nhóm nội tại bên trong một
bộ dữ liệu không có nhãn. Nhưng làm thế nào để quyết định cái gì đã tạo nên một
phân cụm dữ liệu tốt? Ta có thể thấy rằng không có tiêu chuẩn tuyệt đối “tốt nhất”
mà sẽ phải phụ thuộc vào mục đích cuối cùng của phân cụm dữ liệu. Do đó, người sử
dụng phải cung cấp tiêu chuẩn. Theo cách như vậy, kết quả của phân cụm dữ liệu sẽ
phù hợp với nhu cầu của họ cần.
Hình 1.2. Ví dụ phân cụm các đối tượng dựa trên khoảng cách [7]
Ví dụ, chúng ta có thể quan tâm đến việc tìm kiếm đối tượng đại diện cho các
nhóm đồng nhất trong “các cụm tự nhiên” và mô tả thuộc tính không biết của chúng
trong việc tìm kiếm các nhóm hữu ích và phù hợp hoặc trong việc tìm kiếm các đối
tượng bất thường trong dữ liệu (cá biệt, ngoại lệ, nhiễu) [1].
6
Một vấn đề thường gặp trong phân cụm là hầu hết các dữ liệu cần cho phân
cụm đều có chứa dữ liệu nhiễu do quá trình thu thập thiếu chính xác hoặc thiếu đầy
đủ. Vì vậy, cần phải xây dựng chiến lược cho bước tiền xử lí dữ liệu nhằm khắc phục
hoặc loại bỏ nhiễu trước khi chuyển sang giai đoạn phân tích cụm dữ liệu. Nhiễu ở
đây được hiểu là các đối tượng dữ liệu không chính xác, không tường minh hoặc là
các đối tượng dữ liệu khuyết thiếu thông tin về một số thuộc tính... Một trong các kỹ
thuật xử lí nhiễu phổ biến là việc thay thế giá trị các thuộc tính của đối tượng nhiễu
bằng giá trị thuộc tính tương ứng. Ngoài ra, dò tìm đối tượng ngoại lai cũng là một
trong những hướng nghiên cứu quan trọng trong phân cụm, chức năng của nó là xác
định một nhóm nhỏ các đối tượng dữ liệu khác thường so với các dữ liệu trong cơ sở
dữ liệu, tức là các đối tượng dữ liệu không tuân theo các hành vi hoặc mô hình dữ
liệu nhằm tránh sự ảnh hưởng của chúng tới quá trình và kết quả của phân cụm.
Hình 1.3. Ví dụ phân cụm các đối tượng dựa trên kích cỡ [7]
Theo các nghiên cứu đến thời điểm hiện nay thì 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 cơ sở
dữ liệu. Hơn nữa, đối với các phương pháp phân cụm cần có cách thức biểu diễn cấu
trúc của cơ sở dữ liệu, với mỗi cách thức biểu diễn khác nhau sẽ có tương ứng một
thuật toán phân cụm phù hợp. Vì vậy phân cụm dữ liệu vẫn đang là một vấn đề khó
và mở, vì phải giải quyết nhiều vấn đề cơ bản một cách trọn vẹn và phù hợp với nhiều
dạng dữ liệu khác nhau, đặc biệt là đối với dữ liệu hỗn hợp đang ngày càng tăng trong
7
các hệ quản trị dữ liệu và đây cũng là một trong những thách thức lớn trong lĩnh vực
khai phá dữ liệu [3].
1.1.3 Các bước cơ bản để 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 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 vector đặc trưng. Phải đảm bảo rằng tất cả các vector đặ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 nhận 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 chuyên gia cho rằng
đang ẩn dấu dưới tập dữ liệu. Chẳng hạn, một cụm loại chặt (compact) của các vector
đặc trưng trong không gian ℓ-chiều có thể dễ nhận thấy theo một tiêu chuẩn, trong
khi một cụm loại “dài và mỏng” lại có thể được dễ nhận thấy bởi một tiêu chuẩn khác.
Tiêu chuẩn phân loại có thể được diễn đạt bởi hàm chi phí hay một vài loại quy tắc
khác.
- Thuật toán phân cụm: Cần lựa chọn một sơ đồ thuật toán riêng biệt nhằm
làm sáng tỏ cấu trúc cụm của tập dữ liệu.
- Công nhận kết quả: Khi đã có kết quả phân loại thì ta phải kiểm tra tính đúng
đắn của nó. Điều này thường được thực hiện bởi việc dùng các kiểm định phù hợp.
- Giải thích kết quả: Trong nhiều trường hợp, chuyên gia trong lĩnh vực ứng
dụng phải kết hợp kết quả phân loại với bằng chứng thực nghiệm và phân tích để đưa
ra các kết luận đúng đắn. Trong một số trường hợp, nên có cả bước khuynh hướng
phân cụm; trong bước này có các kiểm định khác nhau để chỉ ra một dữ liệu có hay
không một cấu trúc phân cụm. Ví dụ như tập dữ liệu của ta có thể hoàn toàn ngẫu
nhiên vì vậy mọi cố gắng phân cụm đều vô nghĩa.
Các lựa chọn khác nhau của các đặc trưng, độ đo gần gũi, tiêu chuẩn phân cụm
có thể dẫn tới các kết quả phân cụm khác nhau. Do đó, việc lựa chọn một cách hợp
8
lý nhất hoàn toàn dựa vào kiến thức và kinh nghiệm của chuyên gia. Tính chủ quan
(của chuyên gia) là một thực tế mà ta phải chấp nhận.
Hình 1.4. Các bước trong quá trình phân cụm
1.2 Một số khái niệm cần thiết khi tiếp cận phân cụm dữ liệu
1.2.1 Phân loại các kiểu dữ liệu
Cho một CSDL D chứa n đối tượng trong không gian k chiều trong đó x, y, z là
các đối tượng thuộc D : x =(x1,x2,..,xk ); y =(y1,y2,..,yk); z =(z1,z2,..,zk), trong đó xi, yi, zi
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.
Sau đây là các kiểu dữ liệu:
1.2.1.1Phân loại các kiểu dữ liệu dựa trên kích thước miền
- Thuộc tính liên tục (Continuous Attribute): nếu miền giá trị của nó là vô hạn
không đếm được
- Thuộc tính rời rạc (Discrette Attribute): Nếu miền giá trị của nó là tập hữu
hạn, đếm được
- Lớp các thuộc tính nhị phân: là trường hợp đặc biệt của thuộc tính rời rạc mà
miền giá trị của nó chỉ có 2 phần tử được diễn tả như : Yes / No hoặc Nam/Nữ,
False/true,…
9
1.2.1.2 Phân loại các kiểu dữ liệu dựa trên hệ đo
Giả sử rằng chúng ta có hai đối tượng x, y và các thuộc tính xi, yi tương ứng
với thuộc tính thứ i của chúng. Chúng ta có các lớp kiểu dữ liệu như sau :
- Thuộc tính định danh (Nominal Scale): đây là dạng thuộc tính khái quát hoá
của thuộc tính nhị phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có
nhiều hơn hai phần tử - nghĩa là nếu x và y là hai đối tượng thuộc tính thì chỉ có thể
xác định là x ≠ y hoặc x = y.
- Thuộc tính có thứ tự (Ordinal Scale): là thuộc tính định danh có thêm tính
thứ tự, nhưng chúng không được định lượng. Nếu x và y là hai thuộc tính thứ tự thì
ta có thể xác định là x ≠ y hoặc x = y hoặc x > y hoặc x yi thì ta nói x cách y một khoảng xi - yi tương ứng với thuộc
tính thứ i.
- Thuộc tính tỉ lệ (Ratio Scale): 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, thí dụ như thuộc tính chiều cao hoặc cân nặng lấy
điểm 0 làm mốc. Trong các thuộc tính dữ liệu trình bày ở trên, thuộc tính định danh
và thuộc tính có thứ tự gọi chung là thuộc tính hạng mục (Categorical), thuộc tính
khoảng và thuộc tính tỉ lệ được gọi là thuộc tính số (Numeric).
1.2.2 Độ đo tương tự và phi tương tự
Để phân cụm, người ta phải đ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ự (Similar)
hoặc là tính độ phi tương tự (Dissimilar) giữa các đối tượng dữ liệu.
1.2.2.1 Không gian metric
Các độ đo thường được xác định trong không gian độ đo metric. Một không
gian metric là một tập các phần tử, trong đó có xác định các “khoảng cách” giữa từng
cặp phần tử, với những tính chất thông thường theo khoảng cách hình học. Nghĩa là,
một tập X (các phần tử của nó có thể là những đối tượng bất kỳ) các đối tượng dữ
liệu trong CSDL D như đã đề cập ở trên được gọi là một không gian metric nếu:
10
- Với mỗi cặp phần tử x, y thuộc X đều có xác định, theo một quy tắc nào đó,
một số thực δ(x,y), được gọi là khoảng cách giữa x và y.
- Quy tắc nói trên thoả mãn hệ tính chất sau : δ(x,y) > 0 nếu x ≠ y ; (ii) δ(x,
y)=0 nếu x = y; (iii) δ(x,y) = δ(y,x) với mọi x,y; (iv) δ(x,y) ≤ δ(x,z)+δ(z,y).
Hàm δ(x,y) được gọi là một metric của không gian. Các phần tử của X được
gọi là các điểm của không gian này.
1.2.2.2Thuộc tính khoảng cách
Sau khi chuẩn hoá, độ đo phi tương tự của hai đối tượng dữ liệu x, y được xác
định bằng các metric khoảng cách như sau:
- Khoảng cách Minskowski: Được thể hiện trong (1.1) trong đó q là số tự nhiên
dương.
1/ q
n
q
d x, y xi yi
i 1
(1.1)
- Khoảng cách Euclide : Được thể hiện bởi (1.2), đây là trường hợp đặc biệt
của khoảng cách Minskowski trong trường hợp q=2.
d x, y
n
x y
i 1
i
2
i
(1.2)
- Khoảng cách Manhattan : Thể hiện trong (1.3), đây là trường hợp đặc biệt
của khoảng cách Minskowski trong trường hợp q=1.
n
d x, y xi yi
(1.3)
i 1
- Khoảng cách cực đại : là trường hợp của khoảng cách Minskowski trong
trường hợp q=∞ thể hiện trong (1.4).
d x, y Maxin1 xi yi
(1.4)
1.2.2.3 Thuộc tính định danh
Độ đo phi tương tự giữa hai đối tượng x và y được định nghĩa như sau:
d x, y
pm
p
(1.5)
Trong đó m là số thuộc tính đối sánh tương ứng trùng nhau, và p là tổng số các
thuộc tính.
11
1.2.2.4 Thuộc tính có thứ tự
Giả sử i là thuộc tính thứ tự có Mi giá trị (Mi kích thước miền giá trị): Các trạng
thái Mi được sắp thứ tự như sau : [1…Mi], chúng ta có thể thay thế mỗi giá trị của
thuộc tính bằng giá trị cùng loại ri, với ri ∈{1…Mi}.
Mỗi một thuộc tính có thứ tự có các miền giá trị khác nhau, vì vậy chúng ta
chuyển đổi chúng về cùng miền giá trị [0,1] bằng cách thực hiện phép biến đổi sau
cho mỗi thuộc tính :
j
Zi
ri j 1
M i 1
(1.6)
Sử dụng công thức tính độ phi tương tự của thuộc tính khoảng đối với các giá
trị Zi j , đây cũng chính là độ phi tương tự của thuộc tính có thứ tự.
1.2.2.5 Thuộc tính tỉ lệ
Có nhiều cách khác nhau để tính độ tương tự giữa các thuộc tính tỉ lệ. Một
trong những số đó là sử dụng công thức tính logarit cho mỗi thuộc tính. Hoặc loại bỏ
đơn vị đo của các thuộc tính dữ liệu bằng cách chuẩn hoá chúng, hoặc gán trọng số
cho mỗi thuộc tính giá trị trung bình, độ lệch chuẩn. Với mỗi thuộc tính dữ liệu đã
được gán trọng số tương ứng wi (1 <= i <= k ), độ tương đồng dữ liệu được xác định
như sau :
d x, y
n
w
i 1
i
xi yi
2
(1.7)
1.3 Những kỹ thuật tiếp cận trong phân cụm dữ liệu
Các kỹ thuật phân cụm có rất nhiều cách tiếp cận và các ứng dụng trong thực
tế, nó đều hướng tới hai mục tiêu chung đó là chất lượng của các cụm khám phá được
và tốc độ thực hiện của thuật toán. Hiện nay, các kỹ thuật phân cụm có thể phân loại
theo các phương pháp tiếp cận chính như sau : Phương pháp phân hoạch (Partitioning
Methods); Phương pháp phân cấp (Hierarchical Methods); Phương pháp dựa trên mật
độ (Density-Based Methods); Phương pháp dựa trên lưới (Grid-Based Methods);
Phương pháp dựa trên mô hình phân cụm (Model-Based Clustering Methods) và
Phương pháp phân cụm dữ liệu có liên kết (Binding data Clustering Methods) [8].
- Xem thêm -