数据挖掘关于kmeans算法的研究(含数据集)

1、 浙江大学算法研究实验报告数据挖掘题目：K-means 目录一、实验内容5二、实验目的7三、实验方法73.1软、硬件环境说明73.2实验数据说明7图3-1 73.3实验参数说明/软件正确性测试7四、算法描述9图4-1 10五、算法实现115.1主要数据结构描述11图5-1 115.2核心代码与关键技术说明115.3算法流程图14六、实验结果156.1实验结果说明156.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个数据对象任意选

2、择k个对象作为初始聚类中心，而对于所剩下的其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类。然后，再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值），不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具体定义如下： (1)其中E为数据库中所有对象的均方差之和，p为代表对象的空间中的一个点，mi为聚类Ci的均值(p和mi均是多维的)。公式(1)所示的聚类标准，旨在使所获得的k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。重点要求：用于聚类的测试级不能仅为单独的一类属性，至少有两种属性值参与聚类。二、 实验目的通过实现K-means算法，加深对课本上聚类算法的理解，并对数据集做出较高的要求，以期锻炼我们的搜索查找能力。最后自己实现K-means算法，可以加强我们的编程能力。三、 实验方法3.1软、硬件环境说明采用win7旗舰版（盗版）系统，用vs2010实现3.2实验数据说明实验数据，源于google的广告关键词推荐页面，在该页面输入关键词，会出现与该关键词相关的一些信息，包

3、括月均搜索量，关键词价值等等，取出来在经过自己处理，就得到了我们需要的实验数据，包括关键词、月均搜索量、竞争力、估价以及关键词排名，包含两种属性。部分数据如下：图3-13.3实验参数说明/软件正确性测试我采用了各种数据对程序进行测试，出现一些数组越界bug，修改后再次测试，无问题，测试通过。四、 算法描述KMeans算法的基本思想是初始随机给定K个簇中心，按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某个给定的值。K-Means聚类算法主要分为三个步骤：(1)第一步是为待聚类的点寻找聚类中心(2)第二步是计算每个点到聚类中心的距离，将每个点聚类到离该点最近的聚类中去(3)第三步是计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心反复执行(2)、(3)，直到聚类中心不再进行大范围移动或者聚类次数达到要求为止 下图展示了对n个样本点进行K-means聚类的效果，这里k取2：(a)未聚类的初始点集(b)随机选取两个点作为聚类中心(c)计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去(d)计算每

4、个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心(e)重复(c),计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去(f)重复(d),计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心 图4-1五、 算法实现5.1主要数据结构描述这里我建造了一个data的结构体，如下：typedef vector Tuple;/存储每条数据记录struct datastring s;/ 存储关键词Tuple tup;/ 存储属性信息;关键词属性1属性2属性3.属性n图5-15.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）表示总共的组数，他们的计算规则如下

5、：Z（Total）= kZ（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 zuBase,zu1,zu2; /确定分组依据zuBase=dataNum/k;zu1=t1.tup4/zuBase+1;/确定分组zu2=t2.tup4/zuBase+1;temp3=(zu1-1)/6;if(temp31)temp3=1;temp4=(zu2-1)/6;if(temp41)temp4=1;/修正序数度量temp1=(t1.tup1-10)/367990;temp2=(t2.tup1-10)/367990;sum+=(temp1-temp2)*(temp1-temp2)+(temp3-temp4)*(temp3-temp4);for(int i=2; idimNum-1; +i)sum +

6、= (t1.tupi-t2.tupi) * (t1.tupi-t2.tupi);return sqrt(sum);5.2.2重新分簇对于每个簇，算出当前每个元祖与各个质心间的距离，重新判定该元组属于哪一个簇，代码如下：int clusterOfTuple(data means,const data& tuple)double dist=getDistXY(means0,tuple);double tmp;int label=0;/标示属于哪一个簇for(int i=1;ik;i+)tmp=getDistXY(meansi,tuple);if(tmp1?根据每个元祖和质心的距离产生簇根据每个元祖和新质心的距离产生新簇打印输出并输出结果到文件结束是否六、 实验结果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 股票投资入门 62 40 0.23 21.38 170 美国股票软件 67 40 0.28 20.74 168 虚拟股票 72 40

《数据挖掘关于kmeans算法的研究(含数据集)》由会员n****分享，可在线阅读，更多相关《数据挖掘关于kmeans算法的研究(含数据集)》请在金锄头文库上搜索。