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

1、1,一、聚類(lèi)挖掘的相關(guān)概念,,1、聚類(lèi) 就是把整個(gè)數(shù)據(jù)分成不同的組，并使組與組之間的差異盡可能大，組內(nèi)數(shù)據(jù)的差異盡可能小。 2、聚類(lèi)與分類(lèi)的差別 聚類(lèi)開(kāi)始時(shí)不知道要把數(shù)據(jù)分成幾組，也沒(méi)有分類(lèi)的具體標(biāo)準(zhǔn)，聚類(lèi)分析時(shí)數(shù)據(jù)集合的特征是未知的，也稱(chēng)無(wú)指導(dǎo)學(xué)習(xí)。 分類(lèi)開(kāi)始時(shí)知道要把數(shù)據(jù)分成幾組，分類(lèi)將要處理的數(shù)據(jù)按照分類(lèi)標(biāo)準(zhǔn)分入不同的類(lèi)別，也稱(chēng)有指導(dǎo)學(xué)習(xí)。 例如，聚類(lèi)：嬰兒區(qū)分動(dòng)物；分類(lèi)：成人區(qū)分動(dòng)物。,2,一、聚類(lèi)

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

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

4、分為三種：數(shù)值型數(shù)據(jù)聚類(lèi)方法所分析的數(shù)據(jù)是數(shù)值型數(shù)據(jù)，因此，可對(duì)所處理的數(shù)據(jù)直接比較大小。符號(hào)值數(shù)據(jù)聚類(lèi)方法所分析的數(shù)據(jù)是符號(hào)型數(shù)據(jù)，因此，對(duì)所處理的數(shù)據(jù)不能直接比較大小?；旌闲蛿?shù)據(jù)聚類(lèi)方法能同時(shí)處理數(shù)值數(shù)據(jù)和符號(hào)數(shù)據(jù)，此方法通常功能強(qiáng)大，但性能往往不盡如人意。,5,一、聚類(lèi)挖掘的相關(guān)概念,,（3）按照聚類(lèi)的尺度，可分為三種：基于距離的聚類(lèi)算法根據(jù)數(shù)據(jù)之間的距離進(jìn)行聚類(lèi)。此算法對(duì)噪聲數(shù)據(jù)和孤立點(diǎn)較敏感?；诿芏鹊木垲?lèi)算

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

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

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

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

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

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

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

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

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

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

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

16、。同理，可以計(jì)算出：TCAD=-2，TCAE=-1，TCBC=-2，TCBD=-2，TCBE=-2選取一個(gè)最小的代價(jià)，如TCAC（C替換A），樣本點(diǎn)被劃分為｛B，A，E｝和｛C，D｝。至此完成第一次迭代，重復(fù)上述過(guò)程，直到代價(jià)不再減小。,15,二、基于劃分的聚類(lèi)方法,,下圖為6個(gè)距離代價(jià)的改變量,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)開(kāi)始：A和B為中心點(diǎn),(b)TCAC：變化-2；TCAD：變化-2,(c)TCAE：變化-1,(e)TCBE：變化-2,(e)TCBD：變化-2,(d)TCBC：變化-2,2,2,3,16,三、層次聚類(lèi)方法,,層次聚類(lèi)方法是對(duì)給定的數(shù)據(jù)集進(jìn)行層次分解，直到滿(mǎn)足某種條件為止。具體可分為凝聚的、分

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

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

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

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

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挑出平均相異度最大的點(diǎn)1放到Splinter group，剩余點(diǎn)在old Party中,21,三、層次聚類(lèi)方法,,第二步，在old Party中找出到最近的Splinter

23、 group中點(diǎn)的距離不大于到old Party中點(diǎn)的最近距離的點(diǎn)，放到Splinter group中，該點(diǎn)是2。第三步，重復(fù)第二步工作，在Splinter group中放入點(diǎn)3。第四步，重復(fù)第二步工作，在Splinter group中放入點(diǎn)4。第五步，沒(méi)有新的old Party中的點(diǎn)被分配給Splinter group，此時(shí)分裂的簇?cái)?shù)為2，達(dá)到終止條件程序終止。（如果沒(méi)有達(dá)到終止條件，下一階段還會(huì)從分裂號(hào)的簇中選一個(gè)直徑最大的簇