PHẦN MỞ ĐẦU
LÝ DO CHỌN ĐỀ TÀI
Phân tích chùm là việc nhóm các phần tử trong tập hợp đã cho thành các chùm sao
cho các phần tử trong cùng chùm tương tự nhau theo những dấu hiệu nào đó. Khi chùm
được xây dựng, những phần tử trong cùng một chùm sẽ có sự tương tự nhiều hơn so với
những phần tử của chùm khác.
Có rất nhiều ứng dụng trong y học, kinh tế, kỹ thuật, xã hội,…
Trong phân tích chùm truyền thống (không mờ), các nhà khoa học đã nghiên cứu
các phương pháp phân tích chùm thứ bậc và không thứ bậc với các tiêu chuẩn đánh giá
khác nhau như khoảng cách hay độ rộng chùm. Tuy nhiên các phương pháp phân tích
chùm không mờ đòi một phần tử phải thuộc hoặc không thuộc một chùm một cách rõ
ràng, điều này không thực sự hợp lý khi trong thực tế có nhiều phần tử nằm ở những vị trí
“nhạy cảm” đan xen giữa các chùm.
Nghiên cứu chùm có kèm theo xác suất gọi là phân tích chùm mờ. Phương pháp này
khắc phục nhược điểm của phương pháp phân tích chùm không mờ khi tập dữ liệu có các
phần tử nằm gần biên giới giữa các chùm.
Mặc dù đã được quan tâm nhiều, nhưng các tài liệu về phân tích chùm cũng được
trình bày khá rời rạc, do đó các ứng dụng thực tế cũng chỉ xét cho từng trường hợp riêng
biệt không có sự so sánh đối chiếu.
Với mong muốn tổng hợp các phương pháp xây dựng chùm mờ và không mờ cho
các phần tử rời rạc làm cơ sở để nghiên cứu lý thuyết vấn đề này, đặc biệt vấn đề tính
toán cho số liệu thực tế lớn để áp dụng cho nhiều lĩnh vực khác nhau em chọn đề tài
Phân tích chùm mờ và không mờ các phần tử rời rạc.
TỔNG QUAN VỀ PHÂN TÍCH CHÙM
Khái niệm phân tích chùm.
Chùm coi như là một đối tượng (phần tử, điểm). trong đó mỗi đối tượng dần tới
đối tượng trung tâm của một chum và những thánh viên của những chùm khác nhau thì
không tương tự nhau. Hay nói ngắn ngọn là ta sẽ thực hiện cực đại hóa sự tương tự giữa
các đối tượng cùng một chum, nhưng cực tiểu hóa các đối tượng khác chum. Trong ý
nghĩa, chum có thể xem như là “mật độ cao khu vực” của một không gian đa chiều.
Quá trình nhốm các đối tượng vào cùng một chùm được gọi là việc xếp nhóm
(clastering). Clastering đề cập tới vấn đề quang trọng nhất là nghiêm cứu không giám sát
( unsperviced learning) – không có thông tin về nhãn lớp của đối tượng. Hay nói cách
khác, đây là công việc “ xử lí để tổ chức các đối tượng vào các nhóm mà trong đó, các
1
phần tử của mỗi nhóm giống nhau theo một nghĩa nào đó”. Phân tích chùm là một lớp các
kĩ thuật được sử dụng để phân loại các đối tượng hoặc các trường hợp thành các nhóm
đối tượng gọi là chùm. Phân tích chùm còn được gọi là phân tích phân loại hoặc phân loại
số.
Phân tích chùm dữ liệu là một lĩnh vực nghiên cứu đầy thách thức và công việc
này luôn đặc ra những yêu cầu đặc thù sau đây:
Tính khả mở: Nhiều thuật toán phân tích chùm hoạt động tốt trên nhựng tập dữ
liệu nhỏ-bao gồm vài tram đối tượng dữ liệu. Tuy nhiên, một cơ sở dữ liệu lớn bao gồm
hàng triệu, hàng tỉ đối tượng. xếp nhóm trên tập dữ liệu lớn có thể dẫn tới kết quả kém.
Các thuật toán này có tính khả mở cao là rất cần thiết.
Khả năng phát hiện được các nhóm có hình dạng bất kì: các thuật toán phải tìm ra
được các nhóm có hình dạng bất kì, bao gồm những hình có kẻ hở, lõm hoặc lồng nhau.
Thích nghi với các kiểu dữ liệu khác nhau: thuật toán có thể áp dụng hiệu quả cho
việc phân chùm với điều kiện dữ liệu khác nhau như: dữ liệu số, nhị phân,…và thích nghi
với các kiểu dữ liệu hỗn hợp của các dữ liệu đơn trên.
Khả năng làm việc được với các dữ liệu chứa nhiễu: cơ chế phân chum thích ứng
được với nhiều điểm nhiễu.
Không nhạy cảm với thứ tự dữ liệu đầu vào: tức là kết quả phân chum độc lập với
dữ liệu input
Giảm thiểu yêu cầu với tham số đầu vào: dữ liệu không cần phải có kiến thức tiên
nhiệm nào
Xử lí được dữ liệu đa chiều: tức là thuộc tính dữ liệu lớn.
Có thể phân chum trên cơ sở ràng buộc: các ứng dụng thực tế có thể cần phân
chum dưới điều kiện rang buộc, Chẳng hạn công việc của bạn là chọn một vị trí dể đặt
máy ATM trong thành phố,… Đây có thể là cả một thử thách của phân tích chum khi dựa
vào bài toán thực tế các lĩnh vực đời sống, tìm ra cách phân tích chum tốt đối với dữ liệu
đầu vào mà vẫn tôn trọng các rang buộc ban đầu.
Tính có thể hiểu được, tiện lợi và khả dụng: Người dùng luôn mong nhận được
một bộ phân chùm có thể hiểu được và tiện lợi. Có một số thuật toán khi thực hiện và so
sánh với các kết quả thực tế không khớp, không hợp lí. Vậy kết quả thực tế là vấn đề
quan trọng của thuật toán, Điều quang trọng là nghiên cứu thực tế có thể chi phối các đặc
trưng và các Phương pháp phân nhóm.
2
Một số ứng dụng của phân tích chùm
Phân tích chùm có nhiều tên gọi khac nhau như: phân tích Q, phân tích phân loại,
phân tích bằng kĩ thuật định lượng,… Có nhiều tên gọi khác nhau như vậy là vì phương
pháp phân tích chùm được ứng dụng trong nhiều lĩnh vực khác nhau. Phân tích chùm đã
và đang được sử dụng rộng rãi và có đóng góp quan trọng trong mọi mặt đời song xã hội.
Các ứng dụng chính bao gồm:
Trong thương mại: Phân tích chùm có thể giúp khám phá ra các khách hang quang
trọng có các đặc trưng tương đồng nhau và đặc tả trong cơ sở mua bán từ dữ liệu khách
hàng. Từ đó nâng cao lợi nhuận, cải thiện thu nhập.
Trong sinh học: phương pháp này hữu dụng để phát hiện các loài sinh vật , phân
loại các gen với các chức năng tương đồng và thu thập được các cấu trúc trong các mẫu.
Trong phân tích dữ liệu không gian: Do sự đồ sộ của các dữ liệu không gian như
các hình ảnh thủ được từ các hình ảnh chụp dduocj từ các vệ tinh, các thiết bị khoa học
hay các hệ thống thông tin địa lí(GÍ),… làm cho người dùng rất khó kiểm tra các dữ liệu
không gian một cách chi tiết rõ ràng. Phương pháp phân tích chùm có thể trợ giúp
nguoief dùng tự động phân tích và xử lí các dự liệu không gian như nhận dạng chiết xuất
các đặc tính hoặc các dữ liệu quan tâm có thể tồn tại trông cơ sở dữ liệu không gian.
Trong web mining: Phân tích chùm có thể khám phá ra các nhóm tài liệu quan
trọng. có ý nghĩa theo tiêu chí đặc ra. Tương lai của web mining sẽ ngày càng phát triển
cùng với sụ phát triển của internet.
Trong địa lí: Phân lớp động vật và thực vật và đưa ra đặc trung của chúng.
Trong qui hoạch đô thị: Nhận dạng các nhóm nhà theo kiểu và vị trí địa lí,…
Nhằm cung cấp thông tin cho qui hoạch đô thị.
Trong nghiên cứu trái đất: Phân tích chùm để theo dõi các trận động đất nhằm
cung cấp thông tin cho nhận dạng các vùng nguy hiểm.
Trong nén dữ liệu: Tìm ra các nhóm thể hiện đồng nhất từ đó có thể hổ trợ nén dữ
liệu.
Chương I: PHÂN TÍCH CHÙM KHÔNG MỜ
1.1 GIỚI THIỆU
Theo Jain và Dubes (1988), Kaufman và Rousseeuw (1990), Sharma (1996) và
Everitt et al (2001), phân tích chùm là một phương pháp thống kê đa biến nhằm nhóm
một tập các đối tượng lại thành các chùm theo những đặc điểm định trước. Chùm được
coi như là một nhóm dữ liệu, trong đó những phần tử trong cùng một chùm thì có sự
3
tương tự nhau theo một nghĩa nào đó. Khi có nhiều dữ liệu, người ta muốn chia các dữ
liệu này thành nhiều nhóm sao cho những đối tượng trong cùng nhóm thì gần nhau hơn
so với những đối tượng của nhóm khác. Từ yêu cầu đó bài toán phân tích chùm ra đời.
Chúng ta có thể hiểu phân tích chùm là việc nhóm các phần tử trong dữ liệu ban đầu
thành các chùm sao cho các phần tử trong cùng một chùm thì tương tự nhau theo một
dấu hiệu nào đó. Khi chùm được xây dựng, những phần tử trong cùng một chùm sẽ có sự
tương tự nhiều hơn so với những phần tử của chùm khác. Bài toán phân tích chùm là một
hướng phát triển quan trọng của nhận dạng thống kê, thường được gọi là nhận dạng
không được giám sát. Phần tử trong phân tích chùm là những phần tử rời rạc hoặc các
hàm mật độ xác suất. Đối với phần tử rời rạc, việc xác định sự tương tự của các phần tử
chủ yếu dựa vào khoảng cách giữa các phần tử đó, những phần tử có khoảng cách nhỏ
nhất so với những phần tử khác thì gần nhau hơn và được xếp cùng một chùm.
Hiện tại có hai phương pháp chủ yếu để xây dựng chùm cho các phần tử rời rạc:
phương pháp thứ bậc và phương pháp không thứ bậc. Trong đó khoảng cách của hai phần
L1
tử được sử dụng chủ yếu là khoảng cách Euclide và khoảng cách . Trong khi khoảng
cách giữa hai tập hợp được sử dụng là khoảng cách min, khoảng cách max, khoảng cách
trung bình và khoảng cách Ward. Các phần mềm thống kê như Matlab, Maple, … đều có
những gói sử dụng cho bài toán phân tích chùm các phần tử rời rạc với các tiêu chuẩn
đánh giá là các khoảng cách vừa nêu.
Phân tích chùm được sử dụng đầu tiên bởi Tryon (1939) với một số ý tưởng đơn
giản ban đầu. Các ý tưởng này được phát triển thành các thuật toán phân tích chùm cụ thể
bởi Sibson (1973), Defays (1977) và Rohlf (1982). Các thuật toán này dựa trên tiêu chuẩn
khoảng cách giữa các phần tử rời rạc. Nhiều tác giả đã phát triển thuật toán này bằng
cách thay đổi những khoảng cách khác nhau. Webb (2002) đã tổng kết khá đầy đủ bài
toán phân tích chùm của các dữ liệu rời rạc.
Phân tích chùm được ứng dụng khá phổ biến trong nhiều lĩnh vực: sinh học, y học,
kinh tế, xã hội…. Hartigan (1975) đã cung cấp một bảng tóm tắt tương đối đa dạng và
đầy đủ những nghiên cứu thực tế của bài toán phân tích chùm. Chẳng hạn như, trong y
học phân tích chùm giúp phân loại bệnh có những dấu hiệu gần nhau. Trong khoa học khí
tượng, phân tích chùm đã phát triển rộng rãi từ năm 1990 cho đến nay. Trong khảo cổ
học, phân tích chùm dùng để phân loại công cụ bằng đá. Eshref Shevki và Wendell Bell
(1955) sử dụng phân tích chùm trong điều tra dữ liệu dân số. Nhóm tác giả Piotr
Kulczycki, Malgorzata Charytanowicz, Piotr A. Kowalski, Szymon Lukasik (2011) dùng
phân tích chùm để phân loại hạt giống ngũ cốc phục vụ cho sản xuất và hỗ trợ chiến lược
tiếp thị điều hành điện thoại di động cho các nhà cung cấp mạng điện thoại di động.
Ở Việt Nam, chúng tôi chưa tìm thấy những đóng góp đáng kể về mặt lý thuyết cho
bài toán phân tích chùm, tuy việc áp dụng đã được một số nhà toán học, tin học quan tâm
trong lĩnh vực khai phá dữ liệu.
4
1.2 TIÊU CHUẨN XÂY DỰNG CHÙM CÁC PHẦN TỬ RỜI RẠC
1.2.1 Khoảng cách giữa hai phần tử rời rạc
Khoảng cách là đại lượng dùng để đánh giá sự tương tự của các chùm khi dữ liệu
phân tích là các phần tử rời rạc. Khoảng cách giữa hai phần tử là một metric, nghĩa là nếu
d x, y
d x, y
là khoảng cách của hai phần tử x và y thì
phải thỏa các điều kiện sau đây:
∀ x, y
x= y
�
i) d(x,y) 0
. Dấu bằng xảy ra khi
,
ii)
d(x,y) = d(y,x),
�
iii)
d(x,y) + d(y,z) d(x,z).
Theo 3 điều kiện trên, ta có thể định nghĩa khoảng cách giữa 2 phần tử x và
N
y (x, y ∈ R ) theo nhiều cách khác nhau. Thông thường các loại khoảng cách sau
được sử dụng phổ biến:
1
2
�
�
d e ( x, y ) �
�( xi yi )2 �
i 1
�
�
n
Khoảng cách Euclide:
(1.1)
n
d cb x, y �xi yi
Khoảng cách city- block:
Khoảng cách Chebyshev:
i 1
(1.2)
d ch x, y max xi yi
i
(1.3)
1
m
�n
m�
d m x, y �
�xi yi �
�i 1
�
Khoảng cách Minkowski với bậc m:
(1.4)
Nhận xét:
i)
Khoảng cách Euclide là khoảng cách thường được sử dụng nhất trong
trong toán học, nó mô tả độ dài của đoạn thẳng nối hai điểm x và y.
ii) Khoảng cách city-block mô tả tổng độ dài (tổng các khoảng cách Euclide) của n
đoạn gấp khúc nối hai điểm x, y thuộc không gian n chiều. Mỗi đoạn trong n đoạn này sẽ
song song với 1 trục tương ứng trong n trục chúng ta chọn làm hệ quy chiếu.
iii) Khoảng cách Chebyshev mô tả đoạn thẳng có độ dài lớn nhất trong n đoạn gấp
khúc đã được đề cập trong khoảng cách city- block. Đây là khoảng cách tổng quát nhất,
với những m khác nhau, khoảng cách Minkowski bậc m sẽ tương ứng với một loại
5
khoảng cách khác nhau. Với m =1,
d m x, y d cb x, y
, với m = 2,
d m x, y d e x , y
� � d m x, y dch x, y
độ lớn của khoảng cách càng giảm khi m càng tăng, khi m
,
Hình vẽ sau minh họa 3 khoảng cách phổ biến của hai điểm x(1;2) và y(2;4).
.
6
Khoang cach Euclide
mo ta do dai doan thang nay
5
y(2;4)
4
Khoang cach
Chebyshev mo
ta do dai duongt
gap khuc lon nha
3
2
x(1;2)
1
0
Khoang cach cityblock
mo ta do dai 2 doan gap khuc
1
2
2
1
0
1
2
3
4
5
6
Hình 1.1: Các loại khoảng cách giữa hai phần tử x và y
Như đã thấy, khoảng cách Euclide mô tả đoạn thẳng nối 2 điểm x và y trong khi
khoảng cách city-block mô tả 2 đoạn gấp khúc nối x và y, chúng lần lượt song song với
�3
trục hoành và trục tung của hệ tọa độ. Tương tự như vậy, nếu x, y thuộc không gian
thì khoảng cách city-block sẽ mô tả 3 đoạn thẳng lần lượt song song với Ox, Oy, Oz.
Hình trên cũng chỉ ra khoảng cách Chebyshev mô tả đoạn thẳng dài nhất trong hai
đường gấp khúc.
1.2.2 Khoảng cách giữa hai tập các phần tử rời rạc
Cho A, B là hai nhóm, mỗi nhóm gồm nhiều phần tử rời rạc khác nhau. Gọi D(A;B)
là khoảng cách giữa hai nhóm A và B, d(x,y) là khoảng cách giữa phần tử x và phần tử
y(
x �A; y �B
). Thông thường ta sử dụng các định nghĩa sau cho D(A;B):
Khoảng cách min:
Dmin A; B min d x, y
x�A
y�B
Dmax A; B max d x, y
Khoảng cách max:
x�A
y�B
(1.5)
(1.6)
Davg A; B
1
nA nB
Khoảng cách trung bình:
6
�d x, y
x�A
y�B
(1.7)
,
nA , nB
Với
Nhận xét:
lần lượt là số phần tử của nhóm A và nhóm B.
i) Việc tính khoảng cách giữa hai nhóm dữ liệu không chỉ phụ thuộc vào việc chọn
loại khoảng cách giũa hai nhóm mà còn phụ thuộc vào loại khoảng cách giữa
hai phần tử, do đó sẽ có nhiều kết quả khác nhau tùy vào loại khoảng cách được
chọn. Cho đến nay, người ta chưa chứng minh được sử dụng khoảng cách nào là
tối ưu. Trong thực tế các loại khoảng cách phổ biến đã được nêu ở trên thường
được sử dụng nhiều nhất.
ii) Khi hai nhóm A và B được nhập lại thành một nhóm (A+B) thì việc tính khoảng
cách từ nhóm (A+B) đến một nhóm C bất kỳ cũng có thể thực hiện theo những
công thức trên. Tuy nhiên, ta có thể áp dụng những công thức sau đây để cho
việc tính toán được thuận tiện hơn.
�
�
�
�
Dmin A B , C min Dmin A, C , Dmin B, C min �
min d x, z , min d y , z �
x�A
y�B
�
�
z�C
�z�C
(1.8)
�
�
�
�
Dmax A B, C max Dmax A, C , Dmax B, C max �max d x, z , max d y , z �
x�A
y�B
�
�
z�C
�z�C
(1.9)
Davg A B, C
nA
nB
Davg A, C
Davg B, C
n A nB
n A nB
(1.10)
Ngoài các khoảng cách thông dụng trên, Ward (1963) đã đưa ra công thức tính
khoảng cách trường hợp này bằng biểu thức:
n n
n n
nC
DWard A B, C A C D A, C B C D B, C
D A, B
nA nB nC
nA nB nC
nA nB nC
(1.11)
n A nB
nC
�
�
� A,5 B
�và C.
Trong đó , , và
lần
tử2của
A�
a1 lượt
2 số
, a2phần
2;
�
3; �
, a4 3;3 �
4;là
, a3nhóm
� 2�
�
Ví dụ 1.1. Cho
�
1�
�
�
B�
b1 3; 1 , b2 �
2; �
, b3 1; 1 �
2�
�
�
�
�
� 3�
C�
c1 1; 2 , c2 �
1;7 �
�
2
� �
�
Tính:
a)
b)
Dmin , Dmax , Davg
Dmin , Dmax , Davg
giữa A và B.
giữa A+C và B.
Giải
Trước tiên ta chọn khoảng cách Euclide làm khoảng cách giữa hai phần tử. Khoảng
cách giữa các nhóm được tính như sau:
Dmin A, B min de a1 , b1 , d e a1 , b2 ...d e a4 , b3
a)
d e a2 , b2
=
Tương tự
5
2
Dmax A, B max d e a1 , b1 , de a1 , b2 ...d e a4 , b3
=
Davg A, B
b)
= 2.5
d e a4 , b3 2 5 �4.4721
1
nA nB
�d x, y �3.5197
x�A
y�B
Dmin A C , B min Dmin A, B , Dmin C , B
�5 41 � 5
min � ,
�
�2 2 � 2 d a2 , b2
=
Dmax A C , B max Dmax A, B , Dmax C , B
5
4
=
max 2 5, 5 5 d cDmax(A,B)
1 , b1
Y
Nhom A+C
Nhom A
nC
nA
Davg A3 C , B
Davg A, B
Davg C , B
nA nC
nA nC
2
1
Nhom
C
4
2
3.5197 4.0058 �3.6817
Dmin(A,B)
6
6
=
O
Ta có thể mô tả hình học ví dụ trên như sau:
0
Dmin(A+C,B)
1
3
6
8
Nhom B
2
5
4
3
X
2
1
Dmax(A+C,B)
0
1
2
3
Y
5
4
Nhom A
3
2
Nhom
C
1
X
0
O
1
Nhom B
2
3
6
5
4
3
2
1
0
1
2
3
Hình 1.2: Khoảng cách giữa các nhóm
Davg A, B
bằng trung bình các khoảng cách được thể hiện bởi các đoạn thẳng liền
nét.
9
Davg A+C,B
bằng trung bình các khoảng cách được thể hiện bởi các đoạn thẳng
liền nét và không liền nét.
Chú ý:
i) Trước khi tính khoảng cách đối với các biến dữ liệu kiểu số thì cần chú ý về vấn
đề chuẩn hóa dữ liệu sao cho chúng cùng một thang đo dữ liệu. Tình huống thực tế nảy
sinh là có nhiều dữ liệu nhưng thang đo khác nhau. Ví dụ trong bộ dữ liệu có các thuộc
tính như: cân nặng, chiều cao, lương,… đều là dữ liệu kiểu số nhưng rõ ràng thang đo
của chúng là khác nhau (cân tính theo kg, chiều cao tính theo cm hay m, lương tính theo
đơn vị đồng,....). Nếu sử dụng trực tiếp ngay khoảng cách trên tập dữ liệu số chưa được
chuẩn hoá dễ gây sai lệch về độ đo. Ví dụ khoảng cách trọng lượng giữa hai người là 10
kg được coi là lớn (cách xa nhau), nhưng khoảng cách lương 100 000 có thể coi là nhỏ
(đối với vật giá hiện tại). Nhưng số 100 000 lại là quá lớn so với 10. Do đó các dữ liệu
cần được chuẩn hoá về cùng một “thang bậc” để không ảnh hưởng đến phân tích chùm.
ii) Có nhiều loại dữ liệu khác nhau có thể thực hiện bài toán phân tích chùm. Thông
thường ta có các loại dữ liệu phổ biến là dữ liệu kiểu số, nhị phân, định giá, thứ tự,…
1.3 XÂY DỰNG CHÙM CÁC PHẦN TỬ RỜI RẠC
1.3.1 Phương pháp thứ bậc
Một trong những phương pháp phổ biến trong cả phân tích chùm là phương pháp
thứ bậc. Kết quả của phương pháp này là tạo ra một dãy các chùm, trong đó một số chùm
có thể chứa các lớp con bên trong nó, và đến lượt các lớp con này lại chứa bên trong nó
các lớp con nhỏ hơn. Cấu trúc chùm được minh họa bởi một đồ thị hai chiều được gọi là
sơ đồ (sơ đồ nhánh hoặc cây phân tích chùm). Cây phân tích chùm minh họa cho việc
hợp nhất hoặc chia nhỏ các chùm đã được thực hiện bằng cách phân nhóm, và có thể
hiển thị theo chiều dọc hoặc chiều ngang.
Hình 1.3: Cây phân tích chùm 3 phần tử A, B, C
Thuật toán phân tích chùm theo phương pháp thứ bậc cụ thể như sau:
10
Bước 1: Bắt đầu với n chùm, mỗi chùm chứa một phần tử. Tính từng đôi khoảng
cách của hai phần tử. Thành lập ma trận đối xứng của các khoảng cách
là khoảng cách giữa hai phần tử i và j,
i 1...n, j �i
E�
d ij �
�
�
với
dij
.
Bước 2: Trong ma trận khoảng cách E, tìm khoảng cách nhỏ nhất của hai chùm khác
nhau, tức là hai chùm có sự tương tự nhiều nhất.
dUV
Bước 3: Gọi
là khoảng cách giữa hai chùm U và V có sự tương tự nhau nhất.
Hợp nhất hai chùm U và V thành chùm mới. Tính toán lại ma trận khoảng cách giữa các
chùm mới.
Bước 4: Lặp lại bước 2 và bước 3 cho đến khi các phần tử được nhóm lại thành một
chùm duy nhất.
X 1, 2,7,9
A, B, C , D
Ví dụ 1.2. Gọi
là số lần bắn trúng trọng tâm của 4 xạ thủ
.
Sử dụng khoảng cách giữa các phần tử là khoảng cách Euclide, khoảng cách giữa các tập
hợp là khoảng cách trung bình, ta tiến hành phân tích chùm bằng phương pháp thứ bậc
như sau:
- Ban đầu, xem mỗi phần tử là một chùm,
các chùm:
0 1
�
�
1 0
E �
�
6 5
�
8 7
�
ta có ma trận khoảng cách ban đầu của
6
5
0
2
8�
7�
�
2�
�
0�
- Hợp nhất hai chùm A và B lại thành chùm (AB) tính toán lại ma trận khoảng cách:
�0 5.5 7.5 �
�
�
E �
5.5 0
2 �
�
7.5 2
0 �
�
�
- Hợp nhất hai chùm C và D lại thành chùm (CD), tính toán lại ma trận khoảng
cách:
�0
E �
6.5
�
11
6.5 �
�
0 �
- Cuối cùng, hợp nhất hai chùm (AB) và (CD) lại thành một chùm duy nhất. Ta có
cây phân tích chùm như sau:
A
A
B
B
C
D
Hình 1.4: Cây phân tích chùm 4 phần tử A, B, C, D
Ví dụ 1.3. Cho bảng sau:
Bảng 1.1: Số lần bắn trúng mục tiêu của các vận động viên
Vận động
viên
A
B
C
D
Số lần bắn trúng mục
tiêu cố định
1
2
7
9
Số lần bắn trúng mục tiêu
di động
0
0
4
10
Sử dụng khoảng cách giữa các phần tử là khoảng cách Euclide, khoảng cách giữa
các tập hợp là khoảng cách trung bình, ta tiến hành phân tích chùm bằng phương pháp
thứ bậc như sau:
- Ban đầu, xem mỗi phần tử là một chùm, ta có ma trận khoảng cách ban đầu của
các chùm:
1
7.21 12.81�
�0
�1
0
6.40 12.21 �
�
�
E
�7.21 6.40
0
6.32 �
�
�
12.81 12.21 6.32
0 �
�
- Hợp nhất hai chùm A và B lại thành chùm (AB) tính toán lại ma trận khoảng cách:
12
6.80 12.50 �
�0
�
�
E �6.80
0
6.32 �
�
12.50 6.32
0 �
�
�
- Hợp nhất hai chùm C và D lại thành chùm (CD), tính toán lại ma trận khoảng
cách:
� 0 9.55 �
E �
�
�9.55 0 �
Cuối cùng, hợp nhất hai chùm (AB) và (CD) lại thành một chùm duy nhất. Ta có
cây phân tích chùm như sau:
Hình 1.5: Cây
động viên
A
A
B
B
C
D
phân tích chùm của 4 vận
1.3.2 Phương pháp không thứ bậc
a) Phương pháp
Trong phương pháp thứ bậc, các chùm được thành lập theo cấp độ của sự tương tự
từ nhiều đến ít. Tập các phần tử được xem là một chùm lớn, chùm lớn này chứa các chùm
nhỏ hơn và cứ vậy cho đến chùm cuối cùng chỉ gồm 1 phần tử. Trong thực tế người ta có
nhu cầu phân chia dữ liệu ban đầu thành k chùm một cách riêng biệt, do đó bên cạnh
phương pháp thứ bậc, người ta còn phân tích chùm theo phương pháp không thứ bậc. Kết
quả của phương pháp không thứ bậc là quá trình phân nhóm một tập dữ liệu thành k
chùm riêng biệt và các chùm này không chứa các chùm con khác bên trong nó.
Thuật toán phân tích chùm theo phương pháp không thứ bậc được trình bày cụ thể
như sau:
Bước 1: Chia n phần tử thành k chùm một cách ngẫu nhiên (số lượng phần tử trong
mỗi chùm là tùy ý). Tính trọng tâm của mỗi chùm.
Bước 2: Tính khoảng cách từ mỗi phần tử đến trọng tâm của các chùm. Nếu khoảng
cách từ một phần tử đến trọng tâm của chùm nó đang thuộc là nhỏ nhất thì ta giữ phần tử
13
đó trong chùm ban đầu. Nếu tồn tại một chùm khác mà khoảng cách từ phần tử đang xét
đến trọng tâm của chùm là nhỏ nhất thì ta gán phần tử đang xét vào chùm này, bỏ phần tử
trong chùm nó đang thuộc. Nếu phần tử được di chuyển đến chùm khác thì cần phải tính
lại giá trị trọng tâm của hai chùm mới có sự thay đổi.
Bước 3: Quay lại bước 2 và dừng lại khi ta có k chùm, sao cho một phần tử bất kỳ
trong chùm có khoảng cách đến chùm nó đang thuộc nhỏ hơn khoảng cách đến các chùm
khác
Ví dụ 1.4 Với dữ liệu ở ví dụ 1.2 phân tích chùm bằng phương pháp không thứ bậc
với k = 2.
Sử dụng khoảng cách giữa các phần tử là khoảng cách Euclide, ta tiến hành phân
tích chùm bằng phương pháp thứ bậc như sau:
- Chia các phần tử thành 2 chùm một cách ngẫu nhiên:
tọa độ trọng tâm của mỗi chùm, ta có kết quả
v1
1 7
4
2
v2
29
5.5
2
AC
và
BD
.
Tính
- Khoảng cách từ các phần tử đến trọng tâm các chùm lần lượt là
d A, v1 3 d A, v2 4.5
,
d B, v1 2 d B, v2 3.5
,
d C , v1 3 d C , v2 1.5
,
d D, v1 5 d D, v2 3.5
,
- Ta thấy khoảng cách từ B đến trọng tâm chùm thứ nhất nhỏ hơn khoảng cách từ B
đến chùm chứa nó nên ta chuyển B từ chùm 2 sang chùm 1. Lặp lại các bước tính trên, ta
lần lượt có kết quả sau:
Bảng 1.2: Vòng lặp 1
ABC
Trọng tâm
Chùm
3.33
14
Chùm
9
D
Khoảng cách từ
phần tử đến trọng
tâm chùm
A
B
C
D
Chùm
ABC
2.33
1.33
3.67
5.67
D
Chùm
8
7
2
0
Bảng 1.3: Vòng lặp 2
AB
Trọng tâm
Khoảng cách từ phần
tử đến trọng tâm chùm
A
B
C
D
CD
Chùm
1.5
Chùm
8
Chùm
0.5
0.5
5.5
7.5
Chùm
7
6
1
1
AB
CD
Sau hai vòng lặp thì điều kiện khoảng cách từ các phần tử đến trọng tâm chùm chứa
nó là nhỏ nhất đã thỏa mãn. Do đó thuật toán kết thúc và ta có kết quả hai chùm riêng biệt
AB
CD
là chùm
và
. Kết quả này cũng phù hợp với kết quả của cây phân tích chùm ở
phương pháp thứ bậc.
b) Vấn đề xác định số chùm ban đầu
Trong phân tích chùm theo phương pháp không thứ bậc, chúng ta cần phần tích bộ
số liệu thành k chùm riêng biệt. Tuy nhiên, đối với những bộ số liệu lớn, việc xác định
chính xác số k và chọn chùm khởi tạo như thế nào là một vấn đề khó khăn. Vì kết quả của
thuật toán không thứ bậc đặc biệt đối với những bộ số liệu lớn phụ thuộc nhiều vào việc
chọn số chùm k và cách chọn các phần tử vào chùm khởi tạo nên vấn đề này được quan
tâm rất nhiều. Có nhiều phương pháp được áp dụng để tìm số chùm được đưa ra như dựa
vào kiến thức tiên nghiệm về tập dữ liệu hay so sánh các hệ số tương quan phân vùng, chỉ
số phân vùng, chỉ số Xie-Beni của các trường hợp với các số k khác nhau. Tuy nhiên,
việc tính các chỉ số này được thực hiện sau khi đã phân tích bộ số liệu thành các trường
hợp k chùm khác nhau, điều này làm cho việc tính toán trở nên cồng kềnh, kém hiệu quả.
Mặt khác, việc áp dụng các phương pháp này chỉ có thể xác định gần đúng k mà lại
không xác định được nên chọn chùm khởi tạo như thế nào để việc tính toán là tối ưu,
không trải qua nhiều vòng lặp. Phần này của luận văn sẽ trình bày một phương pháp mới
15
được Hung và Wen Liang đưa ra gọi là phương pháp “tự động cập nhật” SU (self
update). Phần chứng minh tính đúng đắn và hiệu quả của phương pháp đã được trình bày
trong [6], trong luận văn chỉ trình bày thuật toán SU và ví dụ minh họa.
V v1 ,v2 ,...vN
X x1 ,x2 ,...xN
t
t
t
t
Gọi
là dãy N điểm dữ liệu,
là dãy N trọng
tâm của chùm mà N điểm dữ liệu đó thuộc. Thuật toán SU được trình bày như sau:
Bước 1: Khi
t 0
V v1 ,v2 ,...vN
0
, khởi tạo
0
0
0
=
X = x1 ,x2 ,...xN 0
,
rất
nhỏ.
Bước 2: Cập nhật dãy trọng tâm theo công thức:
�K v , v .v
N
vi
t 1
t
t
j
i
j 1
�K v
N
j 1
t
i
t
i
t
,vj
Trong công thức trên,
ds
Với
, i 1, ..., N
(1.12)
d�
��
�
�
� �
�
e
khi d d vi , v j �d s
K �
�
0 khi d d s
�
1
�d i, j
Cn2 i j
là trung bình các khoảng cách của các điểm dữ liệu và
ds
10
.
max d vi ,vi
Bước 3: Lặp lại bước 2 cho đến khi
i
t
t+1
<ε
.
Ví dụ 1.5. Thực hiện lại ví dụ 1.4 với thuật toán SU để tìm chùm khởi tạo
d s 4.83
0.483
A
B
Với dữ liệu đã cho, ta tính được
và
2, ta lần lượt có kết quả được cho trong bảng sau:
Bảng 1.4: Kết quả các vòng lặp thuật toán SU
Trọng tâm của chùm
chứa phần tử
16
. Áp dụng công thức ở bước
C
D
Vòng lặp 0
Vòng lặp 1
Vòng lặp 2
Vòng lặp 3
Vòng lặp 4
Vòng lặp 5
Vòng lặp 6
Vòng lặp 7
Vòng lặp 8
Vòng lặp 9
Vòng lặp 10
Vòng lặp 11
Vòng lặp 12
Vòng lặp 13
Vòng lặp 14
Vòng lặp 15
1.00
1.11
1.24
1.37
1.47
1.50
1.50
1.50
1.50
1.50
1.50
1.50
1.50
1.50
1.50
1.50
2.00
1.89
1.76
1.63
1.53
1.50
1.50
1.50
1.50
1.50
1.50
1.50
1.50
1.50
1.50
1.50
7.00
7.03
7.07
7.10
7.15
7.20
7.25
7.32
7.39
7.48
7.49
7.72
7.85
7.96
8.00
8.00
9.00
8.97
8.93
8.90
8.85
8.80
8.75
8.68
8.61
8.52
8.51
8.28
8.15
8.04
8.00
8.00
Như vậy, sau 15 vòng lặp, ta thấy trọng tâm của phần tử A và B hội tụ về 1.5, còn
trọng tâm của C và D hội tụ hội về 8.0 nên ta chọn chùm khởi tạo cho thuật toán không
A, B
C , D
thứ bậc gồm 2 chùm là
và
. Kết quả này cũng tương ứng với vòng lặp cuối
cùng của ví dụ 1.4, nghĩa là ta kết thúc thuật toán không thứ bậc chỉ với việc tính toán
khoảng cách giữa các phần tử đến trọng tâm của chùm mà không phải thực hiện vòng lặp
nào cả.
1.4 VẤN ĐỀ TÍNH TOÁN
Việc thực hiện thủ công các phương pháp phân tích chùm với các công thức phức
tạp là một vấn đề khó khăn, đặc biệt đối với các bộ số liệu lớn. Phần này của luận văn sẽ
trình bày các chương trình được viết trên phần mềm Matlab nhằm đưa bài toán phân tích
chùm trở nên dễ thực hiện và áp dụng trong thực tế nhiều hơn.
Chương trình 1.1 Phương pháp thứ bậc với khoảng cách min, max, trung bình,
ward
% Nhap chuoi so lieu
x = [chuoi phan tu];
% Tinh khoang cach va dua ve dang ma tran vuong
y=pdist(x,'euclide')
squareform(y)
% Phan tich chum phuong phap thu bac voi khoang cach trung binh
z=linkage(y,'single')
% Ve do thi
d=dendrogram(z,'colorthreshold','default')
17
set(d,'linewidth',2)
Nếu sử dụng khoảng cách max, trung bình, ward thì ta thay thế single lần lượt bằng
complete, average, ward.
Chương trình 1.2 Phương pháp không thứ bậc
% Khai báo chuoi cac phan tu
x= [chuoi phan tu]
% Nhap vao so k chum
k=so chum
% Thuc hien phan tich
[z c]=kmeans(x,k,'Distance','sqeuclide')
BÀI TOÁN ỨNG DỤNG
Kết quả thi học kì II các môn Khoa học tự nhiên (gồm toán, lí, hóa) của 13 lớp
khối 10 trường THPT Tân Quới. Nhà trường muốn biết mức độ tương đồng của các lớp
thông qua điểm thi của các môn này( Toán-biến X, Lí- biến Y, Hóa- biến Z) để có thể
phân bố lại lớp trong năm học sau.
Tổng quan việc thực hiện:
Số liệu: Số liệu được cung cấp bới phòng đào tạo trường THPT Tân Quới. Của 14
lớp khối 10 và điểm thi của 321 học sinh thuộc các lớp. Các lớp được mã hóa như sau:
1: Lớp 10A1
2: Lớp 10A2
3: Lớp 10A3
4: Lớp 10 A4
5 : Lớp 10 A5
6: Lớp 10A6
7: Lớp 10A7
8: Lớp 10A8
9: Lớp 10A9
10: Lớp 10A10
11: Lớp 10A11
12: Lớp 10A12
13: Lớp 10A13
18
14: Lớp 10A14
Phương pháp thực hiện: Trước tiên ta tính giá tri trung bình của mỗi nhóm rồi lấy
giá trị đó làm đại diện sau đó phân chùm các nhóm theo khoảng cach min, khoảng cách
max, khoảng cách ward rồi đưa ra kết luận định hướng phân bố cho nhà trường.
Phân tích chùm không mờ.
Phương pháp phân tích chùm theo thứ bậc
i ) Sử dụng khoảng cách Euclide giữa hai phần tử và khoảng cách min giữa hai chùm.
Theo thuật toán 1 quá trình tính toán theo các bước sau:
Bước 0: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
Bước 1: (79), 1, 2, 3, 4, 5, 6, 8, 10, 11, 12, 13, 14
Bước 2: (23), (79), 1, 4, 5, 6, 8, 10, 11, 12, 13,14
Bước 3: (112), (23), (79), 4, 5, 6, 8, 10, 11, 13, 14
Bước 4: (11210), (23), (79), 4, 5, 6, 8, 11, 13, 14
Bước 5: (7911), (11210), (23), 4, 5, 6, 8, 13, 14
Bước 6: (79115), (11210), (23), 4, 6, 8, 13, 14
Bước 7: (112108), (79115), (23), 4, 6, 13, 14
Bước 8: (11210814), (79115), (23), 4, 6, 13
Bước 9: (1121081413), (79115), (23), 4, 6
Bước 10: (236), (1121081413), (79115), 4
Bước 11: (2364), (1121081413), (79115)
Bước 12: (23641121081413), (79115)
Bước 13: (2364112108141379115)
19
Hình 1.6
ii) Sử dụng khoảng cách Euclide giữa hai phần tử và khoảng cách max giữa hai
chùm. Theo thuật toán 1 quá trình tính toán theo các bước sau:
Bước 0: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
Bước 1: (79), 1, 2, 3, 4, 5, 6, 8, 10, 11, 12, 13, 14
Bước 2: (23), (79), 1, 4, 5, 6, 8, 10, 11, 12, 13,14
Bước 3: (112), (23), (79), 4, 5, 6, 8, 10, 11, 13, 14
Bước 4: (7911), (23), (112), 4, 5, 6, 8, 10, 13, 14
Bước 5: (11210), (7911), (23), 4, 5, 6, 8, 13, 14
Bước 6: (814), (11210), (7911), (23), 4, 5 , 6, 13
Bước 7: (236), (814), (11210), (7911), 4, 5, 13
Bước 8: (791113), (236), (814), (11210), 4, 5
Bước 9: (11210814), (791113), (236), 4, 5
Bước 10: (7911135), (11210814), (236), 4
Bước 11: (2364), (7911135), (11210814)
Bước 12: (791113511210814), (2364)
Bước 13: (7911135112108142364)
20
- Xem thêm -
.DOCX 
62 
242 
68 
