数据挖掘关于Kmeans算法的研究报告含数据集.doc

- .

大学算法研究实验报告

数据挖掘

题目：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;//存储属性信息
};
关键词
属性1
属性2
属性3
...
属性n

图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 zuBase,zu1,zu2; //确定分组依据
zuBase=dataNum/k;
zu1=t1.tup[4]/zuBase+1; //确定分组
zu2=t2.tup[4]/zuBase+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算法流程图
开场
获取维数并从文件中读入数据
打印所有数据
进入K-means算法随机生成k个质心
计算每个簇的均值M1
根据均值产生新的质心
计算新簇的均值M2
|M2-M1|>1?
根据每个元祖和质心的距离产生簇
根据每个元祖和新质心的距离产生新簇
打印输出并输出结果到文件
完毕
是
否

六、实验结果
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 0.13 30.66 199
股票市盈率 81 50 0.07 24.42 184
股市走势 86 50 0.1 17.05 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 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
新浪财经股票首页 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.64 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 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 50 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 236
澳洲股票 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.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 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.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 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
股票资讯 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 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.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 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 720 0.06 39.59 217
证券