ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
PHẠM THỊ THU
CÁC THUẬT TOÁN PHÂN CỤM DỮ DIỆU
VÀ ỨNG DỤNG TRONG PHÂN LOẠI PROTEIN
LUẬN VĂN THAC SĨ KHOA HỌC MÁY TÍNH
Thái Nguyên – 2015
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
PHẠM THỊ THU
CÁC THUẬT TOÁN PHÂN CỤM DỮ DIỆU VÀ
ỨNG DỤNG TRONG PHÂN LOẠI PROTEIN
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01 01
Ngƣời hƣớng dẫn khoa học
PGS.TS. Đoàn Văn Ban
Thái Nguyên - 2015
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
i
LỜI CẢM ƠN
Để hoàn thành chƣơng trình cao học và viết luận văn này, tôi đã nhận
đƣợc sự hƣớng dẫn, giúp đỡ và góp ý nhiệt tình của quý thầy cô trƣờng Đại
học Công nghệ thông tin và Truyền thông. Đặc biệt là những thầy cô ở
Viện công nghệ thông tin Hà Nội đã tận tình dạy bảo cho tôi suốt thời gian
học tập tại trƣờng.
Tôi xin gửi lời cảm ơn sâu sắc đến PGS.TS Đoàn Văn Ban đã dành
nhiều thời gian và tâm huyết hƣớng dẫn tôi hoàn thành luận văn này.
Mặc dù tôi đã có nhiều cố gắng hoàn thiện luận văn bằng tất cả năng
lực của mình, tuy nhiên không thể tránh khỏi những thiếu sót, rất mong
nhận đƣợc sự đóng góp quí báu của quí thầy cô và các bạn.
Tôi xin chân thành cảm ơn!
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
ii
LỜI CAM ĐOAN
Tôi xin cam đoan tất cả các nội dung của luận văn này hoàn toàn
đƣợc hình thành và phát triển từ quan điểm của chính cá nhân tôi, dƣới sự
hƣớng dẫn chỉ bảo của PGS.TS Đoàn Văn Ban. Các số liệu kết quả có đƣợc
trong luận văn tốt nghiệp là hoàn toàn trung thực.
Học viên
Phạm Thị Thu
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
iii
BẢNG KÝ HIỆU CÁC CHỮ VIẾT TẮT
Chữ viết
tắt
KDD
CSDL
Nghĩa tiếng anh
Nghĩa tiếng việt
Kownledge Discovery in
Khám phá tri thức trong cơ sở dữ
Database
liệu
Data base
Cơ sở dữ liệu
Khai phá dữ liệu
KPDL
Clustering Using
Representatives
Phân cụm dữ liệu sử dụng điểm đại
diện
Clustering Large Application
Thuật toán phân cụm ứng dụng lớn
Self-organizing Trees
Cây tự tổ chức
DesoxyriboNucleic Acid
Phân tử nucleic acid mang thông
tin di truyền mã hóa cho hoạt động
sinh trƣởng và phát triển của các
dạng sống
RNA
RiboNucleic Acid
Là một trong hai loại axít nucleic,
là cơ sở di truyền ở cấp độ phân
tử.
rRNA
ribosome RNA
Là ARN mã hóa và mang thông tin
từ AND
tRNA
transfer RNA
Là RNA vận chuyển
mRNA
messenger RNA
RNA thông tin
SCOP
Structural Classification of
Phân loại cấu trúc các protein
Proteins
CATH
Class Architecture Topology
Homologous superfamily
Phân loại cấu trúc protein với
CATH
DDD
Dali Domain Dictionary
Từ điển miền Dali
PDB
Protein Data Bank
Ngân hàng dữ liệu protein
FSSP
Families of Structurally
Similar Proteins
Dòng họ protein với cấu trúc tƣơng
tự
CURE
CLARA
SoT
DNA
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
iv
Trang
Hình 1.1. Ví dụ phân cụm của tập dữ liệu vay nợ thành 3 cụm
6
Hình 1.2. Các chiến lƣợc phân cụm phân cấp
15
Hình 1.3. Một số hình dạng khám phá bởi phân cụm trên mật độ
16
độ
Hình 1.4. Mô hình cấu trúc dữ liệu lƣới
18
Hình 2.1. Các thiết lập để xác định danh giới các cụm ban đầu
25
Hình 2.2. Tính toán trọng tâm của các cụm mới
26
Hình 2.3. Minh họa trực quan quá trình phân cụm
28
Hình 2.4. Phân cụm Chameleon
31
34
35
35
Hình 2.8. Nguyên lý chung của AntTree
37
Hình 2.9. Kiến trúc khác nhau giữa SOM và SoT
40
Hình 2.10. Phân việc từ cây treec cho treec
44
Hình 2.11. Tách subtreex khỏi cây treec và đƣa vào list
44
Hình 2.12. Tái liên kết subtreex vào treec
45
Hình 3.1. Thuyết trung tâm của sinh học phân tử
47
Hình 3.2. Cấu trúc DNA
48
Hình 3.3. Sự phát triển của cấu trúc dữ liệu protein
51
Hình 3.4. Dữ liệu đầu vào của thuật toán
57
Hình 3.5. Giao diện chọn bộ dữ liệu
65
old
old
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
v
Hình 3.6. Thông tin về bộ dữ liệu
66
Hình 3.7. Kết quả phân cụm với số tâm cụm bằng 10
67
Hình 3.8. Kết quả phân cụm bằng SoT với số tâm cụm bằng 10
67
Hình 3.9. Giao diện hiển thị 10 phân cụm trong thuật toán SoT
68
Hình 3.10. Chi tiết phân cụm thứ tám trong thuật toán SoT
68
Hình 3.11. Tập tin kết quả phân cụm clara
69
DANH MỤC BẢNG
Bảng 3.1. Nguồn tài nguyên cho phân loại cấu trúc protein
52
Bảng 3. 2. Các cấp độ chính của CATH
53
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
vi
MỤC LỤC
LỜI CẢM ƠN ......................................................................................................... i
LỜI CAM ĐOAN .................................................................................................. ii
BẢNG KÝ HIỆU CÁC CHỮ VIẾT TẮT ............................................................ iii
........................................................................................ iv
MỞ ĐẦU ................................................................................................................ 1
CHƢƠNG 1. KHAI PHÁ DỮ LIỆU ..................................................................... 3
1.1. Khái niệm chung ......................................................................................... 3
1.2. Phân lớp dữ liệu .......................................................................................... 4
1.3. Phân cụm dữ liệu ......................................................................................... 5
1.3.1. Tổng quan về phân cụm dữ liệu ........................................................... 5
1.3.2. Các yêu cầu cơ bản đối với các kỹ thuật phân cụm dữ liệu ................. 9
1.3.3. Các kiểu dữ liệu trong phân cụm dữ liệu ............................................. 9
1.3.4. Độ đo trong phân cụm dữ liệu............................................................ 11
1.3.5. Các kỹ thuật tiếp cận với bài toán phân cụm ..................................... 13
1.4. Luật kết hợp .............................................................................................. 20
1.4.1. Một số khái niệm cơ sở ...................................................................... 20
............................................. 21
............................................................. 21
1.5. Một số ứng dụng của phân cụm dữ liệu .................................................... 22
1.5.1. Ứng dụng trong tin sinh học .............................................................. 22
1.5.2. Ứng dụng trong phân loại đối tƣợng văn bản .................................... 23
1.5.3. Ứng dụng trong phân đoạn ảnh, nhận dạng ....................................... 23
1.6. Kết luận chƣơng 1 ..................................................................................... 24
CHƢƠNG 2. CÁC THUẬT TOÁN PHÂN CỤM .............................................. 25
2.1. Thuật toán K-means .................................................................................. 25
2.2. Thuật toán CHAMELEON ....................................................................... 29
2.3. Thuật toán CLARA ................................................................................... 32
2.4. Thuật toán CURE ...................................................................................... 33
2.5. Thuật toán AntTree ................................................................................... 37
2.6. Thuật toán cây tự tổ chức SoT .................................................................. 39
2.7. Kết luận chƣơng 2 ..................................................................................... 46
CHƢƠNG 3. CHƢƠNG TRÌNH THỬ NGHIỆM .............................................. 47
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
vii
3.1. Protein và các kỹ thuật phân loại Protein .................................................. 47
3.1.1. Thuyết trung tâm của sinh học phân tử .............................................. 47
3.1.2. Các kỹ thuật phân loại Protein ........................................................... 50
3.2. Cài đặt thử nghiệm thuật toán phân cụm dữ liệu trong phân loại Protein 55
3.2.1. Phát biểu bài toán ............................................................................... 55
3.2.2. Mô tả dữ liệu ...................................................................................... 56
3.2.3. Chuẩn bị dữ liệu ................................................................................. 57
3.2.4. Môi trƣờng cài đặt và thử nghiệm ...................................................... 61
3.3. Nhận xét, đánh giá chƣơng trình thử nghiệm............................................ 70
3.4. Kết luận chƣơng 3 ..................................................................................... 70
KẾT LUẬN VÀ HƢỚNG NGHIÊN CỨU ......................................................... 71
TÀI LIỆU THAM KHẢO .................................................................................... 72
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
1
MỞ ĐẦU
Trong những năm gần đây, cùng với sự phát triển vƣợt bậc của công
nghệ thông tin, khả năng thu thập và lƣu trữ thông tin của các hệ thống
thông tin không ngừng đƣợc nâng cao. Theo đó, lƣợng thông tin đƣợc lƣu
trữ trên các thiết bị nhớ không ngừng tăng lên.
Khai phá dữ liệu là quá trình khám phá các tri thức mới có ích ở
dạng tiềm năng trong nguồn dữ liệu đã có. Quá trình khám phá tri thức là
một chuỗi lặp gồm các bƣớc: làm sạch dữ liệu, tích hợp dữ liệu, chọn lựa
dữ liệu, đánh giá mẫu, biểu diễn tri thức. Khai phá dữ liệu liên quan đến
nhiều lĩnh vực khác nhau nhƣ: công nghệ cơ sở dữ liệu, lý thuyết thống kê,
học máy, khoa học thông tin, trực quan hóa,...
Vấn đề ứng dụng các kỹ thuật khai phá dữ liệu, phân cụm dữ liệu
trong Tin sinh học, một lĩnh vực còn khá mới, đã ra đời, sử dụng các công
nghệ của các ngành toán học ứng dụng, tin học, thống kê, khoa học máy
tính, trí tuệ nhân tạo, hóa học, sinh học để giải quyết các vấn đề của sinh
học. Việc tìm hiểu và nghiên cứu phân loại protein đã nổi lên nhƣ một
hƣớng đi mới với những trải nghiệm hƣớng vào việc khám phá cấu trúc
của các phân tử sinh học.
Nghiên cứu và ứng dụng một cách hiệu quả các phƣơng pháp khai
phá dữ liệu là vấn đề hấp dẫn, đã và đang thu hút sự quan tâm chẳng những
của các nhà nghiên cứu, ứng dụng mà của cả các tổ chức, doanh nghiệp. Do
đó, tôi đã chọn đề tài nghiên cứu “ Các thuật toán phân cụm dữ liệu và
ứng dụng trong phân loại Protein”
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
2
Nội dung của đề tài gồm 3 chƣơng:
Chƣơng 1. Khai phá dữ liệu: Chƣơng này trình bày tổng quan về
khai phá dữ liệu và đi sâu tìm hiểu về phân cụm dữ liệu, các kỹ thuật phân
cụm và một số ứng dụng của phân cụm dữ liệu.
Chƣơng 2. Các thuật toán phân cụm dữ liệu: Trình bày về các thuật
toán điển hình trong phân cụm dữ liệu là: K-Means, Chameleon, Clara,
Cure, AntTree và SoT.
Chƣơng 3. Chƣơng trình thử nghiệm: Để khẳng định cho khả năng
và hiệu quả của một số thuật toán phân cụm dữ liệu đã trình bày ở chƣơng
2. Đó là thuật toán Clara và thuật toán SoT.
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
3
CHƢƠNG 1. KHAI PHÁ DỮ LIỆU
1.1. Khái niệm chung
Cuối thập kỷ 80 của thế kỷ 20, sự phát triển rộng khắp của các CSDL
đã tạo ra sự bùng nổ thông tin trên toàn cầu, vào thời gian này ngƣời ta bắt
đầu đề cập đến khái niệm khủng hoảng trong việc phân tích dữ liệu tác
nghiệp để cung cấp thông tin với yêu cầu chất lƣợng ngày càng cao cho
ngƣời làm quyết định trong các tổ chức chính phủ, tài chính, thƣơng mại,
khoa học, ...
Lƣợng dữ liệu khổng lồ này thực sự là một nguồn tài nguyên có
nhiều giá trị bởi thông tin là yếu tố then chốt phục vụ cho mọi hoạt động
quản lý, kinh doanh, phát triển sản xuất và dịch vụ, ... nó giúp ngƣời điều
hành và quản lý có những hiểu biết về môi trƣờng và tiến trình hoạt động
của tổ chức mình trƣớc khi ra quyết định để tác động đến quá trình hoạt
động nhằm đạt đƣợc các mục tiêu một cách hiệu quả và bền vững.[1]
KPDL là một lĩnh vực mới đƣợc nghiên cứu, nhằm tự động khai thác
thông tin, tri thức mới hữu ích, tiềm ẩn từ những CSDL lớn cho các đơn vị,
tổ chức, doanh nghiệp, ... từ đó làm thúc đẩy khả năng sản xuất, kinh
doanh, cạnh tranh cho các đơn vị, tổ chức này. Các kết quả nghiên cứu
khoa học cùng những ứng dụng thành công trong KDD cho thấy KPDL là
một lĩnh vực phát triển bền vững, mang lại nhiều lợi ích và có nhiều triển
vọng, đồng thời có ƣu thế hơn hẳn so với các công cụ tìm kiếm phân tích
dữ liệu truyền thống. Các kỹ thuật chính đƣợc áp dụng trong lĩnh vực
KPDL phần lớn đƣợc thừa kế từ lĩnh vực CSDL, học máy, trí tuệ nhân tạo,
lý thuyết thông tin, xác suất thống kê và tính toán hiệu năng cao, ...
Nhƣ vậy, ta có thể khái quát hóa khái niệm KPDL là một quá trình
tìm kiếm, phát hiện các tri thức mới, hữu ích, tiềm ẩn trong CSDL lớn.
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
4
KDD là mục tiêu chính của KPDL, do vậy hai khái niệm KPDL và
KDD đƣợc các nhà khoa học trên hai lĩnh vực xem là tƣơng đƣơng với
nhau. Thế nhƣng nếu phân chia một cách chi tiết thì KPDL là một bƣớc
chính trong quá trình KDD.
1.2. Phân lớp dữ liệu
Phân lớp dữ liệu là kỹ thuật dựa trên tập huấn luyện và những giá trị
hay là nhãn của lớp trong một thuộc tính phân lớp và sử dụng nó trong việc
phân lớp dữ liệu mới. Bên cạnh kỹ thuật phân lớp có một hình thức tƣơng
tự là kỹ thuật tiên đoán, kỹ thuật tiên đoán khác với phân lớp ở chỗ phân
lớp chỉ liên quan đến tiên đoán loại lớp của nhãn còn kĩ thuật tiên đoán mô
hình những hàm đánh giá liên tục.
Kỹ thuật phân lớp đƣợc tiến hành bao gồm 2 bƣớc: Xây dựng mô
hình và sử dụng mô hình [1]
+ Xây dựng mô hình: Là mô tả một tập những lớp đƣợc định nghĩa
trƣớc trong đó: mỗi bộ hoặc mẫu đƣợc gán thuộc về một lớp đƣợc định
nghĩa trƣớc nhƣ là đƣợc xác định bởi thuộc tính nhãn lớp, tập hợp của
những bộ đƣợc sử dụng trong việc sử dụng mô hình đƣợc gọi là tập huấn
luyện. Mô hình đƣợc biểu diễn là những luật phân lớp, cây quyết định và
những công thức toán học.
+ Sử dụng mô hình: Việc sử dụng mô hình phục vụ cho mục đích
phân lớp dữ liệu trong tƣơng lai hoặc phân lớp cho những đối tƣợng chƣa
biết đến. Trƣớc khi sử dụng mô hình ngƣời ta thƣờng phải đánh giá tính
chính xác của mô hình, trong đó: nhãn đƣợc biết của mẫu kiểm tra đƣợc so
sánh với kết quả phân lớp của mô hình, độ chính xác là phần trăm của tập
hợp mẫu kiểm tra phân loại đúng bởi mô hình, tập kiểm tra là độc lập với
tập huấn luyện.
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
5
Phân lớp là một hình thức học đƣợc giám sát tức là: tập dữ liệu huấn
luyện (quan sát, thẩm định…) đi đôi với những với những nhãn chỉ định
lớp quan sát những dữ liệu mới đƣợc phân lớp dựa trên tập huấn luyện.
Ngƣợc lại với hình thức học đƣợc giám sát là hình thức học không
đƣợc giám sát lúc đó nhãn lớp của tập dữ liệu huấn luyện là không đƣợc
biết.
1.3. Phân cụm dữ liệu
1.3.1. Tổng quan về phân cụm dữ liệu
Mục đích chính của phân cụm dữ liệu (PCDL) nhằm khám phá cấu
trúc của mỗi dữ liệu để thành lập các nhóm dữ liệu từ tập dữ liệu lớn, theo
đó nó cho phép ngƣời ta đi sâu vào phân tích và nghiên cứu cho từng cụm
dữ liệu này nhằm khám phá và tìm kiếm các thông tin tiềm ẩn, hữu ích
phục vụ cho việc ra quyết định. Ví dụ “Nhóm các khách hàng trong cơ sở
dữ liệu (CSDL) ngân hàng có vốn các đầu tƣ vào bất động sản cao”,… Nhƣ
vậy, PCDL là một phƣơng pháp xử lý thông tin quan trọng và phổ biển, nó
nhằm khám phá mối liên hệ giữa các mẫu dữ liệu bằng cách tổ chức chúng
thành các cụm.
Ta có thể khái quát hóa khái niệm PCDL: PCDL là một kĩ thuật
trong khai phá dữ liệu (KPDL), 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, quan trọng trong tập dữ liệu lớn từ đó cung
cấp thông tin, tri thức hữu ích cho việc ra quyết định. [1]
Nhƣ vậy, PCDL là quá trình phân chia một tập dữ liệu ban đầu thành
các cụm dữ liệu sao cho các phần tử trong một cụm “tƣơng tự” với nhau và
các phần tử trong các cụm khác nhau sẽ “phi tƣơng tự” với nhau. 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 của phƣơng pháp phân cụm.
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
6
Trong PCDL khái niệm hai hoặc nhiều đối tƣợng cùng đƣợc xếp vào
một cụm nếu chúng có chung một định nghĩa về khái niệm hoặc chúng xấp
xỉ với các khái niệm mô tả cho trƣớc.
Trong học máy, PCDL đƣợc xem là vấn đề học không có giám sát,
vì nó phải giải quyết vấn đề tìm một cấu trúc trong tập hợp dữ liệu chƣa
biết trƣớc các thông tin về lớp hay các thông tin về tập huấn luyện. Trong
nhiều trƣờng hợp, nếu phân lớp đƣợc xem là vấn đề học có giám sát thì
PCDL là một bƣớc trong phân lớp dữ liệu, PCDL sẽ khởi tạo các lớp cho
phân lớp bằng cách xác định các nhãn cho các nhóm dữ liệu.
Trong KPDL, ngƣời ta có thể nghiên cứu các phƣơng pháp phân tích
cụm có hiệu quả và hiệu suất cao trong CSDL lớn. Những mục tiêu trƣớc
tiên của nghiên cứu là tập trung vào khả năng mở rộng của các phƣơng
pháp phân cụm, tính hiệu quả của các phƣơng pháp phân cụm với các hình
dạng phức tạp, những kĩ thuật cho phân cụm với nhiều kiểu dữ liệu có kích
cỡ lớn và những phƣơng pháp cho PCDL tƣờng minh và những dữ liệu
dạng số hỗn hợp trong CSDL lớn. PCDL đƣợc sử dụng rộng rãi trong
nhiều ứng dụng, bao gồm nhận dạng mẫu, phân tích dữ liệu, xử lý ảnh,
nghiên cứu thị trƣờng, ...
Hình 1.1. Ví dụ phân cụm của tập dữ liệu vay nợ thành 3 cụm
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
7
Vấn đề thƣờng gặp trong PCDL 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ì 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 bƣớc vào giai đoạn phân
tích PCDL. Ở đây “nhiễu” có thể là các đối tƣợng dữ liệu không chính xác
hoặc 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ủa các
thuộc tính của đối tƣợng “nhiễu” bằng giá trị thuộc tính tƣơng ứng của đối
tƣợng dữ liệu gần nhất.
Ngoài ra, dò tìm phần tử ngoại lai là một trong những hƣớng nghiên
cứu quan trọng trong PCDL, 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 khác trong CSDL tức là đố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 PCDL.
Khám phá các phần tử ngoại lai đã đƣợc phát triển và ứng dụng trong viễn
thông, dò tìm gian lận thƣơng mại, …
Tóm lại, PCDL là một vấn đề khó vì ngƣời ta phải đi giải quyết các
vấn đề con cơ bản nhƣ sau:
- Biểu diễn dữ liệu.
- 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 cụm dữ liệu.
- Xây dựng 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.
Theo các nghiên cứu thì đế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
cụm dữ liệu. Hơn nữa, các phƣơng pháp phân cụm cần có cách thức biểu
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
8
diễn cấu trúc các cụm dữ liệu khác nhau, với mỗi cách thức biểu diễn khác
nhau sẽ có một thuật toán phân cụm phù hợp. PCDL đang là vấn đề mở và
khó vì ngƣời ta cần phải đi giải quyết nhiều vấn đề cơ bản nhƣ đã đề cập ở
trê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 đối tƣợng với dữ liệu hỗn hợp, đang ngày càng tăng trƣởng không
ngừng trong các hệ quản trị dữ liệu, đây cũng là một trong những thách
thức lớn trong lĩnh vực KPDL trong những thập kỷ tiếp theo và đặc biệt
trong lĩnh vực KPDL bằng phƣơng pháp phân cụm dữ liệu.
Phân cụm là chia dữ liệu thành các nhóm mà các đối tƣợng trong
cùng một nhóm thì giống nhau theo một nghĩa nào đó và khác với các đối
tƣợng trong các nhóm khác. Các phần tử tƣơng tự nhau đƣợc phân thành
một cụm (cluster). Mỗi đối tƣợng đƣợc mô tả bởi một tập các độ đo hoặc
bằng mối quan hệ với các đối tƣợng khác. Cũng có rất nhiều định nghĩa về
cụm, nhƣng các định nghĩa sau đây đƣợc sử dụng nhiều nhất:
- "Một cụm là một tập các đối tƣợng giống nhau và khác với các đối
tƣợng không ở trong cụm đó".
- "Một cụm là một tập các điểm trong không gian mà khoảng cách
giữa hai điểm bất kì trong nó luôn nhỏ hơn khoảng cách giữa một điểm bất
kì trong nó và một điểm ngoài".
- "Các cụm có thể đƣợc mô tả nhƣ các miền liên thông trong không
gian đa chiều chứa mật độ tƣơng đối cao các điểm, phân biệt giữa các miền
bằng mật độ khá thấp của các điểm".
Phân cụm có ý nghĩa rất quan trọng trong hoạt động của con ngƣời
từ y tế, giáo dục, xử lý thông tin, nghiên cứu phân tích thị trƣờng,... Phân
cụm đƣợc sử dụng rộng rãi trong nhiều ứng dụng, bao gồm nhận dạng mẫu,
phân tích dữ liệu, xử lý ảnh, nghiên cứu thị trƣờng, phân loại trong tin sinh
học,…
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
9
1.3.2. Các yêu cầu cơ bản đối với các kỹ thuật phân cụm dữ liệu
Phân cụm là một thách thức trong lĩnh vực nghiên cứu ở chỗ 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, sau đây là một số yêu cầu cơ bản của phân cụm dữ
liệu:
- Có khả năng mở rộng
- Khả năng thích nghi với các kiểu thuộc tính khác nhau
- Khám phá các cụm với hình dạng bất kỳ
- Tối thiểu lƣợng tri thức cần cho xác định các tham số đầu
vào
- Khả năng thích nghi với dữ liệu nhiễu
- Ít nhạy cảm với thứ tự của các dữ liệu vào
- Số chiều lớn
- Phân cụm ràng buộc.
- Dễ hiểu và dễ sử dụng
1.3.3. Các kiểu dữ liệu trong phân cụm dữ liệu
Trong phân cụm, các đối tƣợng dữ liệu thƣờng đƣợc biểu diễn 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). 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ó hai đặc trƣng để phân loại: kích
thƣớc miền và hệ đo.
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
10
-
Cho một cơ sở dữ liệu 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: x = (x1, x2,...,xk); y = (yl, y2,...,
yk); z = (zl, 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:
* 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ụ, 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...)
* Loại 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 hóa 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ử. 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 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.
Thuộc tính tỉ lệ: Là thuộc tính khoảng nhƣng đƣợc xác định một
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
11
cách tƣơng đối so với điểm mốc đầy ý nghĩa.
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 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, ...). Dữ liệu không gian có thể là dữ liệu liên tục hoặc rời rạc.
1.3.4. Độ đo trong phân cụm dữ liệu
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 của 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à ngƣời sử dụng phân tích [2]
Tất cả các độ đo dƣới đây đƣợc xác định trong không gian metric.
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 cơ sở dữ liệu 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.
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/