聚類分析算法學(xué)習(xí)報告課件

1、聚類分析算法 學(xué)習(xí)匯報第1頁，共31頁。聚類分析概述寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院 1、什么是聚類？ 聚類（clustering）是將物理或抽象對象的集合分組成為多個類或簇（cluster）的過程，使得在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。 2、與分類的不同 它要劃分的類是未知的。即聚類是一種無指導(dǎo)學(xué)習(xí)，它不依賴預(yù)先定義的類和帶類標(biāo)號的訓(xùn)練實例。 第2頁，共31頁。聚類分析的應(yīng)用 聚類分析已經(jīng)廣泛的用在許多應(yīng)用中，包括模式識別、數(shù)據(jù)分析、圖像處理以及市場研究。典型的應(yīng)用： （1）商業(yè)：幫助市場分析人員從客戶基本庫中發(fā)現(xiàn)不同的客戶群，并且用不同的購買模式描述不同客戶群的特征

2、。 （2）生物學(xué)：推導(dǎo)植物或動物的分類，活的對種群固有結(jié)構(gòu)的認(rèn)識。 （3）WEB文檔分類 （4）其他：地球觀測數(shù)據(jù)庫中相似地區(qū)的確定各類保險投保人的分組，一個城市中不同類型、價值、地理位置房子的分組等。 （5）作為其他數(shù)據(jù)挖掘算法的預(yù)處理：即先進行聚類，然后再進行分類等其他數(shù)據(jù)挖掘?qū)幭拇髮W(xué)數(shù)學(xué)與計算機學(xué)院第3頁，共31頁。聚類分析的要求寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院可伸縮性處理不同類型屬性的能力發(fā)現(xiàn)任意形狀的聚類 用于決定輸入?yún)?shù)的領(lǐng)域知識最小化 處理噪聲數(shù)據(jù)的能力 對于輸入記錄的順序不敏感高維性基于約束的聚類可解釋性和可用性第4頁，共31頁。聚類分析中的數(shù)據(jù)類型寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院 聚類分析中

3、數(shù)據(jù)類型用于度量對象間的相異度，常用的數(shù)據(jù)類型:區(qū)間標(biāo)度變量二元變量標(biāo)稱型、序數(shù)型和比例標(biāo)度型變量混合類型變量第5頁，共31頁。區(qū)間標(biāo)度變量 寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院 1、 區(qū)間標(biāo)度變量是一個粗略線性標(biāo)度的連續(xù)度量。典型的例子包括重量和高度，經(jīng)度和緯度坐標(biāo)，以及大氣溫度。2、選擇不同的度量單位（如“米”與英尺、“千克”與“磅”等）將直接影響聚類分析的結(jié)果。 3、為了避免聚類分析對度量單位的依賴性，數(shù)據(jù)需要進行標(biāo)準(zhǔn)化。 4、怎樣將一個變量的數(shù)據(jù)標(biāo)準(zhǔn)化呢？為了實現(xiàn)度量值的標(biāo)準(zhǔn)化，一種方法是將原來的度量值轉(zhuǎn)換為無單位的值。 第6頁，共31頁。度量值的標(biāo)準(zhǔn)化 寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院 （1）計算平均的

4、絕對偏差（mean absolute deviation）:其中： （2）計算標(biāo)準(zhǔn)化的度量值，或（z-score）: 第7頁，共31頁。對象間的相異度計算歐幾里德距離：曼哈坦距離：明考斯基距離： 寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院第8頁，共31頁。聚類分析中的數(shù)據(jù)類型寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院 聚類分析中數(shù)據(jù)類型用于度量對象間的相異度，常用的數(shù)據(jù)類型:區(qū)間標(biāo)度變量二元變量標(biāo)稱型、序數(shù)型和比例標(biāo)度型變量混合類型變量第9頁，共31頁。二元變量寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院 一個二元變量只有兩個狀態(tài)：0或者1，0表示該變量為空，1表示該變量存在。 如果假設(shè)所有的二元變量有相同的權(quán)重，則得到一個兩行兩列的可能性表。在下

