數(shù)據挖掘報告

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

d(x,z) >Minijijjixi￡式中，d(x,z)表示計算數(shù)據間距離的函數(shù)，他jij可以是不同的度量方式，本文選擇歐氏距離度量函數(shù)來度量，k為聚類數(shù)目，Z.為j類樣本的聚類中心。j2.1貓群算法模型基本流程：貓群算法的基本流程分為以下5步。具體流程如圖1所示。初始化貓群。根據分組率將貓群隨機分成搜尋模式和跟蹤模式兩組。根據貓的模式標志位所確定的模式進行位置更新，如果貓在搜尋模式下，則執(zhí)行搜尋模式的行為；否則，執(zhí)行跟蹤模式的行為。通過適應度函數(shù)來計算每一只貓的適應度，記錄保留適應度最優(yōu)的貓。判斷是否滿足終止條件，若滿足則輸出最優(yōu)解，結束程序；否則繼續(xù)執(zhí)行步驟。輸出最優(yōu)解，算法.結束丿圖輸出最優(yōu)解，算法.結束丿3儲層含油性識別問題的聚類分析本文從儲層含油性問題入手，以Oilsk81等3口井測井解釋成果為例，對儲層參數(shù)分布特征通過K-means算法、貓群算法進行了聚類分析，最后與測井原有結果對比，研究比較K-means算法、貓群算法基于不同數(shù)據集以及不同迭代次數(shù)的分類準確率。3.1樣本和指標的選取實驗數(shù)據來自于江漢油田某區(qū)塊，該區(qū)塊有oilsk81等3口井，本文選用的實驗數(shù)據來分別自于oilsk81、oilsk83、oilsk85井。其中oilsk81井屬性和對應的測井解釋結論如表1所/示0表1oilsk81井測井解釋成果表層號聲波(ys/m)中子(%)深測向電阻率(Q.m)孔隙度(%)含油飽和度(%)滲透率(mym2)結論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ù)據可以看出，用于儲層含油性識別的屬性集合為：聲波時差，中子，深測向電阻率，孔隙度，含油飽和度和滲透率。測并解釋結論為：油層，差油層，水層和干層。3.2K-means算法的聚類分析本文應用的是matlab軟件自帶的K-means函數(shù)，即傳統(tǒng)的K-means算法。K值是已知的，值為4。在命令窗口中輸入命令，[cid,C,sumD]=Kmeans(x,4)”。輸出參數(shù)分別為cid,C,sumD,cid為N*1的向量，存儲的是每個點的聚類標號；C為K*P的矩陣，存儲的是K個聚類質心位置；sumD1*K的和向量，存儲的是類間所有點與該類質心點距離之和。x為樣本數(shù)據的矩陣。以Oilsk81為樣本數(shù)據集，結果為｛333113114112242221442114141411圖3K-means聚類分析結果以Oilsk83為樣本數(shù)據集，聚類分析結果如圖:圖4最優(yōu)聚類結果圖3K-means圖3K-means聚類分析結果以Oilsk83為樣本數(shù)據集，聚類分析結果如圖:圖4最優(yōu)聚類結果圖3K-means聚類分析結果圖4最優(yōu)聚類結果以Oilsk85為樣本數(shù)據集，聚類分析結果如圖:圖3K-means聚類分析結果圖4最優(yōu)聚類結果由于K-means算法采用隨機法選取k個初始聚類中心點，隨機選擇的初始中心點可能導致算法聚類效果不穩(wěn)定，且使算法常陷入局部最優(yōu)而聚類結果非全局最優(yōu)。從上述K-means聚類分析結果與最優(yōu)聚類結果的對比圖中，可看出K-means算法對初始聚類中心選擇具有依賴性。3.2貓群算法的聚類分析設貓群數(shù)量CatNum=200,記憶池大小SMP=5,啟發(fā)式因子Ot=l,樣本特征值變化概率CDC=1，樣本變化值范圍SRD=0.2，每個貓個體所屬行為模式標志flag=0為搜尋模式，flag=1時為跟蹤模式，同時在種群中選擇2%個貓執(zhí)行跟蹤模式，其他為搜尋模式。聚類時以歐氏距離衡量相似性，為消除數(shù)值在不同量綱下的差異，對數(shù)據進行了歸一化處理。數(shù)據集的6個屬性全部用于儲層含油性的識別。聚類的結果如表1、表二所示：表2基于不同數(shù)據集的聚類正確率井號迭代次數(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ù)據集的樣本聚類錯誤情況井號迭代次數(shù)為50迭代次數(shù)為100迭代次數(shù)為200迭代次數(shù)為500Oilsk81無無無無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&在貓群算法針對oilsk81井測井解釋成果表中的特征值進行反復地運行分類后，可以發(fā)現(xiàn)oilsk81表的特征值在迭代10次后，在第10代出現(xiàn)了與原有結果完全一致的結論，而后分別在迭代50次、100次、200次、500次中得出了完全一樣的結果。所以貓群算法針對oilsk81表的數(shù)據集在以上4種迭代次數(shù)的環(huán)境下，其準確率達到了100%。在貓群算法針對oilsk83井測井解釋成果表中的特征值進行反復地運行分類后，發(fā)現(xiàn)oilsk83表的特征值在迭代20次后，與原有結論相比，出現(xiàn)了三個不同的結論，即第4,5,6項中的差油層和干層均被分為水層。而后進行了50次、100次、200次、500次的迭代，結果與原結論相比，仍有三個差異項。由于oilsk83表與oilsk81表相比，數(shù)據項增多，故在相同迭代條件下，未能達到完全準確。固定的分類錯誤項受算法本身的代碼設計影響，所以貓群算法針對oilsk83表的數(shù)據集在以上4種迭代次數(shù)的環(huán)境下，其準確率達到94%。3.3兩種算法的聚類效果比較K-means算法是聚類分析中一種常用的基于劃分的方法，同時存在不足，聚類結果受初始類中心影響較大而過早收斂于次優(yōu)解。從聚類效果的分析對比圖中可以看出，K-means傾向于局部最優(yōu)而非全局最優(yōu)，這是它的缺點。而貓群算法在以oilsk81井測井結果為數(shù)據集時，聚類效果能夠達到最優(yōu)；在數(shù)據集較大的情況下，準確率會下降，如以oilsk85井測井結果為數(shù)據集時正確率僅能達到67.69%。故大膽推測，在數(shù)據量相對較小時，選用貓群算法的聚類效果更好。參考文獻:⑴ 張立;基于新聞評論數(shù)據的K-means聚類算法的