Báo cáo thực tập SV: Nguyễn Quang Thắng SV: Nguyễn Quang Thắng
Chương I: Giới thiệu bài toán phân cụm và khai phá dữ liệu
I.Giới thiệu
II. Tách tuyến tính hoặc lồi
1.Tách tuyến tính.
2 .Tách toàn phương lồi.
III. Côm theo tâm
1.Trường hợp
.||),(
1
∑
=
−=
n
j
jj
xaxad
2.Trường hợp
.||||),(
1
2
∑
=
−=
n
j
jj
xaxad
3.Tối ưu đơn điệu.
IV. Côm theo siêu phẳng
V.Phõn cụm trên mặt phẳng và mặt cầu

Vi dô:
1.(Y học) Bệnh nhân là các dữ liệu vật lý về những bệnh nhân bị nghi ung thu vú và ta
muốn dùa và dữ liệu đú phõn cỏc đối tượng thành hai nhóm u lành và u ác.
2.(Kinh tế) Đối tượng là các dữ liệu tài chính về những doanh nghiệp đang hoạt động và
ta muốn dùa vào các dữ liệu Êy phõn cỏc đối tượng thành hai nhóm: Doanh nghiệp trên
đà thất bại và doanh nghiệp đang làm ăn bình thường.
Có nhiều cách tiếp cận khác nhau đối với vấn đề đó nờu: thống kê, máy móc, tối ưu,
trong đó cách tiếp cận tối ưu đã tỏ ra có hiệu quả hơn cả. Với bài toán này chúng ta tiếp
cận bài toán dùng tối ưu toàn cục.
II. Tách tuyến tính hoặc lồi
Bài toán đặt ra như sau: cho hai tập A={
r
aaa ,,,
21

} và B={
r
bbb ,,,
21

}, hóy tìm
một hàm
)(xf
thuộc một líp hàm cho trước
F
tách hai tập A,B, nghĩa là sao cho
1)(
1)(
>
<

)(1
i
af
−
.
Vậy trong mọi trường hợp, sai số xếp loại
i
a
bởi
)(xf
có thể đo bằng biểu thức:
{ }
1)(,0max:
−=
i
i
afy
.
Tương tự như thế sai số xếp loại
j
b
có thể đo bằng biểu thức:
{ }
1)(,0max:
+−=
j
i
bfz
.
Thành thử sai số xếp loại bởi hàm

}1)(,0max{
1
min{
11
∑∑
==
∈+−+−
s
j
j
r
i
i
Ffbf
s
af
r

Thông thường người ta xét trường hợp
F
là họ hàm tuyến tính hoặc toàn phương.
1.Tách tuyến tính. Vì
)(xf
chỉ cần xác định xê xích một hằng số nên ta chỉ xét những
hàm tuyến tính có dạng
0
,)( wxwxf
−=
với
+

j
i
i
s
j
j
r
i
i


Đây là một quy hoach tuyến tính thưo các biến
0
,,, wwyx
(biến chính là
0
, ww
). Người ta
đã áp dụng mô hình này để nghiên cứu việc chuẩn đoán ung thư vú (r+s=569, n ban đầu
là
1
30
, sau sử lý sơ bộ rỳt cũn 3). Kết hợp với một số kỹ thuật tính toán phụ, kết quả
đạt được cho thấy phù hợp thực tế đến 97.5%. Người ta cũng đã áp dụng mô hình này để
nghiên cứu phân loại các foanh nghiệp thất bại và bình thường (n=6). Kết quả phù hợp
với thực tế 92%(không kỹ thuật phụ nào khác).
2 .Tách toàn phương lồi. Họ
F
ở đây gồm những hàm có dạng
0,,)(



=+++−≥
=−−+≥
+
∑∑
==
n
BxxUx
∈∀≥
0,
(hình cầu đơn vị trong
n
R
)
00
≥≥
zy
Đây là một quy hoạch lồi, với hàm mục tiêu tuyến tính, và vô số rằng buộc tuyến tính.
Rằng buộc
0U
thường gọi là một bất đẳng thức ma trận tuyến tính (LMI). Người ta đã
áp dụng mô hình này để nghiên cứu phân loại doanh nghiệp thất bại và tiến triển bình
thường. Khi xét đến cả hàm mục tiêu lồi
∑∑
==
−+
s
j
j

+=
N
i
ii
QxQQ
1
0
, với
),,1,0( miRQ
mm
i

=∈
×
và ký hiệu
0
≥
Q
có nghĩa Q là ma trận nửa xác đinh dương.
Phương pháp xấp xỉ ngoài đã đề xuất để giải bài toán trên tỏ ra hữu hiệu khi n<10 (trường
hợp khá thường gặp trong một số ứng dụng, như đánh giá xác suất thất bại của các doanh
nghiệp).
Bài toán tách tuyến tính hoặc lồi cũng đã được áp dụng có kết quả trong nhiều nghiên cứu
về viễn thông (xử lý tỡn hiệu).
3
Báo cáo thực tập SV: Nguyễn Quang Thắng SV: Nguyễn Quang Thắng
III. Côm theo tâm
Bài toán đặt ra như sau: cho một tập hợp
nm
Raaa ⊆},,,{

=
(P)
Khi đã chọn cỏc tõm
k
xxx ,,,
21

thì tập
},,,{
21 m
aaa 
được chia thành k côm
k
CC ,,
1

trong đó
}.),(:{ lhxadaC
hii
l
≠∀=
Nếu ta coi mỗi
i
a
là trung tâm một khu
dân cư còn mỗi
l
x
là địa điểm xây dựng một cơ sở dịch vụ (bệnh viện, trường học,….)
thỡ đõy cũng là bài toán lùa chọn địa điểm xây dựng các cơ sở dịch vụ dao cho tỏng

ilil
il
k
l
il
iliiil
m
i
n
j
il
jkl
ttyt
kjmiyxayts
y
11
1 1
,,1
.1,0,
,,1,,,1.
)(minmin


(BLP)
sau đó giải (BLP) theo thuật toán: cố định biến t để giải quy hoạch tuyến tính theo y, rồi
cố định biến y để giải quy hoạch tuyến tính theo t, cứ thế luân phiên cố định t và y để giải
quy hoạch tuyến tính tương ứng, cho đến bao giê không cải tiến được lời giải nữa thì
dừng. Vì bài toán (P) còn có tên goi là bài toán k_median nên người ta đã gọi thuật toán
trên là k_median. Thật ra thuật toán này đã được biết đến từ lâu nhưng Ýt nhất được chú
ý vì chỉ cho một lời giải tối ưu địa phương, chứ chưa phải toàn cục. Tuy vậy thì kết quả

−−−=−
rl
li
k
l
kr
lili
kl
xaxaxa ||||max||||||||min
1
,,1
,,1


bài toán (P) có thể viết lại thành
4
Báo cáo thực tập SV: Nguyễn Quang Thắng SV: Nguyễn Quang Thắng
}.,,1,:||||max||||{min
1
,,1
11
,,1
klRxxaxa
nl
rl
li
m
i
kr
m

dùa vào lý thuyết tối ưu đơn điệu mới xây dựng gần đây. Dĩ nhiên
∑∑
==
−+=
n
j
j
n
j
j
xxxadxad
11
)),((),(
mà
∑
=
+=
n
j
j
xxadxau
1
),(:),(
và
∑
=
n
j
j
x

cũng là hàm d.m. Tóm lại (P2) có thể viết dưới dạng
}:)(max)(min{
1
,,1
kn
i
m
i
kl
i
Rxxhxg
×
+
=
=
∈−
∑

trong đó
∑
=
m
i
i
xg
1
)(
là hàm tuyến tính tăng, và
)(max
,,1

=
= 
đạt cực tiểu. Ở đây d(a,H) chỉ khoảng cách từ a đến siêu phẳng H. Khi đã chọn cỏc siờu
phẳng
k
HHH ,,,
21

thì tập
},,,{
21 m
aaa 
chia thành k côm
k
CC ,,
1

, trong đó
l
C
gồm các
i
a
gần
l
H
hơn tõt cả
h
H
với

=
∈=∈−
∑
RwwRwwwa
llnlli
m
i
kl 
(Q)
theo công thức
),0min(2|| ggg
−=
ta có
),,0min(2,|,|
000
llillilli
wwawwawwa
−−−=−
.
Đương nhiên có thể giả thiết
ni
Ra
++
∈
cho nên
lli
wwa
0
,
−

RwwRwwwa
llnlli
m
i
kl 
(Q’)
Phương pháp giải bài toán này dựa trờn sự kiện sau.
(*) Cho A là ma trận có hàng i là
ni
i
ReaA
∈==
)1,,1(, 
. Lời giải tối ưu của bài toán
}.1||||,),(:||min{||
2
0
2
0
=×∈−
wRRwwewAw
nTT
(3)
đạt cực tiểu tại một vectơ riêng bất kỳ w của ma trận
)(
m
ee
IAB
T
T

21

bất kỳ, dùa theo cỏc siờu phẳng đó chia
},,,{
21 m
aaa 
ra k cụm, rồi với mỗi cụm Êy
dùng (*) xác định siêu phẳng đạt cực tiểu tổng bình phương khoảng cách từ mỗi phần tử
trong cụm đến nó. Như vậy được một tập k siêu phẳng mới , và với tập k siêu phẳng này
lại lặp lại quá trình tính toán đó cho đến khi cải tiến hàm mục tiêu thêm nữa. Đương
nhiên lời giải theo phương pháp này chỉ là tối ưu địa phương. Tuy vậy ưu điểm của
phương pháp này là dễ tính toán. Thử nghiệm trên cơ sở dữ liệu dự báo ung thu vó cho
pháp xác định các đướng sống sót tách biệt hơn hẳn phương pháp tuyến tính trước đây.
V.Phõn cụm trên mặt phẳng và mặt cầu
Trở lại bài toán k-median (P) (Phân cụm theo k tâm) trong đó tập hợp cần phân cụm là
một tập hợp hữu hạn A=
nm
Raaa ⊆},,,{
21

. Mét câu hỏi nẩy ra: sẽ xẩy ra điều gì nẩu
tập A vô hạn chẳng hạn A là tập hợp các điểm trong một hình chữ nhật trong
2
R
và k rất
lớn?
Thật vậy tưởng tượng ta cần chọn địa điểm đặt k thùng thu hay trạm điện thoại công cộng
trong một thành phố lớn, mà dân cư dải đều trên một địa bàn a rất rộng. Khi Êy dân ở đâu
sẽ dùng thùng thư gần đó nhất, cho nên muốn tiết kiệm đường đi của dân ta phải giải một
bài toán k-median cho tập hợp A. Vì A vô hạn và k rất lớn nờn cỏc phương pháp trỡnh

x
khác. Rõ ràng
i
V
là một đa giác, có tên là ô Voronoi (hay ô Dirichlet). Sự phân
cụm chữ nhật A thành những ô Voronoi như vậy cũng gọi là biểu đồ Voronoi theo
k
xxx ,,,
21

. Có nhiều thuật toán hữu hiệu đã được đề cập tới trong hình học toán học để
xõy dựng biểu đồ Voronoi.
2. bài toán k-median liên tục. Ký hiệu
kk
Axxxx ∈= ),,,(
21

thì hàm mục tiêu ta
muốn tìm cực tiểu ở đây là
∑ ∑
∫
= =
=−=
k
i
k
i
i
v
i

tụt từ
0
x
xuống
1
x
;
5. 5 Dõng nếu
01
xx −
dủ nhỏ, nều khụn thỡ lặp lại
6. Phương pháp này chỉ cho một lời giải tối ưu địa phương, có thể chưa phải tối ưu toàn cục,
nhưng hiện nay chưa có phương pháp nào tụt hơn.
3.Phân bổ k điểm trên hình cầu. Sự kiện vừa rồi cho thấy mối liên hệ giữa vấn đề phân
cụm với bài toán phân bổ đều đặn một số lớn điểm trên một mặt cầu là một bài toán đăng
tạo nguồn cảm hứng không chỉ cho nhiều nhà toán học mà còn cho rất đông chuyên gia
vật lý, hoá học, sinh học làm việc trong những lĩnh vực rất khác nhau của khoa học hiện
đại
Số là trước đây mười lăm năm người ta phát hiện ra những phân tử ổn định cacbon- 60
với các nguyên tử sắp xếp trên một mặt cầu tựa như một quả bóng đá. Điều này đã dẫn
đến một loạt suy diễn thó vị trong khoa học. Trong tĩnh điện học, bài toán phân bổ vị trí
những điểm tích điện trên một mặt cầu sao cho đạt cân bằng theo định luật thế vị của
Coulomb là một bài toán khó được gọi là đối ngẫu với bài toán phân tử ổn định. Một bài
toán khác, cùng loại là xác định vị trí k điểm trên mặt cầu sao cho tớch cỏc khoảng cách
từng đôi là lớn nhất.
Một sự lạ đỏng chú ý là khi bố chí k điểm trên mặt cầu thưo một tiểu chuẩn tối ưu nào đó
thì chỉ trừ một Ýt đặc biệt của k (như k=2,3,6,12,24) cũn núi chung, bất kờt tiêu chuẩn tối
ưu nào, các cấu hình tối ưu cũng luôn theo đúng một kiểu như sau: k điểm Êy được bố trí
để tất cả cỏc ụ Voronoi lập thành đều là lục giác, chỉ trừ đúng 12 ô là ngũ giỏc.
Bài toán nói trên có quan hệ với bài toán các định k điểm

iji
ijij
kixxxtt 
.
9. Đây là một bài toán tối ưu d.c. nhưng cực khú vỡ cỡ quá lớn. Việc tìm ra một thuật giải
hữu hiệu là một thách thức lớn với các nhà toán học thế kỷ 21. Với các phương pháp hiện
có vẫn có thể có ý nghĩa là thử giải bài toán với những giá trị k nhá.
Chương II: Ý tưởng thuật toán
Bài toán đặt ra là cho n điểm trên mặt phẳng toạ độ hóy phõn n điểm đo ra thành các cụm
sao cho tổng các khoảng cách từ các điểm đến tâm cụm của nó nhỏ nhất là có thể. Với bài
toán đặt ra như trên có rất nhiều cách giải quyết khác nhau. Ở đây ta đề xuất một thuật
toán giải để quyết bài toán này, cách giải quyết này mang chỉ đem lại kết quả tối ưu cục
bộ nhưng nó có thể chạy được với dữ liệu lớn.
I. Cách giải quyết
Với tập hợp m điểm đã cho
},,,{
21 m
aaa 
ta tỡm tõm của các điểm đó như sau (Toạ độ
tâm cum):
m
Y
Y
m
x
X
m
i
i
m

},,,{
21 pkkk
aaa 
(gồm p điểm)
a. Tìm cạnh lớn nhất trong tập hợp các điểm
},,,{
21 pkkk
aaa 
. Giả sử là cạnh
},{
jkik
aa
b. Cho hai điểm đó làm hai tâm cum
c. Bắt đầu tối ưu hai cum đó như bước 2
Sau khi tối ưu hai cụm đó ta sẽ tiếp tục tối ưu n+1 cụm như bước 2. Ta chon cạnh lớn
nhất để chia tập hợp
},,,{
21 pkkk
aaa 
thành hai phần xa nhau nhõt, để rút ngắn được tối
đa khoảng cách.
Như vậy ở đây chúng ta cần tối ưu n cụm thì trước hết ta cần tối ưu n-1 cum đã. Với 1
cụm thì ta chỉ cầm tỡm tõm cụm.
II. Trường hợp gặp phải
1.Trong bước hai khi ta tối ưu k cụm có thể có cụm không có điểm nào khi Êy ta sẽ tìm
được k’ côm (k’<k) với kết quả vẫn tối ưu hơn. Vấn đề này sẽ được giải quyết vi sau đó
ta sẽ thực hiện tối ưu với k’+1 cụm như bước 3 chon đến khi k’=k thì thôi. Bài toán luôn
dừng vì mỗi lần ta sẽ thu được một kết quả tối ưu hơn kết quả trước đó mà tổng khoảng
cách từ các điểm tới tâm của nó luôn là số dương nờn nú không thể giảm mó quỏ 0 được.
2.Sau mỗi lần tối ưu thì cụm không có điểm nào có thể là điểm bất kỳ trong sè k cụm vây

d. Tính lại tâm cụm
e. Kiểm tra nếu còn tối ưu được thì quay lại bước c.
- Tỗi ưu tập hợp tâm cụm thu được
a . Xác định điểm nào gần tâm cụm nào cho vào cụm đó
b. Tính lại tâm cụm
c. Kiểm tra nếu còn tối ưu được thì quay lại bước a.
Bước 3: sắp xếp
Bước 4: Kiểm tra kết thúc nếu chưa kết thúc quay lại bước 2
II.Xõy dùng lớp.
Vì bài toán là mô phỏng thuật toán nên ta chỉ cần xây dựng một líp “PhanCum” như sau:
1.Các thuộc tính của đối tượng
- Ta có n điểm vậy cần có một mảng để lưu trữ các điểm. Với mỗi điểm cần xác
định tạo độ điểm đó và tâm cụm mà điểm đó thuộc vào.
- Ta có k tâm vậy cần một mảng tâm để lưu trữ cỏc tõm. với mỗi tâm ta cần xác
định toạ độ của tâm và những điểm thuộc tõm đú. Vỡ ở đây ta sắp xếp tăng
dần mảng điểm theo tâm cụm nên ta chỉ cần xác định điểm đầu và điểm cuụi
trong mảng điểm thuộc tâm
Cụ thể:
// Toạ độ điểm
struct TD
10
Báo cáo thực tập SV: Nguyễn Quang Thắng SV: Nguyễn Quang Thắng
{
int x,y;
};
//Phần tử điểm gồm toạ độ và điểm đó thuộc tâm cụm thứ mấy
struct DIEM
{
TD td;
int c;

double Tinh();
void SapXep();//Sắp xếp lại mảng diểm và cỏc tõm
int KTKT();//kiểm tra kết thúc hay chưa
void KQ();//In kết quả ra file.
//Tìm cụm có tổng khoảng cách từ các điểm thuộc cum tới tâm của nó là //max
int PhanCum::Tim()
{
int j=0;
for (int i=1;i<nx;i++)
if ((c[i].e>c[j].e) || ((c[i].e==c[j].e)&&(c[i].c-c[i].d>c[j].c-c[j].d))) j=i;
return j;
}
//tìm cạnh max ở cụm x sau đó khởi tạo tâm x và nx để chia côm x thành //hai cum tối
ưu nhất
void PhanCum::XDTam(int x)
{
int p,q;
p=0;q=1;
12
Báo cáo thực tập SV: Nguyễn Quang Thắng SV: Nguyễn Quang Thắng
for (int i=c[x].d;i<c[x].c-1;i++)
for (int j=i+1;j<c[x].c;j++)
if (KC(d[i].td,d[j].td)>KC(d[p].td,d[q].td))
{
p=i;
q=j;
}
c[x].td=d[p].td;
c[nx].td=d[q].td;
}

if (k2!=0)
{
c[x].td.x=int(x2/k2);
c[x].td.y=int(y2/k2);
}
if (k1!=0)
{
c[nx].td.x=int(x1/k1);
c[nx].td.y=int(y1/k1);
}
}
//Tính kết qủa sau mỗi lần tối ưu cum x thành hai cum x và nx
double PhanCum::Tinh(int x)
{
double E=0;
14
Báo cáo thực tập SV: Nguyễn Quang Thắng SV: Nguyễn Quang Thắng
for (int i=c[x].d;i<c[x].c;i++) E+=KC(d[i].td,c[d[i].c].td);
return E;
}
//Xác định lại nhóm cho tất cả các cụm từ 1 đến nx
void PhanCum::XDNhom()
{
for (int i=0;i<nd;i++)
{
d[i].c=0;
for (int j=1;j<=nx;j++)
if (KC(d[i].td,c[d[i].c].td)>KC(d[i].td,c[j].td)) d[i].c=j;
}
}

for (i=0;i<=nx;i++) E+=c[i].e;
return E;
}
//Đổi toạ độ sang toạ độ màn hình để vẽ cho trực quan
void PhanCum::SapXep()
{
for (int i=0;i<nd-1;i++)
for (int j=i+1;j<nd;j++)
if (d[i].c>d[j].c)
{
DIEM temp=d[i];
d[i]=d[j];
d[j]=temp;
16
Báo cáo thực tập SV: Nguyễn Quang Thắng SV: Nguyễn Quang Thắng
}
i=0;j=0;
int k=0;
long x=0,y=0;
do
{
if (d[j+1].c==d[j].c) {
d[j].c=i;
x+=d[j].td.x;
y+=d[j].td.y;
}
else {
d[j].c=i;
x+=d[j].td.x;
y+=d[j].td.y;

liệu cự thể.
- 5. Thoát.
Chương trình minh hoạ từng bước tối ưu, sau mỗi bước bạn Ên một phím bất kỳ để
xem bước tiếp theo.
Chương IV: Kết luận
I. Nhõn xột và đánh giá kết quả
Vơi các dữ liệu ngẫu nhiên:
18
Báo cáo thực tập SV: Nguyễn Quang Thắng SV: Nguyễn Quang Thắng
1.Sè điểm n=1000; Số cụm 10
2.Sè điểm n=2000; Số cụm 20;
3:Sè điểm n=3000; Số cụm 30;
19
Báo cáo thực tập SV: Nguyễn Quang Thắng SV: Nguyễn Quang Thắng
4.Nhõn xét
Với số điểm bố trí đều thỡ cỏc cụm phân bố rất đều giống như các tổ ong.
II. Kết luận
Bài toán phân cụm và khai phá dữ liệu là một bài toán hay và có nhiều cách giải
quết khác nhau, ở đây là một cách giải quyết mang tớnh chõt tham lam nửa đệ quy nhiều
hơn để mong đưa đến một kết quả tối ưu nhất. Bài toán ngày càng tối ưu hơn sau mỗi
bước lặp nờn nú sẽ dừng lại sau một số hữu han lần.
Cách giải quyết bài toán này chỉ mang lại kết quả tối ưu cô bé nhưng nó chạy
được dữ liệu rất lớn. Chương trình chạy ổn định. Với các dữ liệu nhỏ thỡ nú rất chính
xác.
Chóng ta so thể cải tiến một số đoạn chương trình để chương trình chạy nhanh
hơn như việc sắp xếp chúng ta có thể dùng quicksort hay dùng sắp xếp vun đống…
Ta có thể áp dụng bài toán này vào một số trường hợp tối ưu về khoảng cách như
việc bố trí các trường học hay bệnh viện sao cho dân di lại là tiện nhất về khoảng cách.

20