數(shù)據(jù)挖掘報(bào)告

數(shù)據(jù)挖掘課程報(bào)告班級(jí) XXXXXX 學(xué)生姓名 XXXXXX 學(xué)號(hào)2010100XXXXX指導(dǎo)教師 XXXXXXX日期2013年10月15日k-means算法與貓群算法的聚類效果比較分析摘要：本文在聚類個(gè)數(shù)k值預(yù)先設(shè)定的前提下，分別應(yīng)用了k-means算法、貓群算法對(duì)儲(chǔ)層含油性問(wèn)題進(jìn)行聚類分析，比較了這兩種算法的聚類效果。實(shí)驗(yàn)結(jié)果顯示：本文所采用的傳統(tǒng)的k-means算法常容易陷入局部最優(yōu)。而貓群算法在樣本數(shù)目較小時(shí)（如以表oilsk81為例時(shí)），是一種快速、高效的識(shí)別算法。當(dāng)樣本數(shù)目翻倍時(shí)，受實(shí)際算法代碼設(shè)計(jì)的影響，識(shí)別的正確率將會(huì)下降，這也充分說(shuō)明了貓群算法的運(yùn)算效果受代碼和樣本大小的影響，有較大的不確定性。關(guān)鍵詞：k-means；貓群算法；聚類分析；1引言K-means算法⑴是由J.B.MacQueen于1967年提出的，該算法是一個(gè)經(jīng)典的基于劃分的聚類算法，因其算法效率較高，易于其它方法相結(jié)合，目前已成為數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、模式識(shí)別和數(shù)量統(tǒng)計(jì)等領(lǐng)域應(yīng)用最廣的聚類算法之一。近幾年來(lái)提出了很多的群體智能算法,這些算法都是通過(guò)模仿生物界中某些動(dòng)物的行為演化出來(lái)的智能算法⑵。貓群算法作為群體智能算法之一，具有良好的局部搜索和全局搜索能力⑶，算法控制參數(shù)較少，通過(guò)兩種模式的結(jié)合搜索，大大的提高了搜索優(yōu)良解的可能性和搜索效率，較其他算法較容易實(shí)現(xiàn)，收斂速度快，具有較高的運(yùn)算速度，易于其他算法結(jié)合。但也有出現(xiàn)“早熟”現(xiàn)象的弊端［4］。群體中個(gè)體的優(yōu)化只是根據(jù)一些表層的信息，即只是通過(guò)適應(yīng)度值來(lái)判斷個(gè)體的好壞，缺乏深層次的理論分析和綜合因素的考慮。由于貓群算法出現(xiàn)較晚，該算法目前主要應(yīng)用于函數(shù)優(yōu)化問(wèn)題習(xí)，故在聚類分析研究方面，很有必要對(duì)貓群算法進(jìn)行深入研究。傳統(tǒng)的k-means算法與新興的聚類方法貓群算法相比較會(huì)有哪些異同點(diǎn)呢，接下來(lái)將具體闡述。2算法模型2.1K-means算法模型設(shè)對(duì)n個(gè)m維樣本集進(jìn)行聚類，n個(gè)樣本集表示為X二｛X,X，…，X｝，其中TOC\o"1-5"\h\z1 2 nX=（x,x，…，x），聚類成k個(gè)分類表示為C二｛C,C，…C｝，其質(zhì)心表示為i i1i2 im 12 k1z=工X,j=1,2,....k\o"CurrentDocument"jn' nC 一jxeCj ，j為j中包含的數(shù)據(jù)點(diǎn)的個(gè)數(shù)，則聚類的目標(biāo)是使k個(gè)類滿足以下條件：

