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

聚類(lèi)分析算法——學(xué)習(xí)匯報(bào)聚類(lèi)分析算法1聚類(lèi)分析概述寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院

1、什么是聚類(lèi)？

聚類(lèi)（clustering）是將物理或抽象對(duì)象的集合分組成為多個(gè)類(lèi)或簇（cluster）的過(guò)程，使得在同一個(gè)簇中的對(duì)象之間具有較高的相似度，而不同簇中的對(duì)象差別較大。

2、與分類(lèi)的不同

它要?jiǎng)澐值念?lèi)是未知的。即聚類(lèi)是一種無(wú)指導(dǎo)學(xué)習(xí)，它不依賴(lài)預(yù)先定義的類(lèi)和帶類(lèi)標(biāo)號(hào)的訓(xùn)練實(shí)例。聚類(lèi)分析概述寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院2聚類(lèi)分析的應(yīng)用

聚類(lèi)分析已經(jīng)廣泛的用在許多應(yīng)用中，包括模式識(shí)別、數(shù)據(jù)分析、圖像處理以及市場(chǎng)研究。典型的應(yīng)用：

（1）商業(yè)：幫助市場(chǎng)分析人員從客戶(hù)基本庫(kù)中發(fā)現(xiàn)不同的客戶(hù)群，并且用不同的購(gòu)買(mǎi)模式描述不同客戶(hù)群的特征。

（2）生物學(xué)：推導(dǎo)植物或動(dòng)物的分類(lèi)，活的對(duì)種群固有結(jié)構(gòu)的認(rèn)識(shí)。（3）WEB文檔分類(lèi)（4）其他：地球觀測(cè)數(shù)據(jù)庫(kù)中相似地區(qū)的確定各類(lèi)保險(xiǎn)投保人的分組，一個(gè)城市中不同類(lèi)型、價(jià)值、地理位置房子的分組等。（5）作為其他數(shù)據(jù)挖掘算法的預(yù)處理：即先進(jìn)行聚類(lèi)，然后再進(jìn)行分類(lèi)等其他數(shù)據(jù)挖掘

寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院聚類(lèi)分析的應(yīng)用聚類(lèi)分析已經(jīng)廣泛的用在許多應(yīng)用中，包括3聚類(lèi)分析的要求寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院可伸縮性處理不同類(lèi)型屬性的能力發(fā)現(xiàn)任意形狀的聚類(lèi)

用于決定輸入?yún)?shù)的領(lǐng)域知識(shí)最小化

處理噪聲數(shù)據(jù)的能力

對(duì)于輸入記錄的順序不敏感高維性基于約束的聚類(lèi)可解釋性和可用性聚類(lèi)分析的要求寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院4聚類(lèi)分析中的數(shù)據(jù)類(lèi)型寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院

聚類(lèi)分析中數(shù)據(jù)類(lèi)型用于度量對(duì)象間的相異度，常用的數(shù)據(jù)類(lèi)型:

區(qū)間標(biāo)度變量二元變量標(biāo)稱(chēng)型、序數(shù)型和比例標(biāo)度型變量混合類(lèi)型變量聚類(lèi)分析中的數(shù)據(jù)類(lèi)型寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院聚類(lèi)分析中5區(qū)間標(biāo)度變量

寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院1、

區(qū)間標(biāo)度變量是一個(gè)粗略線(xiàn)性標(biāo)度的連續(xù)度量。典型的例子包括重量和高度，經(jīng)度和緯度坐標(biāo)，以及大氣溫度。

2、選擇不同的度量單位（如“米”與英尺、“千克”與“磅”等）將直接影響聚類(lèi)分析的結(jié)果。

3、為了避免聚類(lèi)分析對(duì)度量單位的依賴(lài)性，數(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ú)單位的值。區(qū)間標(biāo)度變量寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院1、區(qū)間標(biāo)度變6度量值的標(biāo)準(zhǔn)化

寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院

（1）計(jì)算平均的絕對(duì)偏差（meanabsolutedeviation）:其中：

（2）計(jì)算標(biāo)準(zhǔn)化的度量值，或（z-score）:

度量值的標(biāo)準(zhǔn)化寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院（1）計(jì)算平均7對(duì)象間的相異度計(jì)算歐幾里德距離：曼哈坦距離：明考斯基距離：

寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院對(duì)象間的相異度計(jì)算歐幾里德距離：寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院8聚類(lèi)分析中的數(shù)據(jù)類(lèi)型寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院

聚類(lèi)分析中數(shù)據(jù)類(lèi)型用于度量對(duì)象間的相異度，常用的數(shù)據(jù)類(lèi)型:

區(qū)間標(biāo)度變量二元變量標(biāo)稱(chēng)型、序數(shù)型和比例標(biāo)度型變量混合類(lèi)型變量聚類(lèi)分析中的數(shù)據(jù)類(lèi)型寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院聚類(lèi)分析中9二元變量寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院

一個(gè)二元變量只有兩個(gè)狀態(tài)：0或者1，0表示該變量為空，1表示該變量存在。

如果假設(shè)所有的二元變量有相同的權(quán)重，則得到一個(gè)兩行兩列的可能性表。在下面這個(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。ObjectjObjecti二元變量寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院一個(gè)二元變量只有10

基于對(duì)稱(chēng)二元變量的相似度稱(chēng)為恒定的相似度，即當(dāng)一些或者全部二元變量編碼改變時(shí)，計(jì)算結(jié)果不會(huì)發(fā)生變化。

如果二元變量的兩個(gè)狀態(tài)的輸出不是同樣重要，則該二元變量是不對(duì)稱(chēng)的。基于這樣變量的相似度被稱(chēng)為非恒定的相似度。

二元變量相似度的計(jì)算寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院基于對(duì)稱(chēng)二元變量的相似度稱(chēng)為恒定的相似度，即當(dāng)11聚類(lèi)分析中的數(shù)據(jù)類(lèi)型寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院

聚類(lèi)分析中數(shù)據(jù)類(lèi)型用于度量對(duì)象間的相異度，常用的數(shù)據(jù)類(lèi)型:

區(qū)間標(biāo)度變量二元變量標(biāo)稱(chēng)型、序數(shù)型和比例標(biāo)度型變量混合類(lèi)型變量聚類(lèi)分析中的數(shù)據(jù)類(lèi)型寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院聚類(lèi)分析中121、標(biāo)稱(chēng)型變量標(biāo)稱(chēng)變量（nominal）是二元變量的推廣，它可以具有多于兩個(gè)的狀態(tài)值。例如，map-color是一個(gè)標(biāo)稱(chēng)變量，它可能有五個(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ì)稱(chēng)的二元變量來(lái)編碼標(biāo)稱(chēng)變量。標(biāo)稱(chēng)型變量寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院1、標(biāo)稱(chēng)型變量標(biāo)稱(chēng)型變量寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)13

一個(gè)離散的序數(shù)（ordinal）型變量類(lèi)似于標(biāo)稱(chēng)變量，除了序數(shù)型變量的Ｍ個(gè)狀態(tài)是以有意義的序列排序的。在計(jì)算對(duì)象的相異度時(shí)，序數(shù)型變量的處理與區(qū)間標(biāo)度變量非常類(lèi)似。

（1）將xif用它對(duì)應(yīng)的秩代替。（2）將每個(gè)變量的值域映射到[0.0，1.0]上，使得每個(gè)變量都有相同的權(quán)重。這通過(guò)用zif來(lái)替代rif來(lái)實(shí)現(xiàn)。

（3）用前面所述的區(qū)間標(biāo)度變量的任一種距離計(jì)算方法來(lái)計(jì)算。序數(shù)型變量寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院一個(gè)離散的序數(shù)（ordinal）型變量類(lèi)似于標(biāo)稱(chēng)變量，14

用比例標(biāo)度型變量描述對(duì)象之間相異度有以下三種方法：（1）采用與處理區(qū)間標(biāo)度變量相同的方法。（2）對(duì)比例標(biāo)度型變量進(jìn)行對(duì)數(shù)變換，如：

yif=log(xif)然后再對(duì)變換得到的值按區(qū)間標(biāo)度的值處理。（3）將其作為連續(xù)的序數(shù)型數(shù)據(jù)，將其秩作為區(qū)間標(biāo)度的值來(lái)對(duì)待。比例標(biāo)度型變量寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院用比例標(biāo)度型變量描述對(duì)象之間相異度有以下三種方法：比例15聚類(lèi)分析中的數(shù)據(jù)類(lèi)型寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院

