浙江大学算法研究实验报告
数据挖掘
题目：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，M3，剥豆子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实验结果说明美好一天的心情说说
