數(shù)據(jù)挖掘4

1、1,一、聚類挖掘的相關概念,,1、聚類 就是把整個數(shù)據(jù)分成不同的組，并使組與組之間的差異盡可能大，組內數(shù)據(jù)的差異盡可能小。 2、聚類與分類的差別 聚類開始時不知道要把數(shù)據(jù)分成幾組，也沒有分類的具體標準，聚類分析時數(shù)據(jù)集合的特征是未知的，也稱無指導學習。 分類開始時知道要把數(shù)據(jù)分成幾組，分類將要處理的數(shù)據(jù)按照分類標準分入不同的類別，也稱有指導學習。 例如，聚類：嬰兒區(qū)分動物；分類：成人區(qū)分動物。,2,一、聚類

2、挖掘的相關概念,,3、聚類問題的數(shù)學描述給定數(shù)據(jù)集合V｛vi|i=1，2，┅，n｝，其中vi為數(shù)據(jù)對象，根據(jù)數(shù)據(jù)對象間的相似程度將數(shù)據(jù)集合分成k組，并滿足如下條件：則該過程成為聚類。4、簇聚類中的組稱為簇。其它關于簇的定義：一些相似成員的集合，不同簇中的成員是不相似的。簇中兩點之間的距離要小于簇中一點與簇外任一點之間的距離。,,3,一、聚類挖掘的相關概念,,5、聚類分析方法的分類（1）按照聚類的標準，可分為兩種：統(tǒng)

3、計聚類方法基于對象之間的相似性度量進行聚類。包括：系統(tǒng)聚類法、分解法、加入法、動態(tài)聚類法、有序樣品聚類、有重疊聚類和模糊聚類等。此方法基于全局的比較，需要考察所有個體，因此，數(shù)據(jù)必須預先給定，不能動態(tài)增加新的數(shù)據(jù)對象。概念聚類方法基于對象具有的概念進行聚類。這里的距離不是傳統(tǒng)方法的集合距離，而是根據(jù)概念的描述來確定的。典型方法有：COBWEB、CLOC和基于列連的方法。,4,一、聚類挖掘的相關概念,,（2）按照所處理的數(shù)據(jù)類型，可

4、分為三種：數(shù)值型數(shù)據(jù)聚類方法所分析的數(shù)據(jù)是數(shù)值型數(shù)據(jù)，因此，可對所處理的數(shù)據(jù)直接比較大小。符號值數(shù)據(jù)聚類方法所分析的數(shù)據(jù)是符號型數(shù)據(jù)，因此，對所處理的數(shù)據(jù)不能直接比較大小?；旌闲蛿?shù)據(jù)聚類方法能同時處理數(shù)值數(shù)據(jù)和符號數(shù)據(jù)，此方法通常功能強大，但性能往往不盡如人意。,5,一、聚類挖掘的相關概念,,（3）按照聚類的尺度，可分為三種：基于距離的聚類算法根據(jù)數(shù)據(jù)之間的距離進行聚類。此算法對噪聲數(shù)據(jù)和孤立點較敏感。基于密度的聚類算

5、法此方法認為簇是具有相同密度的聯(lián)通區(qū)域。因此，需要掃描整個數(shù)據(jù)集，將數(shù)據(jù)劃分為不同的小方格，并使用小方格的并來近似表示簇。因此可能不夠精確。該方法對于噪聲數(shù)據(jù)和孤立點不敏感。基于互連性的聚類算法此類方法將聚類對象映射為圖模型或超圖模型，然后根據(jù)邊尋找高連通度的結點集合。此方法能較好第反映數(shù)據(jù)之間的相關程度。,6,一、聚類挖掘的相關概念,,（4）按照聚類分析算法的主要思路，可分為：劃分法：給定由n個對象或者元組的數(shù)據(jù)庫，將數(shù)據(jù)劃分

6、為k（k≤n）組，每個組表示一個簇，每個組至少包含一個對象，每個對象必須屬于且只屬于一個組。層次法：對給定的數(shù)據(jù)對象進行層次的分解。又分為凝聚法和分裂法凝聚法：也稱自底向上的方法，一開始將每個對象單獨作為一個簇，然后逐步合并相近的簇，直到每個簇滿足特征性條件。分裂法：也稱自頂向下的方法，一開始將所有的對象置于一個簇中，然后逐步分裂成更小的簇，直到每個簇滿足特征性條件?；谀Ｐ偷姆椒ǎ航o每個簇假定一個模型，然后去尋找能夠很好地滿足

7、此模型的數(shù)據(jù)集。本章主要討論基于劃分的聚類算法和基于層次的聚類算法。,7,一、聚類挖掘的相關概念,,6、距離與相似性度量聚類分析的質量取決于度量標準的選擇，下面是一些常用的度量標準（1）距離函數(shù)歐氏距離明可夫斯基距離二次性距離余弦距離二元特征樣本的距離（2）類間距離最短距離法最長距離法中心法類平均法離差平方和,8,二、基于劃分的聚類方法,,1.主要思想給定一個有n個對象的數(shù)據(jù)集，劃分聚類方法將構造數(shù)據(jù)的k（