聚類(lèi)分析中數(shù)據(jù)類(lèi)型用于度量對(duì)象間的相異度，常用的數(shù)據(jù)類(lèi)型:

區(qū)間標(biāo)度變量二元變量標(biāo)稱(chēng)型、序數(shù)型和比例標(biāo)度型變量混合類(lèi)型變量聚類(lèi)分析中的數(shù)據(jù)類(lèi)型寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院聚類(lèi)分析中16

在許多現(xiàn)實(shí)的數(shù)據(jù)庫(kù)中，對(duì)象是被混合類(lèi)型的變量描述的。一般來(lái)說(shuō)，一個(gè)數(shù)據(jù)庫(kù)可能包含上面列出的全部六種變量類(lèi)型。用以下的公式計(jì)算i和j的相異度：

其中，p為對(duì)象中的變量個(gè)數(shù)（1）如果xif或xjf缺失（即對(duì)象i或?qū)ο骿沒(méi)有變量f的值），或者xif=xjf=0，且變量f是不對(duì)稱(chēng)的二元變量，則指示項(xiàng)δij(f)=0；否則δij(f)=1。（2）f是二元變量或標(biāo)稱(chēng)變量:ifxif=xjfdij(f)=0,elsedij(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ì)待混合類(lèi)型變量寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院在許多現(xiàn)實(shí)的數(shù)據(jù)庫(kù)中，對(duì)象是被混合類(lèi)型的變量描述的。一17基于劃分的方法基于層次的方法基于密度的方法基于網(wǎng)格的方法基于模型的方法

主要聚類(lèi)分析方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院主要聚類(lèi)分析方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院18

劃分方法（partitioningmethod）的基本思想是：給定一個(gè)n個(gè)對(duì)象或元組的數(shù)據(jù)庫(kù)，一個(gè)劃分方法構(gòu)建數(shù)據(jù)的k個(gè)劃分，每個(gè)劃分表示一個(gè)聚簇，并且k<n。也就是說(shuō)，它將數(shù)據(jù)劃分成為k個(gè)組，同時(shí)滿(mǎn)足如下要求：每個(gè)組至少包括一個(gè)對(duì)象；每個(gè)對(duì)象必須屬于且只屬于一個(gè)組?；趧澐值木垲?lèi)會(huì)要求窮舉所有可能的劃分。實(shí)際上，絕大多數(shù)應(yīng)用采用了以下兩個(gè)比較流行的啟發(fā)式方式：（1）k-平均算法。在該算法當(dāng)中，每個(gè)簇用該簇中對(duì)象的平均值來(lái)表示。（2）k-中心點(diǎn)算法。在該算法中每個(gè)簇用接近聚類(lèi)中心的一個(gè)對(duì)象來(lái)表示。

基于劃分的方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院劃分方法（partitioningmet19

層次方法（hierarchicalmethod）的基本思想是：對(duì)給定數(shù)據(jù)對(duì)象集合進(jìn)行層次的分解。根據(jù)層次的分解如何形成，層次的方法可以分為凝聚的和分裂的。

（1）凝聚的方法：又稱(chēng)為自底向上的方法，一開(kāi)始將每個(gè)對(duì)象作為單獨(dú)的一個(gè)組，然后根據(jù)一些規(guī)則相繼地合并相近的對(duì)象或者組，將它們聚合成越來(lái)越大的類(lèi)，直到所有的組合并為一個(gè)，或者達(dá)到一個(gè)預(yù)先設(shè)定的終止條件。

基于層次的方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院層次方法（hierarchicalmethod）的基20（2）分裂的方法：又稱(chēng)為自頂向下的方法，是一個(gè)與凝聚的方式相反的過(guò)程。即開(kāi)始時(shí)將所有的對(duì)象置于一個(gè)簇中。在迭代的每一步中，一個(gè)簇被分裂為更小的簇，直到最終每個(gè)對(duì)象在單獨(dú)的一個(gè)簇中，或者達(dá)到一個(gè)終止條件（例如：類(lèi)的數(shù)目到了預(yù)定值，最近的兩個(gè)類(lèi)之間的最小距離大于設(shè)定值等）。

