大數(shù)據(jù)挖掘聚類(lèi)算法課程設(shè)計(jì)報(bào)告材料

1、實(shí)用標(biāo)準(zhǔn)文案數(shù)據(jù)挖掘聚類(lèi)問(wèn)題 (Plants Data Set)實(shí)驗(yàn)報(bào)告1. 數(shù)據(jù)源描述1.1 數(shù)據(jù)特征本實(shí)驗(yàn)用到的是關(guān)于植物信息的數(shù)據(jù)集，其中包含了每一種植物(種類(lèi)和科屬 )以及它們生長(zhǎng)的地區(qū)。數(shù)據(jù)集中總共有68 個(gè)地區(qū)，主要分布在美國(guó)和加拿大。一條數(shù)據(jù)(對(duì)應(yīng)于文件中的一行)包含一種植物 (或者某一科屬 )及其在上述68 個(gè)地區(qū)中的分布情況?？梢赃@樣理解，該數(shù)據(jù)集中每一條數(shù)據(jù)包含兩部分內(nèi)容，如下圖所示。植物名稱 ( 科屬 +名稱 )分布區(qū)域圖 1 數(shù)據(jù)格式例如一條數(shù)據(jù) :abroniafragrans,az,co,ks,mt,ne,nm,nd,ok,sd,tx,ut,wa,wy。其中abro

2、niafragrans是植物名稱 (abronia是科屬， fragrans是名稱 ) ，從 az 一直到 wy是該植物的分布區(qū)域，采用縮寫(xiě)形式表示，如az 代表的是美國(guó)Arizona州。植物名稱和分布地區(qū)用逗號(hào)隔開(kāi)，各地區(qū)之間也用逗號(hào)隔開(kāi)。1.2 任務(wù)要求聚類(lèi)。采用聚類(lèi)算法根據(jù)某種特征對(duì)所給數(shù)據(jù)集進(jìn)行聚類(lèi)分析，對(duì)于聚類(lèi)形成的簇要使得簇內(nèi)數(shù)據(jù)對(duì)象之間的差異盡可能小，簇之間的差距盡可能大。2. 數(shù)據(jù)預(yù)處理2.1 數(shù)據(jù)清理所給數(shù)據(jù)集中包含一些對(duì)聚類(lèi)過(guò)程無(wú)用的冗余數(shù)據(jù)。數(shù)據(jù)集中全部數(shù)據(jù)的組織結(jié)構(gòu)是：先給出某一科屬的植物及其所有分布地區(qū)，然后給出該科屬下的具體植物及其分布地區(qū)。例如：文檔大全實(shí)用標(biāo)準(zhǔn)文

3、案abelmoschus,ct,dc,fl,hi,il,ky,la,md,mi,ms,nc,sc,va,pr,viabelmoschus esculentus,ct,dc,fl,il,ky,la,md,mi,ms,nc,sc,va,pr,viabelmoschus moschatus,hi,pr上述數(shù)據(jù)中第行給出了所有屬于abelmoschus這一科屬的植物的分布地區(qū)，接下來(lái)的兩行分別列出了屬于abelmoschus科屬的兩種具體植物及其分布地區(qū)。從中可以看出后兩行給出的所有地區(qū)的并集正是第一行給出的地區(qū)集合。在聚類(lèi)過(guò)程中第行數(shù)據(jù)是無(wú)用的，因此要對(duì)其進(jìn)行清理。2.2 數(shù)據(jù)變換本實(shí)驗(yàn)是依據(jù)植物的

