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算法
作为补充.
