大数据挖掘关于某Kmeans算法地研究

1、浙江大学算法研究实验报告数据挖掘题目：K-means目录一、实验内容5二、实验目的7三、实验方法73.1 软、硬件环境说明73.2 实验数据说明7图3-173.3 实验参数说明/软件正确性测试7四、算法描述9图4-110五、算法实现115.1 主要数据结构描述11图5-1115.2 核心代码与关键技术说明115.3 算法流程图14六、实验结果156.1 实验结果说明156.2 实验结果比拟21七、总结23实验内容实现K-means算法,其中该算法介绍如下：k-means算法是根据聚类中的均值进行聚类划分的聚类算法.输入：聚类个数k,以及包含n个数据对象的数据.输出：满足方差最小标准的k个聚类.

2、处理流程：Step1.从n个数据对象任意选择k个对象作为初始聚类中央；Step2.根据每个聚类对象的均值中央对象,计算每个对象与这些中心对象的距离,并根据最小距离重新对相应对象进行划分；Step3.重新计算每个有变化聚类的均值中央对象Step4.循环Step2到Step3直到每个聚类不再发生变化为止；k-means算法的工作过程说明如下：首先从n个数据对象任意选择k个对象作为初始聚类中央,而对于所剩下的其它对象,那么根据它们与这些聚类中央的相似度距离,分别将它们分配给与其最相似的聚类中央所代表的聚类.然后,再计算每个所获新聚类的聚类中央该聚类中所有对象的均值,不断重复这一过程直到标准测度函数开

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

4、7旗舰版盗版系统,用vs2021实现3.2 实验数据说明实验数据,源于google的广告关键词推荐页面,在该页面输入关键词,会出现与该关键词相关的一些信息,包括月均搜索量,关键词价值等等,取出来在经过自己处理,就得到了我们需要的实验数据,包括关键词、月均搜索量、竞争力、估价以及关键词排名,包含两种属性.局部数据如下：关键词月均搜索量竞争力建议出价排名模拟股票700.1427.89194股票交流300.1119.17160股票交易系统300.1711.46101股票交易5900.3131.86203gupiao10000.0615.94137股市投资200.292.8216股票趋势200.116

5、.9555财经网19000.2213.38123股票书500.0689.06246图3-13.3 实验参数说明/软件正确性测试我采用了各种数据对程序进行测试,出现一些数组越界bug,修改后再次测试,无问题,测试通过.算法描述KMeans算法的根本思想是初始随机给定K个簇中央,根据最邻近原那么把待分类样本点分到各个簇.然后按平均法重新计算各个簇的质心,从而确定新的簇心.一直迭代,直到簇心的移动距离小于某个给定的值.K-Means聚类算法主要分为三个步骤：(1)第一步是为待聚类的点寻找聚类中央(2)第二步是计算每个点到聚类中央的距离,将每个点聚类到离该点最近的聚类中去(3)第三步是计算每个聚类中所

6、有点的坐标平均值,并将这个平均值作为新的聚类中央反复执行(2)、(3),直到聚类中央不再进行大范围移动或者聚类次数到达要求为止下列图展示了对n个样本点进行K-means聚类的效果,这里k取2：(a)未聚类的初始点集(b)随机选取两个点作为聚类中央(c)计算每个点到聚类中央的距离,并聚类到离该点最近的聚类中去(d)计算每个聚类中所有点的坐标平均值,并将这个平均值作为新的聚类中央(e)重复(c),计算每个点到聚类中央的距离,并聚类到离该点最近的聚类中重复(d),计算每个聚类中所有点的坐标平均值,并将这个平均值作为新的聚类中央图4-15、 算法实现5.1 主要数据结构描述这里我建造了一个data的结