5、面這個表中，a是對于對象i和j值都為1的變量的數(shù)目，b是對于對象I值為1而對象j的值為0的變量數(shù)目，s是對于對象c值為0而在對于對象j值為1的變量數(shù)目，d是對于對象i和j的值都為0的變量的數(shù)目。變量的總數(shù)是p，p=a+b+c+d。 Object jObject i第10頁，共31頁。 基于對稱二元變量的相似度稱為恒定的相似度，即當(dāng)一些或者全部二元變量編碼改變時，計算結(jié)果不會發(fā)生變化。 如果二元變量的兩個狀態(tài)的輸出不是同樣重要，則該二元變量是不對稱的?；谶@樣變量的相似度被稱為非恒定的相似度。 二元變量相似度的計算寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院第11頁，共31頁。聚類分析中的數(shù)據(jù)類型寧夏大學(xué)數(shù)學(xué)與計算

6、機學(xué)院 聚類分析中數(shù)據(jù)類型用于度量對象間的相異度，常用的數(shù)據(jù)類型:區(qū)間標(biāo)度變量二元變量標(biāo)稱型、序數(shù)型和比例標(biāo)度型變量混合類型變量第12頁，共31頁。 1、標(biāo)稱型變量 標(biāo)稱變量（nominal）是二元變量的推廣，它可以具有多于兩個的狀態(tài)值。例如，map-color是一個標(biāo)稱變量，它可能有五個狀態(tài)：紅色，黃色，綠色，粉紅色和藍色。兩個對象和j之間的相異度可以用兩種方法來計算： （1）簡單匹配方法 M是匹配的數(shù)目，P是全部變量的數(shù)目 （2）使用二元變量 為每一個狀態(tài)創(chuàng)建一個新的二元變量，可以用非對稱的二元變量來編碼標(biāo)稱變量。標(biāo)稱型變量寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院第13頁，共31頁。 一個離散的序數(shù)（or

7、dinal）型變量類似于標(biāo)稱變量，除了序數(shù)型變量的個狀態(tài)是以有意義的序列排序的。在計算對象的相異度時，序數(shù)型變量的處理與區(qū)間標(biāo)度變量非常類似。（1）將xif 用它對應(yīng)的秩代替。 （2）將每個變量的值域映射到0.0，1.0上，使得每個變量都有相同的權(quán)重。這通過用zif來替代rif來實現(xiàn)。 （3）用前面所述的區(qū)間標(biāo)度變量的任一種距離計算方法來計算。序數(shù)型變量寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院第14頁，共31頁。 用比例標(biāo)度型變量描述對象之間相異度有以下三種方法： （1）采用與處理區(qū)間標(biāo)度變量相同的方法。 （2）對比例標(biāo)度型變量進行對數(shù)變換，如： yif = log(xif) 然后再對變換得到的值按區(qū)間標(biāo)度的

8、值處理。 （3）將其作為連續(xù)的序數(shù)型數(shù)據(jù)，將其秩作為區(qū)間標(biāo)度的值來對待。比例標(biāo)度型變量寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院第15頁，共31頁。聚類分析中的數(shù)據(jù)類型寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院 聚類分析中數(shù)據(jù)類型用于度量對象間的相異度，常用的數(shù)據(jù)類型:區(qū)間標(biāo)度變量二元變量標(biāo)稱型、序數(shù)型和比例標(biāo)度型變量混合類型變量第16頁，共31頁。 在許多現(xiàn)實的數(shù)據(jù)庫中，對象是被混合類型的變量描述的。一般來說，一個數(shù)據(jù)庫可能包含上面列出的全部六種變量類型。用以下的公式計算i和j的相異度： 其中，p為對象中的變量個數(shù) （1）如果xif或xjf缺失（即對象i或?qū)ο骿沒有變量f的值），或者xif = xjf =0，且變量f是不對稱的

