聚類算法簡介-ppt-s

1、聚類算法簡介聚類算法概念介紹聚類的基本概念聚類的基本要素聚類的典型要求聚類的經(jīng)典算法聚類的基本概念-什么是聚類?聚類中沒有任何指導信息，完全按照數(shù)據(jù)的分布進行類別劃分。聚類的大小和結構都沒有事先假定。聚類就是對大量未知標注的數(shù)據(jù)集，按數(shù)據(jù)的內在相似性將數(shù)據(jù)集劃分為多個類別，使類別內的數(shù)據(jù)相似度較大而類別間的數(shù)據(jù)相似度較小;聚類的基本概念-類似概念-分類?學習：用分類算法分析訓練數(shù)據(jù)。學習模型或分類法以分類規(guī)則形式提供。 分類：測試數(shù)據(jù)用于評估分類規(guī)則的準確率。如果準確率是可以接受的，則規(guī)則用于新的數(shù)據(jù)元組分類分類(Categorization or Classification)就是按照某種標

2、準給對象貼標簽(label)，再根據(jù)標簽來區(qū)分歸類。分類是事先定義好類別 ，類別數(shù)不變 。分類器需要由人工標注的分類訓練語料訓練得到，屬于有指導學習范疇。訓練數(shù)據(jù)待分類數(shù)據(jù)聚類的基本概念-聚類與分類的主要區(qū)別有類別標記和無類別標記;有監(jiān)督與無監(jiān)督（有訓練語料與無訓練語料）聚類的基本要素數(shù)據(jù)之間的相似度;聚類有效性函數(shù)（停止判別條件）; 1. 在聚類算法的不同階段會得到不同的類別劃分結果，可以通過聚類有效性函數(shù)來判斷多個劃分結果中哪個是有效的; 2. 使用有效性函數(shù)作為算法停止的判別條件，當類別劃分結果達到聚類有效性函數(shù)時即可停止算法運行;類別劃分策略（算法）; 通過何種類別劃分方式使類別劃分結

3、果達到有效性函數(shù);相似度歐氏距離:E D (Ai,Aj)=sqrt(1.n（Aim - Ajm ）2)如：用戶A，流量20MB，通話時長100分鐘，用戶B流量0MB，通話時長100分鐘，他們的距離=20單位。數(shù)據(jù)表示為向量，向量中某一維對應數(shù)據(jù)某一特征或屬性。曼哈頓距離：MD (Ai,Aj)=(1.n|Aim - Ajm |)明考斯基距離 最小方差:衡量同一類別內數(shù)據(jù)的平均誤差和;聚類的基本概念-最小誤差（ ）:衡量屬于不同類別的數(shù)據(jù)與類別中心的的誤差和;聚類的典型要求可伸縮性許多聚類算法在小于 200 個數(shù)據(jù)對象的小數(shù)據(jù)集合上工作得很好；但是，一個大規(guī)模數(shù)據(jù)庫可能包含幾百萬個對象，在這樣的大

4、數(shù)據(jù)集合樣本上進行聚類可能會導致有偏的結果。我們需要具有高度可伸縮性的聚類算法。處理不同類型屬性的能力許多算法被設計用來聚類數(shù)值類型的數(shù)據(jù)。但是，應用可能要求聚類其他類型的數(shù)據(jù)，如二元類型(binary)，分類/標稱類型（categorical/nominal），序數(shù)型（ordinal）數(shù)據(jù)，或者這些數(shù)據(jù)類型的混合。發(fā)現(xiàn)任意形狀的聚類許多聚類算法基于歐幾里得或者曼哈頓距離度量來決定聚類?；谶@樣的距離度量的算法趨向于發(fā)現(xiàn)具有相近尺度和密度的球狀簇。但是，一個簇可能是任意形狀的。提出能發(fā)現(xiàn)任意形狀簇的算法是很重要的。用于決定輸入?yún)?shù)的領域知識最小化許多聚類算法在聚類分析中要求用戶輸入一定的參數(shù)，

