..
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
ĐỖ THỊ PHƢƠNG LAN
ỨNG DỤNG PHƢƠNG SAI TRONG
PHÂN CỤM DỮ LIỆU MỜ
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 Nguyễn Tân Ân
THÁI NGUYÊN
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
i
LỜI CAM ĐOAN
Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm cá nhân,
không sao chép lại của người khác. Trong toàn bộ nội dung luận văn, những điều
được trình bày là của cá nhân hoặc là tổng hợp từ nhiều nguồn tài liệu. Tất cả các
tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp pháp.
Tôi xin chịu trách nhiệm và mọi hình thức kỷ luật theo quy định cho lời
cam đoan của mình.
Thái Nguyên, tháng 10 năm 2013
Tác giả luận văn
Đỗ Thị Phƣơng Lan
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
ii
LỜI CẢM ƠN
Em xin chân thành cảm ơn thầy PGS.TS Nguyễn Tân Ân đã tận tình
hướng dẫn khoa học và chỉ bảo em hoàn thành tốt luận văn tốt nghiệp này.
Em cũng xin bày gửi lời cảm ơn tới các thầy giáo, cô giáo đã chỉ bảo và
truyền đạt kiến thức cho em trong suốt quá trình học tập và nghiên cứu.
Thái Nguyên, tháng 10 năm 2013
Tác giả luận văn
Đỗ Thị Phƣơng Lan
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
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 KÝ HIỆU, CÁC TỪ VIẾT TẮT.................................. v
DANH MỤC CÁC HÌNH .......................................................................... vi
DANH MỤC CÁC BẢNG ........................................................................ vii
CHƢƠNG 1: BÀI TOÁN PHÂN CỤM DỮ LIỆU ..................................... 3
1.1. Khái quát chung ...................................................................................... 3
1.2. Các kiểu dữ liệu và độ đo khoảng cách .................................................... 5
1.2.1. Các kiểu dữ liệu .................................................................................... 5
1.2.2 . Độ đo tương tự và phi tương tự............................................................ 7
1.2.3. Các biến tỷ lệ khoảng cách ................................................................... 9
1.2.4. Các biến nhị phân ............................................................................... 11
1.2.5. Các biến tên, có thứ tự và dựa trên tỷ lệ .............................................. 14
1.2.6 .Các biến có sự pha trộn của các kiểu .................................................. 16
1.3. Các đặc trưng cơ bản để phân cụm dữ liệu ............................................ 18
1.3.1. Các yêu cầu của phân cụm dữ liệu ...................................................... 18
1.3.2. Các đặc trưng cơ bản để phân cụm dữ liệu ......................................... 20
1.4. Những phương pháp tiếp cận trong phân cụm dữ liệu............................ 21
1.4.1. Phương pháp phân cụm phân hoạch.................................................... 21
1.4.2. Phương pháp phân cụm phân cấp ....................................................... 22
1.4.3. Phương pháp phân cụm dựa trên mật độ ............................................. 24
1.4.4. Phương pháp phân cụm dựa trên mô hình ........................................... 25
1.4.5. Phương pháp phân cụm dựa trên lưới ................................................. 25
1.4.6. Phương pháp phân cụm có dữ liệu ràng buộc ..................................... 26
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
iv
1.5. Các ứng dụng của phân cụm dữ liệu ...................................................... 28
1.6. Kết luận ................................................................................................. 28
CHƢƠNG 2: ỨNG DỤNG PHƢƠNG SAI TRONG PHÂN CỤM DỮ
LIỆU MỜ .................................................................................................... 30
2.1. Thuật toán Fuzzy C-Means chuẩn ......................................................... 30
2.2. Thuật toán Fuzzy C-Means cải tiến ....................................................... 34
2.2.1. Cấu trúc khoảng cách ......................................................................... 34
2.2.2. Thuật toán Fuzzy C-Means cải tiến .................................................... 37
2.3. Kết luận ................................................................................................. 51
CHƢƠNG 3: CHƢƠNG TRÌNH THỰC NGHIỆM ................................ 52
3.1. Giới thiệu bài toán ................................................................................. 52
3.2. Thiết kế chương trình ............................................................................ 55
KẾT LUẬN ................................................................................................. 61
TÀI LIỆU THAM KHẢO.......................................................................... 62
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
v
DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT
FCM
: Fuzzy C-Means
CSDL : Cơ sở dữ liệu
PCDL : Phân cụm dữ liệu
KPDL : Khai phá dữ liệu
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
vi
DANH MỤC CÁC HÌNH
Hình 1.1: Ví dụ về phân cụm dữ liệu .............................................................. 3
Hình 1.2: So sánh giữa khoảng cách Euclid và khoảng cách Manhattan ....... 11
Hình 1.3: Các bước trong quá trình phân cụm .............................................. 21
Hình 1.4: các chiến lược phân cụm phân cấp ................................................ 23
Hình 1.5: Các cụm dữ liệu được khám phá bởi Cure .................................... 24
Hình 1.6: Cấu trúc phân cụm dữ liệu dựa trên lưới ....................................... 26
Hình 1.7: Các cách mà các cụm có thể đưa ra............................................... 27
Hình 2.1: Ví dụ thể hiện giới hạn của khoảng cách Euclid trong dựng hình
theo hàm Gaussian........................................................................ 36
Hình 2.2: Phân cụm sử dụng thuật toán FCM chuẩn..................................... 48
Hình 2.3: Phân cụm sử dụng thuật toán FCM cải tiến................................... 48
Hình 2.4: Khoảng cách từ mỗi cụm dữ liệu tới các trung tâm cụm sử dụng khoảng
cách (2.7) trong trường hợp thuật toán FCM chuẩn với tập hợp ba cụm. 48
Hình 2.5: Khoảng cách từ mỗi cụm dữ liệu tới các trung tâm cụm sử dụng
khoảng cách (2.7) trong trường hợp sử dụng thuật toán FCM cải
tiến với tập hợp ba cụm ................................................................ 49
Hình 2.6: Khoảng cách từ mỗi cụm dữ liệu tới các trung tâm cụm sử dụng khoảng
cách (2.7) trong trường hợp thuật toán FCM chuẩn với tập hợp hai cụm 49
Hình 2.7: Khoảng cách từ mỗi cụm dữ liệu tới các trung tâm cụm sử dụng
khoảng cách (2.7) trong trường hợp thuật toán FCM cải tiến với tập
hợp hai cụm .................................................................................. 50
Hình 3.1. Gan trong cơ thể người ................................................................. 52
Hình 3.2: Giao diện khi thực hiện chương trình............................................ 57
Hình 3.3: Chức năng thoát khỏi chương trình ............................................... 58
Hình 3.4: Cập nhật danh sách bệnh nhân ...................................................... 58
Hình 3.5: Thiết lập các thông số đầu vào để phân cụm ................................. 58
Hình 3.6: Quá trình phân cụm ...................................................................... 59
Hình 3.7: Kết quả phân cụm ......................................................................... 59
Hình 3.8: Đưa kết quả bài toán ra giấy ......................................................... 60
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
vii
DANH MỤC CÁC BẢNG
Bảng 1.1: Bảng ngẫu nhiên cho các biến nhị phân........................................ 12
Bảng 1.2: Bảng quan hệ chứa hầu hết các thuộc tính nhị phân ..................... 13
Bảng 2.1: Thuật toán FCM ........................................................................... 34
Bảng 2.2: Bảng thuật toán FCM cải tiến ....................................................... 46
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
1
MỞ ĐẦU
Ngày nay, cùng với sự phát triển của công nghệ thông tin thì lượng
thông tin mà con người có thể thu thập được ngày càng lớn. Trong những
kho dữ liệu khổng lồ ấy đều chứa một kho tàng tri thức quý báu. Con
người đã nhận ra điều đó và từ đó cũng là các phương pháp để khai thác
dữ liệu đã ra đời. Trong khai phá dữ liệu (KPDL), phân cụm dữ liệu
(PCDL) là một kỹ thuật được nghiên cứu mở rộng hiện nay với nhiều khả
năng ứng dụng trong thực tế. Phân cụm các đối tượng để các đối tượng
trong cùng một cụm sẽ nhận được được sự quan tâm giống nhau, chịu
những phương pháp tác động giống nhau. Ví dụ phân cụm các học sinh để
các học sinh trong cùng một cụm sẽ nhận được các phương pháp giáo dục
như nhau. Phân cụm các ngân hàng để các ngân hàng trong cùng một cụm
sẽ nhận được sự đầu tư giống nhau… Như vậy, phân cụm là một việc khó.
Mỗi đối tượng tham gia vào quá trình phân cụm thường được đặc trưng bởi
nhiều thuộc tính. Dựa vào giá trị của các thuộc tính đó, qua những phương
pháp thích hợp, người ta chia các đối tượng này vào các cụm khác nhau sao
cho hai đối tượng trong cùng một cụm phải giống nhau hơn một đối tượng ở
cụm này so với một đối tượng ở cụm khác.
Trong phân cụm việc xác định mức độ giống nhau giữa hai đối
tượng có ảnh hưởng lớn tới chất lượng phân cụm. Trong trường hợp
mỗi đối tượng được biểu diễn bởi nhiều thuộc tính, một số thuộc tính
đó lại là thuộc tính mờ, việc biểu diễn các đối tượng, việc xác định độ
giống nhau giữa các đối tượng rất phức tạp. Khi đó hệ thống phân
cụm phải là hệ thống xử lý các tín hiệu mờ.
Đã có nhiều phương pháp PCDL, tuy nhiên không có phương pháp nào
đủ tổng quát để mang lại hiệu quả tốt nhất cho mọi trường hợp. Do tầm quan
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
2
trọng của phân cụm, hiện nay người ta vẫn đang tìm kiếm các phương pháp
phân cụm mới hoặc cải thiện những phương pháp phân cụm đã có nhằm nâng
cao hiệu quả của phân cụm.
Luận văn trình bày một số vấn đề về PCDL - đây là một trong những
kỹ thuật cơ bản để KPDL. Đây là một hướng nghiên cứu có triển vọng và chỉ
ra những sơ lược trong việc tìm hiểu và khai thác các thông tin hữu ích còn
tiềm ẩn và hiểu được ý nghĩa thực tiễn của dữ liệu.
Trong khuôn khổ của luận văn thạc sỹ, tôi chọn đề tài: “Ứng dụng
phương sai trong phân cụm dữ liệu mờ” nhằm kết hợp giữa việc phân cụm
với lý thuyết xác suất nhằm nâng cao hiệu quả của phân cụm.
Luận văn được trình bày trong 3 chương:
Chƣơng 1: Trình bày tổng quan về bài toán PCDL, các kiểu dữ liệu
và một số kỹ thuật tiếp cận trong PCDL. Qua đó ta thấy đƣợc ứng dụng
của PCDL trong hoạt động đời sống xã hội;
Chƣơng 2: Giới thiệu, phân tích và đánh giá thuật toán Fuzzy CMeans (FCM) chuẩn và thuật toán FCM cải tiến;
Chƣơng 3: Demo chƣơng trình thử nghiệm.
Kết luận: Tóm lược các vấn đề tìm hiểu trong luận văn và các vấn đề
liên quan trong luận văn, đưa ra phương hướng nghiên cứu tiếp theo.
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
3
CHƢƠNG 1:
BÀI TOÁN PHÂN CỤM DỮ LIỆU
1.1. Khái quát chung
Khái niệm về khai phá dữ liệu (Data Mining) hay phát hiện tri thức
(Knowledge Discovery) có rất nhiều cách diễn đạt khác nhau nhưng về bản
chất đó là quá trình tự động trích xuất thông tin có giá trị (thông tin dự
đoán - Predictive Information) ẩn chứa trong khối lượng dữ liệu khổng lồ
trong thực tế[4].
Trong KPDL thì phân cụm là một trong các phương pháp quan trọng
trong quá trình khai thác dữ liệu[2]. Chưa có một khái niệm cụ thể nào về
phân cụm nhưng có thể hiểu rằng phân cụm dữ liệu hay phân cụm, cũng có
thể được gọi là phân tích cụm, phân tích phân đoạn, phân tích phân loại, là
quá trình nhóm một tập các đối tượng tương tự nhau trong một tập dữ liệu vào
với cụm sao cho hai đối tượng cùng một cụm là tương tự nhau hơn một đối
tượng ở cụm này so với một đối tượng ở cụm khác.
PCDL là một ví dụ của phương pháp học không có thầy. Không giống
như việc phân lớp dữ liệu, PCDL 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 PCDL là một cách học bằng quan sát,
trong khi phân lớp dữ liệu là cách học bằng các ví dụ... Ngoài ra PCDL còn có
thể được sử dụng như một bước tiền xử lý cho các thuật toán KPDL 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.
Hình 1.1: Ví dụ về phân cụm dữ liệu
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
4
Phân cụm có ý nghĩa rất quan trọng trong hoạt động của con người.
Trong cuộc sống hằng ngày chúng ta luôn gặp những bài toán phân cụm.
Chẳng hạn như trong ngành bưu điện, hàng ngày bưu điện phải phân loại thư
theo mã nước, trong mã nước lại phân loại theo mã tỉnh/thành phố. Sau đó khi
thư về đến bưu điện tỉnh thì bưu điện tỉnh lại phải phân loại thư theo
quận/huyện để gửi đi, đến bưu điện quận/huyện lại phân loại thư theo
xã/phường để gửi thư. Đó chính là một ứng dụng của bài toán phân cụm dữ
liệu rõ. Nhưng trên thực tế không phải lúc nào bài toán phân cụm dữ liệu rõ
được áp dụng. Ví dụ, theo khảo sát trên thị trường thì những người dùng điện
thoại đắt tiền là những người có tiền, những người dùng điện thoại rẻ tiền là
những người ít tiền. Vậy những người vừa dùng điện thoại nhiều tiền, vừa
dùng điện thoại ít tiền thì là người có nhiều tiền hay ít tiền?! Từ bài toán đó
con người chúng ta đã đưa vào khái niệm bài toán phân cụm dữ liệu mờ.
Phân cụm được sử dụng rộng rãi trong nhiều lĩnh vực như nhận dạng
mẫu, phân tích dữ liệu, xử lý ảnh, nghiên cứu thị trường,... Là một chức năng
trong KPDL, phân tích phân cụm được sử dụng như một công cụ độc lập
chuẩn để quan sát đặc trưng của mỗi cụm thu được bên trong sự phân bố của
dữ liệu và tập trung vào một tập riêng biệt của các cụm để giúp cho việc phân
tích đạt kết quả.
Một 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 quá nhiều dữ liệu nhiễu do quá trình thu thập thiếu chính
xác hoặc không đầ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ó thể đượ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 thuộc tính, hoặc các phần tử ngoại lai,... 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
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
5
tượng nhiễu bằng giá trị thuộc tính tương ứng. Ngoài ra, dò tìm phần tử 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ó 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 CSDL, 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.
Mục tiêu của phân cụm là xác định được bản chất nhóm trong tập dữ
liệu chưa có nhãn. Nhưng để có thể quyết định được những dữ liệu nào tạo
thành một cụm thì có thể chỉ ra rằng không có chuẩn tuyệt đối “tốt” mà có thể
không phụ thuộc vào kết quả phân cụm. Vì vậy, nó đòi hỏi người sử dụng
phải cung cấp chuẩn này, theo cách mà kết quả phân cụm sẽ đáp ứng yêu cầu.
Theo các nghiên cứu cho thấy thì hiện nay chưa có một phương pháp
phân cụm tổng quát nào có thể giải quyết được trọn vẹn cho tất cả các dạng
cấu trúc có 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 diễn của các loại dữ liệu, với mỗi cách thức biểu diễn khác nhau thì sẽ có
tương ứng một thuật toán phân cụm phù hợp.
Vì vậy PCDL vẫn đang là một vấn đề khó và mờ, vì nó 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 lên trong
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 KPDL.
1.2. Các kiểu dữ liệu và độ đo khoảng cách
1.2.1. Các kiểu dữ liệu
Cho một CSDL D chứa n đối tượng trong không gian n chiều trong đó
x, y, z là các đối tượng thuộc D sao cho 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.
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
6
Để phân loại các kiểu dữ liệu ta có thể:
+ Phân loại dựa trên kích thước miền (Domain Size):
Thuộc tính liên tục: nghĩa là giữa hai giá trị tồn tại vô số giá trị
khác. Ví dụ như các thuộc tính về màu, nhiệt độ hoặc cường độ âm thanh.
Thuộc tính rời rạc: nghĩa là nếu miền giá trị của nó là tập hữu hạn,
đếm được. Ví dụ như các thuộc tính về số thành viên trong một gia đình,…
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
False/True,…
+ Phân loại dựa trên hệ đo(Measurement Scale):
Thuộc tính định danh: đây là dạng thuộc tính khái quát hóa các
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. Ví dụ như thuộc tính nơi sinh của một người.
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ì ta
có thể xác định là x = y hoặc x ≠ y hoặc x > y hoặc x < y. Ví dụ như kết quả
xếp loại đua xe ô tô công thức.
Thuộc tính khoảng: với thuộc tính khoảng, chúng ta 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ì ta nói x cách y một khoảng xi - yi tương
ứng với thuộc tính thứ i. Ví dụ như thuộc tính số kênh trên truyền hình.
Thuộc tính tỷ lệ: là thuộc tính khoảng nhưng được xác định một
cách tương đối so với điểm mốc. Ví dụ như thuộc tính chiều cao và 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 thứ tự gọi chung là thuộc tính hạng mục; thuộc tính khoảng và
thuộc tính tỷ lệ gọi chung là thuộc tính số.
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
7
1.2.2 . Độ đo tương tự và phi tương tự
Ứng với mỗi kiểu dữ liệu thì có một hàm tính độ đo tương tự để xác
định khoảng cách giữa hai phần tử của cùng một kiểu dữ liệu. Và để phân
cụm, người ta phải đi tìm cách thích hợp nào đó để xác định “khoảng cách”
giữa các đối tượng, hay chính là phép đo tương tự dữ liệu. Đây chính là các
hàm để so sánh 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 tính độ phi tương tự
(Dissimilar) giữa các đối tượng dữ liệu. Theo quy ước, giá trị của hàm tính độ
đo tương tự càng lớn thì sự tương đồng giữa các đối tượng càng lớn và ngược
lại. Hàm tính độ đo phi tương tự tỉ lệ nghịch với hàm tính độ đo tương tự.
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 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 của khoảng cách hình học. Bất kỳ
một không gian metric nào cũng là một độ đo nhưng ngược lại thì không đúng.
Độ đo ở đây có thể là tương tự hoặc phi tương tự. Nghĩa là với 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:
+ Với mỗi cặp phần tử i, j thuộc X đều có xác định theo một quy tắc
nào đó, một số thực
, được gọi là khoảng cách giữa x và y.
+ Quy tắc trên thỏa mãn hệ tính các yêu cầu toán học của một hàm
khoảng cách:
d(i,j) ≥ 0 cho biết khoảng cách là một số không âm
d(i,i) = 0 cho biết khoảng cách của một đối tượng tới chính nó thì bằng 0
d(i,j) = d(j,i) cho biết khoảng cách là một hàm đối xứng
d(i,j) ≤ d(i,h) + d(h,j) bất đẳng thức tam giác này cho biết khoảng
cách trực tiếp từ i tới j không lớn hơn khoảng cách đi theo đường vòng qua
bất kỳ một điểm h nào.
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
8
Hàm
được đo bởi sự giống nhau hay độ tương tự nhau giữa c đối
tượng i và j.
Như vậy thì, phép đo trong phân cụm được dùng để đo chất lượng của
phân cụm. Độ tương tự d(i,j) là một số không âm, nó gần bằng 0 khi i, j gần
nhau và sẽ lớn hơn khi chúng khác biệt nhau nhiều hơn. Độ tượng tự có được
bằng các đánh giá chủ quan đơn giản bởi một tập các quan sát viên hay các
chuyên gia trên các đối tượng khác nhau nào đó. Độ tượng tự được tính toán
từ các hệ số tương quan. Cho trước n đối tượng để phân cụm, tương quan giữa
hai biến f và g được định nghĩa trong (1.1), tại đó f và g là các biến mô tả các
đối tượng, mf và mg là các giá trị trung bình của f và g và xif là giá trị của f
cho đối tượng thứ i, xig là giá trị của g cho đối tượng thứ i.
Công thức chuyển đổi (1.2) được dùng để tính hệ số tương tự d(f,g) từ
các hệ số tương quan R(f,g):
Các biến với một tương quan dương cao sẽ ấn định hệ số tương tự gần
bằng 0. Các biến với một tương quan âm mạnh sẽ ấn định hệ số không tương
tự gần bằng 1 (nghĩa là các biến rất khác nhau). Trong nhiều ứng dụng, người
dùng thích dùng công thức chuyển đổi (1.3) hơn, tại đó các biến với tương
quan âm hay dương cao ấn định cùng một giá trị tương đồng cao.
Người dùng có thể sử dụng hệ số không tương đồng s(i,j) thay cho hệ số
không tương đồng. Công thức (1.4) được dùng để chuyển đổi giữa hai hệ số.
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
9
Lưu ý rằng không phải tất cả các biến đều cần trong phép phân tích
cụm. Một biến là vô nghĩa với một phân cụm cho trước thì tính hữu ích sẽ ít
hơn, do vậy nó ẩn đi thông tin hữu ích đã cung cấp bởi các biến khác. Ví dụ,
số điện thoại của một người thường vô ích trong phân cụm người theo mô tả
về họ như tuổi, chiều cao, cân nặng,... Kiểu biến "rác" như vậy nên có trọng
số 0, trừ khi nó được phép phân cụm xử lý.
1.2.3. Các biến tỷ lệ khoảng cách
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 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 của khoảng cách hình
học. Bất kỳ một không gian metric nào cũng là một độ đo nhưng ngược lại thì
không đúng. Độ đo ở đây có thể là tương tự hoặc phi tương tự.
Các phép đo này bao gồm các khoảng cách Euclidean, Mahattan và
Minkowski. Các mẫu điển hình như trọng lượng và chiều cao, sự kết hợp vĩ
độ và kinh độ và nhiệt độ khí hậu. Đơn vị phép đo đã dùng có thể ảnh hưởng
đến phép phân cụm.
Ví dụ, thay đổi các đơn vị đo, như thay đổi từ meter tới inch cho chiều
cao hay từ kilogram tới pound cho trọng lượng, có thể dẫn tới một cấu trúc
phân cụm rất khác biệt.
Nhìn chung, biểu diễn một biến dưới các đơn vị nhỏ hơn sẽ dẫn tới một
phạm vi lớn hơn cho biến đó và do vậy một hiệu ứng lớn hơn trên kết quả cấu
trúc phân cụm. Để tránh sự phụ thuộc vào việc lựa chọn đơn vị đo, dữ liệu
nên được chuẩn hoá. Chuẩn hoá các phép đo cố gắng mang lại cho tất cả các
biến một trọng số như nhau.
Tuy nhiên, trong nhiều ứng dụng người ta có thể cố ý muốn mang tới
trọng số lớn hơn cho một tập các biến nào đó so với các biến khác. Ví dụ, khi
phân cụm các cầu thủ chơi bóng rổ người ta có thể thích mang tới trọng số
hơn cho biến chiều cao.
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
10
Để chuẩn hoá các phép đo, một lựa chọn đó là chuyển đổi các phép đo
gốc sang các biến không đơn vị. Cho trước các phép đo đối với biến f. Điều
này có thể được biểu diễn như sau:
- Tính trung bình độ lệch tuyệt đối sf
với x1f ,..., xnf là n phép đo của f, mf là giá trị trung bình của f, tức là
- Tính phép đo chuẩn hóa, gọi là chỉ số Z (z-score: số đo độ rủi ro)như sau:
Thuận lợi của việc sử dụng độ lệch tuyệt đối trung bình đó là z-scores
của các phần tử ngoại lai không trở nên quá nhỏ, do vậy các phần tử ngoại lai
vẫn dễ nhận thấy. Tuy nhiên lựa chọn việc chuẩn hoá và biểu diễn chuẩn hoá
như thế nào là thuộc về phía người dùng.
Sau khi chuẩn hoá hay không cần chuẩn hoá trong một số ứng dụng nào
đó, ta tính độ tương tự (hay không tươn gtự) giữa các đối tượng. Cho trước các
biến tỷ lệ khoảng cách, dựa trên khoảng cách giữa từng cặp đối tượng. Có một
số tiếp cận để định nghĩa khoảng cách giữa các đối tượng. Phép đo khoảng cách
phổ biến nhất là khoảng cách Euclidean, nó được định nghĩa như sau:
với i = (xi1, xi2,..., xip) và j =(xj1,xj2,...,xjp) là hai đối tượng dữ liệu p chiều.
Trong không gian metric vẫn thường dùng khoảng cách Mahattan:
Cả khoảng cách Euclidean và khoảng cách Mahattan thoả các yêu cầu
toán học của một hàm khoảng cách.
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
11
Khoảng cách Minkowski là tổng quát hoá của cả hai khoảng cách
Euclidean và Mahattan. Nó được định nghĩa như sau:
với q là một số nguyên dương, nó đại diện cho khoảng cách Mahattan
khi q = 1 và Euclidean khi q = 2.
Nếu mỗi biến được ấn định một trọng số theo độ quan trọng nhận biết
của nó, khoảng cách Euclidean được đánh trọng số có thể được tính như sau:
Các trọng số cũng được áp dụng cho khoảng cách Mahattan và
Minkowski.
Dưới đây là ví dụ về việc so sánh giữa khoảng cách Euclid và khoảng
cách Manhattan trong việc tính khoảng cách giữa hai điểm trong hệ tọa độ
Oxy giữa hai điểm P1có tọa độ (x1, y1) và điểm P2 có tọa độ (x2, y2). Các
đường mầu đỏ, xanh lam, vàng biểu diễn khoảng cách Manhattan có cùng độ
dài là 12, trong khi đường mầu xanh lục biểu diễn khoảng cách Euclid với độ
dài 6×√2 ≈ 8.48[12].
Hình 1.2: So sánh giữa khoảng cách Euclid và khoảng cách Manhattan
1.2.4. Các biến nhị phân
Một biến nhị phân chỉ có hai trạng thái 0 hay 1 với 0 là biến vắng mặt 1
là biến có mặt. Cho trước biến hút thuốc mô tả một bệnh nhân, ví dụ: 1 chỉ
rằng bệnh nhân hút thuốc và 0 cho biết bệnh nhân không hút thuốc. Xử lý các
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
12
biến nhị phân giống như các biến tỷ lệ khoảng cách có thể dẫn tới sự sai lệch
các kết quả phân cụm. Bởi vậy, các phương pháp chỉ định cho dữ liệu nhị
phân cần phải tính toán độ tương tự.
Nếu tất cả các biến nhị phân được xem như là có cùng trọng số, ta có
bảng ngẫu nhiên 2 x 2, bảng 1.1, với a là số các biến bằng 1 cho cả hai đối
tượng i và j, b là số các biến bằng 1 cho đối tượng i và 0 cho đối tượng j, c là
số các biến bằng 0 cho đối tượng i và 1 cho đối tượng j, d là số các biến bằng
0 cho cả đối tượng i và j. Tổng số lượng của các biến là p, p = a + b + c + d.
Bảng 1.1: Bảng ngẫu nhiên cho các biến nhị phân
j=0
j=1
Tổng
i=1
b
a
a+b
i=0
d
c
c+d
Tổng
b+d
a+c
p
Một biến nhị phân là đối xứng nếu như cả hai trạng thái của nó có cùng
trị giá và mang cùng trọng số, do vậy không có sự ưu tiên nên kết quả mã hoá
là 0 hay 1. Ví dụ, giới tính có thể là nam hay nữ. Độ tương đồng dựa trên các
biến nhị phân đối xứng được gọi là độ tương đồng bất biến trong đó kết quả
không thay đổi khi một số hay tất cả các biến nhị phân được mã hoá khác
nhau. Đối với các độ đo tương đồng bất biến, hệ số được biết đến nhiều nhất
là hệ số đối sánh đơn giản được định nghĩa trong (1.11).
Một biến nhị phân là không đối xứng nếu như kết quả của các trạng
thái quan trọng không bằng nhau. Ta sẽ mã hoá như sau: kết quả có tầm quan
trọng nhất là 1 (ví dụ dương tính HIV) và những cái còn lại bằng 0 (ví dụ như
âm tính HIV). Độ tương đồng dựa trên các biến đó được gọi là độ tương đồng
không bất biến. Đối với các độ tương đồng không bất biến, hệ số được biết
Số hóa bởi trung tâm học liệu
http://www.lrc-tnu.edu.vn/
- Xem thêm -