9、二元變量，則指示項ij(f)=0；否則ij(f)=1。 （2）f 是二元變量或標(biāo)稱變量: if xif = xjf dij(f) = 0, else dij(f) = 1 （3）f是區(qū)間標(biāo)度變量：dij(f) = | xif-xjf |/maxhxhf-minhxhf （4）f 是序數(shù)型或比例標(biāo)度型： 計算秩rif 計算zif并將其作為區(qū)間標(biāo)度變量值對待混合類型變量寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院第17頁，共31頁?；趧澐值姆椒ɑ趯哟蔚姆椒ɑ诿芏鹊姆椒ɑ诰W(wǎng)格的方法基于模型的方法 主要聚類分析方法寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院第18頁，共31頁。 劃分方法（partitioning method）的基

10、本思想是：給定一個n個對象或元組的數(shù)據(jù)庫，一個劃分方法構(gòu)建數(shù)據(jù)的k個劃分，每個劃分表示一個聚簇，并且kn。也就是說，它將數(shù)據(jù)劃分成為k個組，同時滿足如下要求： 每個組至少包括一個對象； 每個對象必須屬于且只屬于一個組。 基于劃分的聚類會要求窮舉所有可能的劃分。實際上，絕大多數(shù)應(yīng)用采用了以下兩個比較流行的啟發(fā)式方式： （1）k-平均算法。在該算法當(dāng)中，每個簇用該簇中對象的平均值來表示。 （2）k-中心點算法。在該算法中每個簇用接近聚類中心的一個對象來表示。 基于劃分的方法寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院第19頁，共31頁。 層次方法（hierarchical method）的基本思想是：對給定數(shù)據(jù)對象集

11、合進行層次的分解。根據(jù)層次的分解如何形成，層次的方法可以分為凝聚的和分裂的。 （1）凝聚的方法：又稱為自底向上的方法，一開始將每個對象作為單獨的一個組，然后根據(jù)一些規(guī)則相繼地合并相近的對象或者組，將它們聚合成越來越大的類，直到所有的組合并為一個，或者達到一個預(yù)先設(shè)定的終止條件。 基于層次的方法寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院第20頁，共31頁。（2）分裂的方法：又稱為自頂向下的方法，是一個與凝聚的方式相反的過程。即開始時將所有的對象置于一個簇中。在迭代的每一步中，一個簇被分裂為更小的簇，直到最終每個對象在單獨的一個簇中，或者達到一個終止條件（例如：類的數(shù)目到了預(yù)定值，最近的兩個類之間的最小距離大于設(shè)定

12、值等）?；趯哟蔚姆椒▽幭拇髮W(xué)數(shù)學(xué)與計算機學(xué)院第21頁，共31頁。 絕大多數(shù)劃分方法基于對象之間的距離進行聚類。這樣的方法只能發(fā)現(xiàn)球狀的簇，而在發(fā)現(xiàn)任意形狀的簇上遇到了困難。隨之提出了基于密度的聚類方法（density-based method）。 基本思想是：只要臨近區(qū)域的密度（對象或數(shù)據(jù)點的數(shù)目）超過某個值，就繼續(xù)聚類。也就是說，對給定類中的每個數(shù)據(jù)點，在一個給定范圍的區(qū)域中必須至少包含某個數(shù)目點。這樣的方法可以用來過濾“噪聲”孤立點數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇?；诿芏鹊姆椒▽幭拇髮W(xué)數(shù)學(xué)與計算機學(xué)院第22頁，共31頁。 基于網(wǎng)格的方法（grid-based method）的基本思想是：對象空間