4、分布區(qū)域進(jìn)行聚類(lèi)，所給數(shù)據(jù)集中的分布區(qū)域是字符串形式，不適合進(jìn)行聚類(lèi)，因此將其變換成適合聚類(lèi)的數(shù)值形式。具體思想如下：數(shù)據(jù)集中總共包含68 個(gè)區(qū)域，每一種植物的分布區(qū)域是這68 個(gè)區(qū)域中的一部分。本實(shí)驗(yàn)中將 68 個(gè)區(qū)域看成是數(shù)據(jù)對(duì)象的68 個(gè)屬性，這 68 個(gè)屬性是二元類(lèi)型的變量，其值只能去0 或者 1。步驟如下：1.把 68 個(gè)區(qū)域按一定順序存放在字符串?dāng)?shù)組(記為 str) 中(順序可以自己定，確定后不能改變 )。2.為數(shù)據(jù)集中的每個(gè)數(shù)據(jù)對(duì)象設(shè)置一個(gè)長(zhǎng)度為68 字符串?dāng)?shù)組，初始元素值全為 0。將數(shù)據(jù)對(duì)象的分布區(qū)域逐個(gè)與 str 中的所有元素比較。如果存在于str中下標(biāo) i 的位置，就將該數(shù)

5、據(jù)對(duì)象的字符串?dāng)?shù)組的第i 位置為 1。例如，一個(gè)數(shù)據(jù)對(duì)象為：abies fraseri,ga,nc,tn,va。其分布區(qū)域包含ga,nc,tn和 va 四個(gè)地區(qū)，將這四個(gè)地區(qū)逐個(gè)與 str 中全部 68 個(gè)元素比較。 假設(shè)這四個(gè)地區(qū)分別存在于 str 中的第 0,1,2,3 位置，則將為該數(shù)據(jù)對(duì)象設(shè)置的字符串?dāng)?shù)組中第 0,1,2,3 位置全部置為 1 。文檔大全實(shí)用標(biāo)準(zhǔn)文案數(shù)據(jù)預(yù)處理代碼 ( 包括數(shù)據(jù)清理和數(shù)據(jù)變換) ：publicArrayList<String> getRaw_DataSet() ArrayList<String> raw_dataSet =newA

