Luận văn Nghiên cứu các kỹ thuật phân cụm dữ liệu và ứng dụng
i
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
===================
Nguyễn Thị Huế
NGHIÊN CỨU CÁC KỸ THUẬT PHÂN CỤM DỮ LIỆU
VÀ ỨNG DỤNG
LUẬN VĂN THẠC SỸ
HÀ NỘI - 2011
ii
LỜI CẢM ƠN
Để hoàn thành được luận văn này, trước hết tôi xin gửi lời cảm ơn sâu sắc nhất
tới GS.TS Vũ Đức Thi, Viện trưởng Viện công nghệ thông tin đã tận tình hướng
dẫn, chỉ bảo, định hướng, đóng góp những ý kiến quý báu trong suốt quá trình tôi
thực hiện luận văn.
Tôi xin chân thành cảm ơn các thầy, cô giáo trong Bộ môn Hệ thống thông tin,
Khoa Công nghệ thông tin, Phòng Đào tạo Sau đại học - Nghiên cứu Khoa học,
Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tạo mọi điều kiện tốt nhất
để tôi hoàn thành khóa học này. Đồng thời, tôi cũng xin cảm ơn gia đình, bạn bè,
những người luôn khuyến khích và giúp đỡ tôi trong mọi hoàn cảnh khó khăn. Tôi
xin cảm ơn cơ quan và các đồng nghiệp đã hết sức tạo điều kiện cho tôi trong suốt
quá trình học tập và làm luận văn này.
Hà Nội, ngày 10 tháng 04 năm 2011
Học viên
Nguyễn Thị Huế
iii
LỜI CAM ĐOAN
Tôi xin cam đoan những kiến thức trình bày trong luận văn này là do tôi tìm
hiểu, nghiên cứu và trình bày lại theo cách hiểu của tôi. Trong quá trình làm luận
văn tôi có tham khảo các tài liệu có liên quan và đã ghi rõ nguồn tài liệu tham khảo
đó. Phần lớn những kiến thức tôi trình bày trong luận văn này chưa được trình bày
hoàn chỉnh trong bất cứ tài liệu nào.
Hà Nội, ngày 10 tháng 04 năm 2011
Học viên
Nguyễn Thị Huế
iv
MỤC LỤC
MỞ ĐẦU ................................................................................................................1
Chương 1.................................................................................................................3
TỔNG QUAN VỀ KHAI PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU ..................3
1.1. Giới thiệu chung ...........................................................................................3
1.2. Khai phá tri thức và quá trình khai phá tri thức .............................................3
1.2.1. Khai phá tri thức ....................................................................................3
1.2.2. Quá trình khai phá tri thức .....................................................................4
1.3. Khai phá dữ liệu ...........................................................................................5
1.3.1. Khai phá dữ liệu.....................................................................................5
1.3.2. Mục tiêu của khai phá dữ liệu ................................................................6
1.3.3. Quá trình khai phá dữ liệu......................................................................6
1.3.4. Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong khai phá dữ liệu..7
1.3.5. Thách thức – khó khăn trong khai phá tri thức và khai phá dữ liệu.......13
1.3.6. Ứng dụng của khai phá dữ liệu.............................................................13
1.3.7. Kết luận ...............................................................................................14
Chương 2. PHÂN CỤM DỮ LIỆU VÀ CÁC THUẬT TOÁN TRONG ...............15
PHÂN CỤM DỮ LIỆU .........................................................................................15
2.1. Giới thiệu....................................................................................................15
2.2. Các ứng dụng của phân cụm .......................................................................16
2.3. Các yêu cầu về thuật toán phân cụm dữ liệu................................................17
2.4. Các kiểu dữ liệu trong phân cụm.................................................................18
2.5. Phép đo độ tương tự và khoảng cách đối với các kiểu dữ liệu .....................21
2.6. Các hướng tiếp cận của bài toán phân cụm dữ liệu......................................28
2.6.1.
2.6.2.
2.6.3.
2.6.4.
2.6.5.
Phương pháp phân hoạch (Partitioning Methods) ...........................28
Phương pháp phân cấp (Hierarchical Methods) ..............................36
Phương pháp dựa trên mật độ (Density-Based Methods) ................44
Phương pháp dựa trên lưới (Gird-Based Methods)..........................51
Kết luận..........................................................................................56
Chương 3: ỨNG DỤNG........................................................................................58
KẾT LUẬN...........................................................................................................65
TÀI LIỆU THAM KHẢO .....................................................................................66
PHỤ LỤC..............................................................................................................68
v
DANH MỤC CÁC KÝ HIỆU, TỪ VIẾT TẮT
Từ hoặc cụm từ
Cơ sở dữ liệu
Từ viết tắt
Từ tiếng Anh
CSDL
DataBase
Khai phá tri thức trong cơ sở dữ liệu KDD
Knowledge Discovery in
Databases
Khai phá dữ liệu
Phân cụm dữ liệu
Khai phá tri thức
KPDL
PCDL
KPTT
Data Mining
Data Clustering
Knowledge Discovery
vi
DANH MỤC HÌNH VẼ
Hình 1.2: Quá trình khai phá tri thức .....................................................................4
Hình 1.3: Qúa trình khai phá dữ liệu.......................................................................7
Hình 2.1: Mô hình về phân cụm dựa trên tiêu chuẩn thu nhập và số nợ.................15
Hình 2.2: Khoảng cách Euclidean........................................................................24
Hình 2.3: Bảng tham số.........................................................................................26
Hình 2.4: Ví dụ quá trình phân hoạch với k=3 ......................................................30
Hình 2.6: Ví dụ về một số hình dạng cụm dữ liệu được khám phá bởi K-means.....32
Hình 2.7: Các chiến lược phân cụm phân cấp .......................................................37
Hình 2.8: Ví dụ về kết quả phân cụm bằng thuật toán BIRCH. ..............................39
Hình 2.9. Khái quát thuật toán CURE ...................................................................41
Hình 2.10. Các cụm dữ liệu được khám phá bởi CURE ........................................41
Hình 2.11. Ví dụ thực hiện phân cụm bằng thuật toán CURE ...............................43
Hình 2.12: Các bước thuật toán CHAMELEON ....................................................44
Hình 2.13: Hình dạng các cụm được khám phá bởi DBSCAN ...............................45
Hình 2.14: Mật độ - đến được trực tiếp .................................................................46
Hình 2.15: Mật độ - đến được................................................................................47
Hình 2.16: Mật độ - liên thông ..............................................................................47
Hình 2.17: Cụm và nhiễu.......................................................................................48
Hình 2.18: Mô hình cấu trúc dữ liệu lưới ..............................................................52
Hình 2.19: Mô hình thuật toán STING...................................................................53
Hình 3.1: Kết quả phân cụm với Minpt = 3, Epxilon = 200000000 ......................60
Hình 3.2: Kết quả phân cụm trên dữ liệu thuộc tính và trên bản đồ.......................61
Hình 3.3: Màu của các cụm thể hiện trên bản đồ..................................................61
Hình 3.4: Giao diện chương trình Phân cụm dữ liệu bằng thuật toán DBSCAN ....68
Hình 3.5: Giao diện chương trình sau khi thực hiên phân cụm..............................69
Hình 3.6: Kết quả phân cụm..................................................................................70
1
MỞ ĐẦU
Sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ thông tin
trong các lĩnh vực của đời sống, kinh tế, xã hội trong nhiều năm qua cũng đồng
nghĩa với lượng dữ liệu đã được các cơ quan thu thập và lưu trữ ngày một tích lũy
nhiều lên. Hơn nữa, các công nghệ lưu trữ và phục hồi dữ liệu phát triển một cách
nhanh chóng vì thế cơ sở dữ liệu ở các cơ quan, doanh nghiệp, đơn vị ngày càng
nhiều thông tin tiềm ẩn phong phú và đa dạng. Mặt khác, trong môi trường cạnh
tranh, người ta ngày càng cần có nhiều thông tin với tốc độ nhanh để trợ giúp việc
ra quyết định và ngày càng có nhiều câu hỏi mang tính chất định tính cần phải trả
lời dựa trên một khối lượng dữ liệu khổng lồ đã có. Với những lý do như vậy, các
phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp
ứng được thực tế đã làm phát triển một khuynh hướng kỹ thuật mới đó là Kỹ thuật
khai phá tri thức và khai phá dữ liệu (KDD - Knowledge Discovery and Data
Mining). Khai phá tri thức trong cơ sở dữ liệu có thể được coi như quá trình tìm tri
thức có ích, cần thiết, tiềm ẩn và chưa được biết trước trong cơ sở dữ liệu lớn
(discovery of interesting, implicit, and previously unknown knowledge from large
databases)[5]
Kỹ thuật khai phá tri thức và khai phá dữ liệu đã và đang được nghiên cứu,
ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại Việt Nam kỹ
thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa
vào ứng dụng trong những năm gần đây. Những vấn đề được quan tâm là phân lớp
nhận dạng mẫu, luật kết hợp, phân cụm dữ liệu, phần tử dị biệt,…
Phân cụm cơ sở dữ liệu là một trong những phương pháp quan trọng trong
quá trình tìm kiếm tri thức. Phân cụm là phương pháp học từ quan sát (learning
from obversation) hay còn gọi là học không thầy (unupervised learning or
automatic classfication) trong trí tuệ nhân tạo. Phân cụm đặc biệt hiệu quả khi ta
không biết về thông tin của các cụm, hoặc khi ta quan tâm tới những thuộc tính của
cụm mà chưa biết hoặc biết rất ít về những thông tin đó. Phân cụm được coi như
một công cụ độc lập để xem xét phân bố dữ liệu, làm bước tiền xử lý cho các thuật
toán khác. Việc phân cụm dữ liệu có rất nhiều ứng dụng như trong tiếp thị, sử dụng
đất, bảo hiểm, hoạch định thành phố … Hiện nay, phân cụm dữ liệu là một hướng
được nghiên cứu rất nhiều trong Tin học. Chính vì lý do đó mà em chọn đề tài
“Nghiên cứu các kỹ thuật phân cụm dữ liệu và Ứng dụng” là hướng nghiên cứu
chính cho luận văn của mình.
2
Nội dung chính của luận văn được trình bày trong 3 chương:
Chương 1: Tổng quan về khai phá tri thức và khai phá dữ liệu. Trong
chương này trình bày tổng quan về khai phá tri thức, khai phá dữ liệu; qui trình khai
phá tri thức, khai phá dữ liệu; …
Chương 2: Phân cụm và các kỹ thuật phân cụm. Trong chương này trình bày
tổng quan về phân cụm dữ liệu, một số phương pháp phân cụm dữ liệu 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; trình bày một số giải thuật điển hình của mỗi phương pháp
phân cụm; …
Chương 3: Ứng dụng, triển khai bài toán với giải thuật DBSCAN
Phần kết luận trình bày tóm tắt về các nội dung thực hiện trong luận văn,
đồng thời đưa ra các vấn đề nghiên cứu tiếp cho tương lai. Phần phụ lục trình bày
một số modul chương trình cài đặt bằng thuật toán DBSCAN.
Do thời gian nghiên cứu và trình độ có hạn, luận văn không tránh khỏi những
hạn chế và thiếu sót. Em rất mong nhận được sự chỉ bảo, đóng góp ý kiến của các
thầy thầy/ cô giáo cũng như bạn bè và đồng nghiệp.
Em xin chân thành cảm ơn!
3
Chương 1.
TỔNG QUAN VỀ KHAI PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU
1.1. Giới thiệu chung
Cách mạng khoa học kỹ thuật tạo ra bước nhảy vọt trong tất cả các lĩnh vực
của đời sống kinh tế, xã hội, … Một thành công không thể không kể đến của cuộc
cách mạng này là sự bùng nổ thông tin, khiến cho khối lượng thông tin mà con
người thu thập và lưu trữ ngày một khổng lồ, kích thước của CSDL tăng một cách
nhanh chóng. Trong những CSDL đó tiềm ẩn nhiều rất nhiều tri thức mà con người
chưa khám phá ra được. Đứng trước núi dữ liệu khổng lồ thu thập được, việc khám
phá tri thức và thông tin trở nên rất khó khăn. Chính vì lý do đó nhu cầu tìm kiếm
tri thức trong khối CSDL đã nảy sinh, nhu cầu này ngày một cấp thiết và dẫn tới sự
hình thành của một lĩnh vực mới – lĩnh vực khai phá dữ liệu (Data Mining) hay khai
phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in databases - KDD).
Khai phá tri thức trong cơ sở dữ liệu có thể được coi như quá trình tìm tri
thức có ích, cần thiết, tiềm ẩn và chưa được biết trước trong cơ sở dữ liệu lớn
(discovery of interesting, implicit, and previously unknown knowledge from large
databases)
Tuy mới ra đời nhưng khai phá tri thức và khai phá dữ liệu đã và đang được
nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại
Việt Nam kỹ thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu
và dần đưa vào ứng dụng trong những năm gần đây. Những vấn đề được quan tâm
là phân lớp nhận dạng mẫu, luật kết hợp, phân cụm dữ liệu, phần tử dị biệt,…
1.2. Khai phá tri thức và quá trình khai phá tri thức
1.2.1. Khai phá tri thức
Khai phá hay phát hiện tri thức trong các cơ sở dữ liệu là một quy trình nhận
biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: Phân tích, tổng hợp,
hợp thức, khả ích, và có thể hiểu được. Còn khám phá dữ liệu là một bước trong qui
trình khám phá tri thức gồm có các thuật toán khai thác dữ liệu chuyên dùng dưới
một số qui định về hiệu quả tính toán chấp nhận được để tìm ra các mẫu hoặc các
4
mô hình trong dữ liệu. Nói một cách khác, mục đích của phát hiện tri thức và khai
phá dữ liệu chính là tìm ra các mẫu và/hoặc các mô hình đang tồn tại trong các cơ
sở dữ liệu nhưng nhưng vẫn còn bị che khuất bởi hàng núi dữ liệu.
1.2.2. Quá trình khai phá tri thức
Việc khai phá tri thức thông thường có thể mô tả bằng sơ đồ các quy trình
sau [4]:
Hình 1.2: Quá trình khai phá tri thức
Trong đó, mỗi bước là một quy trình có vai trò riêng và nhiệm vụ khác nhau,
bao gồm:
Bước thứ nhất: tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bước này
sẽ quyết định cho việc rút ra được các tri thức hữu ích và cho phép chọn các phương
pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và bản chất của dữ liệu.
Bước thứ hai: thu thập và xử lý dữ liệu thô, còn được gọi là tiền xử lý dữ liệu
nhằm loại bỏ nhiễu, xử lý việc thiếu dữ liệu, biến đổi dữ liệu và rút gọn dữ liệu nếu
cần thiết, bước này thường chiếm nhiều thời gian nhất trong toàn bộ quy trình khai
phá tri thức.
Bước thứ ba: khai phá dữ liệu, hay nói cách khác là trích ra các mẫu hoặc/và
các mô hình ẩn dưới các dữ liệu.
5
Bước thứ tư: hiểu tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và
dự đoán. Các bước trên có thể lặp đi lặp lại một số lần, kết quả thu được có thể
được lấy trung bình trên tất cả các lần thực hiện.
Bước thứ năm: sử dụng tri thức đã được khám phá vào thực tế, các tri thức
phát hiện được tích hợp chặt chẽ trong hệ thống. Tuy nhiên để sử dụng được các tri
thức đó đôi khi cần đến các chuyên gia trong các lĩnh vực quan tâm vì tri thức rút ra
có thể chỉ mang tính chất hỗ trợ quyết định hoặc cũng có thể được sử dụng cho một
quá trình khai phá tri thức khác.
Mặc dù được tóm tắt thành năm bước như trên, nhưng thực chất quá trình
xây dựng và thực hiện việc khám phá tri thức không chỉ phải tuân theo các bước cố
định mà các quá trình này còn có thể được lặp đi lặp lại ở một hoặc một số giai
đoạn, lần sau sẽ hoàn thiện hơn lần trước và giai đoạn sau dựa vào kết quả của giai
đoạn trước và cứ tiếp tục như thế sẽ làm cho quá trình khai phá và tìm kiếm dữ liệu
ngày càng hoàn thiện hơn.
1.3. Khai phá dữ liệu
1.3.1. Khai phá dữ liệu
Khai phá dữ liệu là một giai đoạn quan trọng trong quá trình KPTT. Về bản
chất nó là giai đoạn duy nhất tìm ra được thông tin mới. Việc khai phá dữ liệu còn
được coi như là việc khai phá tri thức từ dữ liệu (knowlegde mining from
databases), trích lọc tri thức (knowlegde extraction), phân tích dữ liệu - mẫu (data-
partent analysis), khảo cứu dữ liệu (data archaeology), đào xới, nạo vét dữ liệu
(data dredging).
Khai phá dữ liệu (Data Mining) được định nghĩa là quá trình trích lọc các
thông tin có giá trị ẩn trong lượng lớn dữ liệu được lưu trữ trong các CSDL hoặc
các kho dữ liệu,… Khai phá dữ liệu cũng còn được coi là một quá trình tìm kiếm,
khám phá ở nhiều góc độ để tìm ra các mối tương quan, các mối liên hệ dưới nhiều
góc độ khác nhau nhằm tìm ra các mẫu hay các mô hình tồn tại bên trong cơ sở dữ
liệu đang bị che khuất. Để trích rút các mẫu, mô hình tiềm ẩn có tính “tri thức” ta
phải tìm và áp dụng các phương pháp, kỹ thuật khai phá sao cho các kỹ thuật và
6
phương pháp này phải phù hợp với tính chất, đặc trưng của dữ liệu và mục đích sử
dụng. Tuy khai phá dữ liệu chỉ là một bước trong quá trình khám phá tri thức nhưng
nó lại là bước tiên quyết, quan trọng và ảnh hưởng đến toàn bộ quá trình.
Tóm lại, khai phá dữ liệu là một quá trình tìm kiếm thông tin “tri thức” tiềm
ẩn trong cơ sở dữ liệu lớn, khổng lồ. Vì thế, có thể nói rằng hai thuật ngữ khám phá
tri thức và khai phá dữ liệu là tương đương nếu nói ở khía cạnh tổng quan, còn nếu
xét ở một góc độ chi tiết thì khai phá dữ liệu là một giai đoạn có vai trò quan trọng
trong quá trình khám phá tri thức [3][4][9].
1.3.2. Mục tiêu của khai phá dữ liệu
Qua những nội dung đã trình bày ở trên, ta có thể hiểu một cách sơ lược rằng
khai phá dữ liệu là quá trình tìm kiếm thông tin hữu ích, tiềm ẩn và mang tính dự
báo trong các cơ sở dữ liệu lớn. Việc khai phá dữ liệu nhằm các mục đích chính như sau:
- Khai thác những thông tin tiềm ẩn mang tính dự đoán từ những cơ sở dữ liệu
lớn dựa trên các công cụ khai phá dữ liệu nhằm dự đoán những xu hướng
trong tương lai nhằm giúp các đối tượng cần tri thức khai phá như: các tổ
chức, doanh nghiệp, nhà nghiên cứu, …. để hỗ trợ việc đưa ra những quyết
định kịp thời, được định hướng trên những tri thức được khám phá mang lại;
- Thực hiện phân tích xử lý, tính toán dữ liệu một cách tự động cho mỗi quá
trình xử lý dữ liệu để tìm ra tri thức.
1.3.3. Quá trình khai phá dữ liệu
KPDL là một giai đoạn quan trọng trong quá trình KPTT. Về bản chất, nó là
giai đoạn duy nhất tìm ra được thông tin mới, thông tin tiềm ẩn có trong CSDL chủ
yếu phục vụ cho mô tả và dự đoán. Dự đoán là thực hiện việc suy luận trên dữ liệu
để đưa ra các dự báo nhằm phân tích tập dữ liệu huấn luyện và tạo ra một mô hình
cho phép dự đoán các mẫu, mô hình mới chưa biết. Mô tả dữ là tổng kết hoặc diễn
tả những đặc điểm chung của những thuộc tính dữ liệu trong kho dữ liệu mà con
người có thể hiểu được.
Quá trình KPDL bao gồm các bước như trong hình sau:
7
Hình 1.3: Qúa trình khai phá dữ liệu
. Xác định nhiệm vụ: Xác định chính xác các vấn đề cần giải quyết.
. Xác định các dữ liệu liên quan: Dùng để xây dựng giải pháp.
. Thu thập và tiền xử lý dữ liệu: Thu thập các dữ liệu liên quan và tiền
xử lý chúng sao cho thuật toán KPDL có thể hiểu được. Đây là một
quá trình rất khó khăn, có thể gặp phải rất nhiều các vướng mắc như:
dữ liệu phải được sao ra nhiều bản (nếu được chiết xuất vào các tệp),
quản lý tập các dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình
(nếu mô hình dữ liệu thay đổi), v.v..
. Thuật toán khai phá dữ liệu: Lựa chọn thuật toán KPDL và thực hiện
việc PKDL để tìm được các mẫu có ý nghĩa, các mẫu này được biểu
diễn dưới dạng luật kết hợp, cây quyết định... tương ứng với ý nghĩa
của nó.
1.3.4. Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong khai phá dữ liệu
Vấn đề khai phá dữ liệu có thể được phân chia theo lớp các hướng tiếp cận
chính sau:
1.3.4.1. Phân lớp và dự đoán
Hướng tiếp cận này làm 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 thời. Kỹ thuật này gồm có: phân lớp (classification), hồi quy
(regression)... Là quá trình xếp một đối tượng vào một trong những lớp đã biết
trước (ví dụ: phân lớp các bệnh nhân theo dữ liệu hồ sơ bệnh án, phân lớp vùng địa
lý theo dữ liệu thời tiết...). Đối với hướng tiếp cận này thường sử dụng một số kỹ
8
thuật của học máy như cây quyết định (decision tree), mạng nơron nhân tạo (neural
network),...
1.3.4.2. Phân cụm dữ liệu
Mục tiêu của phương pháp phân cụm dữ liệu là quá trình nhóm các điểm dữ
liệu trong cơ sở dữ liệu thành các cụm sao cho những điểm dữ liệu trong cùng một
cụm có độ tương đồng lớn và những điểm không cùng một cụm có sự tương đồng là
rất nhỏ. Điểm mạnh của phân cụm dữ liệu là đưa ra được những cấu trúc có ích
hoặc những cụm các đối tượng tìm thấy trực tiếp từ dữ liệu mà không cần bất kì một
tri thức cơ sở nào. Giống như cách tiếp cận học máy, phân cụm dữ liệu được hiểu
như là phương pháp “học không có thầy” (unsupervised learning). 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 (learning by observation), trong khi phân lớp dữ liệu là học bằng ví dụ
(learning by example). Trong phương pháp này sẽ không thể biết kết quả các cụm
thu được sẽ như thế nào khi bắt đầu quá trình. Vì vậy, cần có một chuyên gia để
đánh giá các cụm thu được. Phân cụm dữ liệu được sử dụng nhiều trong các ứng
dụng về phân đoạn thị trường, phân đoạn khách hàng, nhận dạng mẫu, phân loại
trang Web… 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.
1.3.4.3. Phân lớp dữ liệu và hồi qui
Mục tiêu của phương pháp phân lớp dữ liệu là dự đoán nhãn lớp cho các mẫu
dữ liệu. Quá trình phân lớp dữ liệu thường gồm 2 bước: xây dựng mô hình và sử
dụng mô hình:
- Bước 1: một mô hình sẽ được xây dựng dựa trên việc phân tích các mẫu dữ
liệu sẵn có. Mỗi mẫu tương ứng với một lớp, được quyết định bởi một thuộc
tính gọi là thuộc tính lớp. Các mẫu dữ liệu này còn được gọi là tập dữ liệu
huấn luyện (training data set). Các nhãn lớp của tập dữ liệu huấn luyện đều
phải được xác định trước khi xây dựng mô hình, vì vậy phương pháp này còn
9
được gọi là học có thầy (supervised learning) khác với phân cụm dữ liệu là
học không có thầy (unsupervised learning).
- Bước 2: sử dụng mô hình để phân lớp dữ liệu. Trước hết phải tính độ chính
xác của mô hình. Nếu độ chính xác là chấp nhận được, mô hình sẽ được sử
dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai. Phương
pháp hồi qui khác với phân lớp dữ liệu ở chỗ, hồi qui dùng để dự đoán về các
giá trị liên tục còn phân lớp dữ liệu thì chỉ dùng để dự đoán về các giá trị rời
rạc.
1.3.4.4. Luật kết hợp
Có rất nhiều kiểu luật có thể được phát hiện từ cơ sở dữ liệu nói chung. Ví dụ
như luật đặc trưng, luật biệt số, luật kết hợp, luật về sự lệch hướng và sự phát triển.
Phương pháp phát hiện luật kết hợp không gian cũng là một phương pháp
quan trọng trong khám phá tri thức. Phương pháp phát hiện luật kết hợp đưa ra
những luật về sự kết hợp giữa một hoặc nhiều thuộc tính đối với một hoặc nhiều
thuộc tính khác. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực kinh
doanh, y học, tin sinh học, giáo dục, viễn thông, tài chính và thị trường chứng
khoán,...
Khái niệm về luật kết hợp được phát biểu diễn như sau: một luật có dạng X
Y (c%) với X và Y là tập các thuộc tính với độ tin cậy là c% được coi là luật kết
hợp nếu có ít nhất c% đối tượng trong cơ sở dữ liệu đang xét thoả mãn: nếu điều
kiện X được thoả mãn thì điều kiện Y cũng thoả mãn.
Ví dụ, luật sau là luật kết hợp: is_a(x, school) close (x, park) (80%). Luật
trên thể hiện là: 80% trường học gần với công viên.
Như vậy, có rất nhiều kiểu thuộc tính có thể tạo thành những luật kết hợp.
Điều này khiến cho trong nhiều trường hợp số luật kết hợp tìm được vượt quá nhu
cầu. Để hạn chế số luật kết hợp tìm được, người ta sử dụng khái niệm hỗ trợ tối
thiểu (minimum support) và độ tin cậy tối thiểu (minimum confidence). Hai
tham số sẽ giúp loại bớt các luật tìm thấy và chỉ để lại những luật thực sự có ích cho
người sử dụng:
1. Hỗ trợ tối thiểu
10
Trong cơ sở dữ liệu lớn, có thể có rất nhiều luật giữa các đối tượng nhưng
phần lớn các luật đó chỉ có thể áp dụng vào một số nhỏ các đối tượng hoặc độ tin
cậy của luật là rất thấp. Chính vì thế mà phần lớn các luật không có ích với người sử
dụng. Ví dụ, người sử dụng có thể không quan tâm nhiều tới mối quan hệ giữa nhà
ở và trường học nếu luật đó chỉ áp dụng cho 5% số nhà ở trong khi người ta muốn ít
nhất luật đó cũng phải được áp dụng cho trên 50% các ngôi nhà. Do đó chúng ta có
thể lọc bỏ những luật kết hợp mà chỉ có thể áp dụng cho % đối tượng trong cơ sở
dữ liệu.
2. Độ tin cậy tối thiểu
Nếu một luật được đưa ra với mức độ tin cậy (độ tin cậy là tỉ lệ số đối tượng
dữ liệu thoả mãn X và thoả mãn Y so với tổng số các đối tượng thoả mãn X) thấp
thì cũng không có ý nghĩa ứng dụng. Ví dụ như luật: số người bị bệnh tim do ăn cá
biển chỉ đúng 1% thì gần như không có ý nghĩa trong y học khi chuẩn đoán nguyên
nhân bị bệnh tim của một bệnh nhân. Do đó, chúng ta sẽ loại bỏ những luật có độ
tin cậy thấp mà chỉ giữ lại luật có độ tin cậy cao tỷ lệ đúng tối thiểu %.
1.3.4.5. Phân tích chuỗi theo thời gian
Cũng tương tự như khai phá dữ liệu bằng luật kết hợp nhưng có thêm tính
thứ tự và tính thời gian. Một luật mô tả mẫu tuần tự có dạng tiêu biểu X -> Y, phản
ánh sự xuất hiện của biến cố X sẽ dẫn đến việc xuất hiện biến cố Y. Hướng tiếp cận
này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán bởi
chúng có tính dự báo cao.
1.3.4.6. Khai phá dữ liệu sử dụng mạng Neural
Mạng Neural là một phương pháp khai phá dữ liệu phát triển dựa trên cấu
trúc toán học với khả năng học trên mô hình hệ thần kinh con người.
Mạng Neural có thể đưa ra ý nghĩa các dữ liệu phức tạp hoặc không chính
xác và có thể được sử dụng để chiết suất các mẫu và phát hiện xu hướng quá phức
tạp mà con người cũng như các kỹ thuật máy tính khác không thể phát hiện được.
Một trong những ưu điểm của mạng Neural là khả năng tạo ra các mô hình
dự đoán do độ chính xác cao, có thể áp dụng cho nhiều các bài toán khác nhau, đáp
ứng được các nhiệm vụ đặt ra của khai phá dữ liệu như: phân lớp, phân nhóm, mô
hình hoá, dự báo…
11
Mẫu chiết suất bằng mạng Neural được thể hiện bằng một trong những nút
đầu của mạng. Mạng Neural sử dụng các hàm số chứ không sử dụng các hàm biểu
tượng để tính mức tích cực của các nút đầu ra và cập nhật các trọng số của nó.
Đặc điểm của mạng Neural là không cần gia công dữ liệu nhiều, trước khi
bắt đầu quá trình học như các kỹ thuật khác. Tuy nhiên, để có thể sử dụng mạng
Neural có hiệu quả cần phải xác định các yếu tố khi thiết kế mạng như:
- Mô hình mạng là gì?
- Mạng cần bao nhiêu nút?
- Số lớp ẩn sử dụng cho mạng là như thế nào?
- Khi nào thì việc học dừng?
Ngoài ra còn có nhiều bước quan trọng cần phải làm để tiền xử lý dữ liệu
trước khi đưa vào mạng Neural để mạng có thể hiểu được.
Mạng Neural được đóng gói với những thông tin trợ giúp của các chuyên gia
đáng tin cậy và được họ đảm bảo các mô hình này làm việt tốt. Sau khi học, mạng
có thể được coi là một chuyên gia trong lĩnh vực thông tin mà nó vừa được học.
1.3.4.7. Khai phá dữ liệu sử dụng thuật giải di truyền
Đây là phương pháp không chỉ thực hiện phát hiện tri thức mà còn phục vụ
rất nhiều bài toán khác. Tư tưởng của thuật toán là áp dụng quy luật của sự chọn lọc
tự nhiên. Người ta mô phỏng tập dữ liệu ban đầu bằng ký tự nhị phân và gọi là
những quần thể xuất phát. Bằng các thao tác lai ghép, đột biến nhằm biến đổi quần
thể gene ban đầu và loại đi một số gene, làm cho số lượng gene trong quần thể là
không thay đổi. Một hàm thích nghi được xây dựng để xác định mức độ thích nghi
ngày càng cao. Về mặt lý thuyết giải thuật di truyền cho lời giải tối ưu toàn cục
(khác với phương pháp mạng Neural). Tuy nhiên, người ta cũng hạn chế lời giải với
một mức độ thích nghi nào đó để hạn chế số lượng các bước xây dựng quần thể.
Nói theo nghĩa rộng, giải thuật di truyền mô phỏng lại hệ thống tiến hoá
trong tự nhiên, chính xác hơn là giải thuật chỉ ra tập các cá thể được hình thành,
được ước lượng và biến đổi như thế nào. Ví dụ như xác định xem làm thế nào để
lựa chọn các cá thể tạo giống và lựa chọn các cá thể nào để loại bỏ.
12
Giải thuật di truyền là một giải thuật tối ưu hoá, được sử dụng rất rộng rãi
trong việc tối ưu hoá các kỹ thuật khai phá dữ liệu trong đó có kỹ thuật mạng
Neural. Sự kết hợp của nó với các giải thuật khai phá dữ liệu ở chỗ tối ưu hoá là cần
thiết để xác định các giá trị tham số nào tạo ra các luật tốt nhất.
1.3.4.8. Khai phá dữ liệu sử dụng cây quyết định
Phân lớp khai phá dữ liệu luật là cách tiếp cận quan trọng trong quá trình
khai phá dữ liệu, với mục tiêu nhằm tạo ra một tập luật tương đối nhỏ có độ đúng
đắn cao từ cơ sở dữ liệu lớn. Cây quyết định được cọi là phương pháp tiếp cận
truyền thống cho phép phân lớp luật [10]. Cây quyết định đưa ra cách tiếp cận
heuristic nhằm tìm kiếm các thuộc tính tốt nhất và dẫn đến kết quả cao nhất. Tuy
nhiên, cây quyết định có một số hạn chế khi triển khai lựa chọn thuộc tính khi xây
dựng cây.
Hạn chế của cây quyết định là các trường hợp phân rã và tái tạo, vấn đề khi
phân rã là khi cây quyết định cần phân chia dữ liệu nhiều lần để có thể nhận biết
được toàn bộ dữ liệu mẫu. Vấn đề khi tái tạo là một cây con cần được xây dựng lại
nhiều lần làm cho cây quyết định có độ sâu quá lớn và khó hiểu.
Cây quyết định là một mô tả tri thức dạng đơn giản nhằm phân các đối tượng
dữ liệu thành một số lớp nhất định. Các nút của cây được gán nhãn là tên của các
thuộc tính, các cạnh được gán các giá trị có thể của các thuộc tính, các lá mô tả các
lớp khác nhau. Các đối tượng được phân lớp theo các đường đi trên cây, qua các
cạnh tương ứng với giá trị của thuộc tính của đối tượng tới lá.
Quá trình xây dựng cây quyết định là quá trình phát hiện ra các luật phân
chia dữ liệu đã cho thành các lớp đã được định nghĩa. Trong thực tế, tập các cây
quyết định có thể có đối với bài toán này rất lớn và rất khó có thể duyệt hết một
cách tường tận.
Có nhiều phương pháp xây dựng cây quyết định khi khai phá dữ liệu, đó là
các phương pháp sử dụng các thuật toán CLS, ID3, C4.5,… và một phương pháp
tương đối tiên tiến hiện nay và đang là tâm điểm được nghiên cứu là phương pháp
xây dựng cây quyết định dựa trên phụ thuộc hàm.
13
1.3.5. Thách thức – khó khăn trong khai phá tri thức và khai phá dữ liệu
KPTT và KPDL liên quan đến nhiều ngành, nhiều lĩnh vực trong thực tế, vì
vậy các thách thức và khó khăn ngày càng nhiều, càng lớn. Một số các thách thức
và khó khăn cần được quan tâm:
Các cơ sở dữ liệu lớn, các tập dữ liệu cần xử lý có kích thước rất lớn, trong
thực tế, kích thước của các tập dữ liệu thường ở mức tera-byte (hàng ngàn giga-
byte).
- Mức độ nhiễu cao hoặc dữ liệu bị thiếu
- Số chiều lớn
- Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện không
còn phù hợp
- Quan hệ giữa các trường phức tạp
1.3.6. Ứng dụng của khai phá dữ liệu
Các kỹ thuật KDD có thể được áp dụng vào trong nhiều lĩnh vực, điển hình:
Thông tin thương mại:
o Phân tích dữ liệu tiếp thị và bán hàng và thị trường;
o Phân tích vốn đầu tư;
o Quyết định cho vay vốn;
o Phát hiện gian lận;
o v.v..
Thông tin sản xuất:
o Điều khiển và lập lịch;
o Hệ thống quản lý;
o Quản trị mạng;
o Phân tích kết quả thí nghiệm;
o V.v ...
Thông tin khoa học:
o Dự báo thời tiết;
o CSDL sinh học;
14
o Khoa học địa lý: tìm động đất; v.v..
Thông tin cá nhân
V.v…
1.3.7. Kết luận
Khai phá dữ liệu là lĩnh vực đã và đang trở thành một trong những hướng
nghiên cứu thu hút được sự quan tâm của nhiều chuyên gia về CNTT trên thế giới
và được ứng dụng trong nhiều lĩnh vực khác nhau. Tại Việt Nam kỹ thuật này còn
tương đối mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng.
Trong những năm gần đây, rất nhiều các phương pháp và thuật toán mới liên tục
được công bố. Điều này chứng tỏ những ưu thế, lợi ích và khả năng ứng dụng thực
tế to lớn của khai phá dữ liệu. Trong chương này đã trình bày một cách tổng quan
về khai phá tri thức và khai phá dữ liệu.
15
Chương 2. PHÂN CỤM DỮ LIỆU VÀ CÁC THUẬT TOÁN TRONG
PHÂN CỤM DỮ LIỆU
2.1. Giới thiệu
Phân cụm là quá trình nhóm các điểm dữ liệu trong cơ sở dữ liệu thành các
cụm sao cho những điểm dữ liệu trong cùng một cụm có độ tương đồng lớn và
những điểm không cùng một cụm có sự tương đồng là rất nhỏ. Một cụm các đối
tượng dữ liệu có thể xem như là một nhóm trong nhiều ứng dụng, ví dụ: mô hình về
phân cụm các trường dựa trên tiêu chuẩn về thu nhập và số nợ. Cụm 1 là cụm
những người thu nhập cao, số nợ nhiều. Cụm 2 gồm những người thu nhập cao
nhưng nợ ít. Cụm 3 gồm những đối tượng thu nhập ít nhưng nợ nhiều.
Hình 2.1: Mô hình về phân cụm dựa trên tiêu chuẩn thu nhập và số nợ
Quá trình phân cụm là quá trình tìm ra các đối tượng trong cơ sở dữ liệu một
cách tự động. Không giống như phân lớp (clasification), phân cụm không cần
những thông tin được xác định trước. Nói cách khác, phân cụm là phương pháp học
từ quan sát (learning from obversation) hay còn gọi là học không thầy
(unsupervised learning or automatic classfication) trong trí tuệ nhân tạo. Phân cụm
đặc biệt hiệu quả khi không biết về thông tin các cụm, hoặc khi ta quan tâm tới các
thuộc tính của cụm mà chưa biết hoặc biết rất ít về các thông tin đó.
Đã có rất nhiều thuật toán cũng như hệ thống được phát triển cho bài toán
phân cụm trong cơ sở dữ liệu lớn. Sự phát triển của lĩnh vực này đã được áp dụng
16
vào nhiều lĩnh vực ứng dụng như xử lý ảnh, nhận dạng, đánh giá kinh doanh…Sự
đa dạng của thuật toán phân cụm là do sự khác nhau của những ứng dụng thực tế
cũng dẫn tới những yêu cầu về dữ liệu khác nhau và đòi hỏi những thuật toán phân
cụm khác nhau.
Một trong những câu hỏi lớn đặt ra trong bài toán phân cụm là đo độ tương
đồng không gian giữa các đối tượng dữ liệu (spatial similarity). Trong dữ liệu
không gian thì độ đo tương đồng được xem như sự quan hệ về vị trí không gian
giữa các đối tượng dữ liệu. Nói cách khác thì hai đối tượng dữ liệu được gọi là
tương đồng nếu “khoảng cách không gian” giữa chúng là nhỏ.
Một trong những phương pháp đo độ tương đồng giữa hai đối tượng là bằng
nghịch đảo của hàm không tương đồng (dissimilarity function). Hàm không tương
đồng, hàm dựa trên những thuộc tính không gian của các đối tượng dữ liệu như: toạ
độ của các đối tượng, độ cao của các đối tượng… Trong nhiều trường hợp thì hàm
không tương đồng được xem như là hàm khoảng cách không gian giữa các đối
tượng như hàm khoảng cách Euclid, hàm khoảng cách Manhattan, hàm khoảng cách
Minkowski…
Bài toán phân cụm là quá trình nhóm một cơ sở dữ liệu thành những nhóm
đối tượng dữ liệu phục vụ cho mục đích cụ thể của từng ứng dụng thực tế. Không
có một thuật toán phân cụm nào là tốt nhất và thích hợp cho tất cả mọi ứng dụng mà
với mỗi ứng dụng khác nhau thì người sử dụng phải lựa chọn ra một thuật toán phân
cụm cụ thể thích ứng với ứng dụng đó. Kết quả đánh giá cho từng thuật toán cũng
phụ thuộc vào những yêu cầu của từng ứng dụng.
2.2. Các ứng dụng của phân cụm
Phân cụm dữ liệu đã và đang được nghiên cứu, ứng dụng trong nhiều lĩnh vực
khác nhau ở các nước trên thế giới, tại Việt Nam kỹ thuật này tương đối còn mới
mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng tại nhiều lĩnh
vực như:
Quy hoạch đô thị: Nhận dạng các nhóm nhà theo kiểu và vị trí địa lí… nhằm
cung cấp thông tin cho quy hoạch đô thị;
17
Nghiên cứu trái đất: Phân cụm để theo dõi các tâm động đất nhằm cung cấp
thông tin cho nhận dạng các vùng nguy hiểm;
Thương mại: Tìm kiếm nhóm các khách hàng quan trọng có đặc trưng tương
đồng và những đặc tả họ từ các bản ghi mua bán trong CSDL mua hàng;
Sinh học: Phân loại các gen với các chức năng tương đồng và thu được các
cấu trúc trong mẫu;
Thư viện: Theo dõi độc giả, sách, dự đoán nhu cầu của độc giả…;
Bảo hiểm: : 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 của khách hàng, phát hiện gian lận tài chính;
WWW: Phân loại tài liệu, phân loại người dùng web.
2.3. Các yêu cầu về thuật toán phân cụm dữ liệu
Theo các nghiên cứu cho thấy hiện này 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 CSDL. Hơn
nữa, 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ác CSDL,
với mỗi cách thức biểu diễn khác nhau sẽ có tương ứng 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à với kho dữ liệu hỗn hợp đang ngày càng tăng và đây cũng là một
trong những thách thức lớn trong lĩnh vực KPDL.
Vậy phân cụm dữ liệu là một thách thức trong lĩnh vực nghiên cứu vì những
ứng dụng tiềm năng của chúng được đưa ra ngay chính trong những yêu cầu đặc
biệt của chúng. Do đặc thù của của cơ sở dữ liệu là lớn, phức tạp, và có dữ liệu
nhiễu nên những thuật toán phân cụm được áp dụng phải thoả mãn những yêu cầu
sau:[4][14]:
Thuật toán phải hiệu quả và thời gian chạy phải là tăng tuyến tính theo kích thước
của dữ liệu
18
Thuật toán phải xử lý và áp dụng được với cơ sở dữ liệu nhiều nhiễu, phức
tạp gồm cả dữ liệu không gian, phi không gian, dữ liệu số, phi số, kiểu nhị
phân, dữ liệu định danh, hạng mục, thích nghi với kiểu dữ liệu hỗn hợp.
Thuật toán phải có khả năng xác định được những cụm với hình dáng bất kỳ
bao gồm cả những cụm có hình dạng lồng nhau, cụm có hình dạng lõm, hình
cầu, hình que…
Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào. Do các giá trị
đầu vào thường ảnh hưởng rất lớn đến thuật toán phân cụm và rất phức tạp
để xác định các giá trị vào thích hợp đối với các CSDL lớn.
Thuật toán phải thực hiện với mọi thứ tự đầu vào dữ liệu. Nói cách khác kết
quả của thuật toán nên độc lập với dữ liệu đầu vào (Cùng một tập dữ liệu, khi
đưa vào xử lý cho thuật toán PCDL với các thứ tự vào của các đối tượng dữ
liệu ở các lần thực hiện khác nhau thì không ảnh hưởng lớn đến kết quả phân
cụm )
Thuật toán không đòi hỏi những tri thức về cơ sở dữ liệu từ người dùng
Thuật toán phải làm việc được với cơ sở dữ liệu chứa nhiều lớp đối tượng dữ
liệu phức tạp và có tính chất khác nhau.
Thuật toán phải thích nghi với dữ liệu đa chiều: Thuật toán có khả năng áp
dụng hiệu quả cho dữ liệu có số khác chiều nhau.
Thuật toán phải dễ hiểu, dễ cài đặt và khả thi: Người sử dụng có thể chờ đợi
những kết quả phân cụm dễ hiểu, dễ lý giải và dễ sử dụng. Nghĩa là, sự phân
cụm có thể cần được giải thích ý nghĩa và ứng dụng rõ ràng. Việc nghiên cứu
cách để một ứng dụng đạt được mục tiêu rất quan trọng có thể gây ảnh
hưởng tới sự lựa trọn các phương pháp phân cụm.
2.4. Các kiểu dữ liệu trong phân cụm
Trong phân cụm, các đối tượng dữ liệu thường được diễn tả dưới dạng các
đặc tính hay còn gọi là thuộc tính ( Khái niệm “các kiểu dữ liệu” và “các kiểu thuộc
tính dữ liệu“ được xem là tương đương với nhau). Các thuộc tính này là các tham số
19
để giải quyết vấn đề phân cụm và sự lựa chọn chúng có tác động đáng kể đến kết
quả phân cụm. Phân loại các kiểu thuộc tính khác nhau là vấn đề cần giải quyết đối
với hầu hết các tập dữ liệu nhằm cung cấp các phương tiện thuận lợi để nhận dạng
sự khác nhau của các phần tử dữ liệu. Các thuật toán phân cụm thường sử dụng một
trong hai cấu trúc dữ liệu sau:
Ma trận dữ liệu (Data matrix, object-by-variable structure): là mảng n
hàng, p cột, trong đó p là số thuộc tính của mỗi đối tượng. Mỗi hàng biểu diễn một
đối tượng, các phần tử trong mỗi hàng chỉ giá trị thuộc tính tương ứng của đối
tượng đó. Mảng được cho như sau:
x
... x1 f ... x1p
11
... ... ... ... ...
xi1 ... xif ... x
ip ..
... ... ... ... ...
xn1 ... xnf ... xnp
Ma trận phi tương tự (Dissimilarity matrix, object-by-object structure): là
mảng n hàng, n cột. Phần tử d(i,j) chứa khoảng cách hay độ khác biệt giữa các đối
tượng i và đối tượng j, d(i,j) là một số không âm, trong đó nếu d(i,j) xấp xỉ 0 thì hai
đối tượng i và j là khá "gần" nhau, nếu d(i,j) càng lớn thì hai đối tượng i, j khá khác
nhau. Do d(i,j) = d(j,i) = 0 nên ta có thể biểu diễn ma trận phi tương tự như sau:
0
d(2,1)
0
d(3,1) d(3,2) 0
... ... ... ... ...
d(n,1) d(n,2) ... ... 0
Phần lớn các thuật toán phân cụm sử dụng cấu trúc ma trận phi tương tự. Do
vậy, nếu dữ liệu cần phân cụm được tổ chức dưới dạng ma trận dữ liệu thì cần biến
đổi về dạng ma trận phi tương tự trước khi tiến hành phân cụm.
Có hai đặc trưng để phân loại: kích thước miền và hệ đo [10].
Cho một CSDL D chứa n đối tượng trong không gian k chiều; x, y, z là các đối
tượng thuộc D:
20
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; như vậy sẽ có các kiểu dữ liệu sau:
1. 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ụ, các thuộc tính mầu,
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 (ví dụ:
các thuộc tính số,…) trường hợp đặc biệt của thuộc tính rời rạc là thuộc tính
nhị phân mà miền giá trị chỉ có hai phân tử (ví dụ: Yes/No, True/False,
On/Off..)
2. Kiểu dữ liệu dựa trên hệ đo
Thuộc tính định danh: Là dạng thuộc tính khái quát hoá của thuộc tính nhị
phân, trong đó có 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ử. 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ự: Là thuộc tính định danh nhưng 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ì
có thể xác định là x ≠ y hoặc x = y hoặc x > y hoặc x< y.
Thuộc tính khoảng: để đo các giá trị theo xấp xỉ tuyến tính, với thuộc tính
khoảng có thể xác định một thuộc tính là đứng trược hoặc đứng sau thuộc
tính khác với một khoảng là bao nhiêu. Nếu xi > yi thì có thể nói x cách y
một khoảng xi - yi tương ứng với thuộc tính thứ i.
Việc lựa chọn đơn vị đo cho các thuộc tính cũng ảnh hưởng đến chất lượng
phân cụm. Nếu đơn vị độ đo của một thuộc tính càng được chia nhỏ, thì khoảng
cách xác định của thuộc tính đó càng lớn và ảnh hưởng nhiều hơn đến kết quả phân
cụm. Để tránh phụ thuộc vào việc lựa chọn đơn vị đo, dữ liệu cần được chuẩn hóa.
Việc chuẩn hóa sẽ gán cho tất cả các thuộc tính một trọng số bằng nhau. Tuy nhiên,
21
trong nhiều trường hợp người sử dụng có thể thay đổi trọng số cho các thuộc tính
ưu tiên.
Để chuẩn hóa các độ đo, một cách làm phổ biến là biến đổi các thuộc tính về
dạng không có đơn vị đo. Giả sử đối với các thuộc tính f, ta thực hiện như sau:
- Tính độ lệch trung bình:
1
Sf ( x1 f mf x2 f mf ... xnf mf )
n
trong đó x1 f ,...xnf là giá trị thuộc tính f của n phần tử dữ liệu, và mf là giá trị trung
1
bình của f, được cho như sau: mf (x1 f x2 f ... xnf )
n
- Độ đo được chuẩn hóa:
xif mf
zif
Sf
Thuộc tính nhị phân là thuộc tính có hai giá trị là 0 và 1.
Thuộc tính 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.
Trong các thuộc tính 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, còn thuộc tính khoảng cách và thuộc tính
tỷ lệ được gọi 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ụ: thông tin về hình học, Quan hệ metric,
Quan hệ hướng, …) 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.
- 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.
2.5. Phép đo độ tương tự và khoảng cách đối với các kiểu dữ liệu
1. Khái niệm tương tự, phi tương tự
22
Khi các đặc tính của dữ liệu được xác định, 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 tương tự có nhiều cách để xác định, chúng
thường được đo bằng khoảng cách giữa các đối tượng. Tất cả các cách đo độ tương
tự đều phụ thuộc vào kiểu thuộc tính mà con người phân tích. Ví dụ, thuộc tính
hạng mục thì không sử dụng độ đo khoảng cách mà sử dụng một hướng hình học
của dữ liệu.
Tất cả các độ đo dưới đây được xác định trong không gian metric. Bất kỳ
một metric nào cũng là một độ đo, nhưng điều ngược lại không đúng. Để tránh sự
nhầm lẫn, thuật ngữ độ đo ở đây đề cập đến hàm tính độ tương tự hoặc hàm tính độ
phi tương tự. Một không gian metric là một tập trong đó có xác định “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 của 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 đề cập ở trên được gọi là một không gian metric nếu:
- Với mỗi cặp phần tử x, y thuộc X đều 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 thỏa mãn hệ tính chất sau:
(i)
δ(x,y) > 0 nếu x ≠ y;
δ(x,y) = 0 nếu x= y ;
(ii)
(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.
2. Thuộc tính khoảng
23
Một thành phần quan trọng trong thuật toán phân cụm là phép đo khoảng
cách giữa hai điểm dữ liệu. Nếu thành phần của vectơ thể hiện dữ liệu thuộc trong
cùng một đơn vị giống nhau thì nó tồn tại khoảng cách Euclidean có thể xác định
được nhóm dữ liệu tương tự. Tuy nhiên, không phải lúc nào khoảng cách Euclidean
cũng cho kết quả chính xác.
Tuy nhiên chú ý rằng đây không phải vấn đề đồ thị: vấn đề phát sinh từ công
thức toán học được sử dụng để kết hợp khoảng cách giữa các thành phần đơn đặc
tính dữ liệu vectơ vào trong một độ đo khoảng duy nhất mà có thể được sử dụng
cho mục đích phân cụm: các công thức khác nhau dẫn tới những cụm khác nhau.
Các thuật toán cần có các phép đo khoảng cách hoặc độ tương tự giữa hai đối
tượng để thực hiện phân cụm. Kiến thức miền phải được sử dụng để để trình bày rõ
ràng phép đo khoảng thích hợp cho mỗi ứng dụng. Hiện nay, phép đo có nhiều mức
độ khách nhau tùy theo từng trường hợp.
Khoảng cách Minkowski được định nghĩa như sau :
n
1/ q
x y q ,q 1;
dist x, y
q
i
i
i1
Trong đó x, y là hai đối tượng với n là số lượng thuộc tính, x (x1, x2 ,..., xn )
và y = (y1, y2 ,..., yn ); dist là kích thước của dữ liệu.
Khoảng cách Euclidean:
n
i 2
distq x, y
x y
;
i
i1
là khoảng cách giữa hai đối tượng trong trường hợp đặc biệt q = 2.
Khoảng cách Manhattan :
n
dist x, y x y ;
q
i
i
i1
là khoảng cách trung bình giữa hai đối tượng trong trường hợp đặc biệt q=1.
Khoảng cách Chebychev :
dist
x, y
maxni1 xi yi ;
24
Trong trường hợp q = ∞, hữu ích để định nghĩa các đối tượng phi tương tự nếu
chúng khác nhau chỉ trong một kích thước biến đổi.
Bình phương khoảng cách Euclidean.
2
n
dist x, y
x y
q
i
i
i1
(1)
Tỉ lệ khác nhau. Giả sử các biến là tuyệt đối.
dist x, y Number x y / i
(2)
i
i
Khoảng cách Euclidean được sử dụng phổ biến nhất để đo độ tương tự của
khoảng cách Minkowski. Giả sử có hai trường hợp C1 và C2 có các biến liên tục x
và y, lấy lần lượt các giá trị (x1, y1) và (x2, y2) tương ứng, có thể vẽ đồ thị hai trường
hợp trong không gian x-y (Hình 2.2) :
y
d12
C2(x2, y2)
C1(x1, y1)
x
Hình 2.2: Khoảng cách Euclidean
Tuy nhiên không có nguyên tắc tổng quát để chọn phép đo áp dụng cho bất
cứ bài toán nào. Một cách đơn giản để đo độ tương tự giữa các nhóm trong khung
tương tự bằng cách thay thế nhóm cho thuộc tính thứ i của đối tượng đo chẳng hạn
như khoảng cách Euclidean, khoảng cách Manhattan, hoặc bình phương
xa1 , xa2 ,...,xan
A
Mahalanobis. Ví dụ, Giả sử rằng nhóm A có vectơ trung bình
và
xb1 , xb2 ,...,xbn
B
nhóm B có vectơ trung bình
, thì cách đo bằng khoảng cách
Euclidean giữa hai nhóm có thể được định nghĩa là:
Tải về để xem bản đầy đủ
101 trang
16/04/2025
100
Bạn đang xem 30 trang mẫu của tài liệu "Luận văn Nghiên cứu các kỹ thuật phân cụm dữ liệu và ứng dụng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- luan_van_nghien_cuu_cac_ky_thuat_phan_cum_du_lieu_va_ung_dun.pdf
