数据挖掘关于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个数据对象的数据。 输出：满足方差最小标

2、准的k个聚类。处理流程：Step 1. 从n个数据对象任意选择k个对象作为初始聚类中心；Step 2. 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分；Step 3. 重新计算每个（有变化）聚类的均值（中心对象）Step 4. 循环Step 2到Step 3直到每个聚类不再发生变化为止；k-means算法的工作过程说明如下：首先从n个数据对象任意选择k个对象作为初始聚类中心，而对于所剩下的其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类。然后，再计算每个所获新聚类的聚类中心（该聚

3、类中所有对象的均值），不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具体定义如下： (1)其中E为数据库中所有对象的均方差之和，p为代表对象的空间中的一个点，mi为聚类Ci的均值(p和mi均是多维的)。公式(1)所示的聚类标准，旨在使所获得的k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。重点要求：用于聚类的测试级不能仅为单独的一类属性，至少有两种属性值参与聚类。二、 实验目的通过实现K-means算法，加深对课本上聚类算法的理解，并对数据集做出较高的要求，以期锻炼我们的搜索查找能力。最后自己实现K-means算法，可以加强我们的编程能

4、力。三、 实验方法3.1软、硬件环境说明采用win7旗舰版（盗版）系统，用vs2010实现3.2实验数据说明实验数据，源于google的广告关键词推荐页面，在该页面输入关键词，会出现与该关键词相关的一些信息，包括月均搜索量，关键词价值等等，取出来在经过自己处理，就得到了我们需要的实验数据，包括关键词、月均搜索量、竞争力、估价以及关键词排名，包含两种属性。部分数据如下：图3-13.3实验参数说明/软件正确性测试我采用了各种数据对程序进行测试，出现一些数组越界bug，修改后再次测试，无问题，测试通过。四、 算法描述KMeans算法的基本思想是初始随机给定K个簇中心，按照最邻近原则把待分类样本点分到

5、各个簇。然后按平均法重新计算各个簇的质心，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某个给定的值。K-Means聚类算法主要分为三个步骤：(1)第一步是为待聚类的点寻找聚类中心(2)第二步是计算每个点到聚类中心的距离，将每个点聚类到离该点最近的聚类中去(3)第三步是计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心反复执行(2)、(3)，直到聚类中心不再进行大范围移动或者聚类次数达到要求为止 下图展示了对n个样本点进行K-means聚类的效果，这里k取2：(a)未聚类的初始点集(b)随机选取两个点作为聚类中心(c)计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去(

6、d)计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心(e)重复(c),计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去(f)重复(d),计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心 图4-1五、 算法实现5.1主要数据结构描述这里我建造了一个data的结构体，如下：typedef vector<double> Tuple;/存储每条数据记录struct datastring s;/ 存储关键词Tuple tup;/ 存储属性信息;关键词属性1属性2属性3.属性n图5-15.2核心代码与关键技术说明5.2.1计算距离函数此函数用于计算两个元

7、祖之间的距离，对于每个元祖的属性值，对于数值型的属性值（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）= kZ（Qi）= Qi/（dataNum/k）+1（其中dataNum为总数据量，K为总分组数。）归一化处理之后，在计算两个元祖之间的欧式几何

8、距离，具体实现代码如下：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(temp3>1)temp3=1;temp4=(zu2-1)/6;if(temp4>1)temp4=1;/修正序数度量temp1=(t1.

9、tup1-10)/367990;temp2=(t2.tup1-10)/367990;sum+=(temp1-temp2)*(temp1-temp2)+(temp3-temp4)*(temp3-temp4);for(int i=2; i<dimNum-1; +i)sum += (t1.tupi-t2.tupi) * (t1.tupi-t2.tupi);return sqrt(sum);5.2.2重新分簇对于每个簇，算出当前每个元祖与各个质心间的距离，重新判定该元组属于哪一个簇，代码如下：int clusterOfTuple(data means,const data& tuple)

