??? K-Means算法的輸入N,K和一個size為N的向量組vector.輸出K個兩兩互不相交的向量組.其本質是將給定的向量組劃分成K個類別,使得同類別的向量相似度比較大,而不同類別的向量之間的相似度較小.
??? 比如以下這個圖,人肉眼能看出有四個點團,但計算機不知道,為了讓計算機明白這一點,可以將點的坐標提取到向量組中,而向量之間的相似度定義為點之間的距離的相反數或者倒數.從而將這些點分開.
??? 實現過程:
??? (1)從n個數據對象任意選擇k個對象作為初始聚類中心;
??? (2)根據每個聚類對象的均值(中心對象),計算每個對象與這些中心對象的距離,并根據最小距離重新對相應對象進行劃分;
??? (3)重新計算每個(有變化)聚類的均值(中心對象);
??? (4)計算標準測度函數,當滿足一定條件,如函數收斂時,則算法終止,如果條件不滿足則回到步驟(2).
??? 實際應用中的問題:
??? 事實上,我是一個做ACM的選手,所以我比較感興趣的是K-Means能否求得一個最優解.對于這樣一個問題:從N個點取出K個作為核心,定義兩個向量之間的相似度函數f(vector1,vector2),使得所有點與其所對應的核心的相似度之和最大.然而事實讓我大失所望,K-Means算法對種子點的選取十分敏感,不同的種子會導致不同的解.
#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
;
}
??? 運行結果如圖所示:
![數據挖掘十大經典算法[0]-K-Means算法_第1張圖片](http://img.it610.com/image/product/34108a0ded634a58aae46ddd7dde9304.png)
??? 另一個問題是算法的收斂速度,重新算了一下,結果如下圖所示:
![數據挖掘十大經典算法[0]-K-Means算法_第2張圖片](http://img.it610.com/image/product/569292dec04249759fcc14e8ff943318.png)
??? 這個結果讓我大吃一驚啊,每次迭代之后更新量都很小,而且最終的值(9259914.963696)跟第一個有意義的值(10352922.175732)相差并不是很多.后來我仔細想了一下,應該是跟輸入數據有關,我的數據完全是在一定范圍內隨機生成的,分布比較均勻,所以即使隨便選也可以得到相當不錯的效果,這是我生成數據的程序:
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程序,想法是先隨機生成K個核心,再在其周圍生成其他的點:
#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
;
}
??? 再重新運行一下,得到如下結果:
??? 可以看出,收斂的速度還是可以的,而且最終結果幾乎只有最初解得一半.
??? 初除此之外,還有一個重要問題,核心數K是作為輸入給定的,而在實際應用中是無法預知的.對此可以用
ISODATA算法
作為補充.
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
