浙江大学算法研究实验报告
数据挖掘
题目：K-means
一、实验内容………………………………………………………5
二、实验目的………………………………………………………7
三、实验方法………………………………………………………7
3.1软、硬件环境说明……………………………………………7
3.2实验数据说明…………………………………………………7
图3-1 ……………………………………………………………7
3.3实验参数说明/软件正确性测试……………………………7
四、算法描述………………………………………………………9
图4-1 ……………………………………………………………10
五、算法实现………………………………………………………11
5.1主要数据结构描述……………………………………………11
图5-1 ……………………………………………………………11
有一种甜作文5.2核心代码与关键技术说明……………………………………11
5.3算法流程图……………………………………………………14
六、实验结果………………………………………………………15
6.1实验结果说明…………………………………………………15
6.2实验结果比较…………………………………………………21
七、总结……………………………………………………………23
一、实验内容
实现K-means算法，其中该算法介绍如下：
k-means算法是根据聚类中的均值进行聚类划分的聚类算法。
输入：聚类个数k，以及包含n个数据对象的数据。
输出：满足方差最小标准的k个聚类。
处理流程：
Step 1. 从n儿童故事大王个数据对象任意选择k个对象作为初始聚类中心；
Step 2. 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分；
Step 3. 重新计算每个（有变化）聚类的均值（中心对象）
Step 4. 循环Step 2到Step 3直到每个聚类不再发生变化为止；
k-means算法的工作过程说明如下：首先从n个数据对象任意选择k个对象作为初始聚类中心，而对于所剩下的其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类。然后，再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值），不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具体定义如下：
(1)
其中E为数据库中所有对象的均方差之和，p为代表对象的空间中的一个点，mi为聚类Ci的均值(p和mi均是多维的)。公式(1)所示的聚类标准，旨在使所获得的k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
重点要求：用于聚类的测试级不能仅为单独的一类属性，至少有两种属性值参与聚类。
二、实验目的
通过实现K-means算法，加深对课本上聚类算法的理解，并对数据集做出较高的要求，以期锻炼我们的搜索查找能力。最后自己实现K-means算法，可以加强我们的编程能力。
三、实验方法
3.1软、硬件环境说明
采用win7旗舰版（盗版）系统，用vs2010实现
3.2实验数据说明
实验数据，源于google的广告关键词推荐页面，在该页面输入关键词，会出现与该关键词相关的一些信息，包括月均搜索量，关键词价值等等，取出来在经过自己处理，就得到了我们需要的实验数据，包括关键词、月均搜索量、竞争力、估价以及关键词排名，包含两种属性。部分数据如下：
图3-1
3.3实验参数说明/软件正确性测试
我采用了各种数据对程序进行测试，出现一些数组越界bug，修改后再次测试，无问题，测试通过。
四、算法描述
KMeans算法的基本思想是初始随机给定K个簇中心，按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某个给定的值。
K-Means聚类算法主要分为三个步骤：
(1)第一步是为待聚类的点寻找聚类中心
(2)第二步是计算每个点到聚类中心的距离，将每个点聚类到离该点最近的聚类中去
(3)第三步是计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心
反复执行(2)、(3)，直到聚类中心不再进行大范围移动或者聚类次数达到要求为止
下图展示了对n个样本点进行K-means聚类的效果，这里k取2：
(a)未聚类的初始点集
(b)随机选取两个点作为聚类中心
(c)计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去
(d)计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心
(e)重复(c),计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去
(f)重复(d),计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心
图4-1
五、地球小卫士算法实现
5.1主要数据结构描述
这里我建造了一个data的结构体，如下：
typedef vector<double> Tuple;//存储每条数据记录
struct data
{
string s;// 存储关键词
Tuple tup;// 存储属性信息
};
图5-1
5.2核心代码与关键技术说明
5.2.1计算距离函数
此函数用于计算两个元祖之间的距离，对于每个元祖的属性值，对于数值型的属性值（X1，X2，X3，Xi，Xn）,我们用女生短头发Yi代替Xi来进行归一化处理，其中Yi计算公式如下：
Yi=（Xi- Xmin）/（Xmax-Xmin）
对于序数型属性值（M1，M2，M塞文河3，Mi，Mn）, 我们用Qi代替Mi进行归一化处理，其中Qi计算公式如下：
Qi=（Z（Qi）-1）/（Z（Total）-1）
其中Z（Qi）表示Qi属于的组数，Z（Total）表示总共的组数，他们的计算规则如下：
Z（Total）= k
Z（Qi）= Qi/（dataNum/k）+1
（其中dataNum为总数据量，K为总分组数。）
归一化处理之后，在计算两个元祖之间的欧式几何距离，具体实现代码如下：
double getDistXY(const data &t1, const data &t2)
{
double sum = 0,temp1=0,temp2=0,temp3=0,temp4=0;
int zuBa,zu1,zu2; //确定分组依据
zuBa=dataNum/k;江村晚眺古诗
zu1=t1.tup[4]/zuBa+1; //确定分组
zu2=t2.tup[4]/zuBa+1;
temp3=(zu1-1)/6;
if(temp3>1)
temp3=1;
temp4=(zu2-1)/6;
if(temp4>1)
temp4=1;//修正序数度量
temp1=(t1.tup[1]-10)/367990;
temp2=(t2.tup[1]-10)/367990;
sum+=(temp1-temp2)*(temp1-temp2)+(temp3-temp4)*(temp3-temp4);
for(int i=2; i<dimNum-1; ++i)
{
sum += (t1.tup[i]-t2.tup[i]) * (t1.tup[i]-t2.tup[i]);
}
return sqrt(sum);
}
5.2.2重新分簇
对于每个簇，算出当前每个元祖与各个质心间的距离，重新判定该元组属于哪一个簇，代码如下：
int clusterOfTuple(data means[],const data& tuple){
double dist=getDistXY(means[0],tuple);
double tmp;
int label=0;//标示属于哪一个簇
for(int i=1;i<k;i++){
tmp=getDistXY(means[i],tuple);
if(tmp<dist) {dist=tmp;label=i;}
}
return label;
}
5.3算法流程图
六、 实验结果
6.1实验结果说明贝壳漫岛
进过归一化操作聚类效果比较明显，可以看到大家对股票的哪一方面比较关心,并且给广告投资商一些参考，帮助其决定把广告投到哪一个关键词上，进而得到的关注量最大同时花费最少。同时，考虑到结果的聚类性，用户搜索某个关键词时，可以推荐给他同一个簇内其他的关键词。具体实验结果如下形容词顺序：
第1个簇：
关键词 编号 搜索量 竞争价值 估价 排名
股票学习网 8 20 0.11 27.19 193
股票初学 15 20 0.16 22.41 171
指数股票 16 20 0.07 26.66 191
怎样看股票 18 20 0.14 18.93 155
股票入门教程 30 20 0.11 17.5 149
购买股票 31 20 0.2 23.75 180
股票交流 35 30 0.11 19.17 160
中国股市论坛 44 30 0.16 23.98 182
上海股票指数 50 30 0.04 29.41 196
股票开户流程 54 30 0.1 25.71 187
股票怎么看 56 30 0.1 19.84 164