6、rrayList<String>();/定義集合存儲(chǔ)從本地獲取的數(shù)據(jù)BufferedReader bufferedReader =null ;FileReader fileReader =null ;File dataFile =newFile( this .fileName);if (dataFile.exists() /如果數(shù)據(jù)文件存在tryfileReader =newFileReader(this .fileName);bufferedReader =newBufferedReader(fileReader);String data =null ;while(data =

7、bufferedReader.readLine() !=null ) if (isRightData(data)raw_dataSet.add(data); catch(Exception e) e.printStackTrace(); elsethis .isFileExit= false ;returnraw_dataSet;文檔大全實(shí)用標(biāo)準(zhǔn)文案/ getRaw_DataSet,從本地 txt 文件獲取數(shù)據(jù)集publicArrayList<DataItem> getFinished_DataSet() /獲取經(jīng)過(guò)預(yù)處理，用來(lái)進(jìn)行聚類(lèi)的數(shù)據(jù)ArrayList<DataIte

8、m> finished_DataSet =newArrayList<DataItem>();ArrayList<String> temp_DataSet =this .getRaw_DataSet();for(inti = 0; i < temp_DataSet.size(); i+) ArrayList<String> eachRomItem =null ;eachRomItem =this .spilt(temp_DataSet.get(i),',' );/除去 "," 后的每一行數(shù)據(jù)DataItem da

9、ta_Item =newDataItem(eachRomItem,true );finished_DataSet.add(data_Item);/ forreturnfinished_DataSet;publicbooleanisRightData(String data) /篩選出合適的數(shù)據(jù)ArrayList<String> tempArrayList =newArrayList<String>();tempArrayList = spilt(data,' ' );if (tempArrayList.size() <= 1)returnfalse

10、 ;returntrue ;/ isRightData,篩選出合適的數(shù)據(jù)文檔大全實(shí)用標(biāo)準(zhǔn)文案publicArrayList<String> spilt(String str,charch) ArrayList<String> words =newArrayList<String>();/用來(lái)存放找到的單詞int beginIndex = 0;for(inti = 0; i < str.length(); i+) if (str.charAt(i) != ch) if (i != str.length() - 1)continue;else words.

11、add(str.substring(beginIndex); else String temp = str.substring(beginIndex, i);words.add(temp);beginIndex = i + 1;/ forreturnwords;3. 聚類(lèi)分析3.1算法描述本實(shí)驗(yàn)采用了聚類(lèi)分析中常用的K 均值 (K-Means) 算法。該算法思想如下：文檔大全實(shí)用標(biāo)準(zhǔn)文案算法：K 均值。用于劃分的K 均值算法，每個(gè)簇的中心用簇中對(duì)象的均值表示。輸入：k ：簇的屬目D ：包含 n 個(gè)對(duì)象的數(shù)據(jù)集。輸出：k 個(gè)簇的集合。方法：(1)從 D 中任意選擇 k 個(gè)對(duì)象作為初始簇中心；(2

12、) repeat(3) 根據(jù)簇中對(duì)象的均值，將每個(gè)對(duì)象 (再)指派到最相似的簇；(4) 更新簇均值，既計(jì)算每個(gè)簇中對(duì)象的均值；(5) until 不再發(fā)生變化根據(jù)上述算法，結(jié)合本實(shí)驗(yàn)實(shí)際情況和數(shù)據(jù)集特征給出程序的執(zhí)行流程圖：開(kāi)始從本地讀取數(shù)據(jù)文件數(shù)據(jù)預(yù)處理輸入 k,簇的個(gè)數(shù)在數(shù)據(jù)集中隨機(jī)選取k 個(gè)數(shù)據(jù)對(duì)象作為初始中心點(diǎn)迭代開(kāi)始。將數(shù)據(jù)集中每個(gè)數(shù)據(jù)對(duì)象與 k 個(gè)中心點(diǎn)作比較，把每個(gè)對(duì)象分到與其 最相似 的中心點(diǎn)所在的簇中計(jì)算每個(gè)簇中對(duì)象的均值，作為該簇新的中心點(diǎn)滿足迭代終迭代終止，輸出結(jié)果。止條件文檔大全實(shí)用標(biāo)準(zhǔn)文案是否圖 2 程序執(zhí)行流程針對(duì)上面的流程圖，有幾點(diǎn)說(shuō)明：1.數(shù)據(jù)預(yù)處理主要包括前述

13、數(shù)據(jù)清理和數(shù)據(jù)變換，最終生成用于聚類(lèi)分析的數(shù)據(jù)集。2.簇的個(gè)數(shù) k 由用戶指定， k 越大聚類(lèi)過(guò)程耗時(shí)越久。3.圖中“最相似” 意思就是距離中心點(diǎn)距離最近，本實(shí)驗(yàn)中采用歐幾里得距離，其定義如下：d (i, j ) ( xi1222x j1)(xi 2 x j 2) .(xin x jn )其中 i( xi1 , xi 2 ,., xin ) 和 j( xj1 , xj 2 ,. xjn ) 是兩個(gè) n維數(shù)據(jù)對(duì)象。在本實(shí)驗(yàn)中，x 和 x 分別代表為 i,j 兩個(gè)數(shù)據(jù)對(duì)象設(shè)置的字符串?dāng)?shù)組 (參看 2.2) 中下標(biāo)為 1 的i 1j1元素值，此處 n 為 68 。4.流程圖中的終止條件指的是：前后兩

14、次中心點(diǎn)之間的距離(仍然用歐幾里得距離 )是否小于設(shè)定的值。 例如，第 n 次迭代完成后重新生成了k 個(gè)新的中心點(diǎn)，計(jì)算 k 個(gè)新中心點(diǎn)與 k 個(gè)舊的中心點(diǎn)距離之和并將結(jié)果與設(shè)定的值比較，若小于文檔大全實(shí)用標(biāo)準(zhǔn)文案設(shè)定值則終止迭代，聚類(lèi)完成，否則繼續(xù)迭代。3.2算法實(shí)現(xiàn)圖 3 代碼文件的組織結(jié)構(gòu)上圖是本實(shí)驗(yàn)源碼的組織結(jié)構(gòu)，該項(xiàng)目包含五個(gè)Java 類(lèi)。每個(gè)類(lèi)的功能描述如下：Cluster.java類(lèi) 該類(lèi)定義了簇的結(jié)構(gòu)，包含簇標(biāo)志，簇成員和簇中心點(diǎn)三個(gè)字段。該類(lèi)的每一個(gè)實(shí)例對(duì)應(yīng)于聚類(lèi)過(guò)程中的一個(gè)簇。DataItem.java類(lèi) 該類(lèi)定義了數(shù)據(jù)對(duì)象的結(jié)構(gòu)，主要包含數(shù)據(jù)對(duì)象名稱( 即植物名稱 )和數(shù)

15、據(jù)對(duì)象字符串?dāng)?shù)組(即植物的分布區(qū)域) 。該類(lèi)的每一個(gè)實(shí)例對(duì)應(yīng)于數(shù)據(jù)集中的一個(gè)數(shù)據(jù)對(duì)象。Main.java類(lèi) 該類(lèi)是程序的核心類(lèi)，主要功能是執(zhí)行聚類(lèi)過(guò)程，包括中心點(diǎn)的選取與更新，計(jì)算各個(gè)數(shù)據(jù)對(duì)象與中心點(diǎn)之間的距離并把其派分到最相似的簇等。ReadData.java類(lèi) 該類(lèi)主要功能是生成聚類(lèi)過(guò)程適用的數(shù)據(jù)集，包括讀取文件，數(shù)據(jù)預(yù)處理等。Tools.java類(lèi) 該類(lèi)是一個(gè)工具類(lèi)，其中定義了多個(gè)程序中使用到的靜態(tài)方法。Mian.java類(lèi)中的核心代碼：(1) 隨機(jī)選取中心點(diǎn)publicvoidsetCenter_ran() /第一次，從數(shù)據(jù)集中隨機(jī)選取中心點(diǎn)文檔大全實(shí)用標(biāo)準(zhǔn)文案beginTime= S