7、构体,如下：typedefvector<double>Tuple;/存储每条数据记录structdatastrings;/存储关键词Tupletup;/存储属性信息;图5-15.2 核心代码与关键技术说明5.2.1 计算距离函数此函数用于计算两个元祖之间的距离,对于每个元祖的属性值,对于数值型的属性值(Xi,X2,X3,Xi,Xn),我们用Yi代替Xi来进行归一化处理,其中Yi计算公式如下：Yi=(XiXmin)/(Xmax-Xmin)对于序数型属性值(M1,M2,M3,Mi,Mn),我们用Qi代替Mi进行归一化处理,其中Qi计算公式如下:Qi=(Z(Qi)-1)/(Z(Total

8、)-1)其中Z(Qi)表示Qi属于的组数,Z(Total)表示总共的组数,他们的计算规那么如下：Z(Total)=kZ(Qi)=Qi/(dataNum/k)+1(其中dataNum为总数据量,K为总分组数.)归一化处理之后,在计算两个元祖之间的欧式几何距离,具体实现代码如下：doublegetDistXY(constdata&t1,constdata&t2)doublesum=0,temp1=0,temp2=0,temp3=0,temp4=0;intzuBase,zu1,zu2;/确定分组依据zuBase=dataNum/k;zu1=t1.tup4/zuBase+1;/确定分组

9、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.tup1-10)/367990;temp2=(t2.tup1-10)/367990;sum+=(temp1-temp2)*(temp1-temp2)+(temp3-temp4)*(temp3-temp4);for(inti=2;i<dimNum-1;+i)sum+=(t1.tupi-t2.tupi)*(t1.tupi-t2.tupi);returnsqrt(sum

10、);5.2.2 重新分簇对于每个簇,算出当前每个元祖与各个质心间的距离,重新判定该元组属于哪一个簇,代码如下：intclusterOfTuple(datameans,constdata&tuple)doubledist=getDistXY(means0,tuple);doubletmp;intlabel=0;/标示属于哪一个簇for(inti=1;i<k;i+)tmp=getDistXY(meansi,tuple);if(tmp<dist)dist=tmp;label=i;returnlabel;5.3 算法流程图开始获取维数并从文件中读入数据打印所有数据进入K-means

11、算法随机生成k个质心根据每个元祖和质心的距离产生簇计算每个簇的均值M1根据均值产生新的质心根据每个元祖和新质心的距离产生新簇计算新簇的均值M2是|M2-M1|>1?打印输出并输出结果到文件结束6、 实验结果6.1 实验结果说明进过归一化操作聚类效果比拟明显,可以看到大家对股票的哪一方面比拟关心,并且给广告投资商一些参考,帮助其决定把广告投到哪一个关键词上,进而得到的关注量最大同时花费最少.同时,考虑到结果的聚类性,用户搜索某个关键词时,可以推荐给他同一个簇内其他的关键词.具体实验结果如下：第1个簇：关键词编号搜索量竞争价值估价排名股票学习网8200.1127.19193股票初学15200

12、.1622.41171指数股票16200.0726.66191怎样看股票18200.1418.93155股票入门教程30200.1117.5149购置股票31200.223.75180股票交流35300.1119.17160中国股市论坛44300.1623.98182上海股票指数50300.0429.41196股票开户流程54300.125.71187股票怎么看56300.119.84164股票投资入门62400.2321.38170美国股票软件67400.2820.74168虚拟股票72400.1330.66199股票市盈率81500.0724.42184股市走势86500.117.0514

13、5查股票90500.2117.02143股票公式102700.0720.73167如何购置股票104700.1719.73163航空股票105700.1219157股票买卖109700.2422.86173中国远洋股票111700.0530.55198模拟股票114700.1427.89194股票走势117700.1121.33169股票根底知识119700.1124.16183股票公司125900.3617.04144股票交易费用129900.1324.47185中国铁建股票131900.0919.05158股票分析软件132900.2422.7172新手股票1411100.1823.921