5、例如希望產(chǎn)生的簇的數(shù)目。聚類結果對于輸入?yún)?shù)十分敏感。參數(shù)通常很難確定，特別是對于包含高維對象的數(shù)據(jù)集來說。這樣不僅加重了用戶的負擔，也使得聚類的質量難以控制。處理“噪聲”數(shù)據(jù)的能力絕大多數(shù)現(xiàn)實中的數(shù)據(jù)庫都包含了孤立點，缺失，或者錯誤的數(shù)據(jù)。一些聚類算法對于這樣的數(shù)據(jù)敏感，可能導致低質量的聚類結果。對于輸入記錄的順序不敏感一些聚類算法對于輸入數(shù)據(jù)的順序是敏感的。例如，同一個數(shù)據(jù)集合，當以不同的順序交給同一個算法時，可能生成差別很大的聚類結果。開發(fā)對數(shù)據(jù)輸入順序不敏感的算法具有重要的意義。高維度（high dimensionality）一個數(shù)據(jù)庫或者數(shù)據(jù)倉庫可能包含若干維或者屬性。許多聚類算法擅

6、長處理低維的數(shù)據(jù)，可能只涉及兩到三維。人類的眼睛在最多三維的情況下能夠很好地判斷聚類的質量。在高維空間中聚類數(shù)據(jù)對象是非常有挑戰(zhàn)性的，特別是考慮到這樣的數(shù)據(jù)可能分布非常稀疏，而且高度偏斜。基于約束的聚類現(xiàn)實世界的應用可能需要在各種約束條件下進行聚類。假設你的工作是在一個城市中為給定數(shù)目的自動提款機選擇安放位置，為了作出決定，你可以對住宅區(qū)進行聚類，同時考慮如城市的河流和公路網(wǎng)，每個地區(qū)的客戶要求等情況。要找到既滿足特定的約束，又具有良好聚類特性的數(shù)據(jù)分組是一項具有挑戰(zhàn)性的任務?？山忉屝院涂捎眯杂脩粝Ｍ垲惤Y果是可解釋的，可理解的，和可用的。也就是說，聚類可能需要和特定的語義解釋和應用相聯(lián)系。應

7、用目標如何影響聚類方法的選擇也是一個重要的研究課題。 聚類算法概念介紹聚類的經(jīng)典算法基于劃分的算法基于層次的算法其它算法示例聚類分析計算方法基于劃分的算法(partitioning methods)典型算法：K-MEANS算法（k均值）、K-MEDOIDS算法（k中心）、CLARANS算法；基于層次的算法(hierarchical methods)代表算法有：最短距離法、BIRCH算法、CURE算法、CHAMELEON算法等；基于密度的方法(density-based methods)代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等；基于網(wǎng)格的方法(grid-based m

8、ethods)代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法；基于模型的方法(model-based methods)通常有兩種嘗試方向：基于統(tǒng)計的方案（COBWEB、CLASSIT等）和基于神經(jīng)網(wǎng)絡（SOM等）的方案?；趧澐值姆椒ǎ≒artitioning method）特點：k事先定好創(chuàng)建一個初始劃分，再采用迭代的重定位技術運算量較小，適用于處理龐大的樣本數(shù)據(jù)適用于發(fā)現(xiàn)球狀類優(yōu)點：聚類時間快; 缺點：對初始參數(shù)敏感;容易陷入局部最優(yōu); 基于劃分的方法：舉例 K-means1設置初始類別數(shù)K，人為設置K個類別中心;2根據(jù)樣本和類別中心的距離進行類別劃分，樣本劃分

9、到距離最近的類別;3重新計算當前類別劃分下每類的中心（類別樣本平均值）;4在得到類別中心下繼續(xù)進行類別劃分;5如果連續(xù)兩次的類別劃分結果不變則停止算法;否則循環(huán)25 ;有 N 個樣本的集合Zs=Z1, Z2, ., ZN，想要聚成 K 個類（事先給定 K）思路：根據(jù)與類別中心的距離聚類，循環(huán)調整類別中心位置基于劃分的方法：舉例 K-means初始化4個類別中心;左側的全體數(shù)據(jù)僅與第一個類別中心相似;基于劃分的方法：舉例 K-means層次法（hierarchical method）分裂或凝聚算法運行到某一階段，類別劃分結果達到聚類標準時即可停止分裂或凝聚;層次的方法（hierarchical