10、double dist=getDistXY(means0,tuple);double tmp;int label=0;/标示属于哪一个簇for(int i=1;i<k;i+)tmp=getDistXY(meansi,tuple);if(tmp<dist) dist=tmp;label=i;return label;5.3算法流程图开始获取维数并从文件中读入数据打印所有数据进入K-means算法随机生成k个质心计算每个簇的均值M1根据均值产生新的质心计算新簇的均值M2|M2-M1|>1?根据每个元祖和质心的距离产生簇根据每个元祖和新质心的距离产生新簇打印输出并输出结果到文件结束

11、是否六、 实验结果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.1

12、1 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 0.13 30.66 199 股票市盈率 81 50 0.07 24.42 184 股市走势 86 50 0.1 17.05

13、 145 查股票 90 50 0.21 17.02 143 股票公式 102 70 0.07 20.73 167 如何购买股票 104 70 0.17 19.73 163 航空股票 105 70 0.12 19 157 股票买卖 109 70 0.24 22.86 173 中国远洋股票 111 70 0.05 30.55 198 模拟股票 114 70 0.14 27.89 194 股票走势 117 70 0.11 21.33 169 股票基础知识 119 70 0.11 24.16 183 股票公司 125 90 0.36 17.04 144 股票交易费用 129 90 0.13 24.47

14、 185 中国铁建股票 131 90 0.09 19.05 158 股票分析软件 132 90 0.24 22.7 172 新手股票 141 110 0.18 23.92 181 谷歌股票 142 110 0.04 20.07 165 股票网 161 140 0.2 17.47 148 中国中铁股票 164 140 0.06 27.17 192 怎么买股票 165 140 0.19 17.86 152 股票技术分析 168 140 0.07 19.37 162 中国联通股票 172 170 0.05 25.72 188 搜狐股票 173 170 0.06 19.08 159 新浪财经股票首页

15、174 170 0.03 23.3 176 香港股票查询 183 210 0.48 23.4 177 股票交易时间 189 210 0.06 30.44 197 股票交易所 190 210 0.17 30.78 201 股票行 194 210 0.49 17.17 146 如何看股票 196 210 0.11 18.66 154 基金股票 197 210 0.21 18.98 156 股指 198 210 0.04 30.73 200 百度股票 202 260 0.05 32.88 204 股票行情查询 205 260 0.04 22.86 174 股票投资 212 320 0.32 25.6

16、4 186 股票網 214 320 0.38 20.35 166 股票知识 215 320 0.12 17.18 147 股票新手 228 390 0.23 23.69 179 股票交易 233 590 0.31 31.86 203 股票软件 234 590 0.2 29.04 195 新加坡股票 235 590 0.35 18.01 153 股票入门 242 880 0.15 26.05 189 中国股票 248 1300 0.11 30.84 202 炒股 250 1900 0.15 26.28 190 gushi 252 2400 0.01 19.18 161 香港股票 254 2400

17、 0.46 23.26 175 新浪股票 256 2900 0.05 17.71 151 港股 260 6600 0.21 23.52 178 股市 266 368000 0.01 17.51 150 第2个簇：关键词 编号 搜索量 竞争价值 估价 排名 股票模拟软件 24 20 0.13 75.05 237 股票自动交易软件 26 20 0.13 77.44 239 新浪股票博客 36 30 0.06 80.16 240 股票怎么买 73 40 0.21 92.89 248 股票技巧 80 50 0.23 85.53 244 新股票 89 50 0.11 68.96 235 股票书 92 5

18、0 0.06 89.06 246 联通股票 93 50 0.03 104.99 252 股票基本知识 107 70 0.09 68.56 234 股票大盘 127 90 0.1 103.13 251 股票研究 133 90 0.11 80.77 241 中国重工股票 138 90 0.1 90.51 247 中国股票行情 148 110 0.07 76.05 238 股票网上开户 159 140 0.1 103.04 250 股票交易手续费 166 140 0.12 85.11 243 石油股票 191 210 0.18 93.22 249 台湾股票 200 210 0.23 71.25 23

