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

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

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


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

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

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

+ 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


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

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:


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ự.

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

Đố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ị

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

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