14、81谷歌股票1421100.0420.07165股票网1611400.217.47148中国中铁股票1641400.0627.17192怎么买股票1651400.1917.86152股票技术分析1681400.0719.37162中国联通股票1721700.0525.72188搜狐股票1731700.0619.08159新浪财经股票首页1741700.0323.3176香港股票查询1832100.4823.4177股票交易时间1892100.0630.44197股票交易所1902100.1730.78201股票行1942100.4917.17146如何看股票1962100.1118.66154

15、基金股票1972100.2118.98156股指1982100.0430.73200百度股票2022600.0532.88204股票行情查询2052600.0422.86174股票投资2123200.3225.64186股票2143200.3820.35166股票知识2153200.1217.18147股票新手2283900.2323.69179股票交易2335900.3131.86203股票软件2345900.229.04195新加坡股票2355900.3518.01153股票入门2428800.1526.05189中国股票24813000.1130.84202炒股25019000.1526

16、.28190gushi25224000.0119.18161香港股票25424000.4623.26175新浪股票25629000.0517.71151港股26066000.2123.52178股市2663680000.0117.51150第2个簇：关键词编号搜索量竞争价值估价排名股票模拟软件24200.1375.05237股票自动交易软件26200.1377.44239新浪股票博客36300.0680.16240股票怎么买73400.2192.89248股票技巧80500.2385.53244新股票89500.1168.96235股票书92500.0689.06246联通股票93500.03

17、104.99252股票根本知识107700.0968.56234股票大盘127900.1103.13251股票研究133900.1180.77241中国重工股票138900.190.51247中国股票行情1481100.0776.05238股票网上开户1591400.1103.04250股票交易手续费1661400.1285.11243石油股票1912100.1893.22249台湾股票2002100.2371.25236澳洲股票2183900.2185.95245新浪股市2233900.0484.8242第3个簇：关键词编号搜索量竞争价值估价排名江苏阳光股票29200.1154.15262今

18、日股市行情大盘49300.12117.53253怎么玩股票52300.1133.11257银行股票68400.11123.23254股票计算器74400.1144.89259股票频道101700.04130.46255a股大盘126900.06174.74264证券股137900.03150.32260中国石化股票1581400.01142.11258st股票1691400.05168.23263民生银行股票1932100.06130.61256招商银行股票2103200.03152.85261第4个簇：关键词编号搜索量竞争价值估价排名美国股票交易软件2100.324.6534股票价格查询41

19、00.091.8311投资美国股票5100.380.11股票书籍下载6100.125.844股票趋势11200.116.9555股市投资12200.292.8216股票怎么开户13200.160.684股票下载17200.23.420世界股市行情19200.130.183加拿大股票交易21200.174.2932怎么买美国股票22200.282.6315购置美国股票23200.183.4221股票购置27200.142.4213股票入门知识38300.124.3533股市资讯网53300.081.058中国股指期货58400.055.3742如何买美国股票61400.263.5123怎样玩股票

20、64400.155.9847深圳股票交易所65400.137.2756股市场69400.211.3910股票操盘手76400.050.856北美股票78500.224.7536股市财经85500.10.12今日股市行情大盘走势91500.130.977股票信息98500.233.2119美国股票市场100700.295.3641怎样买股票108700.246.1148今天股票行情110700.226.4451股票根底122700.073.9625a股新股124900.054.0728股票怎么玩130900.162.5614股市指数136900.095.6843美国股票开户1441100.236

21、.6653香港股票行情1471100.56.6252投资股票1491100.294.9837新加坡股票交易所1501100.141.229全球股票1511100.132.9718巴菲特股票1571100.073.4822a股行情1701400.096.2150人民网新闻1711700.23.9726股票价格1761700.137.3257股票资讯1862100.164.0929如何玩股票2032600.144.735股票查询2042600.156.9554qq股票2062600.085.8645什么是股票2072600.13.6824加拿大股票2173900.084.0427股票市场22039

