Số hóa bởi trung tâm học liệu

ĐẠ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

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

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

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

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


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

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

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


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


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 C-
Means (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

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

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

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 = (x
1
, x
2
,…, x
k
); y = (y
1
, y
2

,…, y
k
);
z = (z
1
, z
2
,…, z
k
), trong đó x
i
, y
i
, z
i
với i = 1,…, k là các đặc trưng hoặc thuộc
tính tương ứng của các đối tượng x, y, z.

Số hóa bởi trung tâm học liệu

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 x
i
> y
i
thì ta nói x cách y một khoảng x
i
- y
i
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


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

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, m
f
và m
g
là các giá trị trung bình của f và g và x
if
là giá trị của f
cho đối tượng thứ i, x
ig
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

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

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 s
f

với x
1f
, , x
nf
là n phép đo của f, m
f
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 = (x
i1
, x
i2
, , x
ip
) và j =(x
j1
,x
j2
, ,x
jp
) 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


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

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

13
đến nhiều nhất là hệ số Jaccard, được định nghĩa trong (1.12), tại đó các đối
sánh âm d được xem là không quan trọng và do vậy đã bị lờ đi khi tính toán.

Khi cả biến nhị phân đối xứng và không đối xứng xuất hiện trong cùng
tập dữ liệu, tiếp cận các biến pha trộn được mô tả trong mục 1.2.6 có thể được
áp dụng.
Ở bảng 1.1 giả sử rằng một bảng các bản ghi bệnh nhân, bảng 1.2 chứa
các thuộc tính tên, giới tính, sốt, ho, test-1,test-2,test-3 và test-4 (test: xét
nghiệm), với tên là một đối tượng, giới tính là một thuộc tính đối xứng và các
thuộc tính còn lại là không đối xứng.
Bảng 1.2: Bảng quan hệ chứa hầu hết các thuộc tính nhị phân
Tên
Giới tính
Sốt
Ho
Test-1
Test-2
Test-3
Test-4
Đại
M

Y
N
P
N
N
N
Lan
F
Y
N
P
N
P
N
Tuấn
M
Y
P
N
N
N
N









Đối với các giá trị thuộc tính không đối xứng, cho các giá trị Y và P là
1; N là 0. Giả sử rằng khoảng cách giữa các đối tượng (bệnh nhân) được tính
toán dựa trên chỉ các biến không đối xứng. Theo công thức hệ số Jaccard
(1.14), khoảng cách giữa mỗi cặp 3 bệnh nhân: Đại, Lan và Tuấn sẽ là:




Số hóa bởi trung tâm học liệu

14
Các phép đo này cho thấy Tuấn và Lan không có hứa hẹn là có bệnh
giống nhau. Trong 3 bệnh nhân này, Đại và Lan có thể có bệnh giống nhau nhất.
1.2.5. Các biến tên, có thứ tự và dựa trên tỷ lệ
a) Các biến tên:
Biến tên là sự suy rộng của biến nhị phân, trong đó nó có thể mang
nhiều hơn hai trạng thái. Ví dụ, bản đồ màu là một biến tên có thể có 5 trạng
thái: đỏ, vàng, xanh lá cây, hồng và xanh da trời.
Cho số các trạng thái của một biến tên là M. Các trạng thái có thể được
chỉ ra bởi các ký tự, các biểu tượng hay một tập các số nguyên như 1 M. Lưu
ý rằng các số nguyên như thế này chỉ được dùng cho dữ liệu điều khiển và
không đại diện cho bất kỳ một trật tự cụ thể nào.
Độ tương đồng giữa hai đối tượng i và j có thể được tính bằng cách sử
dụng tiếp cận đối sánh đơn giản như trong (1.16):

với m là số lượng các đối sánh (tức là số lượng các biến mà i và j có
cùng trạng thái) và p là tổng số của các biến. Các trọng số có thể được ấn định
để làm tăng hiệu quả của m, hay ấn định trọng số lớn hơn cho các đối sánh
trong các biến có số lượng các trạng thái lớn hơn.
Các biến tên có thể được mã hoá bởi một số lượng lớn các biến nhị

phân không đối xứng bằng cách tạo một biến nhị phân mới cho mỗi trạng thái
tên. Đối với một đối tượng với giá trị trạng thái cho trước, biến nhị phân miêu
tả trạng thái đó đặt là 1, trong khi các biến nhị phân còn lại đặt là 0. Ví dụ, để
mã hoá biến tên bản đồ màu, một biến nhị phân có thể được tạo lập cho từng
màu trong danh sách 5 màu trên. Cho một đối tượng có màu vàng, biến vàng
đặt là 1, trong khi bốn biến còn lại đặt là 0. Hệ số không tương đồng cho dạng
này khi mã hoá được tính như các phương pháp trong mục 1.2.4.

Số hóa bởi trung tâm học liệu

15
b) Các biến có thứ tự:
Biến có thứ tự rời rạc tương tự như một biến tên, loại trừ M trạng thái
của giá trị có thứ tự được sắp xếp theo một trật tự có nghĩa. Các biến có thứ tự
rất hữu ích cho việc thể hiện các đánh giá chất lượng một cách chủ quan, mà
không thể đo được bằng cách khách quan. Một biến có thứ tự liên tục trông
giống như một tập dữ liệu liên tục với một tỷ lệ chưa biết, đó là mối quan hệ
có thứ tự của các giá trị, là yếu tố cần thiết nhưng không phải là tính chất
trọng yếu thực sự của chúng. Ví dụ, sắp xếp quan hệ trong một môn thể thao
đặc thù thường cần thiết hơn các giá trị thực tế của một độ đo đặc thù. Các
biến có thứ tự có thể cũng đạt được từ việc rời rạc hoá các con số tỷ lệ khoảng
cách bằng cách chia phạm vi giá trị vào trong một số các lớp hữu hạn. Các giá
trị của một biến có thứ tự có thể được ánh xạ tới các hạng (rank). Giả sử rằng
một biến có thứ tự f có M
f
trạng thái. Các trạng thái được sắp xếp định nghĩa
có thứ tự là 1 M
f
. Nghiên cứu các biến tên hoàn toàn giống với nghiên cứu
các biến tỷ lệ khoảng cách khi tính toán độ tương đồng giữa các đối tượng.

