聚類算法總結
原文:http://blog.chinaunix.net/uid-10289334-id-3758310.html
聚類算法的種類：
基于劃分聚類算法（partition clustering)
| k-means： | 是一種典型的劃分聚類算法，它用一個聚類的中心來代表一個簇，即在疊代過程中選擇的聚點不一定是聚類中的一個點，該算法隻能處理數值型資料 |
| k-modes： | K-Means算法的擴充，采用簡單比對方法來度量分類型資料的相似度 |
| k-prototypes： | 結合了K-Means和K-Modes兩種算法，能夠處理混合型資料 |
| k-medoids： | 在疊代過程中選擇簇中的某點作為聚點，PAM是典型的k-medoids算法 |
| CLARA： | CLARA算法在PAM的基礎上采用了抽樣技術，能夠處理大規模資料 |
| CLARANS： | CLARANS算法融合了PAM和CLARA兩者的優點，是第一個用于空間資料庫的聚類算法 |
| Focused CLARAN： | 采用了空間索引技術提高了CLARANS算法的效率 |
| PCM： | 模糊集合理論引入聚類分析中并提出了PCM模糊聚類算法 |
基于層次聚類算法：
| CURE： | 采用抽樣技術先對資料集D随機抽取樣本，再采用分區技術對樣本進行分區，然後對每個分區局部聚類，最後對局部聚類進行全局聚類 |
| ROCK： | 也采用了随機抽樣技術，該算法在計算兩個對象的相似度時，同時考慮了周圍對象的影響 |
| CHEMALOEN（變色龍算法）： | 首先由資料集構造成一個K-最近鄰圖Gk ,再通過一個圖的劃分算法将圖Gk 劃分成大量的子圖,每個子圖代表一個初始子簇,最後用一個凝聚的層次聚類算法反複合并子簇，找到真正的結果簇 |
| SBAC： | SBAC算法則在計算對象間相似度時，考慮了屬性特征對于展現對象本質的重要程度，對于更能展現對象本質的屬性賦予較高的權值 |
| BIRCH： | BIRCH算法利用樹結構對資料集進行處理，葉結點存儲一個聚類，用中心和半徑表示，順序處理每一個對象，并把它劃分到距離最近的結點，該算法也可以作為其他聚類算法的預處理過程 |
| BUBBLE： | BUBBLE算法則把BIRCH算法的中心和半徑概念推廣到普通的距離空間 |
| BUBBLE-FM： | BUBBLE-FM算法通過減少距離的計算次數，提高了BUBBLE算法的效率 |
基于密度聚類算法：
| DBSCAN： | DBSCAN算法是一種典型的基于密度的聚類算法，該算法采用空間索引技術來搜尋對象的鄰域，引入了“核心對象”和“密度可達”等概念，從核心對象出發，把所有密度可達的對象組成一個簇 |
| GDBSCAN： | 算法通過泛化DBSCAN算法中鄰域的概念，以适應空間對象的特點 |
| DBLASD： | |
| OPTICS： | OPTICS算法結合了聚類的自動性和互動性，先生成聚類的次序，可以對不同的聚類設定不同的參數，來得到使用者滿意的結果 |
| FDC： | FDC算法通過構造k-d tree把整個資料空間劃分成若幹個矩形空間，當空間維數較少時可以大大提高DBSCAN的效率 |
基于網格的聚類算法：
| STING： | 利用網格單元儲存資料統計資訊，進而實作多分辨率的聚類 |
| WaveCluster： | 在聚類分析中引入了小波變換的原理，主要應用于信号處理領域。（備注：小波算法在信号處理，圖形圖像，加密解密等領域有重要應用，是一種比較高深和牛逼的東西） |
| CLIQUE： | 是一種結合了網格和密度的聚類算法 |
| OPTIGRID： |
基于神經網絡的聚類算法：
| 自組織神經網絡SOM： | 該方法的基本思想是--由外界輸入不同的樣本到人工的自組織映射網絡中，一開始時，輸入樣本引起輸出興奮細胞的位置各不相同，但自組織後會形成一些細胞群，它們分别代表了輸入樣本，反映了輸入樣本的特征 |
基于統計學的聚類算法：
| COBWeb： | COBWeb是一個通用的概念聚類方法，它用分類樹的形式表現層次聚類 |
| CLASSIT： | |
| AutoClass： | 是以機率混合模型為基礎，利用屬性的機率分布來描述聚類，該方法能夠處理混合型的資料，但要求各屬性互相獨立 |
---------------------------------------------------------
幾種常用的聚類算法從可伸縮性、适合的資料類型、高維性（處理高維資料的能力）、異常資料的抗幹擾度、聚類形狀和算法效率6個方面進行了綜合性能評價，評價結果如表1所示：
| 算法名稱 | 可伸縮性 | 适合的資料類型 | 高維性 | 異常資料的抗幹擾性 | 聚類形狀 | 算法效率 |
| WaveCluster | 很高 | 數值型 | 很高 | 較高 | 任意形狀 | 很高 |
| ROCK | 很高 | 混合型 | 很高 | 很高 | 任意形狀 | 一般 |
| BIRCH | 較高 | 數值型 | 較低 | 較低 | 球形 | 很高 |
| CURE | 較高 | 數值型 | 一般 | 很高 | 任意形狀 | 較高 |
| K-Prototypes | 一般 | 混合型 | 較低 | 較低 | 任意形狀 | 一般 |
| DENCLUE | 較低 | 數值型 | 較高 | 一般 | 任意形狀 | 較高 |
| OptiGrid | 一般 | 數值型 | 較高 | 一般 | 任意形狀 | 一般 |
| CLIQUE | 較高 | 數值型 | 較高 | 較高 | 任意形狀 | 較低 |
| DBSCAN | 一般 | 數值型 | 較低 | 較高 | 任意形狀 | 一般 |
| CLARANS | 較低 | 數值型 | 較低 | 較高 | 球形 | 較低 |
---------------------------------------------------------
目前聚類分析研究的主要内容：
對聚類進行研究是資料挖掘中的一個熱門方向，由于以上所介紹的聚類方法都存在着某些缺點，是以近些年對于聚類分析的研究很多都專注于改進現有的聚類方法或者是提出一種新的聚類方法。以下将對傳統聚類方法中存在的問題以及人們在這些問題上所做的努力做一個簡單的總結：
1 從以上對傳統的聚類分析方法所做的總結來看，不管是k-means方法，還是CURE方法，在進行聚類之前都需要使用者事先确定要得到的聚類的數目。然而在現實資料中，聚類的數目是未知的，通常要經過不斷的實驗來獲得合适的聚類數目，得到較好的聚類結果。
2 傳統的聚類方法一般都是适合于某種情況的聚類，沒有一種方法能夠滿足各種情況下的聚類，比如BIRCH方法對于球狀簇有很好的聚類性能，但是對于不規則的聚類，則不能很好的工作；K-medoids方法不太受孤立點的影響，但是其計算代價又很大。是以如何解決這個問題成為目前的一個研究熱點，有學者提出将不同的聚類思想進行融合以形成新的聚類算法，進而綜合利用不同聚類算法的優點，在一次聚類過程中綜合利用多種聚類方法，能夠有效的緩解這個問題。
3 随着資訊時代的到來，對大量的資料進行分析處理是一個很龐大的工作，這就關系到一個計算效率的問題。有文獻提出了一種基于最小生成樹的聚類算法，該算法通過逐漸丢棄最長的邊來實作聚類結果，當某條邊的長度超過了某個門檻值，那麼更長邊就不需要計算而直接丢棄，這樣就極大地提高了計算效率，降低了計算成本。
4 處理大規模資料和高維資料的能力有待于提高。目前許多聚類方法處理小規模資料和低維資料時性能比較好，但是當資料規模增大，次元升高時，性能就會急劇下降，比如k-medoids方法處理小規模資料時性能很好，但是随着資料量增多，效率就逐漸下降，而現實生活中的資料大部分又都屬于規模比較大、次元比較高的資料集。有文獻提出了一種在高維空間挖掘映射聚類的方法PCKA（Projected
Clustering based on the K-Means Algorithm），它從多個次元中選擇屬性相關的次元，去除不相關的次元，沿着相關次元進行聚類，以此對高維資料進行聚類。
5 目前的許多算法都隻是理論上的，經常處于某種假設之下，比如聚類能很好的被分離，沒有突出的孤立點等，但是現實資料通常是很複雜的，噪聲很大，是以如何有效的消除噪聲的影響，提高處理現實資料的能力還有待進一步的提高。
分類算法總結
原文：http://blog.csdn.net/chl033/article/details/5204220
目前看到的比較全面的分類算法,總結的還不錯.
2.4.1 主要分類方法介紹解決分類問題的方法很多[40-42] ，單一的分類方法主要包括：決策樹、貝葉斯、人工神經網絡、K-近鄰、支援向量機和基于關聯規則的分類等；另外還有用于組合單一分類方法的內建學習算法，如Bagging和Boosting等。
（1）決策樹
決策樹是用于分類和預測的主要技術之一，決策樹學習是以執行個體為基礎的歸納學習算法，它着眼于從一組無次序、無規則的執行個體中推理出以決策樹表示的分類規則。構造決策樹的目的是找出屬性和類别間的關系，用它來預測将來未知類别的記錄的類别。它采用自頂向下的遞歸方式，在決策樹的内部節點進行屬性的比較，并根據不同屬性值判斷從該節點向下的分支，在決策樹的葉節點得到結論。
主要的決策樹算法有ID3、C4.5（C5.0）、CART、PUBLIC、SLIQ和SPRINT算法等。它們在選擇測試屬性采用的技術、生成的決策樹的結構、剪枝的方法以及時刻，能否處理大資料集等方面都有各自的不同之處。
（2）貝葉斯
貝葉斯（Bayes）分類算法是一類利用機率統計知識進行分類的算法，如樸素貝葉斯（Naive Bayes）算法。這些算法主要利用Bayes定理來預測一個未知類别的樣本屬于各個類别的可能性，選擇其中可能性最大的一個類别作為該樣本的最終類别。由于貝葉斯定理的成立本身需要一個很強的條件獨立性假設前提，而此假設在實際情況中經常是不成立的，因而其分類準确性就會下降。為此就出現了許多降低獨立性假設的貝葉斯分類算法，如TAN（Tree Augmented Na?ve
Bayes)算法，它是在貝葉斯網絡結構的基礎上增加屬性對之間的關聯來實作的。
（3）人工神經網絡
人工神經網絡（Artificial Neural Networks，ANN）是一種應用類似于大腦神經突觸聯接的結構進行資訊處理的數學模型。在這種模型中，大量的節點（或稱”神經元”，或”單元”）之間互相聯接構成網絡，即”神經網絡”，以達到處理資訊的目的。神經網絡通常需要進行訓練，訓練的過程就是網絡進行學習的過程。訓練改變了網絡節點的連接配接權的值使其具有分類的功能，經過訓練的網絡就可用于對象的識别。
目前，神經網絡已有上百種不同的模型，常見的有BP網絡、徑向基RBF網絡、Hopfield網絡、随機神經網絡（Boltzmann機）、競争神經網絡（Hamming網絡，自組織映射網絡）等。但是目前的神經網絡仍普遍存在收斂速度慢、計算量大、訓練時間長和不可解釋等缺點。
（4）k-近鄰
k-近鄰(kNN，k-Nearest Neighbors)算法是一種基于執行個體的分類方法。該方法就是找出與未知樣本x距離最近的k個訓練樣本，看這k個樣本中多數屬于哪一類，就把x歸為那一類。k-近鄰方法是一種懶惰學習方法，它存放樣本，直到需要分類時才進行分類，如果樣本集比較複雜，可能會導緻很大的計算開銷，是以無法應用到實時性很強的場合。
（5）支援向量機
支援向量機（SVM，Support Vector Machine）是Vapnik根據統計學習理論提出的一種新的學習方法[43] ，它的最大特點是根據結構風險最小化準則，以最大化分類間隔構造最優分類超平面來提高學習機的泛化能力，較好地解決了非線性、高維數、局部極小點等問題。對于分類問題，支援向量機算法根據區域中的樣本計算該區域的決策曲面，由此确定該區域中未知樣本的類别。
（6）基于關聯規則的分類
關聯規則挖掘是資料挖掘中一個重要的研究領域。近年來，對于如何将關聯規則挖掘用于分類問題，學者們進行了廣泛的研究。關聯分類方法挖掘形如condset→C的規則，其中condset是項(或屬性-值對)的集合，而C是類标号，這種形式的規則稱為類關聯規則（class association rules，CARS）。關聯分類方法一般由兩步組成：第一步用關聯規則挖掘算法從訓練資料集中挖掘出所有滿足指定支援度和置信度的類關聯規則；第二步使用啟發式方法從挖掘出的類關聯規則中挑選出一組高品質的規則用于分類。屬于關聯分類的算法主要包括CBA[44]
，ADT[45] ，CMAR[46] 等。
（7）內建學習（Ensemble Learning）
實際應用的複雜性和資料的多樣性往往使得單一的分類方法不夠有效。是以，學者們對多種分類方法的融合即內建學習進行了廣泛的研究。內建學習已成為國際機器學習界的研究熱點，并被稱為目前機器學習四個主要研究方向之一。
內建學習是一種機器學習範式，它試圖通過連續調用單個的學習算法，獲得不同的基學習器，然後根據規則組合這些學習器來解決同一個問題，可以顯著的提高學習系統的泛化能力。組合多個基學習器主要采用（權重）投票的方法，常見的算法有裝袋[47] （Bagging），提升/推進[48, 49] （Boosting）等。
有關分類器的內建學習見圖2-5。內建學習由于采用了投票平均的方法組合多個分類器，是以有可能減少單個分類器的誤差，獲得對問題空間模型更加準确的表示，進而提高分類器的分類準确度。
圖2-5：分類器的內建學習
以上簡單介紹了各種主要的分類方法，應該說其都有各自不同的特點及優缺點。對于資料庫負載的自動識别，應該選擇哪種方法呢？用來比較和評估分類方法的标準[50] 主要有：（1）預測的準确率。模型正确地預測新樣本的類标号的能力；（2）計算速度。包括構造模型以及使用模型進行分類的時間；（3）強壯性。模型對噪聲資料或空缺值資料正确預測的能力；（4）可伸縮性。對于資料量很大的資料集，有效構造模型的能力；（5）模型描述的簡潔性和可解釋性。模型描述愈簡潔、愈容易了解，則愈受歡迎。