22、00.224.2331股票型基金2263900.244.1830a股基金2273900.395.340马来西亚股票2325900.152.917雅虎股票2377200.155.8846股票消息2387200.212.1112今日股票行情2438800.26.1949美国股票2448800.315.339新浪网新闻25324000.060.725周26181000.215.1938第5个簇：关键词编号搜索量竞争价值估价排名中国股市大盘33300.0450.39227香港股票软件39300.5440.68219房地产股票40300.134.05208财经资讯41300.0745.02223怎么炒股

23、票42300.1149.45225股票短线43300.0533.05205新浪股市行情51300.0433.96206股市中国57300.0653.1228股票图79500.139.41216股票预测84500.0439.11214同花顺股票88500.0639.06213股市新闻116700.1553.13229股票交易软件128900.2138.16211股票学习1451100.0861.42233股票入门根底知识1531100.1439.81218中国股票市场1621400.1449.94226和讯股票1791700.0558.63231股票指数1812100.0634.19209tcl

24、股票1842100.0459.64232股票吧1852100.0436.77210股价1922100.0546.88224网易股票2113200.142.09221炒股票2163900.2541.99220新浪财经股票2213900.1233.99207中国股市行情2294800.1339.39215中石化股票2315900.0943.83222股票开户2365900.1755.28230苹果股票2407200.0639.59217证券24713000.0438.53212第6个簇：关键词编号搜索量竞争价值估价排名模拟股票游戏1100.0711.78105同花顺股票软件3100.116.731

25、40买什么股票好7100.1314.45127股票证券9200.1312.9118新浪网股票10200.099.4584新浪财经新闻14200.0512.35110上证股票20200.0911.52102学股票25200.1412.85116怎样炒股票28200.237.7258中国股票网32200.1512.59112股票交易系统34300.1711.46101今日股票行情查询37300.169.8789股票自动交易45300.0814.92131买美国股票46300.59.2680如何买卖股票47300.228.4869美国股票交易48300.338.9978如何购置美国股票55300.3

26、8.6272格力股票59400.089.8288股票教程60400.0912.03107指数期货63400.0812.11108股票代码查询66400.110.4592如何选股票70400.077.9662股票走势图71400.119.4885股票新浪75400.068.5571腾讯财经股票77400.1214.85129稀土股票82500.1413.05119股票行情软件83500.1212.77114股票模拟94500.139.7886股票新闻95500.168.975股票入门书籍96500.0413.81124财经股票97500.6615.39134股票期货99500.18.3668股票

27、网站103700.1313.17120股票工具106700.2510.6394股票游戏112700.0814.45128如何炒股票113700.238.0465香港股票开户115700.710.9896如何投资股票118700.349.3682财经新闻网120700.477.7760紫金矿业股票121700.113.27121美国股票行情123900.319.1479创业板股票134900.0614.12126鸿海股票135900.077.7459新上市股票1391100.188.8374建设银行股票1401100.0515.77136中阈股票市埸1431100.2716.81141股票走势1

28、461100.238.5370股票估值1521100.1114.07125中国证券1541100.0311.2999香港股票交易所1551100.5212.22109股票是什么1561100.19.3281买股票1601400.2215.34133财经频道1631400.0215.96138股票手续费1671400.1216.67139如何买股票1751700.1815.22132股市大盘1771700.0712.88117股票佣金1781700.3715.56135股票报价1801700.458.0466看股票1822100.0911.2598深圳股票1872100.2912.65113股票

29、1882100.5511.58103股票推荐1952100.1613.33122股票代码1992100.078.0263日本股票2012600.1712.36111今日股票2082600.188.9677股票资轩12092600.2611.77104中阈股市行情2133200.077.8861股票基金2193900.2616.97142股票配资2243900.198.9476股票论坛2253900.0912.79115上海股票2304800.0811.88106全球股市指数2397200.019.3983股市幸艮2417200.28.0264gupiao24510000.0615.94137腾讯股票24610000.0510.8695财经新闻24913000.1910.4893财经网25119000.2213.38123今日股市行情25524000.068.