Giả sử f là một biến trong tập các biến có thứ tự mô tả n đối tượng. Độ không
tương đồng tính toán đối với f bao gồm các bước sau:
 Giá trị của f cho đối tượng thứ i là x
if
và f có M
f
trạng thái đã được sắp
xếp, miêu tả bởi thứ tự 1 M
f
. Thay thế mỗi x
if
bởi hạng (rank) tương
ứng của nó r
if
∈{1 M
f
}.
 Từ đó mỗi một biến có thứ tự có một số lượng các trạng thái khác nhau,
ánh xạ phạm vi của mỗi biến lên trên [0-1] bằng cách thay thế hạng r
if
của đối tượng thứ i trong biến thứ f bởi:
 Tính độ không tương đồng, sử dụng bất kỳ độ đo khoảng cách nào
đã mô tả trong mục 1.2.2, sử dụng z
if
đại diện cho giá trị f cho đối
tượng thứ i.

Số hóa bởi trung tâm học liệu

16

c) Các biến dựa trên tỷ lệ:
Một biến dựa trên tỷ lệ làm một phép đo dương trên một tỷ lệ không
tuyến tính, như tỷ lệ số mũ, xấp xỉ công thức dưới đây:

(với A và B là các hằng số dương.)
Có ba phương pháp sử dụng các biến dựa trên tỷ lệ để việc tính độ
tương đồng giữa các đối tượng.
 Xử lý các biến dựa trên tỷ lệ giống như các biến tỷ lệ khoảng cách. Tuy
nhiên điều này không phải luôn là lựa chọn tốt bởi tỷ lệ có thể bị bóp méo.
 Áp dụng phép biến đổi log
a
cho một biến dựa trên tỷ lệ f có giá trị x
if

cho đối tượng i bằng cách sử dụng công thức y
if
= log(x
if
). Các giá trị y
if

được xử lý như giá trị tỷ lệ khoảng cách trong mục 1.2.3. Lưu ý rằng
đối với nhiều biến dựa trên tỷ lệ, ta cũng có thể áp dụng phép biến đổi
log hay các phép biến đổi khác, tuỳ thuộc vào định nghĩa và ứng dụng.
 Xử lý x
if
như dữ liệu có thứ tự liên tục và xử lý các hạng của chúng như
giá trị tỷ lệ khoảng cách. Hai phương pháp sau có hiệu quả nhất, mặc
dù việc lựa chọn phương pháp nào để dùng còn phụ thuộc vào ứng
dụng cho trước.

1.2.6 .Các biến có sự pha trộn của các kiểu
Trong một CSDL thì có thể chứa tất cả 6 kiểu biến: các kiểu này có thể
là tỷ lệ khoảng cách, nhị phân đối xứng, nhị phân không đối xứng, tên, có thứ
tự hay dựa trên tỷ lệ. Vì vậy cần một phương pháp để tính độ tương đồng giữa
các đối tượng của các kiểu biến hỗn hợp.
Có thể sử dụng nhóm mỗi loại biến với nhau, thực hiện một phép phân
tích cụm riêng biệt cho mỗi kiểu biến. Điều này là khả thi nếu như các phép
phân tích này nhận được các kết quả thích hợp. Tuy nhiên, trong các ứng

Số hóa bởi trung tâm học liệu

17
dụng thực tế, thường không thể xảy ra một phép phân tích cụm tách biệt cho
mỗi kiểu biến sẽ sinh ra các kết quả thích hợp.
Một tiếp cận được ưa thích hơn là xử lý tất cả các kiểu biến với nhau,
thực hiện một phép phân cụm. Một kỹ thuật như vậy được đề xuất bởi
(Ducker et al. 1965) và mở rộng bởi (Kaufman and Rousseeuw 1990) kết hợp
các biến khác nhau vào trong một ma trận ương đồng và mang tất cả các biến
có nghĩa lên trên một tỷ lệ chung trong khoảng [0,1].
Giả sử rằng tập dữ liệu chứa p biến kiểu hỗn hợp. Độ tương đồng d(i,j)
giữa đối tượng i và j được định nghĩa:

với nếu x
if
hoặc x
jf
khuyết (tức là không có phép đo của biến f
cho đối tượng i hay j) hoặc x
if
=x

jf
=0 và biến f là nhị phân không đối xứng, các
trường hợp còn lại . được tính toán tùy thuộc vào kiểu của nó.
 Nếu f là nhị phân hay tên thì: nếu x
if
=x
jf
, các trường hợp còn
lại thì
 Nếu f là tỷ lệ khoảng cách với h chạy quá tất
cả các đối tượng không khuyết đối với biến f.
 Nếu f là có thứ tự hay dựa trên tỷ lệ: tính toán các hạng r
if
và
và xem xét như tỷ lệ khoảng cách.
Do đó, độ đo tương đồng giữa các đối tượng được tính ngay cả khi các
biến mô tả các đối tượng có kiểu khác nhau.