d(x,z) >Minijijjixi￡式中，d(x,z)表示計(jì)算數(shù)據(jù)間距離的函數(shù)，他jij可以是不同的度量方式，本文選擇歐氏距離度量函數(shù)來(lái)度量，k為聚類數(shù)目，Z.為j類樣本的聚類中心。j2.1貓群算法模型基本流程：貓群算法的基本流程分為以下5步。具體流程如圖1所示。初始化貓群。根據(jù)分組率將貓群隨機(jī)分成搜尋模式和跟蹤模式兩組。根據(jù)貓的模式標(biāo)志位所確定的模式進(jìn)行位置更新，如果貓?jiān)谒褜つＪ较?，則執(zhí)行搜尋模式的行為；否則，執(zhí)行跟蹤模式的行為。通過(guò)適應(yīng)度函數(shù)來(lái)計(jì)算每一只貓的適應(yīng)度，記錄保留適應(yīng)度最優(yōu)的貓。判斷是否滿足終止條件，若滿足則輸出最優(yōu)解，結(jié)束程序；否則繼續(xù)執(zhí)行步驟。輸出最優(yōu)解，算法.結(jié)束丿圖輸出最優(yōu)解，算法.結(jié)束丿3儲(chǔ)層含油性識(shí)別問(wèn)題的聚類分析本文從儲(chǔ)層含油性問(wèn)題入手，以O(shè)ilsk81等3口井測(cè)井解釋成果為例，對(duì)儲(chǔ)層參數(shù)分布特征通過(guò)K-means算法、貓群算法進(jìn)行了聚類分析，最后與測(cè)井原有結(jié)果對(duì)比，研究比較K-means算法、貓群算法基于不同數(shù)據(jù)集以及不同迭代次數(shù)的分類準(zhǔn)確率。3.1樣本和指標(biāo)的選取實(shí)驗(yàn)數(shù)據(jù)來(lái)自于江漢油田某區(qū)塊，該區(qū)塊有oilsk81等3口井，本文選用的實(shí)驗(yàn)數(shù)據(jù)來(lái)分別自于oilsk81、oilsk83、oilsk85井。其中oilsk81井屬性和對(duì)應(yīng)的測(cè)井解釋結(jié)論如表1所/示0表1oilsk81井測(cè)井解釋成果表層號(hào)聲波(ys/m)中子(%)深測(cè)向電阻率(Q.m)孔隙度(%)含油飽和度(%)滲透率(mym2)結(jié)論11957.513.06.000干層222510.07.311.000水層323014.05.512.000水層42209.025.09.0561.3油層52258.030.09.0582.3油層62107.026.06.000干層72208.026.010.0602.4油層82259.030.010.0622.5油層91954.036.05.500干層102209.030.09.0611.7油層112177.550.08.0551.1油層122106.0130.07.0480.7差油層131954.0100.05.000干層141954.070.05.000干層152006.090.06.000干層162004.0130.06.000干層172004.090.05.000干層182159.025.09.0541.6油層191954.070.04.000干層202006.055.06.000干層212004.0100.05.000干層2224013.512.012.0402.4油層232128.036.08.0601.5油層241976.050.06.000干層252026.055.07.0520.8差油層261954.550.06.000干層272035.045.07.0460.6差油層281956.050.06.000干層292107.520.08.0571.2油層302016.016.07.0400.4差油層312139.512.09.0612油層從表1中的數(shù)據(jù)可以看出，用于儲(chǔ)層含油性識(shí)別的屬性集合為：聲波時(shí)差，中子，深測(cè)向電阻率，孔隙度，含油飽和度和滲透率。測(cè)并解釋結(jié)論為：油層，差油層，水層和干層。3.2K-means算法的聚類分析本文應(yīng)用的是matlab軟件自帶的K-means函數(shù)，即傳統(tǒng)的K-means算法。K值是已知的，值為4。在命令窗口中輸入命令，[cid,C,sumD]=Kmeans(x,4)”。輸出參數(shù)分別為cid,C,sumD,cid為N*1的向量，存儲(chǔ)的是每個(gè)點(diǎn)的聚類標(biāo)號(hào)；C為K*P的矩陣，存儲(chǔ)的是K個(gè)聚類質(zhì)心位置；sumD1*K的和向量，存儲(chǔ)的是類間所有點(diǎn)與該類質(zhì)心點(diǎn)距離之和。x為樣本數(shù)據(jù)的矩陣。以O(shè)ilsk81為樣本數(shù)據(jù)集，結(jié)果為｛333113114112242221442114141411圖3K-means聚類分析結(jié)果以O(shè)ilsk83為樣本數(shù)據(jù)集，聚類分析結(jié)果如圖:圖4最優(yōu)聚類結(jié)果圖3K-means圖3K-means聚類分析結(jié)果以O(shè)ilsk83為樣本數(shù)據(jù)集，聚類分析結(jié)果如圖:圖4最優(yōu)聚類結(jié)果圖3K-means聚類分析結(jié)果圖4最優(yōu)聚類結(jié)果以O(shè)ilsk85為樣本數(shù)據(jù)集，聚類分析結(jié)果如圖:圖3K-means聚類分析結(jié)果圖4最優(yōu)聚類結(jié)果由于K-means算法采用隨機(jī)法選取k個(gè)初始聚類中心點(diǎn)，隨機(jī)選擇的初始中心點(diǎn)可能導(dǎo)致算法聚類效果不穩(wěn)定，且使算法常陷入局部最優(yōu)而聚類結(jié)果非全局最優(yōu)。從上述K-means聚類分析結(jié)果與最優(yōu)聚類結(jié)果的對(duì)比圖中，可看出K-means算法對(duì)初始聚類中心選擇具有依賴性。3.2貓群算法的聚類分析設(shè)貓群數(shù)量CatNum=200,記憶池大小SMP=5,啟發(fā)式因子Ot=l,樣本特征值變化概率CDC=1，樣本變化值范圍SRD=0.2，每個(gè)貓個(gè)體所屬行為模式標(biāo)志flag=0為搜尋模式，flag=1時(shí)為跟蹤模式，同時(shí)在種群中選擇2%個(gè)貓執(zhí)行跟蹤模式，其他為搜尋模式。聚類時(shí)以歐氏距離衡量相似性，為消除數(shù)值在不同量綱下的差異，對(duì)數(shù)據(jù)進(jìn)行了歸一化處理。數(shù)據(jù)集的6個(gè)屬性全部用于儲(chǔ)層含油性的識(shí)別。聚類的結(jié)果如表1、表二所示：表2基于不同數(shù)據(jù)集的聚類正確率井號(hào)迭代次數(shù)為50迭代次數(shù)為100迭代次數(shù)為200迭代次數(shù)為500Oilsk81100%100%100%100%Oilsk8394%94%94%94%Oilsk8566.15%69.23%70.77%76.92%表3基于不同數(shù)據(jù)集的樣本聚類錯(cuò)誤情況井號(hào)迭代次數(shù)為50迭代次數(shù)為100迭代次數(shù)為200迭代次數(shù)為500Oilsk81無(wú)無(wú)無(wú)無(wú)Oilsk824,5,64,5,64,5,64,5,613,14,16,18,19,20,21,13,14,15,16,17,18,19,5,13,14,18,19,20,21,22,13,14,15,16,17,1&19,222,23,24,25,26,27,31,20,21,22,24,25,26,31,24,25,26,31,40,43,46,470,21,22,24,25,26,31,34,Oilsk8534,40,43,49,50,55,5&34,40,43,49,50,55,5&,49,50,51,54,57,40,43,49,50,55,5&在貓群算法針對(duì)oilsk81井測(cè)井解釋成果表中的特征值進(jìn)行反復(fù)地運(yùn)行分類后，可以發(fā)現(xiàn)oilsk81表的特征值在迭代10次后，在第10代出現(xiàn)了與原有結(jié)果完全一致的結(jié)論，而后分別在迭代50次、100次、200次、500次中得出了完全一樣的結(jié)果。所以貓群算法針對(duì)oilsk81表的數(shù)據(jù)集在以上4種迭代次數(shù)的環(huán)境下，其準(zhǔn)確率達(dá)到了100%。在貓群算法針對(duì)oilsk83井測(cè)井解釋成果表中的特征值進(jìn)行反復(fù)地運(yùn)行分類后，發(fā)現(xiàn)oilsk83表的特征值在迭代20次后，與原有結(jié)論相比，出現(xiàn)了三個(gè)不同的結(jié)論，即第4,5,6項(xiàng)中的差油層和干層均被分為水層。而后進(jìn)行了50次、100次、200次、500次的迭代，結(jié)果與原結(jié)論相比，仍有三個(gè)差異項(xiàng)。由于oilsk83表與oilsk81表相比，數(shù)據(jù)項(xiàng)增多，故在相同迭代條件下，未能達(dá)到完全準(zhǔn)確。固定的分類錯(cuò)誤項(xiàng)受算法本身的代碼設(shè)計(jì)影響，所以貓群算法針對(duì)oilsk83表的數(shù)據(jù)集在以上4種迭代次數(shù)的環(huán)境下，其準(zhǔn)確率達(dá)到94%。3.3兩種算法的聚類效果比較K-means算法是聚類分析中一種常用的基于劃分的方法，同時(shí)存在不足，聚類結(jié)果受初始類中心影響較大而過(guò)早收斂于次優(yōu)解。從聚類效果的分析對(duì)比圖中可以看出，K-means傾向于局部最優(yōu)而非全局最優(yōu)，這是它的缺點(diǎn)。而貓群算法在以oilsk81井測(cè)井結(jié)果為數(shù)據(jù)集時(shí)，聚類效果能夠達(dá)到最優(yōu)；在數(shù)據(jù)集較大的情況下，準(zhǔn)確率會(huì)下降，如以oilsk85井測(cè)井結(jié)果為數(shù)據(jù)集時(shí)正確率僅能達(dá)到67.69%。故大膽推測(cè)，在數(shù)據(jù)量相對(duì)較小時(shí)，選用貓群算法的聚類效果更好。參考文獻(xiàn):⑴ 張立;基于新聞評(píng)論數(shù)據(jù)的K-means聚類算法的