10、method）特點：類的個數(shù)不需事先定好需確定距離矩陣運算量大，適用于處理小樣本數(shù)據(jù) 一旦一個步驟（合并或分裂）完成，就不能被撤銷或修正，因此產(chǎn)生了改進的層次聚類方法，如BRICH, BURE, ROCK, Chameleon。 廣泛采用的類間距離：重心法（centroid hierarchical method）類的重心之間的距離對異常值不敏感，結果更穩(wěn)定 其它方法：最短距離法、最長距離法、平均距離法等層次法：舉例-最相似聚類法有 N 個樣本的集合Zs=Z1, Z2, ., ZN，想要聚成 K 個類（事先給定 K）思路：尋找“相似”（距離最近）的兩個樣本結合1數(shù)據(jù)初始化，k=N, Ci=Zi

11、, i=1,2,.,N2設定結束條件，if k=K then END3找到 Ci 與Cj 之間的距離d(Ci, Cj)最小的一對4Ci 和Cj 合成一個類Ci, 并計算新的Ci 的中心5去除 Cj, k=k-1. 跳轉 2其它1：基于密度的方法（density-based method）思想：臨近區(qū)域的密度超過一定的閥值，把它加到與之相近的聚類中去特點：可以過濾噪聲和孤立點，能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點，發(fā)現(xiàn)任意形狀的類。舉例：DBSCAN算法。該算法將具有足夠高密度的區(qū)域劃分為簇，并可以在帶有“噪音”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。它定義簇為密度相連的點的最大集合。一

12、個給定對象周圍半徑內的區(qū)域稱為該對象的鄰域。如果一個對象的鄰域至少包含最小數(shù)目Mi的對象，那么該對象稱為核心對象。給定一個對象集合D，如果p 是在q 的鄰域內，而q 是一個核心對象，我們說對象p 從對象q 出發(fā)是直接密度可達的）其它2：基于網(wǎng)格的方法（grid-based method）思想這種方法首先將數(shù)據(jù)空間劃分成為有限個單元（cell）的網(wǎng)格結構,所有的處理都是以單元為對象。優(yōu)點處理速度很快。例：STING算法將空間區(qū)域劃分為矩形單元。多個級別的單元，形成層次結構：高層的每個單元被劃分為多個低一層的單元。高層單元的統(tǒng)計參數(shù)可以很容易地從低層單元的計算得到。這些參數(shù)包括：屬性無關的參數(shù)co

13、unt；屬性相關的參數(shù)m（平均值），s（標準偏差），min，max，該單元中屬性值遵循的分布類型等。其它3：基于模型的方法（model-based method）思想：基于這樣的假設：數(shù)據(jù)是根據(jù)潛在的概率分布生成的。為每個類假定一個模型，尋找數(shù)據(jù)對給定模型的最佳擬合。特點：對某些問題有很好的效果。計算復雜度較高。MOU_CLASS109876543210012345678910FLOW_CLASS通過流量和計費時長兩個指標給用戶分群，設定分為5個聚類。示例：1 數(shù)據(jù)規(guī)整：流量和計費時長單位不同，不易比較，通過排序，對全省用戶進行流量分檔，0流量用戶記為flow_class = 0，每10%一檔，最高flow_class 10，同樣設定mou_class。2 網(wǎng)格化：根據(jù)flow_class、mou_class分成121個網(wǎng)格，人為剔除雙0網(wǎng)格，中心定義為重心，保留參數(shù)numFLOW_CLASSMOU_CLASSNUM101109593.示例：3 最短距離合并：遍歷所有網(wǎng)格，找到中心間距離最短的兩個網(wǎng)格，合并并重新計算中心，重復進行本步驟直至網(wǎng)格數(shù)量為5聚類結果F