【文章內容簡介】 標識。聚類分析生成的類標識刻畫了數據所蘊含的類知識。當然，數據挖掘中的分類和聚類技術都是在已有的技術基礎上發(fā)展起來的，它們互有交叉和補充。 目前，數據挖掘研究中的聚類技術研究也是一個熱點問題。 1999 年， Jain等給出了聚類研究中的主要問題和方法。聚類技術主要是以統計方法、機器學習、神經網絡等方法為基礎的。作為統計學的一個重要分支，聚類分析已經被廣泛地研究和應用。比較有代表性的聚類技術是基于幾何距離度量的聚類方法，如歐式距離、曼哈坦距離、明考斯基距離等。在很多情況下，聚類的結果是形 成一個概念，即當一組數據對象可以由一個概念來描述時，就形成一個簇。因此，有的文獻中又稱其為概念聚類。所以，一些問題可能不再是傳統統計方法中的幾何距離所能描述的，而是根據概念的描述來確定。 聚類分析概述 聚類分析源于許多研究領域，包括數據挖掘、統計學、機器學習、模式識別等。它是數據挖掘中的一個功能，但也能作為一個獨立的工具來獲得數據分布的情況，概況出每個簇的特點，或者集中注意力對特定的某些簇作進一步的分析。此外，聚類分析也可以作為其他分析算法的預處理步驟，這些算法在生成的簇上進行處理。 數據挖掘技 術的一個突出的特點是處理巨大的、復雜的數據集，這對聚類分析技術提出了特殊的挑戰(zhàn)，要求算法具有可伸縮性、處理不同類型屬性的能力、發(fā)現任意形狀的類的能力、處理高維數據的能力等。根據潛在的各項應用，數據挖掘對聚類分析方法提出了不同要求。典型要求可以通過以下幾個方面來刻畫。 1． 可伸縮性 可伸縮性是指聚類算法不論對于小數據集還是對于大數據集，都應是有效的。在很多聚類算法當中，數據對象小于幾百個的小數據集合上魯棒性很好，而對于包含上萬個數據對象的大規(guī)模數據庫進行聚類時，將會導致不同的偏差結果。研究大容量數據集的高效聚 類方法是數據挖掘必須面對的挑戰(zhàn)。 2．具有處理不同類型屬性的能力 4 既可處理數據型數據，又可處理非數據型數據，既可以處理離散數據，又可以處理連續(xù)域內的數據，如布爾型，序數型，枚舉型或這些數據類型的混合。 3．能夠發(fā)現任意形狀的聚類 許多聚類算法經常使用歐幾里得距離來作為相似性度量方法，但基于這樣的距離度量的算法趨向于發(fā)現具有相近密度和尺寸的球狀簇。但對于一個簇可能是任意形狀的情況，提出能發(fā)現任意形狀簇的算法是很重要的。 4．輸入參數對領域知識的弱依賴性 在聚類分析當中，許多聚類算法要求用戶輸入一定的參數，如希 望得到的簇的數目。聚類結果對于輸入的參數很敏感，通常參數較難確定，尤其是對于含有高維對象的數據集更是如此。要求用人工輸入參數不但加重了用戶的負擔，也使得聚類質量難以控制。一個好的聚類算法應該對這個問題給出一個好的解決方法。 5．對于輸入記錄順序不敏感 一些聚類算法對于輸入數據的順序是敏感的。例如，對于同一個數據集合，以不同的順序提交給同一個算法時，可能產生差別很大的聚類結果。研究和開發(fā)對數據輸入順序不敏感的算法具有重要的意義。 6．挖掘算法應具有處理高維數據的能力 既可處理屬性較少的數據，又能處理屬性較多的 數據。很多聚類算法擅長處理低維數據，一般只涉及兩到三維，人類對兩三維數據的聚類結果很容易直觀地判斷聚類的質量。但是，高維數據聚類結果的判斷就不是直觀了。數據對象在高維空間的聚類是非常具有挑戰(zhàn)性的，尤其是考慮到這樣的數據可能高度偏斜并且非常稀疏。 7．處理噪聲數據的能力 在現實應用中絕大多數的數據都包含了孤立點、空缺、未知數據或者錯誤的數據。如果聚類算法對于這樣的數據敏感，將會導致質量較低的聚類結果。 8．基于約束的聚類 在實際應用當中可能需要在各種約束條件下進行聚類。既要找到滿足特定的約束，又要具有良好聚類 特性的數據分組是一項具有挑戰(zhàn)性的任務。 9．挖掘出來的信息是可理解的和可用的 5 這點是容易理解的，但在實際挖掘中有時往往不能令人滿意。 聚類分析在數據挖掘中的應用主要有以下幾個方面： 1．聚類分析可以作為其他算法的預處理步驟 利用聚類進行數據預處理，可以獲得數據的基本概況，在此基礎上進行特征抽取或分類就可以提高精確度和挖掘效率。也可將聚類結果用于進一步關聯分析，以進一步獲得有用的信息。 2．可以作為一個獨立的工具來獲得數據的分布情況 聚類分析是獲得數據分析情況的有效方法。例如，在商業(yè)上，聚類分析可以幫助市場分析人員從客戶基本庫當中發(fā)現不同的客戶群，并且用購買模式來刻畫不同的客戶群的特征。通過觀察聚類得到的每個簇的特點，可以集中對特定的某些簇作進一步分析。這在諸如市場細分、目標顧客定位、業(yè)績評估、生物種群劃分等方面具有廣闊的應用前景。 3．聚類分析可以完成孤立點挖掘 許多數據挖掘算法試圖使孤立點影響最小化，或者排除它們。然而孤立點本身可能是非常有用的。如在欺詐探測中，孤立點可能預示著欺詐行為的存在。 PAM 算法分析 PAM 算法詳細論述 PAM（ Partitioning Around Medoid,圍繞中心點的劃分）是聚類分析算法中劃分法的一個聚類方法，是最早提出的 k中心點算法之一。 PAM聚類算法的基本思想為：選用簇中位置最中心的對象，試圖對 n個對象給出 k個劃分；代表對象也被稱為是中心點，其他對象則被稱為非代表對象；最初隨機選擇 k個對象作為中心點，該算法反復地用非代表對象來代替代表對象，試圖找出更好的中心點，以改進聚類的質量；在每次迭代中，所有可能的對象對被分析，每個對中的一個對象是中心點，而另一個是非代表對象。對可能的 各種組合，估算聚類結果的質量；一個對象 Oi可以被使最大平方 誤差值減少的對象代替；在一次迭代中產生的最佳對象集合成為下次迭代的中心點。 為了判定一個非代表對象 Oh是否是當前一個代表對象 Oi的好的替代，對于每一個非中心點對象 Oj，下面的四種情況被考慮： ? 第一種情況：假設 Oi被 Oh代替作為新的中心點， Oj當前隸屬于中心點對 6 象 Oi。如果 Oj離某個中心點 Om最近， i≠ m，那么 Oj被重新分配給 Om。 ? 第二種情況：假設 Oi被 Oh代替作為新的中心點， Oj當前隸屬于中心點對象 Oi。如果 Oj離這個新的中心點 Oh最近，那么 Oj被分配給 Oh。 ? 第三種情況：假設 Oi被 Oh代替作為新的中心點，但是 Oj當前隸屬于另一個中心點對象 Om， m≠ i。如果 Oj依然離 Om最近，那么對象的隸屬不發(fā)生變化。 ? 第四種情況：假設 Oi被 Oh代替作為新的中心點，但是 Oj當前隸屬于另一個中心點對象 Om， m≠ i。如果 Oj離這個新的中心點 Oh最近，那么 Oi被重新分配給 Oh。 每當重新分配發(fā)生時，平方 誤差 E所產生的差別對代價函數有影響。因此，如果一個當前的中心點對象被非中心點對象所代替，代價函數計算平方 誤差值所產生的差別。替換的總代價是所有非中心點對象所產生的代價 之和。如果總代價是負的，那么實際的平方 誤差將會減小， Oi可以被 Oh替代。如果總代價是正的，則當前的中心點 Oi被認為是可接受的，在本次迭代中沒有變化。 PAM 算法需用簇中位置最靠近中心的對象作為代表對象，然后反復地用非代表對象來代替代表對象，試圖找出更好的中心點，在反復迭