基于層次的方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院基于層次的方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院21絕大多數(shù)劃分方法基于對(duì)象之間的距離進(jìn)行聚類(lèi)。這樣的方法只能發(fā)現(xiàn)球狀的簇，而在發(fā)現(xiàn)任意形狀的簇上遇到了困難。隨之提出了基于密度的聚類(lèi)方法（density-basedmethod）?；舅枷胧牵褐灰R近區(qū)域的密度（對(duì)象或數(shù)據(jù)點(diǎn)的數(shù)目）超過(guò)某個(gè)值，就繼續(xù)聚類(lèi)。也就是說(shuō)，對(duì)給定類(lèi)中的每個(gè)數(shù)據(jù)點(diǎn)，在一個(gè)給定范圍的區(qū)域中必須至少包含某個(gè)數(shù)目點(diǎn)。這樣的方法可以用來(lái)過(guò)濾“噪聲”孤立點(diǎn)數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。基于密度的方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院絕大多數(shù)劃分方法基于對(duì)象之間的距離進(jìn)行聚類(lèi)。這樣的22

基于網(wǎng)格的方法（grid-basedmethod）的基本思想是：對(duì)象空間量化為有限數(shù)目的單元，形成了一個(gè)網(wǎng)格結(jié)構(gòu)。所有的聚類(lèi)操作都在這個(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é)院基于網(wǎng)格的方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院23

基本思想是：為每個(gè)簇假定了一個(gè)模型，尋找數(shù)據(jù)對(duì)給定模型的最佳擬合。一個(gè)基于模型的算法可能通過(guò)構(gòu)建反映數(shù)據(jù)點(diǎn)空間分布的密度函數(shù)來(lái)定位聚類(lèi)。它也是基于標(biāo)準(zhǔn)的統(tǒng)計(jì)數(shù)字自動(dòng)決定聚類(lèi)的數(shù)目，考慮“噪聲”數(shù)據(jù)或孤立點(diǎn)，從而產(chǎn)生健壯的聚類(lèi)方法?；谀Ｐ偷姆椒▽幭拇髮W(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院基于模型的方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院24

k-means算法，也被稱(chēng)為k-平均或k-均值，是一種得到最廣泛使用的聚類(lèi)算法。它是將各個(gè)聚類(lèi)子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類(lèi)的代表點(diǎn)，算法的主要思想是通過(guò)迭代過(guò)程把數(shù)據(jù)集劃分為不同的類(lèi)別，使得評(píng)價(jià)聚類(lèi)性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)，從而使生成的每個(gè)聚類(lèi)內(nèi)緊湊，類(lèi)間獨(dú)立。

k-means算法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院k-means算法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院25（1）選定某種距離作為數(shù)據(jù)樣本間的相似性度量例如歐式距離：（2）選擇評(píng)價(jià)聚類(lèi)性能的準(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é)院k-means算法三個(gè)要點(diǎn)寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院26輸入：簇的數(shù)目k和包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)。輸出：k個(gè)簇，使平方誤差準(zhǔn)則最小。算法步驟：1.為每個(gè)聚類(lèi)確定一個(gè)初始聚類(lèi)中心，這樣就有K個(gè)初始聚類(lèi)中心。2.將樣本集中的樣本按照最小距離原則分配到最鄰近聚類(lèi)3.使用每個(gè)聚類(lèi)中的樣本均值作為新的聚類(lèi)中心。4.重復(fù)步驟2.3步直到聚類(lèi)中心不再變化。5.結(jié)束，得到K個(gè)聚類(lèi)

k-means算法流程寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院k-means算法流程寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院27主要優(yōu)點(diǎn)：是解決聚類(lèi)問(wèn)題的一種經(jīng)典算法，簡(jiǎn)單、快速。對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮和高效率的。因?yàn)樗膹?fù)雜度是0(nkt),其中,n是所有對(duì)象的數(shù)目,k是簇的數(shù)目,t是迭代的次數(shù)。通常k<<n且t<<n。當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時(shí),它的效果較好。k-means算法性能分析寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院k-means算法性能分析寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院28主要缺點(diǎn)在簇的平均值被定義的情況下才能使用，這對(duì)于處理符號(hào)屬性的數(shù)據(jù)不適用。必須事先給出k（要生成的簇的數(shù)目），而且對(duì)初值敏感，對(duì)于不同的初始值，可能會(huì)導(dǎo)致不同結(jié)果。它對(duì)于“躁聲”和孤立點(diǎn)數(shù)據(jù)是敏感的，少量的該類(lèi)數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。k-means算法性能分析寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院k-means算法性能分析寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院29

