數(shù)據(jù)挖掘聚類分析第六章

數(shù)據(jù)挖掘聚類分析第六章例某公司下屬30個企業(yè)，公司為了考核下屬企業(yè)的經(jīng)濟效益，設(shè)計了8個指標(biāo)。為了避免重復(fù)，需要對這8個指標(biāo)進(jìn)行篩選，建立一個恰當(dāng)?shù)慕?jīng)濟效益指標(biāo)體系。通過計算30個企業(yè)8個指標(biāo)的相關(guān)系數(shù)距離，數(shù)據(jù)是1-r2。得如下表:

x1x2

x3

x4x5

x6

x7

x8

x10

0.600

0.430.460

0.470.450.120

0.570.450.230.220

0.380.400.210.290.220

0.310.790.650.700.800.660

0.450.450.270.230.140.190.770試用將它們聚類。x2

x3x4x5

x6

x7

x8第2頁,共19頁，星期六，2024年，5月第3頁,共19頁，星期六，2024年，5月確定類的個數(shù)

在聚類分析過程中類的個數(shù)如何來確定才合適呢？這是一個十分困難的問題，人們至今仍未找到令人滿意的方法。但是這個問題又是不可回避的。

給定閾值——通過觀測聚類圖，給出一個合適的閾值T。要求類與類之間的距離不要超過T值。例如我們給定T=2.2，當(dāng)聚類時，類間的距離已經(jīng)超過了2.2，則聚類結(jié)束。第4頁,共19頁，星期六，2024年，5月什么是好的聚類方法?一個好的聚類方法可以產(chǎn)生高質(zhì)量的聚類：類的內(nèi)部具有較高的相似度類間具有較低的相似度聚類結(jié)果的質(zhì)量依賴于相似度評價方法以及它們的應(yīng)用；聚類結(jié)果的質(zhì)量也取決于它發(fā)現(xiàn)隱藏模式的能力。.第5頁,共19頁，星期六，2024年，5月K-均值聚類K-均值聚類方法是最簡單、最常用的使用使用準(zhǔn)則的方法。K-均值聚類是屬于劃分方法中的基于質(zhì)心技術(shù)的一種方法。劃分的思路是以k為參數(shù)，把n個對象分為k個類，以使類內(nèi)具有較高的相似度，而類間的相似度較低。相似度的計算根據(jù)一個類中對象的平均值(被看作類的重心)來進(jìn)行。第6頁,共19頁，星期六，2024年，5月

K-均值聚類的處理流程如下。首先，隨機選擇k個對象，每個對象都初始地代表一個類的平均值或中心。對剩余的對象，根據(jù)其與各自類中心的距離，將它賦給最近的類。然后重新計算每個類的平均值。這個過程不斷重復(fù)，直到準(zhǔn)則函數(shù)收斂。

第7頁,共19頁，星期六，2024年，5月

注意：類均值的初始值是任意分配的，可以隨機分配也可以直接使用前K個成員的屬性值。第8頁,共19頁，星期六，2024年，5月K-均值聚類實例假設(shè)給定如下要進(jìn)行聚類的元組：{2,4,10,12,3,20,30,11,25}，并假設(shè)k=2.初始時用前兩個數(shù)值作為類的均值；m=2和m=4.利用歐幾里德距離，可得K1={2,3}和K2={4,10,12,20,30,11,25}。數(shù)值3與兩個均值的距離相等，所以任意地選擇K1作為其所屬類。在這種情況下，可以進(jìn)行任意指派。計算均值可得m1=2.5和m2=16。重新對類中的成員進(jìn)行分配，不斷重復(fù)上述過程，直至均值不再變化。第9頁,共19頁，星期六，2024年，5月

具體過程如表：m1m2K1K224{2,3}{4,10,12,20,30,11,25}2.516{2,3,4}{10,12,20,30,11,25}318{2,3,4,10}{12,20,30,11,25}4.7519.6{2,3,4,10,11,12}{20,30,25}725{2,3,4,10,11,12}{20,30,25}第10頁,共19頁，星期六，2024年，5月

注意在最后兩步中類的成員是一致的，由于均值不再變化，所以均值已經(jīng)收斂了。因此，該問題的答案為:K1={2,3,4,10,11,12}和K2={20,30,25}K-均值法要求定義的類均值存在，并且要以期望的類的數(shù)目k作為輸入。要求用戶必須事先給出k（要生成的類的數(shù)目）可以算是該方法的一個缺點。而且，它對于“噪聲”和孤立點數(shù)據(jù)是敏感的，少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。第11頁,共19頁，星期六，2024年，5月K-Means聚類示例

第12頁,共19頁，星期六，2024年，5月

增量聚類

在越來越多的應(yīng)用中，必須對收集來的大量數(shù)據(jù)進(jìn)行聚類?！按罅俊钡亩x隨著技術(shù)的改變而不同。在六十年代，“大量”意味著幾千個聚類的樣本。現(xiàn)在，有些應(yīng)用涉及到成千上萬個高維樣本的聚類。增量聚類方法是最流行的，我們將解釋它的基本原理，下面是增量聚類方法的所有步驟：第13頁,共19頁，星期六，2024年，5月

1、對樣本排序后，把第一個數(shù)據(jù)項分配到第一個類里。2、考慮下一個數(shù)據(jù)項，把它分配到目前某個類中或一個新類中。給分配是基于一些準(zhǔn)則的，例如新數(shù)據(jù)項到目前類的重心的距離。在這種情況下，每次添加一個新數(shù)據(jù)項到一個目前的類中時，需要重新計算重心的值。3、重復(fù)步驟2，直到所有的數(shù)據(jù)樣本都被聚類完畢。第14頁,共19頁，星期六，2024年，5月

例如：設(shè)x1=(0,2),x2=(0,0),x3=(1.5,0),x4=(5,0),X5=(5,2)

假定樣本的順序是：X1,X2,X3,X4,X5,類間相似度的閾值水平是s=3。1、第一個樣本X1將變成第一個類C1={x1}.x1的坐標(biāo)就是重心坐標(biāo)M1={0，2}。2、開始分析其他樣本。a)把第2個樣本x2和M1比較，距離d為:

d(x2,M1)==2.0<3第15頁,共19頁，星期六，2024年，5月

因此，x2屬于類C1，新的重心是：

M1={(0,1)}b)第3個樣本x3和重心M1（仍是僅有的重心）比較：

d(x3,M1)=C)第4個樣本X4和重心M1比較：

第16頁,共19頁，星期六，2024年，5月

d(x4,M1)=因為樣本到重心M1的距離比閾值s大，因此該樣本將生成一個自己的類C2={X4},

其相應(yīng)的重心為M2={5，0}。d)第5個樣本和這兩個類的重心相比較：

d(x5,M1)=d(x5,M2)=第17頁,共19頁，星期六，2024年，5月

故

C2={X4,X5}得到M2={5，1}3、分析完所有的樣本，最終的聚類解決方案是獲得兩個類：