大數(shù)據(jù)分析實務(wù)

第7章數(shù)據(jù)挖掘方法7.3聚類分析

聚類分析聚類分析聚類分析聚類分析聚類分析如何度量事物相似性如何把不同事物分組組內(nèi)和組間如何處理7.3.1聚類定義聚類就是按照事物的某些屬性，把事物聚集成類，使類間的相似性盡可能小，類內(nèi)相似性盡可能大。7.3.1聚類定義7.3.1聚類定義一個能產(chǎn)生高質(zhì)量聚類的算法必須滿足下面兩個條件:類內(nèi)數(shù)據(jù)或?qū)ο蟮南嗨菩宰顝?qiáng)類間數(shù)據(jù)或?qū)ο蟮南嗨菩宰钊?.3.2聚類分析中的數(shù)據(jù)許多基于內(nèi)存的聚類算法選擇兩種有代表性的數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)矩陣和相異度矩陣7.3.2聚類分析中的數(shù)據(jù)d(i,j)表示對象i和對象j之間的差異（或不相似程度）；通常d(i,j)為一個非負(fù)數(shù)；當(dāng)對象i和對象j非常相似或彼此“接近”時，該數(shù)值接近0；該數(shù)值越大，就表示對象i和對象j越不相似。由于有d(i,j)=d(j,i)且d(i,i)=07.3.2聚類分析中的數(shù)據(jù)歐氏距離7.3.3層次方法層次的聚類方法可以分為凝聚的（agglomerative）和分裂的（divisive）層次聚類。一旦一個合并或分裂被執(zhí)行，就不能修正，因此一個純粹的層次聚類方法的聚類質(zhì)量受到了一定的限制。7.3.3層次方法

凝聚的層次聚類：首先將每個對象作為一族，然后合并這些原子簇為越來越大的簇，直到所有的對象都在一個簇中，或者某個終結(jié)條件被滿足。一般來說為最小距離法，即找出哪兩個事物距離最短。絕大多數(shù)層次聚類方法屬于這一類，它們只是在簇間相似度的定義上會有所不同。7.3.3層次方法

分裂的層次聚類：首先將所有對象作為一族，然后逐步分裂這個族中的點(diǎn)，直到所有的對象被分開到滿足某個終結(jié)條件。一般來說為最大距離法，即找出哪兩個事物距離最長。例為了研究遼寧等5省1991年城鎮(zhèn)居民生活消費(fèi)情況的分布規(guī)律，根據(jù)調(diào)查資料做類型分類，用最短距離做類間分類。數(shù)據(jù)如下：x1x2x3x4x5x6x7x8遼寧17.9039.778.4912.9419.2711.052.0413.29浙江27.6850.3711.3513.3019.2514.592.7514.87河南39.4227.938.208.1416.179.421.559.76甘肅49.1627.989.019.3215.999.101.8211.35青海510.0628.6410.5210.0516.188.391.9610.81將每一個省區(qū)視為一個樣本，先計算5個省區(qū)之間的歐式距離，用D0表示距離矩陣（對稱陣，故給出下三角陣）因此將3.4合并為一類，為類6，替代了3、4兩類類6與剩余的1、2、5之間的距離分別為：

d(3,4)1=min(d31,d41)=min(13.80,13.12)=13.12d(3,4)2=min(d32,d42)=min(24.63,24.06)=24.06d(3,4)5=min(d35,d45)=min(3.51,2.21)=2.21得到新矩陣合并類6和類5，得到新類7類7與剩余的1、2之間的距離分別為：

d(5,6)1=min(d51,d61)=min(12.80,13.12)=12.80d(5,6)2=min(d52,d62)=min(23.54,24.06)=23.54

得到新矩陣合并類1和類2，得到新類8此時，我們有兩個不同的類：類7和類8。它們的最近距離d(7,8)

=min(d71,d72)=min(12.80,23.54)=12.80得到矩陣最后合并為一個大類。這就是按最短距離定義類間距離的系統(tǒng)聚類方法。最長距離法類似！7.3.4劃分方法：K-meansn個對象或元組的數(shù)據(jù)庫，一個劃分方法構(gòu)建數(shù)據(jù)的k個劃分，每個劃分表示一個聚簇，并且k≤n。也就是說，它將數(shù)據(jù)劃分為k個組，同時滿足如下的要求：（a）每個組至少包含一個對象；（b）每個對象必須屬于且只屬于一個組。7.3.4劃分方法：K-meansK-means算法基本步驟:（1）從n個數(shù)據(jù)對象任意選擇k個對象作為初始聚類中心；（2）根據(jù)每個聚類對象的均值（中心對象），計算每個對象與這些中心對象的距離；并根據(jù)最小距離重新對相應(yīng)對象進(jìn)行劃分；（3）重新計算每個（有變化）聚類的均值（中心對象）；（4）計算標(biāo)準(zhǔn)測度函數(shù)，當(dāng)滿足一定條件，如函數(shù)收斂時，則算法終止；如果條件不滿足則回到步驟（2）。7.3.4劃分方法：K-means7.3.4劃分方法：K-means7.3.4劃分方法：K-means7.3.4劃分方法：K-means收斂聚類實例：中國男足在亞洲什么水平？亞洲15只球隊在2005-2010年間大型杯賽的戰(zhàn)績，其中包括兩次世界杯和一次亞洲杯。對數(shù)據(jù)做預(yù)處理：對于世界杯，進(jìn)入決賽圈則取其最終排名，沒有進(jìn)入決賽圈的，打入預(yù)選賽十強(qiáng)賽賦予40，預(yù)選賽小組未出線的賦予50。對于亞洲杯，前四名取其排名，八強(qiáng)賦予5，十六強(qiáng)賦予9，預(yù)選賽沒出現(xiàn)的予177.3.4劃分方法：K-means下面先對數(shù)據(jù)進(jìn)行[0,1]規(guī)格化，下面是規(guī)格化后的數(shù)據(jù)：

接著用k-means算法進(jìn)行聚類。設(shè)k=3，即將這15支球隊分成三個集團(tuán)?，F(xiàn)抽取日本、巴林和泰國的值作為三個簇的種子，即初始化三個簇的中心為A：{0.3,

0,

0.19}，B：{0.7,

0.76,

0.5}和C：{1,

1,

0.5}。下面，計算所有球隊分別對三個中心點(diǎn)的相異度，這里以歐氏距離度量。下面是用程序求取的結(jié)果：

從做到右依次表示各支球隊到當(dāng)前中心點(diǎn)的歐氏距離，將每支球隊分到最近的簇，可對各支球隊做如下聚類：中國C，日本A，韓國A，伊朗A，沙特A，伊拉克C，卡塔爾C，阿聯(lián)酋C，烏茲別克斯坦B，泰國C，越南C，阿曼C，巴林B，朝鮮B印尼C。日本巴林泰國

聚類習(xí)題（劃分方法）Oxy102