浙江大学算法研究实验报告
数据挖掘
题目：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 个对象作为初始聚类中心，而对于所剩下的其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类。然后，再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值），不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具体定义如下：
21∑∑=∈-=k i i i E C p m p (1)
其中E 为数据库中所有对象的均方差之和，p 为代表对象的空间中的一个点，m i 为聚类C i 的均值(p 和m i 均是多维的)。公式(1)所示的聚类标准，旨在使所获得的k 个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
重点要求：用于聚类的测试级不能仅为单独的一类属性，至少有两种属性值参与聚类。
二、实验目的
通过实现K-means算法，加深对课本上聚类算法的理解，并对数据集做出较高的要求，以期锻炼我们的搜索查找能力。最后自己实现K-means算法，可以加强我们的编程能力。
三、实验方法
3.1软、硬件环境说明
采用win7旗舰版（盗版）系统，用vs2010实现
3.2实验数据说明
实验数据，源于google的广告关键词推荐页面，在该页面输入关键词，会出现与该关键词相关的一些信息，包括月均搜索量，关键词价值等等，取出来在经过自己处理，就得到了我们需要的实验数据，包括关键词、月均搜索量、竞争力、估价以及关键词排名，包含两种属性。部分数据如下：
关键词月均搜索量竞争力建议出价排名
模拟股票700.1427.89194
股票交流300.1119.17160
股票交易系统300.1711.46101
股票交易5900.3131.86203
gupiao10000.0615.94137
股市投资200.29 2.8216
股票趋势200.11 6.9555
财经网19000.2213.38123
股票书500.0689.06246
图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
struct data
{
string s;//存储关键词
Tuple tup;//存储属性信息
};
关键词属性1 属性2 属性3 ... 属性n
图5-1
5.2核心代码与关键技术说明
5.2.1计算距离函数
此函数用于计算两个元祖之间的距离，对于每个元祖的属性值，对于数值型的属性值（X1，X2，X3，X i，X n）,我们用Y i代替X i来进行归一化处理，其中Y i计算公式如下：
Y i=（X i - X min ）/（X max -X min ）
对于序数型属性值（M 1，M 2，M 3，M i ，M n ）, 我们用Q i 代替M i 进行归一化处理，其中Q i 计算公式如下：
Q i=（Z
（Q i ）-1）/（Z （Total ）-1） 其中Z （Q i ）表示Q i 属于的组数，Z （Total ）表示总共的组数，他
们的计算规则如下：
Z
（Total ）= k
Z （
Q i ）= Q i/（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 { 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 tmp=getDistXY(means[i],tuple); if(tmp } 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 深圳股票交易所 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 财经资讯 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 证券 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 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 股票代码查询 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 新上市股票 139 110 0.18 8.83 74 建设银行股票 140 110 0.05 15.77 136 中國股票市場 143 110 0.27 16.81 141 股票走勢 146 110 0.23 8.53 70 股票估值 152 110 0.11 14.07 125 中国证券 154 110 0.03 11.29 99 香港股票交易所 155 110 0.52 12.22 109 股票是什么 156 110 0.1 9.32 81 买股票 160 140 0.22 15.34 133 财经频道 163 140 0.02 15.96 138 股票手续费 167 140 0.12 16.67 139 如何买股票 175 170 0.18 15.22 132 股市大盘 177 170 0.07 12.88 117 股票佣金 178 170 0.37 15.56 135 股票报价 180 170 0.45 8.04 66 看股票 182 210 0.09 11.25 98 深圳股票 187 210 0.29 12.65 113 股票價 188 210 0.55 11.58 103 股票推荐 195 210 0.16 13.33 122 股票代码 199 210 0.07 8.02 63 日本股票 201 260 0.17 12.36 111 今日股票 208 260 0.18 8.96 77 股票資訊 209 260 0.26 11.77 104 中國股市行情 213 320 0.07 7.88 61 股票基金 219 390 0.26 16.97 142 股票配资 224 390 0.19 8.94 76 股票论坛 225 390 0.09 12.79 115 上海股票 230 480 0.08 11.88 106 全球股市指數 239 720 0.01 9.39 83 股市報價 241 720 0.2 8.02 64 gupiao 245 1000 0.06 15.94 137 腾讯股票 246 1000 0.05 10.86 95 财经新闻 249 1300 0.19 10.48 93 财经网 251 1900 0.22 13.38 123 今日股市行情 255 2400 0.06 8.12 67 股價 257 3600 0.08 11.08 97 股票分析 258 4400 0.06 11.38 100 财经 259 5400 0.15 10.31 91 股票行情 262 8100 0.15 10.22 90 基金 263 22200 0.41 9.81 87 美股 264 27100 0.06 8.62 73 股票 265 74000 0.27 14.87 130 第7个簇： 关键词编号搜索量竞争价值估价排名 股票交易平台 87 50 0.43 253.84 265 股票期权 222 390 0.05 380.25 266 6.2实验结果比较 拿来比较的算法用时：5600ms 我的算法用时：4399ms 从性能上看，我的算法好一点。 下面截取一部分拿来比较的算法给出的结果： 第1个簇： 关键词编号搜索量竞争价值估价排名 股票 265 74000 0.27 14.87 130 第2个簇： 关键词编号搜索量竞争价值估价排名 炒股票 216 390 0.25 41.99 220 加拿大股票 217 390 0.08 4.04 27 澳洲股票 218 390 0.21 85.95 245 股票基金 219 390 0.26 16.97 142 股票市场 220 390 0.22 4.23 31 新浪财经股票 221 390 0.12 33.99 207 股票期权 222 390 0.05 380.25 266 新浪股市 223 390 0.04 84.8 242 股票配资 224 390 0.19 8.94 76 股票论坛 225 390 0.09 12.79 115 股票型基金 226 390 0.24 4.18 30 a股基金 227 390 0.39 5.3 40 股票新手 228 390 0.23 23.69 179 中国股市行情 229 480 0.13 39.39 215 上海股票 230 480 0.08 11.88 106 中石化股票 231 590 0.09 43.83 222 马来西亚股票 232 590 0.15 2.9 17 股票交易 233 590 0.31 31.86 203 股票软件 234 590 0.2 29.04 195 新加坡股票 235 590 0.35 18.01 153 股票开户 236 590 0.17 55.28 230 雅虎股票 237 720 0.15 5.88 46 股票消息 238 720 0.21 2.11 12 全球股市指數 239 720 0.01 9.39 83 苹果股票 240 720 0.06 39.59 217 股市報價 241 720 0.2 8.02 64 股票入门 242 880 0.15 26.05 189 今日股票行情 243 880 0.2 6.19 49 美国股票 244 880 0.31 5.3 39 gupiao 245 1000 0.06 15.94 137 腾讯股票 246 1000 0.05 10.86 95 证券 247 1300 0.04 38.53 212 中国股票 248 1300 0.11 30.84 202 财经新闻 249 1300 0.19 10.48 93 第3个簇： 关键词编号搜索量竞争价值估价排名 炒股 250 1900 0.15 26.28 190 财经网 251 1900 0.22 13.38 123 gushi 252 2400 0.01 19.18 161 新浪网新闻 253 2400 0.06 0.72 5 香港股票 254 2400 0.46 23.26 175 今日股市行情 255 2400 0.06 8.12 67 新浪股票 256 2900 0.05 17.71 151 股價 257 3600 0.08 11.08 97 股票分析 258 4400 0.06 11.38 100 第4个簇： 关键词编号搜索量竞争价值估价排名 财经 259 5400 0.15 10.31 91 港股 260 6600 0.21 23.52 178 財經網 261 8100 0.21 5.19 38 股票行情 262 8100 0.15 10.22 90 第5个簇： 关键词编号搜索量竞争价值估价排名 基金 263 22200 0.41 9.81 87 美股 264 27100 0.06 8.62 73 第6个簇： 关键词编号搜索量竞争价值估价排名 股市 266 368000 0.01 17.51 150 可以看到，该算法主要受到搜索量的影响，因为搜索量数值比较大，从而其他数据的影响变得很小，导致个别的几个大的搜索量关键词单独成簇，剩下的第7个簇基本上占了所有数据的百分之70，可以看到聚类效 果不是很好，该算法没有考虑数据的相异性处理，所以出现这样的结果。 通过对比说明，数据的相异性处理和归一化处理很重要，这样可以大大提升结果的准确率和有效性。 七、总结 这学期数据挖掘这门课给我们打开了bigdata的大门，在课上，我们翔实的了解到，bigdata的处理流程和方法，包括，分类、聚类以及筛选。 并且在实验中具体的实现一些代表算法，还自己找到一些数据集进行处 理，最终得到一些结果，他们就是bigdata的语言，在这个过程中，不仅加强了我们的编程能力，还是我们的探索能力得到了锻炼，以后遇到类似的数据处理问题，我们就会有突破口，而不是毫无头绪可言，收益颇丰。 科技广场2010.9 0引言 随着数据库技术的飞速发展，人们在各种应用领域所拥有的数据量急剧增加，这些数据对人们的工作和研究有着重要的作用，但是由于对这些数据进行高级处理的工具比较少，使它们的重要性没有能够充分的发挥。当前多数的数据库系统只是可以对数据库中已有的数据进行存取、查询和统计等简单操作，通过这些操作人们可以获得数据的一些简单信息。但这些信息是从数据表面直观表现出来，对于隐藏于数据背后的如数据之间的关系、数据整体特征的描述以及寻找未来数据发展趋势的预测等信息并不能通过这些手段得到，而这些往往是人们更加需要的并且在决策支持的过程中更有价值。 数据挖掘是信息技术自然演化的结果，正是从存放在数据库、数据仓库或其他信息库中挖掘有用知识的过程。 1数据挖掘的主要步骤 数据挖掘工作作为一个完整的挖掘过程，可分为以下几个主要步骤： (1)陈述问题和阐明假设：多数基于数据的模型研究都是在一个特定的应用领域里完成的。因此在设计数据挖掘算法之前，需要事先确定一个有意义的问题陈述。模型建立者通常会为未知的相关性指定一些变量，如果可能还会指定相关性的一个大体形式作为初始假设。对当前问题可能会有几个阐明的假设，这要求将应用领域的专门技术和数据挖掘模型相结合。实际上，这往往意味数据挖掘人员与应用专家之间密切地协作，在开始数据处理过程之前明确实际工作对数据挖掘结果的要求，根据此要求，确定数据收集过程的具体方法和数据挖掘采用的具体算法。 (2)数据准备和预处理：数据准备和预处理又可分为三个步骤：数据选取、数据预处理、数据变换。 数据选取的目的是确定数据挖掘的处理对象，即目标数据，它是根据由问题陈述中得到的用户需求，从原始数据库中抽取一定的数据用于数据挖掘， 数据挖掘算法的分析与研究 Analysis and Research of Data Mining Algorithms 喻云峰 Yu Yunfeng (江西省商务学校，江西南昌330100) （Jiangxi Commercial School,Jiangxi Nanchang330100） 摘要：本文对数据挖掘的基本理论进行了分析研究，总结了数据挖掘的基本步骤，归纳了数据挖掘的基本方法，并在此基础上，提出了用数据挖掘进行数据分析的通用策略。 关键词：数据挖掘；通用策略 中图分类号：TP311文献标识码：A文章编号：1671-4792-(2010)9-0054-03 Abstract:In this thesis,the basic theory of data mining is researched.Based on this,the basic steps of data min-ing is summarized and the basic method of data mining is generalized.At last,a general tactic of data mining is given. Keywords:Data Mining;General Tactic 54 数据挖掘整理（熊熊整理-----献给梦中的天涯） 单选题 1．下面哪种分类方法是属于神经网络学习算法？（） A. 判定树归纳 B. 贝叶斯分类 C. 后向传播分类 D. 基于案例的推理 2．置信度(confidence)是衡量兴趣度度量（ A ）的指标。 A、简洁性 B、确定性 C.、实用性 D、新颖性 3．用户有一种感兴趣的模式并且希望在数据集中找到相似的模式，属于数据挖掘哪一类任务？(A) A. 根据内容检索 B. 建模描述 C. 预测建模 D. 寻找模式和规则 4．数据归约的目的是（） A、填补数据种的空缺值 B、集成多个数据源的数据 C、得到数据集的压缩表示 D、规范化数据 5．下面哪种数据预处理技术可以用来平滑数据，消除数据噪声？ A.数据清理 B.数据集成 C.数据变换 D.数据归约 6．假设12个销售价格记录组已经排序如下：5, 10, 11, 13, 15, 35, 50, 55, 72, 92, 204, 215 使用如下每种方法将它们划分成四个箱。等频（等深）划分时，15在第几个箱子内？(B) A 第一个 B 第二个 C 第三个 D 第四个 7．下面的数据操作中，（）操作不是多维数据模型上的OLAP操作。 A、上卷(roll-up) B、选择(select) C、切片(slice) D、转轴(pivot) 8．关于OLAP和OLTP的区别描述,不正确的是: (C) A. OLAP主要是关于如何理解聚集的大量不同的数据.它与OTAP应用程序不同. B. 与OLAP应用程序不同,OLTP应用程序包含大量相对简单的事务. C. OLAP的特点在于事务量大,但事务内容比较简单且重复率高. D. OLAP是以数据仓库为基础的,但其最终数据来源与OLTP一样均来自底层的数据库系统,两者面对的用户是相同的 9．下列哪个描述是正确的？（） A、分类和聚类都是有指导的学习 B、分类和聚类都是无指导的学习 计算机工程应用技术本栏目责任编辑：贾薇薇 数据挖掘中的聚类分析方法 黄利文 （泉州师范学院理工学院，福建泉州３６２０００） 摘要：聚类分析是多元统计分析的重要方法之一，该方法在许多领域都有广泛的应用。本文首先对聚类的分类做简要的介绍，然后给出了常用的聚类分析方法的基本思想和优缺点，并对常用的聚类方法作比较分析，以便人们根据实际的问题选择合适的聚类方法。 关键词：聚类分析；数据挖掘 中图分类号：ＴＰ３１１文献标识码：Ａ文章编号：１００９－３０４４（２００８）１２－２０５６４－０２ ＣｌｕｓｔｅｒＡｎｌａｙｓｉｓＭｅｔｈｏｄｓｏｆＤａｔａＭｉｎｉｎｇ ＨＵＡＮＧＬｉ－ｗｅｎ （ＳｃｈｏｏｌｏｆＳｃｉｅｎｃｅ，ＱｕａｎｚｈｏｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｑｕａｎｚｈｏｕ３６２０００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｃｌｕｓｔｅｒａｎａｌｙｓｉｓｉｓｏｎｅｏｆｔｈｅｉｍｐｏｒｔａｎｔｍｅｔｈｏｄｓｏｆｍｕｌｔｉｖａｒｉａｔｅｓｔａｔｉｓｔｉｃａｌａｎａｌｙｓｉｓ，ａｎｄｔｈｉｓｍｅｔｈｏｄｈａｓａｗｉｄｅｒａｎｇｅｏｆａｐｐｌｉｃａ－ｔｉｏｎｓｉｎｍａｎｙｆｉｅｌｄｓ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎｏｆｔｈｅｃｌｕｓｔｅｒｉｓｉｎｔｒｏｄｕｃｅｄｂｒｉｅｆｌｙ，ａｎｄｔｈｅｎｇｉｖｅｓｓｏｍｅｃｏｍｍｏｎｍｅｔｈｏｄｓｏｆｃｌｕｓｔｅｒａｎａｌｙｓｉｓａｎｄｔｈｅａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓｏｆｔｈｅｓｅｍｅｔｈｏｄｓ，ａｎｄｔｈｅｓｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｗｅｒｅｃｏｍｐａｒｅｄａｎｄａｎｓｌｙｚｅｄｓｏｔｈａｔｐｅｏｐｌｅｃａｎｃｈｏｓｅｓｕｉｔａｂｌｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｓａｃｃｏｒｄｉｎｇｔｏｔｈｅａｃｔｕａｌｉｓｓｕｅｓ． Ｋｅｙｗｏｒｄｓ：ＣｌｕｓｔｅｒＡｎａｌｙｓｉｓ；ＤａｔａＭｉｎｉｎｇ １引言 聚类分析是数据挖掘中的重要方法之一，它把一个没有类别标记的样本集按某种准则划分成若干个子类，使相似的样品尽可能归为一类，而不相似的样品尽量划分到不同的类中。目前，该方法已经被广泛地应用于生物、气候学、经济学和遥感等许多领域，其目的在于区别不同事物并认识事物间的相似性。因此，聚类分析的研究具有重要的意义。 本文主要介绍常用的一些聚类方法，并从聚类的可伸缩性、类的形状识别、抗“噪声”能力、处理高维能力和算法效率五个方面对其进行比较分析，以便人们根据实际的问题选择合适的聚类方法。 ２聚类的分类 聚类分析给人们提供了丰富多彩的分类方法，这些方法大致可归纳为以下几种［１，２，３，４］：划分方法、层次方法、基于密度的聚类方法、基于网格的聚类方法和基于模型的聚类方法。 ２．１划分法（ｐａｒｔｉｔｉｏｎｇｉｎｇｍｅｔｈｏｄｓ） 给定一个含有ｎ个对象（或元组）的数据库，采用一个划分方法构建数据的ｋ个划分，每个划分表示一个聚簇，且ｋ≤ｎ。在聚类的过程中，需预先给定划分的数目ｋ，并初始化ｋ个划分，然后采用迭代的方法进行改进划分，使得在同一类中的对象之间尽可能地相似，而不同类的中的对象之间尽可能地相异。这种聚类方法适用于中小数据集，对大规模的数据集进行聚类时需要作进一步的改进。 ２．２层次法（ｈｉｅｔａｒｃｈｉｃａｌｍｅｔｈｏｄｓ） 层次法对给定数据对象集合按层次进行分解，分解的结果形成一颗以数据子集为节点的聚类树，它表明类与类之间的相互关系。根据层次分解是自低向上还是自顶向下，可分为凝聚聚类法和分解聚类法：凝聚聚类法的主要思想是将每个对象作为一个单独的一个类，然后相继地合并相近的对象和类，直到所有的类合并为一个，或者符合预先给定的终止条件；分裂聚类法的主要思想是将所有的对象置于一个簇中，在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者符合预先给定的终止条件。在层次聚类法中，当数据对象集很大，且划分的类别数较少时，其速度较快，但是，该方法常常有这样的缺点：一个步骤（合并或分裂）完成，它就不能被取消，也就是说，开始错分的对象，以后无法再改变，从而使错分的对象不断增加，影响聚类的精度，此外，其抗“噪声”的能力也较弱，但是若把层次聚类和其他的聚类技术集成，形成多阶段聚类，聚类的效果有很大的提高。２．３基于密度的方法（ｄｅｎｓｉｔｙ－ｂａｓｅｄｍｅｔｈｏｄｓ） 该方法的主要思想是只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对于给定的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法就可以用来滤处＂噪声＂孤立点数据，发现任意形状的簇。２．４基于网格的方法（ｇｒｉｄ－ｂａｓｅｄｍｅｔｈｏｄｓ） 这种方法是把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格结构上进行。用这种方法进行聚类处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。 ２．５基于模型的方法（ｍｏｄｅｌ－ｂａｓｅｄｍｅｔｈｏｄ） 基于模型的方法为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。该方法经常基于这样的假设：数据是根据潜在的概 收稿日期：２００８－０２－１７ 作者简介：黄利文（１９７９－），男，助教。 数据挖掘聚类问题(Plants Data Set)实验报告 1.数据源描述 1.1数据特征 本实验用到的是关于植物信息的数据集，其中包含了每一种植物(种类和科属)以及它们生长的地区。数据集中总共有68个地区，主要分布在美国和加拿大。一条数据(对应于文件中的一行)包含一种植物(或者某一科属)及其在上述68个地区中的分布情况。可以这样理解，该数据集中每一条数据包含两部分内容，如下图所示。 图1 数据格式 例如一条数据:abronia fragrans,az,co,ks,mt,ne,nm,nd,ok,sd,tx,ut,wa,wy。其中abronia fragrans是植物名称(abronia是科属，fragrans是名称)，从az一直到wy 是该植物的分布区域，采用缩写形式表示，如az代表的是美国Arizona州。植物名称和分布地区用逗号隔开，各地区之间也用逗号隔开。 1.2任务要求 聚类。采用聚类算法根据某种特征对所给数据集进行聚类分析，对于聚类形成的簇要使得簇内数据对象之间的差异尽可能小，簇之间的差距尽可能大。 2.数据预处理 2.1数据清理 所给数据集中包含一些对聚类过程无用的冗余数据。数据集中全部数据的组织结构是：先给出某一科属的植物及其所有分布地区，然后给出该科属下的具体植物及其分布地区。例如： ①abelmoschus,ct,dc,fl,hi,il,ky,la,md,mi,ms,nc,sc,va,pr,vi ②abelmoschus esculentus,ct,dc,fl,il,ky,la,md,mi,ms,nc,sc,va,pr,vi ③abelmoschus moschatus,hi,pr 上述数据中第①行给出了所有属于abelmoschus这一科属的植物的分布地区，接下来的②③两行分别列出了属于abelmoschus科属的两种具体植物及其分布地区。从中可以看出后两行给出的所有地区的并集正是第一行给出的地区集 数据挖掘方法综述 [摘要]数据挖掘（DM，DataMining）又被称为数据库知识发现（KDD,Knowledge Discovery in Databases）,它的主要挖掘方法有分类、聚类、关联规则挖掘和序列模式挖掘等。 [关键词]数据挖掘分类聚类关联规则序列模式 1、数据挖掘的基本概念 数据挖掘从技术上说是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们事先不知道的、但又是潜在的有用的信息和知识的过程。这个定义包括好几层含义: 数据源必须是真实的、大量的、含噪声的、发现的是用户感兴趣的知识, 发现的知识要可接受、可理解、可运用, 并不要求发现放之四海皆准的知识, 仅支持特定的发现问题, 数据挖掘技术能从中自动分析数据进行归纳性推理从中发掘出潜在的数据模式或进行预测, 建立新的业务模型帮助决策者调整策略做出正确的决策。数据挖掘是是运用统计学、人工智能、机器学习、数据库技术等方法发现数据的模型和结构、发现有价值的关系或知识的一门交叉学科。数据挖掘的主要方法有分类、聚类和关联规则挖掘等 2、分类 分类（Classification）又称监督学习（Supervised Learning）。监 督学习的定义是：给出一个数据集D，监督学习的目标是产生一个联系属性值集合A和类标（一个类属性值称为一个类标）集合C的分类/预测函数，这个函数可以用于预测新的属性集合（数据实例）的类标。这个函数就被称为分类模型（Classification Model），或者是分类器（Classifier）。分类的主要算法有：决策树算法、规则推理、朴素贝叶斯分类、支持向量机等算法。 决策树算法的核心是Divide-and-Conquer的策略，即采用自顶向下的递归方式构造决策树。在每一步中，决策树评估所有的属性然后选择一个属性把数据分为m个不相交的子集，其中m是被选中的属性的不同值的数目。一棵决策树可以被转化成一个规则集，规则集用来分类。 规则推理算法则直接产生规则集合，规则推理算法的核心是Separate-and-Conquer的策略，它评估所有的属性-值对（条件），然后选择一个。因此，在一步中，Divide-and-Conquer策略产生m条规则，而Separate-and-Conquer策略只产生1条规则，效率比决策树要高得多，但就基本的思想而言，两者是相同的。 朴素贝叶斯分类的基本思想是：分类的任务可以被看作是给定一个测试样例d后估计它的后验概率，即Pr（C=c j︱d），然后我们考察哪个类c j对应概率最大，便将那个类别赋予样例d。构造朴素贝叶斯分类器所需要的概率值可以经过一次扫描数据得到，所以算法相对训练样本的数量是线性的，效率很高，就分类的准确性而言，尽管算法做出了很强的条件独立假设，但经过实际检验证明，分类的效果还是 论文关键词：数据挖掘；聚类算法；聚类分析论文摘要：该文详细阐述了数据挖掘领域的常用聚类算法及改进算法，并比较分析了其优缺点，提出了数据挖掘对聚类的典型要求，指出各自的特点，以便于人们更快、更容易地选择一种聚类算法解决特定问题和对聚类算法作进一步的研究。并给出了相应的算法评价标准、改进建议和聚类分析研究的热点、难点。上述工作将为聚类分析和数据挖掘等研究提供有益的参考。 1 引言随着经济社会和科学技术的高速发展，各行各业积累的数据量急剧增长，如何从海量的数据中提取有用的信息成为当务之急。聚类是将数据划分成群组的过程，即把数据对象分成多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。它对未知数据的划分和分析起着非常有效的作用。通过聚类，能够识别密集和稀疏的区域，发现全局的分布模式，以及数据属性之间的相互关系等。为了找到效率高、通用性强的聚类方法人们从不同角度提出了许多种聚类算法，一般可分为基于层次的，基于划分的，基于密度的，基于网格的和基于模型的五大类。 2 数据挖掘对聚类算法的要求(1)可兼容性：要求聚类算法能够适应并处理属性不同类型的数据。(2)可伸缩性：要求聚类算法对大型数据集和小数据集都适用。(3)对用户专业知识要求最小化。(4)对数据类别簇的包容性：即聚类算法不仅能在用基本几何形式表达的数据上运行得很好，还要在以其他更高维度形式表现的数据上同样也能实现。(5)能有效识别并处理数据库的大量数据中普遍包含的异常值，空缺值或错误的不符合现实的数据。(6)聚类结果既要满足特定约束条件，又要具有良好聚类特性，且不丢失数据的真实信息。(7)可读性和可视性：能利用各种属性如颜色等以直观形式向用户显示数据挖掘的结果。(8)处理噪声数据的能力。(9)算法能否与输入顺序无关。 3 各种聚类算法介绍随着人们对数据挖掘的深入研究和了解，各种聚类算法的改进算法也相继提出，很多新算法在前人提出的算法中做了某些方面的提高和改进，且很多算法是有针对性地为特定的领域而设计。某些算法可能对某类数据在可行性、效率、精度或简单性上具有一定的优越性，但对其它类型的数据或在其他领域应用中则不一定还有优势。所以，我们必须清楚地了解各种算法的优缺点和应用范围，根据实际问题选择合适的算法。 3.1 基于层次的聚类算法基于层次的聚类算法对给定数据对象进行层次上的分解，可分为凝聚算法和分裂算法。 (1)自底向上的凝聚聚类方法。这种策略是以数据对象作为原子类，然后将这些原子类进行聚合。逐步聚合成越来越大的类，直到满足终止条件。凝聚算法的过程为：在初始时，每一个成员都组成一个单独的簇，在以后的迭代过程中，再把那些相互邻近的簇合并成一个簇，直到所有的成员组成一个簇为止。其时间和空间复杂性均为O(n2)。通过凝聚式的方法将两簇合并后，无法再将其分离到之前的状态。在凝聚聚类时，选择合适的类的个数和画出原始数据的图像很重要。 [!--empirenews.page--] (2)自顶向下分裂聚类方法。与凝聚法相反，该法先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件。其主要思想是将那些成员之间不是非常紧密的簇进行分裂。跟凝聚式方法的方向相反，从一个簇出发，一步一步细化。它的优点在于研究者可以把注意力集中在数据的结构上面。一般情况下不使用分裂型方法，因为在较高的层很难进行正确的拆分。 3.2 基于密度的聚类算法很多算法都使用距离来描述数据之间的相似性，但对于非凸数据集，只用距离来描述是不够的。此时可用密度来取代距离描述相似性，即基于密度的聚类算法。它不是基于各种各样的距离，所以能克服基于距离的算法只能发现“类圆形”的聚类的缺点。其指导思想是：只要一个区域中的点的密度（对象或数据点的数目）大过某个阈值，就把它加到与之相近的聚类中去。该法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可发现任意形状的簇，并可用来过滤“噪声”数据。常见算法有DBSCAN，DENCLUE 等。[1][2][3]下一页 3.3 基于划分的聚类算法给定一个N个对象的元组或数据库，根据给定要创建的划分的数目k，将数据划分为k个组，每个组表示一个簇类（<=N）时满足如下两点：(1)每个组至少包含一个对象；(2)每个对 数据挖掘分类算法比较 分类是数据挖掘、机器学习和模式识别中一个重要的研究领域。通过对当前数据挖掘中具有代表性的优秀分类算法进行分析和比较，总结出了各种算法的特性，为使用者选择算法或研究者改进算法提供了依据。 一、决策树（Decision Trees） 决策树的优点： 1、决策树易于理解和解释.人们在通过解释后都有能力去理解决策树所表达的意义。 2、对于决策树，数据的准备往往是简单或者是不必要的.其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。 3、能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一。 4、决策树是一个白盒模型。如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。 5、易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。 6、在相对短的时间内能够对大型数据源做出可行且效果良好的结果。 7、可以对有许多属性的数据集构造决策树。 8、决策树可很好地扩展到大型数据库中，同时它的大小独立于数据库的大小。 决策树的缺点： 1、对于那些各类别样本数量不一致的数据，在决策树当中,信息增益的结果偏向于那些具有更多数值的特征。 2、决策树处理缺失数据时的困难。 3、过度拟合问题的出现。 4、忽略数据集中属性之间的相关性。 二、人工神经网络 人工神经网络的优点：分类的准确度高,并行分布处理能力强,分布存储及学习能力强，对噪声神经有较强的鲁棒性和容错能力，能充分逼近复杂的非线性关系，具备联想记忆的功能等。 人工神经网络的缺点：神经网络需要大量的参数，如网络拓扑结构、权值和阈值的初始值；不能观察之间的学习过程，输出结果难以解释，会影响到结果的可信度和可接受程度；学习时间过长,甚至可能达不到学习的目的。 第37卷第7期测绘与空间地理信息 GEOMATICS ＆SPATIAL INFOＲMATION TECHNOLOGY Vol．37，No．7收稿日期：2014－01－22 作者简介：马宏斌（1982－），男，甘肃天水人，作战环境学专业博士研究生，主要研究方向为地理空间信息服务。 大数据时代的空间数据挖掘综述 马宏斌1 ，王 柯1，马团学 2（1．信息工程大学地理空间信息学院，河南郑州450000；2．空降兵研究所，湖北孝感432000） 摘 要：随着大数据时代的到来，数据挖掘技术再度受到人们关注。本文回顾了传统空间数据挖掘面临的问题， 介绍了国内外研究中利用大数据处理工具和云计算技术，在空间数据的存储、管理和挖掘算法等方面的做法，并指出了该类研究存在的不足。最后，探讨了空间数据挖掘的发展趋势。关键词：大数据；空间数据挖掘；云计算中图分类号：P208 文献标识码：B 文章编号：1672－5867（2014）07－0019－04 Spatial Data Mining Big Data Era Ｒeview MA Hong －bin 1，WANG Ke 1，MA Tuan －xue 2 （1．Geospatial Information Institute ，Information Engineering University ，Zhengzhou 450000，China ； 2．Airborne Institute ，Xiaogan 432000，China ） Abstract ：In the era of Big Data ，more and more researchers begin to show interest in data mining techniques again．The paper review most unresolved problems left by traditional spatial data mining at first．And ，some progress made by researches using Big Data and Cloud Computing technology is introduced．Also ，their drawbacks are mentioned．Finally ，future trend of spatial data mining is dis-cussed． Key words ：big data ；spatial data mining ；cloud computing 0引言 随着地理空间信息技术的飞速发展，获取数据的手 段和途径都得到极大丰富，传感器的精度得到提高和时空覆盖范围得以扩大，数据量也随之激增。用于采集空间数据的可能是雷达、红外、光电、卫星、多光谱仪、数码相机、成像光谱仪、全站仪、天文望远镜、电视摄像、电子 显微镜、CT 成像等各种宏观与微观传感器或设备，也可能是常规的野外测量、人口普查、土地资源调查、地图扫描、 地图数字化、统计图表等空间数据获取手段，还可能是来自计算机、 网络、GPS ，ＲS 和GIS 等技术应用和分析空间数据。特别是近些年来，个人使用的、携带的各种传感器（重力感应器、电子罗盘、三轴陀螺仪、光线距离感应器、温度传感器、红外线传感器等），具备定位功能电子设备的普及，如智能手机、平板电脑、可穿戴设备（GOOGLE GLASS 和智能手表等），使人们在日常生活中产生了大量具有位置信息的数据。随着志愿者地理信息（Volunteer Geographic Information ）的出现，使这些普通民众也加入到了提供数据者的行列。 以上各种获取手段和途径的汇集，就使每天获取的 数据增长量达到GB 级、 TB 级乃至PB 级。如中国遥感卫星地面站现在保存的对地观测卫星数据资料达260TB ，并以每年15TB 的数据量增长。比如2011年退役的Landsat5卫星在其29年的在轨工作期间，平均每年获取8．6万景影像，每天获取67GB 的观测数据。而2012年发射的资源三号（ZY3）卫星，每天的观测数据获取量可以达到10TB 以上。类似的传感器现在已经大量部署在卫 星、 飞机等飞行平台上，未来10年，全球天空、地空间部署的百万计传感器每天获取的观测数据将超过10PB 。这预示着一个时代的到来，那就是大数据时代。大数据具有 “4V ”特性，即数据体量大（Volume ）、数据来源和类型繁多（Variety ）、数据的真实性难以保证（Veracity ）、数据增加和变化的速度快（Velocity ）。对地观测的系统如图1所示。 在这些数据中，与空间位置相关的数据占了绝大多数。传统的空间知识发现的科研模式在大数据情境下已经不再适用，原因是传统的科研模型不具有普适性且支持的数据量受限， 受到数据传输、存储及时效性需求的制约等。为了从存储在分布方式、虚拟化的数据中心获取信息或知识，这就需要利用强有力的数据分析工具来将 数据挖掘常用的方法 在大数据时代，数据挖掘是最关键的工作。大数据的挖掘是从海量、不完全的、有噪 声的、模糊的、随机的大型数据库中发现隐含在其中有价值的、潜在有用的信息和知 识的过程，也是一种决策支持过程。其主要基于人工智能，机器学习，模式学习，统 计学等。通过对大数据高度自动化地分析，做出归纳性的推理，从中挖掘出潜在的模式，可以帮助企业、商家、用户调整市场政策、减少风险、理性面对市场，并做出正 确的决策。目前，在很多领域尤其是在商业领域如银行、电信、电商等，数据挖掘可 以解决很多问题，包括市场营销策略制定、背景分析、企业管理危机等。大数据的挖 掘常用的方法有分类、回归分析、聚类、关联规则、神经网络方法、Web 数据挖掘等。这些方法从不同的角度对数据进行挖掘。 (1)分类。分类是找出数据库中的一组数据对象的共同特点并按照分类模式将其划分为不同的类，其目的是通过分类模型，将数据库中的数据项映射到摸个给定的类别中。 可以应用到涉及到应用分类、趋势预测中，如淘宝商铺将用户在一段时间内的购买情 况划分成不同的类，根据情况向用户推荐关联类的商品，从而增加商铺的销售量。 (2)回归分析。回归分析反映了数据库中数据的属性值的特性，通过函数表达数据映射的关系来发现属性值之间的依赖关系。它可以应用到对数据序列的预测及相关关系的 研究中去。在市场营销中，回归分析可以被应用到各个方面。如通过对本季度销售的 回归分析，对下一季度的销售趋势作出预测并做出针对性的营销改变。 (3)聚类。聚类类似于分类，但与分类的目的不同，是针对数据的相似性和差异性将一组数据分为几个类别。属于同一类别的数据间的相似性很大，但不同类别之间数据的 相似性很小，跨类的数据关联性很低。 (4)关联规则。关联规则是隐藏在数据项之间的关联或相互关系，即可以根据一个数据项的出现推导出其他数据项的出现。关联规则的挖掘过程主要包括两个阶段：第一阶 段为从海量原始数据中找出所有的高频项目组;第二极端为从这些高频项目组产生关联规则。关联规则挖掘技术已经被广泛应用于金融行业企业中用以预测客户的需求，各 银行在自己的ATM 机上通过捆绑客户可能感兴趣的信息供用户了解并获取相应信息来改善自身的营销。 (5)神经网络方法。神经网络作为一种先进的人工智能技术，因其自身自行处理、分布存储和高度容错等特性非常适合处理非线性的以及那些以模糊、不完整、不严密的知 识或数据为特征的处理问题，它的这一特点十分适合解决数据挖掘的问题。典型的神 经网络模型主要分为三大类：第一类是以用于分类预测和模式识别的前馈式神经网络 模型，其主要代表为函数型网络、感知机;第二类是用于联想记忆和优化算法的反馈式神经网络模型，以Hopfield 的离散模型和连续模型为代表。第三类是用于聚类的自组 数据挖掘考试题 公司内部编号：（GOOD-TMMT-MMUT-UUPTY-UUYY-DTTI- 数据挖掘考试题 一．选择题 1. 当不知道数据所带标签时，可以使用哪种技术促使带同类标签的数据与带其他标签的数据相分离( ) A.分类 B.聚类 C.关联分析 D.主成分分析 2. ( )将两个簇的邻近度定义为不同簇的所有点对邻近度的平均值，它是一种凝聚层次聚类技术。 A.MIN(单链) B.MAX(全链) C.组平均 D.Ward方法 3.数据挖掘的经典案例“啤酒与尿布试验”最主要是应用了( )数据挖掘方法。 A 分类 B 预测 C关联规则分析 D聚类 4.关于K均值和DBSCAN的比较，以下说法不正确的是( ) A.K均值丢弃被它识别为噪声的对象，而DBSCAN一般聚类所有对象。 B.K均值使用簇的基于原型的概念，DBSCAN使用基于密度的概念。 C.K均值很难处理非球形的簇和不同大小的簇，DBSCAN可以处理不同大小和不同形状的簇 D.K均值可以发现不是明显分离的簇，即便簇有重叠也可以发现，但是DBSCAN 会合并有重叠的簇 5.下列关于Ward’s Method说法错误的是：( ) A.对噪声点和离群点敏感度比较小 B.擅长处理球状的簇 C.对于Ward方法，两个簇的邻近度定义为两个簇合并时导致的平方误差 D.当两个点之间的邻近度取它们之间距离的平方时，Ward方法与组平均非常相似 6.下列关于层次聚类存在的问题说法正确的是：( ) A.具有全局优化目标函数 B.Group Average擅长处理球状的簇 C.可以处理不同大小簇的能力 D.Max对噪声点和离群点很敏感 7.下列关于凝聚层次聚类的说法中，说法错误的事：( ) A.一旦两个簇合并，该操作就不能撤销 B.算法的终止条件是仅剩下一个簇 C.空间复杂度为()2m O D.具有全局优化目标函数 8.规则{牛奶，尿布}→{啤酒}的支持度和置信度分别为：( ) 9.下列( )是属于分裂层次聚类的方法。 A.Min B.Max C.Group Average D.MST 10.对下图数据进行凝聚聚类操作，簇间相似度使用MAX计算，第二步是哪两个簇合并：( ) A.在{3}和{l,2}合并 B.{3}和{4,5}合并 C.{2,3}和{4,5}合并 浙江大学算法研究实验报告 数据挖掘 题目：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 个对象作为初始聚类中心，而对于所剩下的其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类。然后，再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值），不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具体定义如下： 21∑∑=∈-=k i i i E C p m p (1) 其中E 为数据库中所有对象的均方差之和，p 为代表对象的空间中的一个点，m i 为聚类C i 的均值(p 和m i 均是多维的)。公式(1)所示的聚类标准，旨在使所获得的k 个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 重点要求：用于聚类的测试级不能仅为单独的一类属性，至少有两种属性值参与聚类。 数据挖掘聚类算法课程设计报告 数据挖掘聚类问题(Plants Data Set)实验报告 1.数据源描述 1.1数据特征 本实验用到的是关于植物信息的数据集，其中包含了每一种植物(种类和科属)以及它们生长的地区。数据集中总共有68个地区，主要分布在美国和加拿大。一条数据(对应于文件中的一行)包含一种植物(或者某一科属)及其在上述68个地区中的分布情况。能够这样理解，该数据集中每一条数据包含两部分内容，如下图所示。 图1 数据格式 例如一条数据:abronia fragrans,az,co,ks,mt,ne,nm,nd,ok,sd,tx,ut,wa,wy。其中abronia fragrans是植物名称(abronia是科属，fragrans是名称)，从az一直到wy是该植物的分布区域，采用缩写形式表示，如az代表的是美国Arizona州。植物名称和分布地区用逗号隔开，各地区之间也用逗号隔开。 1.2任务要求 聚类。采用聚类算法根据某种特征对所给数据集进行聚类分析，对于聚类形成的簇要使得簇内数据对象之间的差异尽可能小，簇之间的差距尽可能大。 2.数据预处理 2.1数据清理 所给数据集中包含一些对聚类过程无用的冗余数据。数据集中全部数据的组织结构是：先给出某一科属的植物及其所有分布地区，然后给出该科属下的具体植物及其分布地区。例如：abelmoschus,ct,dc,fl,hi,il,ky,la,md,mi,ms,nc,sc,va,pr,vi abelmoschus esculentus,ct,dc,fl,il,ky,la,md,mi,ms,nc,sc,va,pr,vi abelmoschus moschatus,hi,pr 上述数据中第行给出了所有属于abelmoschus这一科属的植物的分布地区，接下来的两行分别列出了属于abelmoschus 科属的两种具体植物及其分布地区。从中能够看出后两行给出的所有地区的并集正是第一行给出的地区集合。在聚类过程中第行数据是无用的，因此要对其进行清理。 2.2数据变换 本实验是依据植物的分布区域进行聚类，所给数据集中的分布区域是字符串形式，不适合进行聚类，因此将其变换成适合聚类的数值形式。具体思想如下： 数据集中总共包含68个区域，每一种植物的分布区域是这68个区域中的一部分。本实验中将68个区域看成是数据对象的68个属性，这68个属性是二元类型的变量，其值只能去0或者1。步骤如下： 1.把68个区域按一定顺序存放在字符串数组(记为str)中(顺序能够自己定，确定后不能改变)。 朴素贝叶斯： 有以下几个地方需要注意： 1. 如果给出的特征向量长度可能不同，这是需要归一化为通长度的向量（这里以文本分类为例），比如说是句子单词的话，则长度为整个词汇量的长度，对应位置是该单词出现的次数。 2. 计算公式如下： 其中一项条件概率可以通过朴素贝叶斯条件独立展开。要注意一点就是的计算方法，而由朴素贝叶斯的前提假设可知， = ，因此一般有两种，一种是在类别为ci的那些样本集中，找到wj出现次数的总和，然后除以该样本的总和；第二种方法是类别为ci的那些样本集中，找到wj出现次数的总和，然后除以该样本中所有特征出现次数的总和。 3. 如果中的某一项为0，则其联合概率的乘积也可能为0，即2中公式的分子为0，为了避免这种现象出现，一般情况下会将这一项初始化为1，当然为了保证概率相等，分母应对应初始化为2（这里因为是2类，所以加2，如果是k类就需要加k，术语上叫做laplace 光滑, 分母加k的原因是使之满足全概率公式）。 朴素贝叶斯的优点： 对小规模的数据表现很好，适合多分类任务，适合增量式训练。 缺点： 对输入数据的表达形式很敏感。 决策树： 决策树中很重要的一点就是选择一个属性进行分枝，因此要注意一下信息增益的计算公式，并深入理解它。 信息熵的计算公式如下: 其中的n代表有n个分类类别（比如假设是2类问题，那么n=2）。分别计算这2类样本在总样本中出现的概率p1和p2，这样就可以计算出未选中属性分枝前的信息熵。 现在选中一个属性xi用来进行分枝，此时分枝规则是：如果xi=vx的话，将样本分到树的一个分支；如果不相等则进入另一个分支。很显然，分支中的样本很有可能包括2个类别，分别计算这2个分支的熵H1和H2,计算出分枝后的总信息熵H’=p1*H1+p2*H2.，则此时的信息增益ΔH=H-H’。以信息增益为原则，把所有的属性都测试一边，选择一个使增益最大的属性作为本次分枝属性。 决策树的优点： 计算量简单，可解释性强，比较适合处理有缺失属性值的样本，能够处理不相关的特征； 缺点： 容易过拟合（后续出现了随机森林，减小了过拟合现象）； Logistic回归： Logistic是用来分类的，是一种线性分类器，需要注意的地方有： 1. logistic函数表达式为： 其导数形式为： 2. logsitc回归方法主要是用最大似然估计来学习的，所以单个样本的后验概率为： 到整个样本的后验概率： 各种聚类算法的比较 聚类的目标是使同一类对象的相似度尽可能地小；不同类对象之间的相似度尽可能地大。目前聚类的方法很多，根据基本思想的不同，大致可以将聚类算法分为五大类：层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法。摘自数据挖掘中的聚类分析研究综述这篇论文。 1、层次聚类算法 1.1聚合聚类 1.1.1相似度依据距离不同：Single-Link:最近距离、Complete-Link：最远距离、Average-Link：平均距离 1.1.2最具代表性算法 1）CURE算法 特点：固定数目有代表性的点共同代表类 优点：识别形状复杂，大小不一的聚类，过滤孤立点 2）ROCK算法 特点：对CURE算法的改进 优点：同上，并适用于类别属性的数据 3）CHAMELEON算法 特点：利用了动态建模技术 1.2分解聚类 1.3优缺点 优点：适用于任意形状和任意属性的数据集；灵活控制不同层次的聚类粒度，强聚类能力 缺点：大大延长了算法的执行时间，不能回溯处理 2、分割聚类算法 2.1基于密度的聚类 2.1.1特点 将密度足够大的相邻区域连接，能有效处理异常数据，主要用于对空间数据的聚类 1）DBSCAN：不断生长足够高密度的区域 2）DENCLUE：根据数据点在属性空间中的密度进行聚类，密度和网格与处理的结合 3）OPTICS、DBCLASD、CURD：均针对数据在空间中呈现的不同密度分不对DBSCAN作了改进 2.2基于网格的聚类 2.2.1特点 利用属性空间的多维网格数据结构，将空间划分为有限数目的单元以构成网格结构； 1）优点：处理时间与数据对象的数目无关，与数据的输入顺序无关，可以处理任意类型的数据 2）缺点：处理时间与每维空间所划分的单元数相关，一定程度上降低了聚类的质量和准确性 2.2.2典型算法 1）STING：基于网格多分辨率，将空间划分为方形单元，对应不同分辨率2）STING+：改进STING，用于处理动态进化的空间数据 3）ＣＬＩＱＵＥ：结合网格和密度聚类的思想，能处理大规模高维度数据4）WaveCluster：以信号处理思想为基础 2.3基于图论的聚类 2.3.1特点 转换为组合优化问题，并利用图论和相关启发式算法来解决，构造数据集的最小生成数，再逐步删除最长边 1）优点：不需要进行相似度的计算 2.3.2两个主要的应用形式 1）基于超图的划分 2）基于光谱的图划分 2.4基于平方误差的迭代重分配聚类 2.4.1思想 逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获最优解 数据挖掘分类算法研究综述 程建华 (九江学院信息科学学院软件教研室九江332005 ) 摘要：随着数据库应用的不断深化,数据库的规模急剧膨胀,数据挖掘已成为当今研究的热点。特别是其中的分类问题,由于其使用的广泛性,现已引起了越来越多的关注。对数据挖掘中的核心技术分类算法的内容及其研究现状进行综述。认为分类算法大体可分为传统分类算法和基于软计算的分类法两类。通过论述以上算法优缺点和应用范围，研究者对已有算法的改进有所了解，以便在应用中选择相应的分类算法。 关键词：数据挖掘；分类；软计算；算法 1引言 1989年8月，在第11届国际人工智能联合会议的专题研讨会上，首次提出基于数据库的知识发现(KDD，Knowledge DiscoveryDatabase)技术[1]。该技术涉及机器学习、模式识别、统计学、智能数据库、知识获取、专家系统、数据可视化和高性能计算等领域，技术难度较大，一时难以应付信息爆炸的实际需求。到了1995年，在美国计算机年会(ACM)上，提出了数据挖掘[2](DM，Data Mining)的概念，由于数据挖掘是KDD过程中最为关键的步骤，在实践应用中对数据挖掘和KDD这2个术语往往不加以区分。 基于人工智能和信息系统，抽象层次上的分类是推理、学习、决策的关键，是一种基础知识。因而数据分类技术可视为数据挖掘中的基础和核心技术。其实，该技术在很多数据挖掘中被广泛使用，比如关联规则挖掘和时间序列挖掘等。因此，在数据挖掘技术的研究中，分类技术的研究应当处在首要和优先的地位。目前，数据分类技术主要分为基于传统技术和基于软计算技术两种。 2传统的数据挖掘分类方法 分类技术针对数据集构造分类器，从而对未知类别样本赋予类别标签。在其学习过程中和无监督的聚类相比，一般而言，分类技术假定存在具备环境知识和输入输出样本集知识的老师，但环境及其特性、模型参数等却是未知的。 2.1判定树的归纳分类 判定树是一个类似流程图的树结构，其中每个内部节点表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶节点代表类或类分布。树的最顶层节点是根节点。由判定树可以很容易得到“IFTHEN”形式的分类规则。方法是沿着由根节点到树叶节点的路径，路径上的每个属性-值对形成“IF”部分的一个合取项，树叶节点包含类预测，形成“THEN”部分。一条路径创建一个规则。 判定树归纳的基本算法是贪心算法，它是自顶向下递归的各个击破方式构造判定树。其中一种著名的判定树归纳算法是建立在推理系统和概念学习系统基础上的ID3算法。 2.2贝叶斯分类 贝叶斯分类是统计学的分类方法，基于贝叶斯公式即后验概率公式。朴素贝叶斯分类的分类过程是首先令每个数据样本用一个N维特征向量X={X1，X2，?X n}表示，其中X k是属性A k的值。所有的样本分为m类：C1，C2，?，C n。对于一个类别的标记未知的数据记录而言，若P(C i/X)>P(C j/X)，1≤ j≤m，j≠i，也就是说，如果条件X下，数据记录属于C i类的概率大于属于其他类的概率的话，贝叶斯分类将把这条记录归类为C i类。 建立贝叶斯信念网络可以被分为两个阶段。第一阶段网络拓扑学习，即有向非循环图的——————————————————— 作者简介：程建华（1982-），女，汉族，江西九江，研究生，主要研究方向为数据挖掘、信息安全。数据挖掘算法的分析与研究
数据挖掘试卷一
数据挖掘中的聚类分析方法
数据挖掘聚类算法课程设计报告
数据挖掘算法综述
各种聚类算法及改进算法的研究
数据挖掘分类算法比较
大数据时代的空间数据挖掘综述
数据挖掘常用的方法
数据挖掘考试题精编版
数据挖掘关于Kmeans算法的研究(含数据集)
数据挖掘聚类算法课程设计报告范本
数据挖掘主要算法
各种聚类算法的比较
数据挖掘分类算法研究综述终板
相关主题
文本预览