13、量化為有限數(shù)目的單元，形成了一個網(wǎng)格結(jié)構(gòu)。所有的聚類操作都在這個網(wǎng)格結(jié)構(gòu)上進行。這種方法的主要優(yōu)點是它的處理速度較快，其處理時間獨立于數(shù)據(jù)對象的數(shù)目，只與量化空間中每一維單元數(shù)目有關(guān)。基于網(wǎng)格的方法寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院第23頁，共31頁。 基本思想是：為每個簇假定了一個模型，尋找數(shù)據(jù)對給定模型的最佳擬合。一個基于模型的算法可能通過構(gòu)建反映數(shù)據(jù)點空間分布的密度函數(shù)來定位聚類。它也是基于標(biāo)準(zhǔn)的統(tǒng)計數(shù)字自動決定聚類的數(shù)目，考慮“噪聲”數(shù)據(jù)或孤立點，從而產(chǎn)生健壯的聚類方法。基于模型的方法寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院第24頁，共31頁。 k-means算法，也被稱為k-平均或k-均值，是一種得到最廣泛使

14、用的聚類算法。 它是將各個聚類子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類的代表點，算法的主要思想是通過迭代過程把數(shù)據(jù)集劃分為不同的類別，使得評價聚類性能的準(zhǔn)則函數(shù)達到最優(yōu)，從而使生成的每個聚類內(nèi)緊湊，類間獨立。 k-means算法寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院第25頁，共31頁。（1）選定某種距離作為數(shù)據(jù)樣本間的相似性度量 例如歐式距離：（2）選擇評價聚類性能的準(zhǔn)則函數(shù) 誤差平方和準(zhǔn)則函數(shù)為：（3）相似度的計算根據(jù)一個簇中對象的平均值來進行。k-means算法三個要點寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院第26頁，共31頁。輸入：簇的數(shù)目k和包含n個對象的數(shù)據(jù)庫。輸出：k個簇，使平方誤差準(zhǔn)則最小。 算法步驟： 1.為每

15、個聚類確定一個初始聚類中心，這樣就有K 個初始聚類中心。 2.將樣本集中的樣本按照最小距離原則分配到最鄰近聚類 3.使用每個聚類中的樣本均值作為新的聚類中心。4.重復(fù)步驟2.3步直到聚類中心不再變化。5.結(jié)束，得到K個聚類 k-means算法流程寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院第27頁，共31頁。主要優(yōu)點：是解決聚類問題的一種經(jīng)典算法，簡單、快速。對處理大數(shù)據(jù)集，該算法是相對可伸縮和高效率的。因為它的復(fù)雜度是0 (n k t ) , 其中, n 是所有對象的數(shù)目, k 是簇的數(shù)目, t 是迭代的次數(shù)。通常k n 且t n 。當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時, 它的效果較好。k-means算法性

16、能分析寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院第28頁，共31頁。主要缺點在簇的平均值被定義的情況下才能使用，這對于處理符號屬性的數(shù)據(jù)不適用。必須事先給出k（要生成的簇的數(shù)目），而且對初值敏感，對于不同的初始值，可能會導(dǎo)致不同結(jié)果。 它對于“躁聲”和孤立點數(shù)據(jù)是敏感的，少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。k-means算法性能分析寧夏大學(xué)數(shù)學(xué)與計算機學(xué)院第29頁，共31頁。 k-means算法對某類簇中所有的樣本點維度求平均值，即獲得該類簇質(zhì)點的維度。當(dāng)聚類的樣本點中有“噪聲”（離群點）時，在計算類簇質(zhì)點的過程中會受到噪聲異常維度的干擾，造成所得質(zhì)點和實際質(zhì)點位置偏差過大，從而使類簇發(fā)生“畸變”。 為了解決該問題，K中心點算法（K-medoids）提出了新的質(zhì)點選取方式，而不是簡單像k-means算法采用均值計算法。在K中心點算法中，每次迭代后的質(zhì)點都是從聚類的樣本點中選取，而選取的標(biāo)準(zhǔn)就是當(dāng)該樣本點成為新的質(zhì)點后能提高類簇的聚類質(zhì)量，使得類簇更緊湊。該算法使用絕對誤差標(biāo)準(zhǔn)來定