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

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

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

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

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

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

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

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

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

9、二元變量，則指示項(xiàng)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)度型： 計(jì)算秩rif 計(jì)算zif并將其作為區(qū)間標(biāo)度變量值對(duì)待混合類型變量寧夏大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院第17頁(yè)，共31頁(yè)。基于劃分的方法基于層次的方法基于密度的方法基于網(wǎng)格的方法基于模型的方法 主要聚類分析方法寧夏大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院第18頁(yè)，共31頁(yè)。 劃分方法（partitioning method）的基

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

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

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

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

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

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

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