??? K-Means算法的輸入N,K和一個(gè)size為N的向量組vector.輸出K個(gè)兩兩互不相交的向量組.其本質(zhì)是將給定的向量組劃分成K個(gè)類別,使得同類別的向量相似度比較大,而不同類別的向量之間的相似度較小.
??? 比如以下這個(gè)圖,人肉眼能看出有四個(gè)點(diǎn)團(tuán),但計(jì)算機(jī)不知道,為了讓計(jì)算機(jī)明白這一點(diǎn),可以將點(diǎn)的坐標(biāo)提取到向量組中,而向量之間的相似度定義為點(diǎn)之間的距離的相反數(shù)或者倒數(shù).從而將這些點(diǎn)分開.
??? 實(shí)現(xiàn)過程:
??? (1)從n個(gè)數(shù)據(jù)對象任意選擇k個(gè)對象作為初始聚類中心;
??? (2)根據(jù)每個(gè)聚類對象的均值(中心對象),計(jì)算每個(gè)對象與這些中心對象的距離,并根據(jù)最小距離重新對相應(yīng)對象進(jìn)行劃分;
??? (3)重新計(jì)算每個(gè)(有變化)聚類的均值(中心對象);
??? (4)計(jì)算標(biāo)準(zhǔn)測度函數(shù),當(dāng)滿足一定條件,如函數(shù)收斂時(shí),則算法終止,如果條件不滿足則回到步驟(2).
??? 實(shí)際應(yīng)用中的問題:
??? 事實(shí)上,我是一個(gè)做ACM的選手,所以我比較感興趣的是K-Means能否求得一個(gè)最優(yōu)解.對于這樣一個(gè)問題:從N個(gè)點(diǎn)取出K個(gè)作為核心,定義兩個(gè)向量之間的相似度函數(shù)f(vector1,vector2),使得所有點(diǎn)與其所對應(yīng)的核心的相似度之和最大.然而事實(shí)讓我大失所望,K-Means算法對種子點(diǎn)的選取十分敏感,不同的種子會(huì)導(dǎo)致不同的解.
#include<math.h>
#include
<stdio.h>
#include
<
string
.h>
#define
Convergence (fabs(last-cur)<1e-8)
#define
dist(a,b) (sqrt((x[a]-px[b])*(x[a]-px[b])+(y[a]-py[b])*(y[a]-py[b])))
int
x[
50000
],y[
50000
],qx[
50000
],qy[
50000
],px[
100
],py[
100
],assign[
50000
];
int
main()
{
freopen(
"
data.txt
"
,
"
r
"
,stdin);
FILE
*fp=fopen(
"
output.txt
"
,
"
w
"
);
int
N,K,i,j,k;
double
ave=
0
,MIN=
1e15;
scanf(
"
%d%d
"
,&N,&
K);
for
(i=
1
;i<=N;i++) scanf(
"
%d%d
"
,&x[i],&
y[i]);
for
(
int
asd=
0
;asd<N;asd++
)
{
printf(
"
Executing case #%d\n
"
,asd);
if
(asd) printf(
"
Current Average:%.6lf\n
"
,ave/
asd);
printf(
"
Current Minimize:%.6lf\n
"
,MIN);
printf(
"
----------------------------------------\n
"
);
fprintf(fp,
"
Executing case #%d\n
"
,asd);
if
(asd) fprintf(fp,
"
Current Average:%.6lf\n
"
,ave/
asd);
fprintf(fp,
"
Current Minimize:%.6lf\n
"
,MIN);
fprintf(fp,
"
----------------------------------------\n
"
);
for
(i=
1
;i<=K;i++
)
{
px[i]
=x[(i+asd)%N+
1
];
py[i]
=y[(i+asd)%N+
1
];
}
double
last=1e15,cur=
0
;
while
(!
Convergence)
{
printf(
"
%.6lf\n
"
,last);
last
=
cur;
for
(i=
1
;i<=N;i++
)
{
double
Min=
1e15;
int
v;
for
(j=
1
;j<=K;j++
)
{
double
d=
dist(i,j);
if
(d<
Min)
{
Min
=
d;
v
=
j;
}
}
assign[i]
=
v;
}
for
(i=
1
;i<=K;i++
)
{
int
cnt=
0
;
for
(j=
1
;j<=N;j++
)
if
(assign[j]==
i)
{
qx[
++cnt]=
x[j];
qy[ cnt ]
=
y[j];
}
double
Min=
1e15;
int
v;
for
(j=
1
;j<=cnt;j++
)
{
double
tmp=
0
;
for
(k=
1
;k<=cnt;k++
)
tmp
+=(sqrt((qx[j]-qx[k])*(qx[j]-qx[k])+(qy[j]-qy[k])*(qy[j]-
qy[k])));
if
(tmp<
Min)
{
Min
=
tmp;
v
=
j;
}
}
px[i]
=
qx[v];
py[i]
=
qy[v];
}
cur
=
0
;
for
(i=
1
;i<=N;i++) cur+=
dist(i,assign[i]);
}
ave
+=
cur;
MIN
=MIN<cur ?
MIN:cur;
}
printf(
"
Total average:%.6lf\n
"
,ave/
N);
printf(
"
Total MIN:%.6lf\n
"
,MIN);
fprintf(fp,
"
Total average:%.6lf\n
"
,ave/
N);
fprintf(fp,
"
Total MIN:%.6lf\n
"
,MIN);
return
0
;
}
??? 運(yùn)行結(jié)果如圖所示:
![數(shù)據(jù)挖掘十大經(jīng)典算法[0]-K-Means算法_第1張圖片](http://img.it610.com/image/product/34108a0ded634a58aae46ddd7dde9304.png)
??? 另一個(gè)問題是算法的收斂速度,重新算了一下,結(jié)果如下圖所示:
![數(shù)據(jù)挖掘十大經(jīng)典算法[0]-K-Means算法_第2張圖片](http://img.it610.com/image/product/569292dec04249759fcc14e8ff943318.png)
??? 這個(gè)結(jié)果讓我大吃一驚啊,每次迭代之后更新量都很小,而且最終的值(9259914.963696)跟第一個(gè)有意義的值(10352922.175732)相差并不是很多.后來我仔細(xì)想了一下,應(yīng)該是跟輸入數(shù)據(jù)有關(guān),我的數(shù)據(jù)完全是在一定范圍內(nèi)隨機(jī)生成的,分布比較均勻,所以即使隨便選也可以得到相當(dāng)不錯(cuò)的效果,這是我生成數(shù)據(jù)的程序:
program
makedata;
var
i,N,K:longint;
begin
assign(output,
'
data.txt
'
);
rewrite(output);
randomize;
N:
=random(
10000
);
K:
=random(
10000
);
writeln(N,
'
'
,K);
for
i:=
1
to
N
do
writeln(random(
10000
),
'
'
,random(
10000
));
close(output);
end
.
??? 于是我重新寫了makedada程序,想法是先隨機(jī)生成K個(gè)核心,再在其周圍生成其他的點(diǎn):
#include<stdio.h>
#include
<time.h>
#include
<math.h>
#include
<stdlib.h>
int
main()
{
srand(unsigned(time(
0
)));
freopen(
"
data.txt
"
,
"
w
"
,stdout);
printf(
"
15000 15\n
"
);
for
(
int
i=
1
;i<=
15
;i++
)
{
int
X=rand()%
1000000
,Y=rand()%
1000000
;
for
(
int
j=
1
;j<=
1000
;j++
)
{
int
dx=rand()%
10000
,dy=rand()%
10000
;
if
(rand()&
1
) dx*=-
1
;
if
(rand()&
1
) dy*=-
1
;
printf(
"
%d %d\n
"
,X+dx,Y+
dy);
}
}
return
0
;
}
??? 再重新運(yùn)行一下,得到如下結(jié)果:
??? 可以看出,收斂的速度還是可以的,而且最終結(jié)果幾乎只有最初解得一半.
??? 初除此之外,還有一個(gè)重要問題,核心數(shù)K是作為輸入給定的,而在實(shí)際應(yīng)用中是無法預(yù)知的.對此可以用
ISODATA算法
作為補(bǔ)充.
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
