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.