8、k≤n）個劃分，每一個劃分代表一個簇，即將數(shù)據(jù)劃分為k個簇，且這k個劃分滿足下列條件：每一個簇至少包含一個對象每一個對象屬于且僅屬于一個簇。對于給定的k，算法首先給定一個初始的劃分方法，以后通過反復迭代改變劃分，使得每一次改進之后的劃分方案都較前一次更好。即同一簇中的對象越近，不同簇中的對象越遠。此類方法包括：k-平均、k-模、k-原型、k-中心點、PAM、CLARA以及ALARANS等。,9,二、基于劃分的聚類方法,,2、K-

9、平均算法（1）算法介紹 也稱k-均值算法，是一種廣泛使用的聚類算法。它以k為參數(shù)，把n個對象分為k個簇，使簇內具有較高的相似度，而簇間的相似度較低。相似的計算根據(jù)簇中對象的平均值進行。（2）算法思想 首先隨機選擇k個對象，每個對象初始代表一個簇的平均值或中心。對剩余的對象根據(jù)其與各個簇中心的距離，將其賦給最近的簇。然后重新計算每個簇的平均值。重復這個過程，直到準則函數(shù)收斂。準則函數(shù)如下： 其中，E是數(shù)據(jù)庫所有對象的平

10、方誤差的總和，x是空間中的點，表示給定的數(shù)據(jù)對象， 是簇的平均值。,,,10,二、基于劃分的聚類方法,,第二次迭代：通過平均值調整對象所在的簇，重新聚類，即按離平均值點（1.5，1）和（3.5，3）最近的原則重新分配。得到兩個新的簇｛1，2，3，4｝和｛5，6，7，8｝。重新計算簇平均值點，得到新的平均值點為（1.5，1.5）和（4.5，3.5）。第三次迭代：將所有點按離平均值（1.5，1.5）和（4.5，3.5）最近的原則重新分

11、配，調整對象，得到兩個新的簇｛1，2，3，4｝和｛5，6，7，8｝。發(fā)現(xiàn)沒有出現(xiàn)重新分配，而且準則函數(shù)收斂，程序結束。,（3）算法執(zhí)行例子對右表的樣本數(shù)據(jù)集，使用k-平均算法進行聚類。執(zhí)行過程如下： 第一次迭代：隨機選擇兩個對象，如序號1和序號3當作初始點，分別找到離兩點最近的對象，并產(chǎn)生兩個簇｛1，2｝和｛3，4，5，6，7，8｝。對產(chǎn)生的簇分別計算平均值，得到平均值點：對于｛1，2｝，平均值點為（1.5，1）對于｛3，4

12、，5，6，7，8｝，平均值點為（3.5，3）,11,二、基于劃分的聚類方法,,3、PAM （1）算法簡介 PAM是最早提出的k-中心點算法之一，他選擇簇中位置最靠近中心的對象作為作為代表對象，對n個對象給出k個劃分。 （2）算法思想 最初隨機選擇k個對象作為中心點，反復用非代表對象代替代表對象，試圖找出更好的中心點以改進簇類的質量。在每次迭代中，所有可能的對象對（一個是中心點，另一個是非代表對象）被分析，對可能的各種組合，估計

13、聚類結果的質量。 PAM算法分為兩個步驟： 建立：隨機尋找k個中心點作為初始的簇中心點。 交換：對于所有可能的對象進行分析，找出交換后可以使平方-誤差減少的對象，代替原中心點。,,,12,二、基于劃分的聚類方法,,（3）算法執(zhí)行例子 假如空間中有五個點｛A，B，C，D，E｝，各點之間的距離關系如表，根據(jù)所給的數(shù)據(jù)用PAM算法進行實現(xiàn)劃分聚類。,,,算法執(zhí)行步驟如下：第一步：建立階段：從5個對象隨機抽取2個中心點為｛A，B｝，則

14、樣本被劃分為｛A，C，D｝和 {B，E}，如圖：,13,二、基于劃分的聚類方法,,第二步，交換階段：為了逐個檢驗三個非中心點｛C，D，E｝是否能夠代替中心點A和B，需要計算6個距離代價的改變量：TCAC、TCAD、TCAE、TCBC、TCBD、TCBE。下面以TCAC（A被C替換）為例說明計算過程：當A被C替換以后，A不再是中心點，因為A離B比A離C近，A被分配到B中心點代表的簇，CAAC=d（A，B）-d（A，A）=1。B是一個中

