Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
Nguyễn Trung Sơn
PHƢƠNG PHÁP PHÂN CỤM VÀ ỨNG DỤNG
Chuyên ngành : KHOA HỌC MÁY TÍNH
Mã số : 60.48.01
LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH
NGƯỜI HƯỚNG DẪN KHOA HỌC
1. PGS. TS VŨ ĐỨC THI
Thái Nguyên – 2009 -2-
MỤC LỤC
TRANG
LỜI CẢM ƠN
5
LỜI MỞ ĐẦU
6
CHƢƠNG I : TỔNG QUAN THUYẾT VỀ PHÂN CỤM DỮ LIỆU
7
1. Phân cụm dữ liệu
7
1.1 Định nghĩa về phân cụm dữ liệu 7
1.2 Một số ví dụ về phân cụm dữ liệu 7
2. Một số kiểu dữ liệu
10
2.1 Dữ liệu Categorical 10
2.2 Dữ liệu nhị phân 13
2.3 Dữ liệu giao dịch 14
2.4 Dữ liệu Symbolic 15
4. Thuật toán phân cụm dữ liệu dựa vào tìm kiếm
46
4.1 Thuật toán di truyền (GAS) 46
4.2 J- Means 48
5. Thuật toán phân cụm dữ liệu dựa vào lƣới
49
5.1 STING 49
5.2. Thuật toán CLIQUE 51
5.3. Thuật toán WaveCluster 52
6. Thuật toán phân cụm dữ liệu dựa vào mật độ
53
6.1 Thuật toán DBSCAN 53
6.2. Thuật toán OPTICS 57
6.3. Thuật toán DENCLUDE 58
7. Thuật toán phân cụm dữ liệu dựa trên mẫu
60
7.1 Thuật toán EM 60
7.2 Thuật toán COBWEB 61
CHƢƠNG III :ỨNG DỤNG CỦA PHÂN CỤM DỮ LIỆU
62
1. Phân đoạn ảnh
62
1.1. Định nghĩa Phân đoạn ảnh 63
1.2 Phân đoạn ảnh dựa vào phân cụm dữ liệu 65
2. Nhận dạng đối tƣợng và ký tự
71
2.1 Nhận dạng đối tượng 71
-4-
2.2 Nhận dạng ký tự. 75
-6-
LỜI MỞ ĐẦU
Trong những năm gần đây, sự phát triển mạnh mẽ của CNTT đã làm
cho khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin tăng
nhanh một cách chóng mặt. Bên cạnh đó, việc tin học hóa một cách ồ ạt và
nhanh chóng các hoạt động sản xuất, kinh doanh cũng như nhiều lĩnh vực
hoạt động khác đã tạo ra cho chúng ta một lượng dữ liệu lưu trữ khổng lồ.
Hàng triệu CSDL đã được sử dụng trong các hoạt động sản xuất, kinh doanh,
quản lý..., trong đó có nhiều CSDL cực lớn cỡ Gigabyte, thậm chí là Terabyte.
Sự bùng nổ này đã dẫn tới một yêu cầu cấp thiết là cần có những kỹ
thuật và công cụ mới để tự động chuyển đổi lượng dữ liệu khổng lồ kia thành
các tri thức có ích. Từ đó, các kỹ thuật khai phá dữ liệu đã trở thành một lĩnh
vực thời sự của nền CNTT thế giới hiện nay nói chung và Việt Nam nói riêng.
Khai phá dữ liệu đang được áp dụng một cách rộng rãi trong nhiều lĩnh vực
kinh doanh và đời sống khác nhau: marketing, tài chính, ngân hàng và bảo
hiểm, khoa học, y tế, an ninh, internet… Rất nhiều tổ chức và công ty lớn trên
thế giới đã áp dụng kỹ thuật khai phá dữ liệu vào các hoạt động sản xuất kinh
doanh của mình và thu được những lợi ích to lớn.
Các kỹ thuật khai phá dữ liệu thường được chia thành 2 nhóm chính:
- Kỹ thuật khai phá dữ liệu mô tả: có nhiệm vụ mô tả về các tính
chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có.
- Kỹ thuật khai phá dữ liệu dự đoán: có nhiệm vụ đưa ra các dự đoán
dựa vào các suy diễn trên dữ liệu hiện thời.
Bản luận văn này trình bày một số vấn đề về Phân cụm dữ liệu, một
trong những kỹ thuật cơ bản để Khai phá dữ liệu. Đây là hướng nghiên cứu
có triển vọng chỉ ra những sơ lược trong việc hiểu và khai thác CSDL khổng
lồ, khám phá thông tin hữu ích ẩn trong dữ liệu; hiểu được ý nghĩa thực tế của dữ liệu.
Luận văn đƣợc trình bày trong 3 chƣơng và phần phụ lục :
Chương 1 : Trình bày tổng quan lý thuyết về Phân cụm dữ liệu, các kiểu dữ
liệu, Phép biến đổi và chuẩn hóa dữ liệu.
,
21
22221
11211
ndnn
d
d
xxx
xxx
xxx
D
gom các cột của ma trận D.
1.2.2 Phân cụm dữ liệu phục trong sức khỏe tâm lý
Phân cụm dữ liệu áp dụng trong nhiều lĩnh vực sức khỏe tâm lý, bao
gồm cả việc thúc đẩy và duy trì sức khỏe, cải thiện cho hệ thống chăm sóc sức
khỏe, và công tác phòng chống bệnh tật và người khuyết tật (Clatworthy et
al., 2005). Trong sự phát triển hệ thống chăm sóc sức khỏe, phân cụm dữ liệu
được sử dụng để xác định các nhóm của người dân mà có thể được hưởng lợi
từ các dịch vụ cụ thể (Hodges và Wotring, 2000). Trong thúc đẩy y tế, nhóm
phân tích được sử dụng để lựa chọn nhắm mục tiêu vào nhóm sẽ có khả năng
đem lại lợi ích cho sức khỏe cụ thể từ các chiến dịch quảng bá và tạo điều
kiện thuận lợi cho sự phát triển của quảng cáo. Ngoài ra, phân cụm dữ liệu
Khai phá dữ liệu
Khai phá dữ liệu trực tiếp
Khai phá dữ liệu gián tiếp
Phân loại
Ước lượng
Dự đoán
Phân cụm
Luật kết hợp
Diễn giải và trực quan hóa
-9-
được sử dụng để xác định các nhóm dân cư bị rủi ro do phát triển y tế và các
điều kiện những người có nguy cơ nghèo.
1.2.3 Phân cụm dữ liệu đối với hoạt đông nghiên cứu thị trường
Trong nghiên cứu thị trường, phân cụm dữ liệu được sử dụng để phân
đoạn thị trường và xác định mục tiêu thị trường (Chrisoppher, 1969;
Saunders, 1980, Frank and Green, 1968). Trong phân đoạn thị trường, phân
cụm dữ liệu thường được dùng để phân chia thị trường thành nhưng cụm
mang ý nghĩa, chẳng han như chia ra đối tượng nam giới từ 21-30 tuổi và
được bắt gặp trong nhiều ứng dụng, chẳng hạn như khai phá văn bản, biểu
diễn gen, phân loại khách hàng, xử lý ảnh…
2. Một số kiểu dữ liệu
Thuật toán phân cụm dữ liệu có nhất rất nhiều liên kết với các loại dữ
liệu. Vì vậy, sự hiểu biết về quy mô, bình thường hoá, và gần nhau là rất quan
trọng trong việc giải thích các kết quả của thuật toán phân cụm dữ liệu. Kiểu
dữ liệu nói đến mức độ lượng tử hóa trong dữ liệu (Jain và Dubes, 1988;
Anderberg, 1973) - một thuộc tính duy nhất có thể được gõ như nhị phân, rời
rạc, hoặc liên tục. thuộc tính nhị phân có chính xác hai giá trị, như là đúng
hoặc sai. Thuộc tính rời rạc có một số hữu hạn các giá trị có thể, vì thế các
loại nhị phân là một trường hợp đặc biệt của các loại rời rạc (xem hình 2).
Dữ liệu quy mô, mà chỉ ra tầm quan trọng tương đối của các con số,
cũng là một vấn đề quan trọng trong phân cụm dữ liệu. Vậy liệu có thể được
chia thành quy mô định lượng và quy mô định tính. quy mô định lượng bao
gồm quy mô danh nghĩa và quy mô giới hạn; quy mô định tính bao gồm quy
mô khoảng và quy mô khoảng tỷ lệ (hình 3). các kiểu dữ liệu sẽ được xem xét
trong phần này .
2.1 Dữ liệu Categorical
Thuộc tính Categorical cũng được gọi là thuộc tính danh nghĩa, thuộc
tính này đơn giản là sử dụng như tên, chẳng hạn như các thương hiệu xe và
tên của các chi nhánh ngân hàng. Chúng ta xem xét các dữ liệu tập hợp với
một số hữu hạn các điểm dữ liệu, một thuộc tính trên danh nghĩa của các điểm
dữ liệu trong tập dữ liệu có thể chỉ có một số hữu hạn các giá trị; như vậy, các
loại danh nghĩa cũng là một trường hợp đặc biệt của kiểu rời rạc.
-11-
4
(B, B, C, C, D, C)
x
5
(B, B, D, D, C, D)
Cho
n
xxxD ,,
21
là một tập dữ liệu tuyệt đối với khoảng cách
n, được mô tả bởi d thuộc tính Categorical v
1
, v
2
,…v
d
. Đặt DOM(v
j
) thuộc
Kiểu dữ liệu
Rời rạc Liên tục
Danh nghĩa Nhị phân
Đối xứng Bất đối xứng
Quy mô dữ liệu
Định lượng
Danh nghĩa Giới hạn
Định tính
j
đã cho trong tập dữ liệu D. Một bảng T
s
của tập
dữ liệu được định nghĩa
Ts = (s
1
, s
2
, … , s
d
), (2.1)
Nơi s
j
)1( dl
là vecto định nghĩa là
T
jnjjj
j
AAAs ,,,
21
.
Vì có nhiều trạng thái có thể là các giá trị (hoặc) cho một biến, một
bảng biểu tượng của một tập dữ liệu thường là không duy nhất. Ví dụ, đối với
bộ dữ liệu trong bảng 1, cả hai bảng 2 và Bảng 3 là bảng biểu tượng của nó.
Bảng tần số được tính theo một bảng biểu tượng và nó đã chính xác
cùng kích thước như bảng biểu tượng. Đặt C là một cụm. Sau đó, bảng tần số
D
C
B
D
C
B
D
C
A
D
C
A
B
A
B
A
Bảng 3 : Bảng biểu tượng của bộ dữ liệu trong bảng 1.
tại mảng thứ j, v.v
,:
jrjjr
AxCxCf
(2.4)
-13-
Nơi x
j
là giá trị bộ phận j của x
Đối với một bảng biểu tượng cho trước của bộ dữ liệu, bảng tần số của
mỗi cụm là duy nhất lên đến rằng bảng biểu tượng. Ví dụ, đối với bộ dữ liệu
trong bảng 2.1, cho C được một cụm, trong đó C = (x
1
, x
2
, x
3
). Sau đó, nếu sử
dụng các biểu tượng trình bày trong bảng 2 bảng tần số tương ứng cho các
nhóm C được cho trong bảng 2.4. Nhưng nếu sử dụng bảng biểu tượng trình
bày trong Bảng 2.3, sau đó là bảng tần số cho các nhóm C được cho trong
bảng 2.5.
Để có được bộ dữ liệu Categorical D, chúng ta thấy rằng T
f
(D) là một
bảng tính toán tần số trên cơ sở dữ liệu toàn bộ thiết lập. Giả sử D là phân
vùng không chồng chéo vào k cụm C
1
, x
2
,…,
x
d
)(Zhang and Srihari 2003), nơi
dix
i
11,0
là giá trị thành phần j của x.
Vecto khối nhị phân I của kích thước d là một vecto nhị phân với mỗi giá trị
nhập vào bằng 1. Việc bổ xung một vecto nhị phân x được định nghĩa là
xIx
, nơi I là một đơn vị vecto nhị phân có cùng kích thước như x.
Xét hai vecto nhị phân x và y trong không gian d, và cho
yxS
ij
,
1,0, ji
biểu thị số lần xuất hiện của i trong x và j trong y tương ứng, ví dụ
ixkyxS
kij
:,
và
00
,11.,
(2.7b)
d
i
ii
yxyxyxS
1
_
01
,1.,
(2.7c)
d
i
ii
yxyxyxS
1
_
10
,1.,
(2.7d)
Ta cũng có :
0
3
Bảng5: Bảng tính toán tần số từ bảng biểu tượng trong bảng 3
1
1
1
1
1
1
0
0
3
3
0
0
3
0
0
3
J
∈ t
i
và b
ij
= 0 nếu I
j
t
i
. Từ điểm này, các dữ liệu giao dịch là
-15-
một trường hợp đặc biệt của dữ liệu nhị phân. Ví dụ phổ biến nhất của dữ liệu
giao dịch là thị trường dữ liệu trong giỏ hàng. Trong một thị trường
thiết lập dữ liệu trong giỏ hàng, giao dịch có chứa một tập hợp con của tập
tổng số mặt hàng mà có thể được mua. Ví dụ, sau đây là hai giao dịch: (táo,
bánh), (táo, món ăn, trứng, cá,). Nói chung, nhiều giao dịch được thực hiện
các mục thưa thớt phân phối. Ví dụ, một khách hàng chỉ có thể mua một số
mặt hàng từ một cửa hàng với hàng nghìn mặt hàng. Như đã chỉ ra bởi Wang
et al. (1999a), cho các giao dịch được thực hiện các mục thưa thớt phân phối,
cặp tương tự là không cần thiết, cũng không đủ để đánh giá xem một cụm
giao dịch là tương tự.
2.4 Dữ liệu Symbolic
Dữ liệu Categorical và dữ liệu nhị phân là loại dữ liệu cổ điển, và dữ
liệu symbolic là một phần mở rộng của các kiểu dữ liệu cổ điển. Trong bộ dữ
liệu thông thường, các đối tượng đang được coi là cá nhân (lần đầu các đối
tượng tự) (Malerba et al, 2001.), trong khi đó tại tập dữ liệu symbolic , các đối
tượng là nhiều hơn "thống nhất" do có nghĩa là các mối quan hệ. Như vậy, các
2000). Ví dụ, giá cổ phiếu các phong trào, nhiệt độ tại một điểm nào đó, và
khối lượng bán hàng theo thời gian tất cả đo là các chuỗi thời gian.
Một chuỗi thời gian là rời rạc nếu biến được xác định trên một tập hữu
hạn các điểm thời gian. Nhiều nhất của chuỗi thời gian gặp phải trong phân
tích cụm là thời gian rời rạc. Khi một biến được định nghĩa ở tất cả các điểm
trong thời gian, sau đó là chuỗi thời gian là liên tục.
Nói chung, một chuỗi thời gian có thể được coi là một hỗn hợp của bốn
thành phần sau (Kendall và Ord, 1990):
1. Một xu hướng, ví dụ., các phong trào lâu dài;
2. Biến động về xu hướng đều đặn hơn hoặc ít hơn;
3. Một thành phần theo mùa;
4. Một hiệu ứng dư hoặc ngẫu nhiên.
3. Phép biến đổi và chuẩn hóa dữ liệu
Trong nhiều ứng dụng của phân cụm dữ liệu, dữ liệu thô, hoặc đo đạc
thực tế, không được sử dụng trực tiếp, trừ khi một mô hình xác suất cho các
thế hệ khuôn mẫu có sẵn (Jain và Dubes, 1988). Việc chuẩn bị cho việc phân
cụm dữ liệu yêu cầu một số loại chuyển đổi, chẳng hạn như biến đổi và
chuẩn hóa dữ liệu. Một số phương pháp biến đổi dữ liệu thường được sử dụng
để phân cụm dữ liệu sẽ được thảo luận trong phần. Một số phương pháp
chuẩn hoá dữ liệu được trình bày trong Phần 4.1.
-17-
Để thuận tiện hãy cho
**
2
*
1
*
,,,
*
1
*
12
*
11
**
2
*
1
,,,
ndnn
d
d
T
n
xxx
xxx
xxx
xxx
(4.1)
3.1 Phép chuẩn hóa dữ liệu
Chuẩn hoá làm cho dữ liệu giảm kích thước đi. Nó có ích để xác định
tiêu chuẩn hoá chỉ số. Sau chuẩn hóa, tất cả các kiến thức về vị trí và quy mô
của các dữ liệu gốc có thể bị mất. Nó là cần thiết để chuẩn hóa các biến trong
-18-
nơi
ij
x
biểu thị giá trị đã được chuẩn hóa,
j
L
là vị trí đo, và
j
M
là quy mô đo.
Chúng tôi có thể có được phương pháp tiêu chuẩn hoá khác nhau bằng
cách chọn khác nhau L
J
và M
J
trong phương trình (4,2). Một số phương pháp
chuẩn hoá nổi tiếng trung bình, tiêu chuẩn độ lệch, phạm vi, Huber của dự
toán, dự toán biweight Tukey's, và Andrew ước tính của sóng.
Bảng 4,1 cho một số hình thức tiêu chuẩn hoá, nơi
*
j
x
,
*
j
R
và
*
(4.3b)
2
1
2
1
***
)(
1
1
n
i
jijj
xx
n
(4.3c)
Biến đổi sẽ có một ý nghĩa của 0 và phương sai một trong số 1. Vị trí
quy mô và thông tin của biến gốc đã bị mất. Chuyển đổi này cũng là trình bày
trong (Jain và Dubes, 1988, trang 24). Một điều quan trọng hạn chế của chuẩn
hóa Z
1
là nó phải được áp dụng trong tiêu chuẩn toàn cầu và không ở trong
phạm vi-cụm tiêu chuẩn hoá (Milligan và Cooper, 1988). Trong thực tế, hãy
xem xét trường hợp hai cụm tách ra cũng tồn tại trong các dữ liệu. Nếu một
mẫu có vị trí mỗi hai cụm trung tâm, sau đó trong vòng-cụm chuẩn sẽ chuẩn
hóa các mẫu nằm tại cụm trung tâm về không vectơ. Bất kỳ thuật toán
clustering sẽ nhóm hai số không vectơ với nhau, có nghĩa là hai nguyên mẫu
-19-
sẽ được được nhóm cho một cluster. Điều này tạo ra một kết quả phân nhóm
rất gây hiểu nhầm.
Bảng 4.1 Một vài phép chuẩn hóa dữ liệu, nơi
*
j
x
,
*
j
R
và
*
j
được định nghĩa
trong biểu thức 4.3
Tên L
x
1
Median
*
2
1
j
n
x
nếu n là lẻ
*
2
2
*
2
2
1
j
Chuẩn hóa USTD (Độ lệch chuẩn các trọng không chính xác) cũng
tương tự như chuẩn hoá điểm z-score và được định nghĩa là
*
*
*
2
j
ij
ijij
x
xZx
(4.5)
Nơi
*
j
được định nghĩa trong biểu thức (4.3c)
Biến đổi bởi Z
2
sẽ có một phương sai của 1. Kể từ khi có điểm số
không được trung tâm bằng cách trừ đi có nghĩa là, các thông tin vị trí giữa
các điểm vẫn còn. Như vậy, chuẩn hóa Z
2
sẽ không phải chịu những vấn đề
của sự mất thông tin về các Cụm centroids.
Phương pháp chuẩn hoá thứ ba trình bày trong Milligan và Cooper
(1988) là sử dụng điểm tối đa về biến:
X
và
X
là trung bình và độ lệch chuẩn của biến gốc. Z
3
là nhạy
cảm với sự hiện diện của Outliers (Milligan và Cooper, 1988). Nếu một đơn
lớn quan sát trên một biến được trình bày, Z
3
sẽ chuẩn hóa các giá trị còn lại
để gần 0. Z
3
có vẻ là có ý nghĩa chỉ khi biến này là một biện pháp trong một
phạm vi tỷ lệ (Milligan và Cooper, 1988).
Hai quy chuẩn có liên quan đến việc sử dụng phạm vi của biến đã được
trình bày trong (Milligan và Cooper, 1988):
*
*
*
4
j
ij
ijij
R
x
xZx
(4.7a)
5
sẽ có nghĩa là
)min()max( XX
X
và
)min()max(
)min(
XX
XX
, tương ứng, và có cùng độ lệch chuẩn
)min()max( XX
X
. Cả
hai Z
4
và Z
5
dễ phải sự hiện diện của Outliers.
Một tiêu chuẩn hoá trên cơ sở bình thường hóa với tổng của các quan
sát trình bày trong (Milligan và Cooper, 1988) được định nghĩa là
,
1
*
,
**
7 ijijij
xRankxZx
(4.9)
Nơi Rank(X) là cấp chỉ định cho X
Một biến chuyển bởi Z
7
sẽ có một ý nghĩa của
2
1n
và một phương sai
của
4
1
6
12
1
nn
n
hàm tuyến tính một
va
1
của các yếu tố của v có tối đa các phương sai, mà a
1
là
một vectơ d-chiều
d
aaa
11211
,,,
do đó,
-22-
d
i
ii
vava
1
1
'
1
j
=
va
j
, nơi a
j
là một eigenvector của
tương ứng với
các thứ giá trị j lớn nhất λ
j
.
Trong thực tế, ở bước đầu tiên, z
1
=
va
j
có thể tìm thấy bằng cách giải
quyết tối ưu hoá vấn đề sau đây:
Maximize
va
1
var
1
1
aaaa
(4.10)
Phương trình khác(4.10) với a
1
, chúng ta có
0
11
aa
0
1
aI
d
Nơi I
d
là ma trận nhận dạng d x d
Vì
là giá trị riêng của
j
(Jolliffe, 2002).
Trong (Dinh và He, 2004), PCA là làm việc để giảm chiều của dữ liệu
thiết lập và sau đó thuật toán K-means được áp dụng trong không gian con
PCA.
Các ví dụ khác của PCA áp dụng trong phân tích cụm dữ liệu có thể
được tìm thấy trong (Yeung và Ruzzo, 2001). Trình diễn PCA là tương đương
với giá trị thực hiện phân hủy từ (SVD) trên các hiệp phương sai ma trận của
dữ liệu. ORCLUS sử dụng SVD (Kanth et al, 1998) kỹ thuật. Để tìm hiểu tùy
tiện theo định hướng không gian con với phân cụm dữ liệu tốt.
3.2.2 SVD
SVD là một kỹ thuật mạnh mẽ trong tính toán ma trận và phân tích,
chẳng hạn như việc giải quyết các hệ thống phương trình tuyến tính và xấp xỉ
ma trận. SVD cũng là một kỹ thuật nổi tiếng chiếu tuyến tính và đã được sử
dụng rộng rãi trong nén dữ liệu và ảo (Andrews và Patterson, 1976a, b). trong
mục này, phương pháp SVD là phương pháp tóm tắt.
Cho
n
xxxD ,,,
21
là một số dữ liệu được đặt trong một không
gian d-chiều. Sau đó, D có thể được đại diện bởi một n x n ma trận X là
,
dn
ij
xX
1
và để cho e
n
là một vectơ cột của n chiều dài với tất cả các yếu tố tương
đương với nó. Sau đó, SVD thể hiện
n
eX
là,
T
n
USVeX
(4.11)
trong đó U là một ma trận n × n trực giao, ví dụ, nghĩa là, U
T
U = I là
ma trận đơn vị. S là một ma trận chéo chứa các giá trị số ít, và V là một ma
trận unita d × d , ví dụ, V
H
V = I, nơi V
H
là ma trận chuyển vị liên hợp của V.
-24-
Các cột của ma trận V là vecto đặc trưng của ma trận hiệp phương sai
C của X; chính xác
n
i
jijj
x
n
của C là bất biến theo luân phiên, nghĩa là,
d
j
j
d
j
j
11
2
Chú ý rằng
nXe
T
TT
eeeXXeXX
TT
nXX
T
VnV
. (4.13)
Kể từ khi V là một ma trận trực giao, từ phương trình (4,13), các giá trị
từ có liên quan đến các giá trị riêng bởi
.,2,1
,
2
djns
jj
Các vecto đặc trưng chiếm các máy tính của X, và các tính năng không
tương quan sẽ được thu được do chuyển đổi
VeXY
n
. PCA chọn các
tính năng với giá trị riêng cao nhất.
3.2.3 Phép biến đổi Karhunen-Loève
Copyright: Tài liệu đại học ©