k-means算法對(duì)某類(lèi)簇中所有的樣本點(diǎn)維度求平均值，即獲得該類(lèi)簇質(zhì)點(diǎn)的維度。當(dāng)聚類(lèi)的樣本點(diǎn)中有“噪聲”（離群點(diǎn)）時(shí)，在計(jì)算類(lèi)簇質(zhì)點(diǎn)的過(guò)程中會(huì)受到噪聲異常維度的干擾，造成所得質(zhì)點(diǎn)和實(shí)際質(zhì)點(diǎn)位置偏差過(guò)大，從而使類(lèi)簇發(fā)生“畸變”。為了解決該問(wèn)題，K中心點(diǎn)算法（K-medoids）提出了新的質(zhì)點(diǎn)選取方式，而不是簡(jiǎn)單像k-means算法采用均值計(jì)算法。在K中心點(diǎn)算法中，每次迭代后的質(zhì)點(diǎn)都是從聚類(lèi)的樣本點(diǎn)中選取，而選取的標(biāo)準(zhǔn)就是當(dāng)該樣本點(diǎn)成為新的質(zhì)點(diǎn)后能提高類(lèi)簇的聚類(lèi)質(zhì)量，使得類(lèi)簇更緊湊。該算法使用絕對(duì)誤差標(biāo)準(zhǔn)來(lái)定義一個(gè)類(lèi)簇的緊湊程度。

K-中心點(diǎn)算法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院k-means算法對(duì)某類(lèi)簇中所有的樣本點(diǎn)維度求平均值，30輸入：結(jié)果簇的數(shù)目K，包含N個(gè)對(duì)象的數(shù)據(jù)庫(kù)。輸出：K個(gè)簇，使得所有對(duì)象與其最近中心點(diǎn)的相異度總和最小。方法：隨機(jī)選擇K個(gè)對(duì)象作為初始的中心點(diǎn)。REPEAT指派每個(gè)剩余的對(duì)象給離它最近的中心點(diǎn)所代表的簇。隨機(jī)地選擇一個(gè)非中心點(diǎn)對(duì)象Orandom；計(jì)算用Orandom代替Oj的總代價(jià)S；ifS<0,thenOrandom代替Oj,形成新的K個(gè)中心點(diǎn)的集合；until不發(fā)生變化；

K-中心點(diǎn)算法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院K-中心點(diǎn)算法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院31聚類(lèi)分析算法——學(xué)習(xí)匯報(bào)聚類(lèi)分析算法32聚類(lèi)分析概述寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院

1、什么是聚類(lèi)？

聚類(lèi)（clustering）是將物理或抽象對(duì)象的集合分組成為多個(gè)類(lèi)或簇（cluster）的過(guò)程，使得在同一個(gè)簇中的對(duì)象之間具有較高的相似度，而不同簇中的對(duì)象差別較大。

2、與分類(lèi)的不同

它要?jiǎng)澐值念?lèi)是未知的。即聚類(lèi)是一種無(wú)指導(dǎo)學(xué)習(xí)，它不依賴(lài)預(yù)先定義的類(lèi)和帶類(lèi)標(biāo)號(hào)的訓(xùn)練實(shí)例。聚類(lèi)分析概述寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院33聚類(lèi)分析的應(yīng)用

聚類(lèi)分析已經(jīng)廣泛的用在許多應(yīng)用中，包括模式識(shí)別、數(shù)據(jù)分析、圖像處理以及市場(chǎng)研究。典型的應(yīng)用：

（1）商業(yè)：幫助市場(chǎng)分析人員從客戶(hù)基本庫(kù)中發(fā)現(xiàn)不同的客戶(hù)群，并且用不同的購(gòu)買(mǎi)模式描述不同客戶(hù)群的特征。

（2）生物學(xué)：推導(dǎo)植物或動(dòng)物的分類(lèi)，活的對(duì)種群固有結(jié)構(gòu)的認(rèn)識(shí)。（3）WEB文檔分類(lèi)（4）其他：地球觀測(cè)數(shù)據(jù)庫(kù)中相似地區(qū)的確定各類(lèi)保險(xiǎn)投保人的分組，一個(gè)城市中不同類(lèi)型、價(jià)值、地理位置房子的分組等。（5）作為其他數(shù)據(jù)挖掘算法的預(yù)處理：即先進(jìn)行聚類(lèi)，然后再進(jìn)行分類(lèi)等其他數(shù)據(jù)挖掘

寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院聚類(lèi)分析的應(yīng)用聚類(lèi)分析已經(jīng)廣泛的用在許多應(yīng)用中，包括34聚類(lèi)分析的要求寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院可伸縮性處理不同類(lèi)型屬性的能力發(fā)現(xiàn)任意形狀的聚類(lèi)

用于決定輸入?yún)?shù)的領(lǐng)域知識(shí)最小化

處理噪聲數(shù)據(jù)的能力

對(duì)于輸入記錄的順序不敏感高維性基于約束的聚類(lèi)可解釋性和可用性聚類(lèi)分析的要求寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院35聚類(lèi)分析中的數(shù)據(jù)類(lèi)型寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院

聚類(lèi)分析中數(shù)據(jù)類(lèi)型用于度量對(duì)象間的相異度，常用的數(shù)據(jù)類(lèi)型:

區(qū)間標(biāo)度變量二元變量標(biāo)稱(chēng)型、序數(shù)型和比例標(biāo)度型變量混合類(lèi)型變量聚類(lèi)分析中的數(shù)據(jù)類(lèi)型寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院聚類(lèi)分析中36區(qū)間標(biāo)度變量

寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院1、

區(qū)間標(biāo)度變量是一個(gè)粗略線(xiàn)性標(biāo)度的連續(xù)度量。典型的例子包括重量和高度，經(jīng)度和緯度坐標(biāo)，以及大氣溫度。

2、選擇不同的度量單位（如“米”與英尺、“千克”與“磅”等）將直接影響聚類(lèi)分析的結(jié)果。

3、為了避免聚類(lèi)分析對(duì)度量單位的依賴(lài)性，數(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ú)單位的值。區(qū)間標(biāo)度變量寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院1、區(qū)間標(biāo)度變37度量值的標(biāo)準(zhǔn)化

寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院

（1）計(jì)算平均的絕對(duì)偏差（meanabsolutedeviation）:其中：

（2）計(jì)算標(biāo)準(zhǔn)化的度量值，或（z-score）:

度量值的標(biāo)準(zhǔn)化寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院（1）計(jì)算平均38對(duì)象間的相異度計(jì)算歐幾里德距離：曼哈坦距離：明考斯基距離：

寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院對(duì)象間的相異度計(jì)算歐幾里德距離：寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院39聚類(lèi)分析中的數(shù)據(jù)類(lèi)型寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院

聚類(lèi)分析中數(shù)據(jù)類(lèi)型用于度量對(duì)象間的相異度，常用的數(shù)據(jù)類(lèi)型:

區(qū)間標(biāo)度變量二元變量標(biāo)稱(chēng)型、序數(shù)型和比例標(biāo)度型變量混合類(lèi)型變量聚類(lèi)分析中的數(shù)據(jù)類(lèi)型寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院聚類(lèi)分析中40二元變量寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院

一個(gè)二元變量只有兩個(gè)狀態(tài)：0或者1，0表示該變量為空，1表示該變量存在。

如果假設(shè)所有的二元變量有相同的權(quán)重，則得到一個(gè)兩行兩列的可能性表。在下面這個(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。ObjectjObjecti二元變量寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院一個(gè)二元變量只有41

基于對(duì)稱(chēng)二元變量的相似度稱(chēng)為恒定的相似度，即當(dāng)一些或者全部二元變量編碼改變時(shí)，計(jì)算結(jié)果不會(huì)發(fā)生變化。

如果二元變量的兩個(gè)狀態(tài)的輸出不是同樣重要，則該二元變量是不對(duì)稱(chēng)的?；谶@樣變量的相似度被稱(chēng)為非恒定的相似度。

二元變量相似度的計(jì)算寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院基于對(duì)稱(chēng)二元變量的相似度稱(chēng)為恒定的相似度，即當(dāng)42聚類(lèi)分析中的數(shù)據(jù)類(lèi)型寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院

聚類(lèi)分析中數(shù)據(jù)類(lèi)型用于度量對(duì)象間的相異度，常用的數(shù)據(jù)類(lèi)型:

區(qū)間標(biāo)度變量二元變量標(biāo)稱(chēng)型、序數(shù)型和比例標(biāo)度型變量混合類(lèi)型變量聚類(lèi)分析中的數(shù)據(jù)類(lèi)型寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院聚類(lèi)分析中431、標(biāo)稱(chēng)型變量標(biāo)稱(chēng)變量（nominal）是二元變量的推廣，它可以具有多于兩個(gè)的狀態(tài)值。例如，map-color是一個(gè)標(biāo)稱(chēng)變量，它可能有五個(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ì)稱(chēng)的二元變量來(lái)編碼標(biāo)稱(chēng)變量。標(biāo)稱(chēng)型變量寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院1、標(biāo)稱(chēng)型變量標(biāo)稱(chēng)型變量寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)44