16、ystem. currentTimeMillis();System. out .println("聚類(lèi)過(guò)程開(kāi)始 ,開(kāi)始于 :" + Tools.currentTime();Random ran =newRandom();int order = 0;/ 隨機(jī)選取中心點(diǎn)while(this.center .size() <numOfCluster) order = ran.nextInt(toBeProcessed.size();if(Tools. isProCener (toBeProcessed.get(order),this .center)this .center

17、.add(toBeProcessed.get(order);/ while(2) 初始化簇集合publicvoidinitArrayCluster(ArrayList<DataItem> center) /初始每個(gè)簇中的中心點(diǎn)屬性this .arrayCluster.clear(); /把簇集合清空f(shuō)or(inti = 0; i < center.size(); i+) Cluster cluster =newCluster(i, center.get(i);if (this .center .get(i).getIsDataItem()cluster.addMembers(

18、center.get(i);this .arrayCluster.add(cluster);(3) 執(zhí)行聚類(lèi)過(guò)程 ( 計(jì)算距離，把數(shù)據(jù)對(duì)象派分到最相似簇中)文檔大全實(shí)用標(biāo)準(zhǔn)文案publicvoidrunCluster(ArrayList<DataItem> center) int beyondIndex = 0;/ 判斷數(shù)據(jù)項(xiàng)屬于哪一個(gè)簇，初始默認(rèn)為是0 簇Random rd =newRandom(); / 隨機(jī)函數(shù)printBeginInfo();/打印以此迭代開(kāi)始前的信息。for(inti = 0; i <toBeProcessed.size(); i+) beyondI

19、ndex = 0;booleanisAlreadyExitInCluster =true ;/標(biāo)記當(dāng)前處理的數(shù)據(jù)對(duì)象是否已經(jīng)存在于某個(gè)簇中doubleminDistance = Tools.calcDistance (toBeProcessed.get(i),center.get(0), 0);intranIndex = rd.nextInt(center.size();/隨機(jī)產(chǎn)生一個(gè)中心點(diǎn)集合的索引for( int j = 0; j < center.size(); j+) /分別與每一個(gè)中心點(diǎn)進(jìn)行比較if (center.contains(toBeProcessed.get(i)/如

20、果正在處理的數(shù)據(jù)對(duì)象存在于中心點(diǎn)集合中，則跳出循環(huán)break;isAlreadyExitInCluster =false ;if (ranIndex >= center.size()ranIndex = ranIndex % center.size();doublecorrentDistance = Tools.calcDistance (toBeProcessed.get(i), center.get(ranIndex), 0);if (correntDistance < minDistance) minDistance = correntDistance;文檔大全實(shí)用標(biāo)準(zhǔn)文案b

21、eyondIndex = ranIndex;/第二個(gè)ifranIndex+;/第二個(gè)forif (!isAlreadyExitInCluster) this .arrayCluster.get(beyondIndex).addMembers(toBeProcessed.get(i); /把數(shù)據(jù)對(duì)象加入到對(duì)應(yīng)的簇中/第一個(gè) forSystem. out .println("第 " + this .count+ " 次迭代完成。");printClusteringInfo();(4) 迭代過(guò)程 ( 產(chǎn)生新的中心點(diǎn)，繼續(xù)執(zhí)行聚類(lèi)過(guò)程直至滿足終止條件)publi

22、cvoidfinishCluster() DecimalFormat df =newDecimalFormat("#.000");/格式化數(shù)據(jù)，保留三位小數(shù)for(inti = 0; i <NUM ; i+) doublemoveDistance = 0.0;/存放各個(gè)簇新舊中心點(diǎn)歐幾里得距離之和/重新計(jì)算簇中心點(diǎn)for( int j = 0; j <numOfCluster; j+) booleanisEmptyCluster =true ;DataItem newCenterItem;/聲明新的中心點(diǎn)對(duì)象文檔大全實(shí)用標(biāo)準(zhǔn)文案int size =this .a

23、rrayCluster.get( j).getMembers().size();double newCenterArea =newdouble NUMOFAREA ;/ 計(jì)算簇中數(shù)據(jù)的均值for (intindex = 0; index <NUMOFAREA ; index+) doubletempValue = 0.0;/暫存每一列區(qū)域值的加和for ( intk = 0; k < size; k+) isEmptyCluster =false ;tempValue +=this .arrayCluster.get( j).getMembers().get(k).getAreas

24、()index;if (!isEmptyCluster) newCenterAreaindex = Double.valueOf (df.format(tempValue / size); elsebreak ;/第三個(gè)forif (!isEmptyCluster) /如果簇不為空String name ="cluster"+ j;newCenterItem =newDataItem(name, newCenterArea,false );/新的簇中心點(diǎn)對(duì)象DataItem oldCenter =this .center .get( j); /獲取舊的簇中心點(diǎn)moveDis

25、tance += Tools.calcDistance (oldCenter,文檔大全實(shí)用標(biāo)準(zhǔn)文案newCenterItem, 0);/計(jì)算新舊中心點(diǎn)移動(dòng)的距離this .center .remove(j); /更新簇中心點(diǎn)集合this .center .add( j, newCenterItem);/第二個(gè)for, 重新計(jì)算簇中心/ System.out.println(this.center.toString();/打印新的中心點(diǎn)信息if (moveDistance <EXIT * numOfCluster) break ;count +;initArrayCluster(this

26、.center );runCluster(this .center );/第一個(gè) for3.3問(wèn)題與改進(jìn)聚類(lèi)分析要求不同簇之間的距離盡可能大，初始隨機(jī)選取的中心點(diǎn)并不能保證不同中心點(diǎn)之間的距離盡可能遠(yuǎn)，本程序?qū)λ惴ㄟM(jìn)行改進(jìn)， 在隨機(jī)選取中心點(diǎn)時(shí)要求與已經(jīng)選取的中心點(diǎn)之間的距離大于設(shè)定值。這樣做保證了隨機(jī)選取的中心點(diǎn)相對(duì)比較分散，提高了聚類(lèi)效果。主要代碼如下：publicstaticbooleanisProCener(DataItem centerItem,/判斷是不是合適的中心點(diǎn)ArrayList<DataItem> center) if (center.size() > 0) /如果當(dāng)前的中心點(diǎn)集合不為空文檔大全實(shí)用標(biāo)準(zhǔn)文案for( int i = 0; i < center.s