19、6 澳洲股票 218 390 0.21 85.95 245 新浪股市 223 390 0.04 84.8 242 第3个簇：关键词 编号 搜索量 竞争价值 估价 排名 江苏阳光股票 29 20 0.1 154.15 262 今日股市行情大盘 49 30 0.12 117.53 253 怎么玩股票 52 30 0.1 133.11 257 银行股票 68 40 0.11 123.23 254 股票计算器 74 40 0.1 144.89 259 股票频道 101 70 0.04 130.46 255 a股大盘 126 90 0.06 174.74 264 证券股 137 90 0.03 150.

20、32 260 中国石化股票 158 140 0.01 142.11 258 st股票 169 140 0.05 168.23 263 民生银行股票 193 210 0.06 130.61 256 招商银行股票 210 320 0.03 152.85 261 第4个簇：关键词 编号 搜索量 竞争价值 估价 排名 美国股票交易软件 2 10 0.32 4.65 34 股票价格查询 4 10 0.09 1.83 11 投资美国股票 5 10 0.38 0.1 1 股票书籍下载 6 10 0.12 5.8 44 股票趋势 11 20 0.11 6.95 55 股市投资 12 20 0.29 2.82

21、16 股票怎么开户 13 20 0.16 0.68 4 股票下载 17 20 0.2 3.4 20 世界股市行情 19 20 0.13 0.18 3 加拿大股票交易 21 20 0.17 4.29 32 怎么买美国股票 22 20 0.28 2.63 15 购买美国股票 23 20 0.18 3.42 21 股票购买 27 20 0.14 2.42 13 股票入门知识 38 30 0.12 4.35 33 股市资讯网 53 30 0.08 1.05 8 中国股指期货 58 40 0.05 5.37 42 如何买美国股票 61 40 0.26 3.51 23 怎样玩股票 64 40 0.15 5

22、.98 47 深圳股票交易所 65 40 0.13 7.27 56 股市场 69 40 0.21 1.39 10 股票操盘手 76 40 0.05 0.85 6 北美股票 78 50 0.22 4.75 36 股市财经 85 50 0.1 0.1 2 今日股市行情大盘走势91 50 0.13 0.97 7 股票信息 98 50 0.23 3.21 19 美国股票市场 100 70 0.29 5.36 41 怎样买股票 108 70 0.24 6.11 48 今天股票行情 110 70 0.22 6.44 51 股票基础 122 70 0.07 3.96 25 a股新股 124 90 0.05

23、4.07 28 股票怎么玩 130 90 0.16 2.56 14 股市指数 136 90 0.09 5.68 43 美国股票开户 144 110 0.23 6.66 53 香港股票行情 147 110 0.5 6.62 52 投资股票 149 110 0.29 4.98 37 新加坡股票交易所 150 110 0.14 1.22 9 全球股票 151 110 0.13 2.97 18 巴菲特股票 157 110 0.07 3.48 22 a股行情 170 140 0.09 6.21 50 人民网新闻 171 170 0.2 3.97 26 股票价格 176 170 0.13 7.32 57

24、股票资讯 186 210 0.16 4.09 29 如何玩股票 203 260 0.14 4.7 35 股票查询 204 260 0.15 6.95 54 qq股票 206 260 0.08 5.86 45 什么是股票 207 260 0.1 3.68 24 加拿大股票 217 390 0.08 4.04 27 股票市场 220 390 0.22 4.23 31 股票型基金 226 390 0.24 4.18 30 a股基金 227 390 0.39 5.3 40 马来西亚股票 232 590 0.15 2.9 17 雅虎股票 237 720 0.15 5.88 46 股票消息 238 720