一個(gè)離散的序數(shù)（ordinal）型變量類(lèi)似于標(biāo)稱(chēng)變量，除了序數(shù)型變量的Ｍ個(gè)狀態(tài)是以有意義的序列排序的。在計(jì)算對(duì)象的相異度時(shí)，序數(shù)型變量的處理與區(qū)間標(biāo)度變量非常類(lèi)似。

（1）將xif用它對(duì)應(yīng)的秩代替。（2）將每個(gè)變量的值域映射到[0.0，1.0]上，使得每個(gè)變量都有相同的權(quán)重。這通過(guò)用zif來(lái)替代rif來(lái)實(shí)現(xiàn)。

（3）用前面所述的區(qū)間標(biāo)度變量的任一種距離計(jì)算方法來(lái)計(jì)算。序數(shù)型變量寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院一個(gè)離散的序數(shù)（ordinal）型變量類(lèi)似于標(biāo)稱(chēng)變量，45

用比例標(biāo)度型變量描述對(duì)象之間相異度有以下三種方法：（1）采用與處理區(qū)間標(biāo)度變量相同的方法。（2）對(duì)比例標(biāo)度型變量進(jìn)行對(duì)數(shù)變換，如：

yif=log(xif)然后再對(duì)變換得到的值按區(qū)間標(biāo)度的值處理。（3）將其作為連續(xù)的序數(shù)型數(shù)據(jù)，將其秩作為區(qū)間標(biāo)度的值來(lái)對(duì)待。比例標(biāo)度型變量寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院用比例標(biāo)度型變量描述對(duì)象之間相異度有以下三種方法：比例46聚類(lèi)分析中的數(shù)據(jù)類(lèi)型寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院

聚類(lèi)分析中數(shù)據(jù)類(lèi)型用于度量對(duì)象間的相異度，常用的數(shù)據(jù)類(lèi)型:

區(qū)間標(biāo)度變量二元變量標(biāo)稱(chēng)型、序數(shù)型和比例標(biāo)度型變量混合類(lèi)型變量聚類(lèi)分析中的數(shù)據(jù)類(lèi)型寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院聚類(lèi)分析中47

在許多現(xiàn)實(shí)的數(shù)據(jù)庫(kù)中，對(duì)象是被混合類(lèi)型的變量描述的。一般來(lái)說(shuō)，一個(gè)數(shù)據(jù)庫(kù)可能包含上面列出的全部六種變量類(lèi)型。用以下的公式計(jì)算i和j的相異度：

其中，p為對(duì)象中的變量個(gè)數(shù)（1）如果xif或xjf缺失（即對(duì)象i或?qū)ο骿沒(méi)有變量f的值），或者xif=xjf=0，且變量f是不對(duì)稱(chēng)的二元變量，則指示項(xiàng)δij(f)=0；否則δij(f)=1。（2）f是二元變量或標(biāo)稱(chēng)變量:ifxif=xjfdij(f)=0,elsedij(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ì)待混合類(lèi)型變量寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院在許多現(xiàn)實(shí)的數(shù)據(jù)庫(kù)中，對(duì)象是被混合類(lèi)型的變量描述的。一48基于劃分的方法基于層次的方法基于密度的方法基于網(wǎng)格的方法基于模型的方法

主要聚類(lèi)分析方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院主要聚類(lèi)分析方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院49

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

基于劃分的方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院劃分方法（partitioningmet50

層次方法（hierarchicalmethod）的基本思想是：對(duì)給定數(shù)據(jù)對(duì)象集合進(jìn)行層次的分解。根據(jù)層次的分解如何形成，層次的方法可以分為凝聚的和分裂的。