15、心點，當A被C替換后，B不受影響，CBAC=0C原先屬于A中心點所在的簇，當A被C替換后，C是新中心點，CCAC=d（C，C）-d（C，A）=0-2=-2。,14,二、基于劃分的聚類方法,,D原先屬于A中心點所在的簇，當A被C替換以后，離D最近的中心點是C， CDAC=d（D，C）-d（D，A）=1-2=-1。E原先屬于B中心點所在的簇，當A被C替換后，離E最近的中心點仍是B，CEAC=0.因此，TCAC=1+0-2-1+0=-2

16、。同理，可以計算出：TCAD=-2，TCAE=-1，TCBC=-2，TCBD=-2，TCBE=-2選取一個最小的代價，如TCAC（C替換A），樣本點被劃分為｛B，A，E｝和｛C，D｝。至此完成第一次迭代，重復上述過程，直到代價不再減小。,15,二、基于劃分的聚類方法,,下圖為6個距離代價的改變量,A,,B,,C,,D,,E,,A,,B,,C,,D,,E,,A,,B,,C,,D,,E,,A,,B,,C,,D,,E,,A,,B,,C,

17、,D,,E,,A,,B,,C,,D,,E,,,,,,,,,,,,,,,,,,,,1,3,1,1,2,3,1,1,3,1,1,3,1,2,2,(a)開始：A和B為中心點,(b)TCAC：變化-2；TCAD：變化-2,(c)TCAE：變化-1,(e)TCBE：變化-2,(e)TCBD：變化-2,(d)TCBC：變化-2,2,2,3,16,三、層次聚類方法,,層次聚類方法是對給定的數(shù)據(jù)集進行層次分解，直到滿足某種條件為止。具體可分為凝聚的、分

18、裂的兩種方案。凝聚的層次聚類是一種自底向上的策略，首先將每個對象作為一個簇，然后逐漸合并為越來越大的簇，直到所有的對象都在一個簇中，或者某個終結條件被滿足。分裂的層次聚類是一種自頂向下的策略，首先將所有對象置于一個簇中，然后逐漸細分為越來越小的簇，直到每個對象自成一簇，或者某個終結條件被滿足。,17,三、層次聚類方法,,（1）AGNES算法 是凝聚的層次聚類方法。算法最初將每個對象作為一個簇，然后根據(jù)某些準則將這些簇一步步合并

19、。例如，如果C1中的一個對象和C2中的一個對象之間的相似度是所有不同簇間最小的，則C1和C2被合并。兩個簇間的相似度由這兩個不同簇中距離最近的數(shù)據(jù)點對的歐氏距離確定。例，對右邊的樣本數(shù)據(jù)集，使用AGNES算法進行聚類（用戶輸入的終止條件為兩個簇）。,18,三、層次聚類方法,,算法步驟如下：初始簇{1}，{2}，{3}，{4}，{5}，{6}，{7}，{8}第一步，根據(jù)初始簇計算每個簇間的距離，隨即找出距離最小的兩個簇，進行合并

20、，最小距離為1，合并后1、2點合并為一個點。第二步，對上一次合并后的簇計算簇間的距離，找出距離最小的兩個簇，進行合并，合并后3、4點合并為一個點。第三步，同上，5，6點成為一簇。第四步，同上，7，8點成為一簇。第五步，合并{1，2}，{3，4}為一個簇。第五步，合并{5，6}，{7，8}為一個簇。合并后簇的數(shù)目為2，達到終止條件程序終止。,19,三、層次聚類方法,,（2）DIANA算法是分裂的層次聚類。算法初始將所有對象都放

21、在一個簇中，然后根據(jù)一些原則（如簇中最鄰近對象的最大歐氏距離），將該簇分裂。分裂過程反復進行，直到達到終止條件。算法使用下面兩種測度方法：簇的直徑：在一個簇中的任意兩個數(shù)據(jù)點都有一個歐氏距離，這些距離中最大值是簇的直徑。平均相異度。例，對下面的樣本數(shù)據(jù)集，使用DIANA算法進行聚類（用戶輸入的終止條件為兩個簇）。,20,三、層次聚類方法,,步驟如下：第一步，找出具有最大直徑的簇，對簇中的每個點計算平均相異度（假定采用歐氏

22、距離）。1的平均距離：（1+1+1.41+3.6+4.24+4.47+5）/7 = 2.962的平均距離：2.5263的平均距離：2.684的平均距離：2.185的平均距離：2.186的平均距離：2.687的平均距離：2.5268的平均距離：2.96挑出平均相異度最大的點1放到Splinter group，剩余點在old Party中,21,三、層次聚類方法,,第二步，在old Party中找出到最近的Splinter

23、 group中點的距離不大于到old Party中點的最近距離的點，放到Splinter group中，該點是2。第三步，重復第二步工作，在Splinter group中放入點3。第四步，重復第二步工作，在Splinter group中放入點4。第五步，沒有新的old Party中的點被分配給Splinter group，此時分裂的簇數(shù)為2，達到終止條件程序終止。（如果沒有達到終止條件，下一階段還會從分裂號的簇中選一個直徑最大的簇