25、 0.21 2.11 12 今日股票行情 243 880 0.2 6.19 49 美国股票 244 880 0.31 5.3 39 新浪网新闻 253 2400 0.06 0.72 5 財經網 261 8100 0.21 5.19 38 第5个簇：关键词 编号 搜索量 竞争价值 估价 排名 中国股市大盘 33 30 0.04 50.39 227 香港股票软件 39 30 0.54 40.68 219 房地产股票 40 30 0.1 34.05 208 财经资讯 41 30 0.07 45.02 223 怎么炒股票 42 30 0.11 49.45 225 股票短线 43 30 0.05 33.

26、05 205 新浪股市行情 51 30 0.04 33.96 206 股市中国 57 30 0.06 53.1 228 股票图 79 50 0.1 39.41 216 股票预测 84 50 0.04 39.11 214 同花顺股票 88 50 0.06 39.06 213 股市新闻 116 70 0.15 53.13 229 股票交易软件 128 90 0.21 38.16 211 股票学习 145 110 0.08 61.42 233 股票入门基础知识 153 110 0.14 39.81 218 中国股票市场 162 140 0.14 49.94 226 和讯股票 179 170 0.05

27、 58.63 231 股票指数 181 210 0.06 34.19 209 tcl股票 184 210 0.04 59.64 232 股票吧 185 210 0.04 36.77 210 股价 192 210 0.05 46.88 224 网易股票 211 320 0.1 42.09 221 炒股票 216 390 0.25 41.99 220 新浪财经股票 221 390 0.12 33.99 207 中国股市行情 229 480 0.13 39.39 215 中石化股票 231 590 0.09 43.83 222 股票开户 236 590 0.17 55.28 230 苹果股票 240

28、 720 0.06 39.59 217 证券 247 1300 0.04 38.53 212 第6个簇：关键词 编号 搜索量 竞争价值 估价 排名 模拟股票游戏 1 10 0.07 11.78 105 同花顺股票软件 3 10 0.1 16.73 140 买什么股票好 7 10 0.13 14.45 127 股票证券 9 20 0.13 12.9 118 新浪网股票 10 20 0.09 9.45 84 新浪财经新闻 14 20 0.05 12.35 110 上证股票 20 20 0.09 11.52 102 学股票 25 20 0.14 12.85 116 怎样炒股票 28 20 0.23

29、7.72 58 中国股票网 32 20 0.15 12.59 112 股票交易系统 34 30 0.17 11.46 101 今日股票行情查询 37 30 0.16 9.87 89 股票自动交易 45 30 0.08 14.92 131 买美国股票 46 30 0.5 9.26 80 如何买卖股票 47 30 0.22 8.48 69 美国股票交易 48 30 0.33 8.99 78 如何购买美国股票 55 30 0.3 8.62 72 格力股票 59 40 0.08 9.82 88 股票教程 60 40 0.09 12.03 107 指数期货 63 40 0.08 12.11 108 股票

30、代码查询 66 40 0.1 10.45 92 如何选股票 70 40 0.07 7.96 62 股票走势图 71 40 0.11 9.48 85 股票新浪 75 40 0.06 8.55 71 腾讯财经股票 77 40 0.12 14.85 129 稀土股票 82 50 0.14 13.05 119 股票行情软件 83 50 0.12 12.77 114 股票模拟 94 50 0.13 9.78 86 股票新闻 95 50 0.16 8.9 75 股票入门书籍 96 50 0.04 13.81 124 财经股票 97 50 0.66 15.39 134 股票期货 99 50 0.1 8.36 68 股票网站 103 70 0.13 13.17 120 股票工具 106 70 0.25 10.63 94 股票游戏 112 70 0.08 14.45 128 如何炒股票 113 70 0.23 8.04 65 香港股票开户 115 70 0.7 10.98 96 如何投资股票 118 70 0.34 9.36 82 财经新闻网 120 70 0.47 7.77 60 紫金矿业股票 121 70 0.1 13.27 121 美国股票行情 123 90 0.31 9.14 79 创业板股票 134 90 0.06 14.12 126 鸿海股票 135 90 0.07 7.74 59