（1）凝聚的方法：又稱(chēng)為自底向上的方法，一開(kāi)始將每個(gè)對(duì)象作為單獨(dú)的一個(gè)組，然后根據(jù)一些規(guī)則相繼地合并相近的對(duì)象或者組，將它們聚合成越來(lái)越大的類(lèi)，直到所有的組合并為一個(gè)，或者達(dá)到一個(gè)預(yù)先設(shè)定的終止條件。

基于層次的方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院層次方法（hierarchicalmethod）的基51（2）分裂的方法：又稱(chēng)為自頂向下的方法，是一個(gè)與凝聚的方式相反的過(guò)程。即開(kāi)始時(shí)將所有的對(duì)象置于一個(gè)簇中。在迭代的每一步中，一個(gè)簇被分裂為更小的簇，直到最終每個(gè)對(duì)象在單獨(dú)的一個(gè)簇中，或者達(dá)到一個(gè)終止條件（例如：類(lèi)的數(shù)目到了預(yù)定值，最近的兩個(gè)類(lèi)之間的最小距離大于設(shè)定值等）。

基于層次的方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院基于層次的方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院52絕大多數(shù)劃分方法基于對(duì)象之間的距離進(jìn)行聚類(lèi)。這樣的方法只能發(fā)現(xiàn)球狀的簇，而在發(fā)現(xiàn)任意形狀的簇上遇到了困難。隨之提出了基于密度的聚類(lèi)方法（density-basedmethod）。基本思想是：只要臨近區(qū)域的密度（對(duì)象或數(shù)據(jù)點(diǎn)的數(shù)目）超過(guò)某個(gè)值，就繼續(xù)聚類(lèi)。也就是說(shuō)，對(duì)給定類(lèi)中的每個(gè)數(shù)據(jù)點(diǎn)，在一個(gè)給定范圍的區(qū)域中必須至少包含某個(gè)數(shù)目點(diǎn)。這樣的方法可以用來(lái)過(guò)濾“噪聲”孤立點(diǎn)數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。基于密度的方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院絕大多數(shù)劃分方法基于對(duì)象之間的距離進(jìn)行聚類(lèi)。這樣的53

基于網(wǎng)格的方法（grid-basedmethod）的基本思想是：對(duì)象空間量化為有限數(shù)目的單元，形成了一個(gè)網(wǎng)格結(jié)構(gòu)。所有的聚類(lèi)操作都在這個(gè)網(wǎng)格結(jié)構(gòu)上進(jìn)行。這種方法的主要優(yōu)點(diǎn)是它的處理速度較快，其處理時(shí)間獨(dú)立于數(shù)據(jù)對(duì)象的數(shù)目，只與量化空間中每一維單元數(shù)目有關(guān)。基于網(wǎng)格的方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院基于網(wǎng)格的方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院54

基本思想是：為每個(gè)簇假定了一個(gè)模型，尋找數(shù)據(jù)對(duì)給定模型的最佳擬合。一個(gè)基于模型的算法可能通過(guò)構(gòu)建反映數(shù)據(jù)點(diǎn)空間分布的密度函數(shù)來(lái)定位聚類(lèi)。它也是基于標(biāo)準(zhǔn)的統(tǒng)計(jì)數(shù)字自動(dòng)決定聚類(lèi)的數(shù)目，考慮“噪聲”數(shù)據(jù)或孤立點(diǎn)，從而產(chǎn)生健壯的聚類(lèi)方法。基于模型的方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院基于模型的方法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院55

k-means算法，也被稱(chēng)為k-平均或k-均值，是一種得到最廣泛使用的聚類(lèi)算法。它是將各個(gè)聚類(lèi)子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類(lèi)的代表點(diǎn)，算法的主要思想是通過(guò)迭代過(guò)程把數(shù)據(jù)集劃分為不同的類(lèi)別，使得評(píng)價(jià)聚類(lèi)性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)，從而使生成的每個(gè)聚類(lèi)內(nèi)緊湊，類(lèi)間獨(dú)立。

k-means算法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院k-means算法寧夏大學(xué)·數(shù)學(xué)與計(jì)算機(jī)學(xué)院56（1）選定某種距離作為數(shù)據(jù)樣本間的相似性度量