數(shù)據(jù)倉庫與數(shù)據(jù)挖掘第七講聚類蒲飛QQ:1150636618實(shí)驗(yàn)回顧正負(fù)樣本失衡的解決方法有哪幾種？抽樣法和擴(kuò)大法在上次實(shí)驗(yàn)中，通過用抽樣法和擴(kuò)大法處理正負(fù)樣本失衡的比較數(shù)據(jù)，可以得到的結(jié)論：對給定的案例，抽樣法還是擴(kuò)大法好？抽樣法和擴(kuò)大法的優(yōu)缺點(diǎn)是什么？

分類法抽樣法

擴(kuò)大法總正確率正確率召回率總正確率正確率召回率決策樹68.44%66.60%74.00%97.18%94.67%100%樸素貝葉斯64.00%63.79%64.78%63.11%63.00%63.50%神經(jīng)網(wǎng)絡(luò)66.44%66.23%67.11%82.16%80.76%84.43%支持向量機(jī)61.22%64.07%51.11%76.89%73.66%83.72%ROC曲線采用抽樣法，比較決策樹、樸素貝葉斯、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)模型的ROC曲線ROC曲線采用擴(kuò)大法，比較決策樹、樸素貝葉斯、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)模型的ROC曲線R畫的ROC曲線決策樹、Bagging的ROC曲線R畫的ROC曲線Boosting的ROC曲線分類和聚類Classification:Supervisedlearning---Learnsamethodforpredictingtheinstanceclassfrompre-labeled(classified)instances.分類和聚類Clustering:Unsupervised

learning--Finds“natural”groupingofinstancesgivenun-labeleddata聚類(Clustering)聚類分析將數(shù)據(jù)劃分成有意義或有用的組（簇）。聚類分析僅根據(jù)在數(shù)據(jù)中發(fā)現(xiàn)的描述對象及其關(guān)系的信息，將數(shù)據(jù)對象分組。其目標(biāo)是，組內(nèi)的對象相互之間是相似的，而不同組中的對象是不同的。聚類是無指導(dǎo)的分類:沒有預(yù)先定義的類。組間的距離最大組內(nèi)的距離最小什么是好的聚類方法?一個(gè)好的聚類方法應(yīng)當(dāng)產(chǎn)生高質(zhì)量的聚類類內(nèi)相似性高類間相似性低聚類結(jié)果的質(zhì)量依賴于方法所使用的相似性度量和它的實(shí)現(xiàn).聚類方法的質(zhì)量也用它發(fā)現(xiàn)某些或全部隱藏的模式的能力來度量數(shù)據(jù)挖掘?qū)垲惖囊?/p>

可伸縮性有的算法當(dāng)數(shù)據(jù)對象少于2000時(shí)處理很好,但對大量數(shù)據(jù)對象偏差較大大型數(shù)據(jù)庫包含數(shù)百萬個(gè)對象處理不同屬性類型的能力許多算法專門用于數(shù)值類型的數(shù)據(jù)實(shí)際應(yīng)用涉及不同的數(shù)據(jù)類型,i.e.混合了數(shù)值和分類數(shù)據(jù)發(fā)現(xiàn)任意形狀的聚類基于距離的聚類趨向于發(fā)現(xiàn)具有相近尺度和密度的球狀簇一個(gè)簇可能是任意形狀的數(shù)據(jù)挖掘?qū)垲惖囊?/p>

用于決定輸入?yún)?shù)的領(lǐng)域知識最小化許多聚類算法要求用戶輸入一定的參數(shù),如希望產(chǎn)生的簇的數(shù)目.聚類結(jié)果對于輸入?yún)?shù)十分敏感參數(shù)難以確定,增加了用戶的負(fù)擔(dān),使聚類質(zhì)量難以控制處理噪聲數(shù)據(jù)和孤立點(diǎn)的能力一些聚類算法對于噪音數(shù)據(jù)敏感,可能導(dǎo)致低質(zhì)量的聚類結(jié)果現(xiàn)實(shí)世界中的數(shù)據(jù)庫大都包含了孤立點(diǎn),空缺,或者錯(cuò)誤的數(shù)據(jù)對于輸入記錄的順序不敏感一些聚類算法對于輸入數(shù)據(jù)的順序是敏感的,以不同的次序輸入會導(dǎo)致不同的聚類數(shù)據(jù)挖掘?qū)垲惖囊蟾呔S性（highdimensionality）許多聚類算法擅長處理低維的數(shù)據(jù),可能只涉及兩到三維數(shù)據(jù)庫或者數(shù)據(jù)倉庫可能包含若干維或者屬性,數(shù)據(jù)可能非常稀疏,而且高度偏斜整合用戶指定的約束現(xiàn)實(shí)世界的應(yīng)用可能需要在各種約束條件下進(jìn)行聚類要找到既滿足特定的約束,又具有良好聚類特性的數(shù)據(jù)分組是一項(xiàng)具有挑戰(zhàn)性的任務(wù)可解釋性和可用性用戶希望聚類結(jié)果是可解釋的,可理解的,和可用的聚類可能需要和特定的語義解釋和應(yīng)用相聯(lián)系聚類的復(fù)雜性Howmanyclusters?FourClustersTwoClustersSixClusters聚類分析的內(nèi)容特征的提取模式相似性度量點(diǎn)與類間的距離類與類間的距離聚類準(zhǔn)則聚類算法聚類有效性分析距離

距離的定義

幾種常見的距離

幾種常見的距離

R中的距離函數(shù)R中dist()函數(shù)給出了各種距離的計(jì)算，其使用格式為dist(x,method=“euclidean”,diag=FALSE,upper=FALSE,p=2)其中x是樣本矩陣或數(shù)據(jù)框,method表示計(jì)算距離的方法，缺省為Euclide距離，所定義的距離有“euclidean”---歐式距離“maximum”---切比雪夫距離“manhattan”---絕對值距離“canberra”---Lance和Williams距離“minkowski”---明可夫斯基距離Diag是邏輯變量，diag=TRUE時(shí)，給出對角線上距離。Upper是邏輯變量，當(dāng)upper=TRUE時(shí)，給出上三角矩陣的值(缺省給出下三角矩陣的值)。數(shù)據(jù)中心化與標(biāo)準(zhǔn)化變換

R中scale()函數(shù)在R語言中可用scale()函數(shù)作數(shù)據(jù)的中心化或標(biāo)準(zhǔn)化，其使用格式是scale(x,center=TRUE,scale=TRUE）其中x是樣本構(gòu)成的數(shù)據(jù)矩陣，center是邏輯變量,TRUE表示對數(shù)據(jù)作中心化變換,FALSE表示不做變換，scale是邏輯變量，TRUE表示對數(shù)據(jù)作標(biāo)準(zhǔn)化變換,FALSE表示不做變換。極差標(biāo)準(zhǔn)化變換

相似度/相似系數(shù)

夾角余弦

相關(guān)系數(shù)

二元變量的距離度量（匹配測度）二元變量(binaryvariable)只有兩個(gè)狀態(tài)0或1.0表示該變量為空,1表示該變量存在例如,描述病人的變量smoker,1表示病人抽煙,而0表示病人不抽煙計(jì)算二元變量的距離，假定所有二元變量具有相同的權(quán)重,則得到一個(gè)兩行兩列的可能性表(contingencytable)對象i對象jq是對象i和j值都為1時(shí)變量的數(shù)目r是在對象i中值為1，在對象j中值為0時(shí)變量的數(shù)目s是在對象i中值為0，在對象j中值為1時(shí)變量的數(shù)目t是在對象i和j中值都為0時(shí)變量的數(shù)目變量的總數(shù)p是q+r+s+t二元變量的相似度

二元變量

二元變量之間的相異度例gender是對稱的其余都不是對稱的Y和P的值設(shè)置為1,而N的值設(shè)置為0NominalVariables(標(biāo)稱變量)距離度量標(biāo)稱變量是二元變量的推廣，它可以具有多于兩個(gè)的狀態(tài)值。例如，map_color是一個(gè)標(biāo)稱變量，它可能有五個(gè)值：紅色,黃色，綠色，粉紅色，和藍(lán)色。

假設(shè)一個(gè)標(biāo)稱變量的狀態(tài)數(shù)目是M。這些狀態(tài)可以用字母，符號，或者一組整數(shù)（如1，2，…,M）來表示。

兩個(gè)變量i和j之間的相異度可以用簡單匹配方法來計(jì)算：

其中m是匹配的數(shù)目，即i和j取值相同的變量的數(shù)目；而p是全部變量的數(shù)目。NominalVariables（標(biāo)稱變量）序數(shù)型變量(ordinalvariable)可以是離散的,也可以是連續(xù)的離散的序數(shù)型變量類似于標(biāo)稱變量,但序數(shù)型變量的M個(gè)狀態(tài)是以有意義的序列排序連續(xù)的序數(shù)型變量看起來像一個(gè)未知刻度的連續(xù)數(shù)據(jù)的集合.值的相對順序是必要的,而其實(shí)際的大小則不重要將區(qū)間標(biāo)度變量的值域劃分為有限個(gè)區(qū)間,從而將其值離散化,也可以得到序數(shù)型變量序數(shù)型變量的值可以映射為秩(rank).例如,假設(shè)變量f有Mf個(gè)狀態(tài),這些有序的狀態(tài)定義了一個(gè)排列1,…,Mf

NominalVariables（標(biāo)稱變量）相異度計(jì)算可以用類似于區(qū)間標(biāo)度變量的方法處理設(shè)第i個(gè)對象f的值為

xif

,用對應(yīng)的秩rif

替代xif,其中rif

∈{1,…,Mf

}將每個(gè)變量的值域映射到[0,1]區(qū)間,以便每個(gè)變量都具有相同的權(quán)重:用下式替換rif

使用區(qū)間標(biāo)度變量計(jì)算距離的方法計(jì)算相異度,zif作為第i個(gè)對象f的值Ratio-ScaledVariables（比例標(biāo)度變量）

比例標(biāo)度變量非線性的刻度上取正的度量值，例如指數(shù)標(biāo)度，近似地遵循如下的公式

AeBt

或Ae-Bt相異度計(jì)算:采用與處理區(qū)間標(biāo)度變量同樣的方法—不是好的選擇!(為什么?—標(biāo)度可能被扭曲)進(jìn)行對數(shù)變換

yif=log(xif)將xif看作連續(xù)的序數(shù)型數(shù)據(jù),將其秩作為區(qū)間標(biāo)度值方法的選取取決于應(yīng)用,但后兩種方法比較有效如何定義類間的距離距離函數(shù)都是關(guān)于兩個(gè)樣本的距離刻畫，然而在聚類應(yīng)用中，最基本的方法是計(jì)算類間的距離四個(gè)廣泛采用的類間距離度量方法

最小距離：dmin(Ci,Cj)=min

p∈Ci,p’∈Cj

|p-p’|

最大距離：dmax(Ci,Cj)=max

p∈Ci,p’∈Cj|p-p’|

平均值的距離：dmean(Ci,Cj)=|mi-mj|

平均距離：davg(Ci,Cj)=∑p∈Ci∑p’∈Cj|p-p’|

/ninj其中,|p-p’|是兩個(gè)對象p和p’之間的距離

mi是簇Ci

的平均值，ni是簇Ci中對象的數(shù)目

如何定義類間的距離最小距離：dmin(Ci,Cj)=min

p∈Ci,p’∈Cj

|p-p’|

如何定義類間的距離最大距離：dmax(Ci,Cj)=max

p∈Ci,p’∈Cj|p-p’|

如何定義類間的距離

如何定義類間的距離平均值的距離：dmean(Ci,Cj)=|mi-mj|

離差平方和法(Ward法)

主要的聚類算法劃分方法（PartitioningMethods）層次方法（HierarchicalMethods）基于密度的方法（Density-BasedMethods）基于網(wǎng)格的方法（Grid-BasedMethods）基于模型的聚類方法（Model-BasedClusteringMethods）孤立點(diǎn)分析（OutlierAnalysis）層次聚類(HierarchicalClustering)層次聚類是聚類分析中用得最多的一種，其基本思想是：開始將n個(gè)樣本各自作為一類，并規(guī)定樣本之間的距離和類與類之間的距離，然后將距離最近的兩類合并成一個(gè)新類，計(jì)算新類與其它類的距離。重復(fù)進(jìn)行兩個(gè)最近類的合并，每次減少一個(gè)類，直到所有的樣本合并為一類。基于層次的聚類層次聚類按數(shù)據(jù)分層建立簇，形成一棵以簇為節(jié)點(diǎn)的樹，稱為聚類圖。

按自底向上層次分解，則稱為凝聚的層次聚類。

按自頂向下層次分解，就稱為分裂的層次聚類。

凝聚的和分裂的層次聚類

凝聚的層次聚類采用自底向上的策略，開始時(shí)把每個(gè)對象作為一個(gè)單獨(dú)的簇，然后逐次對各個(gè)簇進(jìn)行適當(dāng)合并，直到滿足某個(gè)終止條件。

分裂的層次聚類采用自頂向下的策略，與凝聚的層次聚類相反，開始時(shí)將所有對象置于同一個(gè)簇中，然后逐次將簇分裂為更小的簇，直到滿足某個(gè)終止條件。傳統(tǒng)的算法利用相似性或相異性的臨近度矩陣進(jìn)行凝聚的或分裂的層次聚類。凝聚的和分裂的層次聚類

Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)基本凝聚層次聚類方法凝聚層次聚類算法計(jì)算鄰近度矩陣讓每個(gè)點(diǎn)作為一個(gè)clusterRepeat合并最近的兩個(gè)類更新鄰近度矩陣，以反映新的簇與原來的簇之間的鄰近性Until僅剩下一個(gè)簇關(guān)鍵的操作是兩個(gè)聚類的距離計(jì)算不同距離的定義區(qū)分了各種不同的凝聚層次技術(shù)起始步驟開始時(shí)，每個(gè)樣本點(diǎn)為一個(gè)類，給定一個(gè)距離矩陣p1p3p5p4p2p1p2p3p4p5...ProximityMatrix中間步驟經(jīng)過部分融合之后，我們得到一些簇C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5ProximityMatrix中間步驟我們希望合并兩個(gè)最鄰近的簇(C2andC5)并更新鄰近度矩陣C2C1C1C3C5C4C2C3C4C5ProximityMatrixC1C4C2C5C3最終合并如何更新鄰近度矩陣？C1C4C2UC5C3???? ???C2UC5C1C1C3C4C2UC5C3C4ProximityMatrixR語言中的層次聚類R語言中，hclust()函數(shù)提供了層次聚類的計(jì)算，plot()函數(shù)刻畫出聚類的譜系圖(dendrogram)。hclust()的使用格式為：hclust(d,method=“complete”,members=NULL)其中d是有“dist”構(gòu)成的距離結(jié)構(gòu)，method是層次聚類的方法，缺省是最長距離法，其參數(shù)有：“single”---最短距離法“complete”---最長距離法“centroid”---重心法“ward”---離差平均法R語言中的層次聚類plot()函數(shù)畫譜系圖的格式為plot(x,labels=NULL,hang=0.1,aes=TRUE,frame.plot=FALSE,ann=TRUE,main=“ClusterDendrogram”,sub=NULL,xlab=NULL,ylab=“Height”,…)其中x是由hclust()生成的對象，hang表明譜系圖中各類所在的位置，當(dāng)hang取負(fù)值時(shí)，譜系圖中的類從底部畫起。例子1999年全國31個(gè)省份城市城鎮(zhèn)居民平均每人全年消費(fèi)性支出用8個(gè)主要指標(biāo)分析。其中：X1---食品，X2---衣服，X3---家庭用品，X4---醫(yī)療保健，X5---交通和通訊，X6---娛樂、教育和文化，X7---居住，X8---其它商品和服務(wù)?，F(xiàn)分別用最長距離法、類平均法、重心法和WARD法對31個(gè)省份聚類，分析它們的消費(fèi)結(jié)構(gòu)特點(diǎn)。數(shù)據(jù)表如圖：

#用數(shù)據(jù)框形式輸入數(shù)據(jù)X<-data.frame(x1=c(2959.19,2459.77,1495.63,1046.33,1303.97,1730.84,1561.86,1410.11,3712.31,2207.58,2629.16,1844.78,2709.46,1563.78,1675.75,1427.65,1783.43,1942.23,3055.17,2033.87,2057.86,2303.29,1974.28,1673.82,2194.25,2646.61,1472.95,1525.57,1654.69,1375.46,1608.82),x2=c(730.79,495.47,515.90,477.77,524.29,553.90,492.42,510.71,550.74,449.37,557.32,430.29,428.11,303.65,613.32,431.79,511.88,512.27,353.23,300.82,186.44,589.99,507.76,437.75,537.01,839.70,390.89,472.98,437.77,480.99,536.05),例子x3=c(749.41,697.33,362.37,290.15,254.83,246.91,200.49,211.88,893.37,572.40,689.73,271.28,334.12,233.81,550.71,288.55,282.84,401.39,564.56,338.65,202.72,516.21,344.79,461.61,369.07,204.44,447.95,328.90,258.78,273.84,432.46),x4=c(513.34,302.87,285.32,208.57,192.17,279.81,218.36,277.11,346.93,211.92,435.69,126.33,160.77,107.90,219.79,208.14,201.01,206.06,356.27,157.78,171.79,236.55,203.21,153.32,249.54,209.11,259.51,219.86,303.00,317.32,235.82),x5=c(467.87,284.19,272.95,201.50,249.81,239.18,220.69,224.65,527.00,302.09,514.66,250.56,405.14,209.70,272.59,217.00,237.60,321.29,811.88,329.06,329.65,403.92,240.24,254.66,290.84,379.30,230.61,206.65,244.93,251.08,250.28),

例子x6=c(1141.82,735.97,540.58,414.72,463.09,445.20,459.62,376.82,1034.98,585.23,795.87,513.18,461.67,393.99,599.43,337.76,617.74,697.22,873.06,621.74,477.17,730.05,575.10,445.59,561.91,371.04,490.90,449.69,479.53,424.75,541.30),x7=c(478.42,570.84,364.91,281.84,287.87,330.24,360.48,317.61,720.33,429.77,575.76,314.00,535.13,509.39,371.62,421.31,523.52,492.60,1082.82,587.02,312.93,438.41,430.36,346.11,407.70,269.59,469.10,249.66,288.56,228.73,344.85),x8=c(457.64,305.08,188.63,212.10,192.96,163.86,147.76,152.85,462.03,252.54,323.36,151.39,232.29,160.12,211.84,165.32,182.52,226.45,420.81,218.27,279.19,225.80,223.46,191.48,330.95,389.33,191.34,228.19,236.51,195.93,214.40),

s=c("北京","天津","河北","山西","內(nèi)蒙古","遼寧","吉林","黑龍江","上海","江蘇","浙江","安徽","福建","江西","山東","河南","湖北","湖南","廣東","廣西","海南","重慶","四川","貴州","云南","西藏","陜西","甘肅","青海","寧夏","新疆"))#生成距離結(jié)構(gòu)，進(jìn)行系統(tǒng)聚類Province<-dist(scale(X))#scale(x)表示對x做標(biāo)準(zhǔn)化處理，使X的各個(gè)分量可以進(jìn)行比較hc1<-hclust(Province,"complete")plete表示類之間最長距離法hc2<-hclust(Province,"average")#average表示類之間平均距離法hc3<-hclust(Province,"centroid")#centroid表示類之間重心距離法hc4<-hclust(Province,"ward")#ward表示類之間離差平方和距離法opar<-par(mfrow=c(2,1),mar=c(5,4,1,2))#par()用于在一個(gè)設(shè)備上輸出多個(gè)圖形#mar參數(shù)給出整個(gè)圖的邊界距離#mfrow=c(2,1)分割圖層成2行1個(gè)列表示plot(hc1,hang=-1)re1<-rect.hclust(hc1,k=5,border="red")#指定聚成5類plot(hc2,hang=-1)re2<-rect.hclust(hc2,k=5,border="red")plot(hc3,hang=-1)re3<-rect.hclust(hc3,k=5,border="red")#指定聚成5類plot(hc4,hang=-1)re4<-rect.hclust(hc4,k=5,border="red")par(opar)基于劃分的方法劃分方法(Partitioningmethod):給定一個(gè)有n個(gè)對象的數(shù)據(jù)集，劃分聚類技術(shù)將構(gòu)造數(shù)據(jù)的k個(gè)劃分，每一個(gè)劃分就代表一個(gè)簇，k

n。也就是說，它將數(shù)據(jù)劃分為k個(gè)簇，而且這k個(gè)劃分滿足下列條件：每一個(gè)簇至少包含一個(gè)對象。每一個(gè)對象屬于且僅屬于一個(gè)簇。好的劃分的一般準(zhǔn)則:在同一個(gè)類中的對象之間盡可能“接近”或相關(guān),而不同類中的對象之間盡可能“遠(yuǎn)離”或不同

劃分方法全局最優(yōu):窮舉所有可能的劃分啟發(fā)式方法:k-平均值(k-

means)和k-中心點(diǎn)(k-

medoids)算法k-平均值(MacQueen’67):每個(gè)簇用該簇中對象的平均值來表示k-中心點(diǎn)或PAM(partitionaroundmedoids)(Kaufman&Rousseeuw’87):每個(gè)簇用接近聚類中心的一個(gè)對象來表示這些啟發(fā)式算法適合發(fā)現(xiàn)中小規(guī)模數(shù)據(jù)集中的球狀聚類。對于大規(guī)模數(shù)據(jù)集和處理任意形狀的聚類,這些算法需要進(jìn)一步擴(kuò)展。k-平均值聚類算法

算法：k-平均(1)任意選擇k個(gè)對象作為初始的簇中心；(2)repeat(3) 根據(jù)簇中對象的平均值,將每個(gè)對象(重新)賦給最類似的簇；(4) 更新簇的平均值,即重新計(jì)算每個(gè)簇中對象的平均值；(5)until不再發(fā)生變化通常,采用平方誤差準(zhǔn)則作為收斂函數(shù),其定義如下其中,mi是簇Ci的平均值該準(zhǔn)則試圖使生成的結(jié)果簇盡可能緊湊,獨(dú)立

k1k2k3XY隨機(jī)選擇三個(gè)點(diǎn)作為簇的初始中心

k1k2k3XY將每個(gè)點(diǎn)分配到離它最近的簇中心點(diǎn)的簇中

XY重新將簇的中心點(diǎn)選為簇的平均點(diǎn)k1k2k2k1k3k3

XY重新將點(diǎn)各自聚類到離它最近的簇中心的簇中Q:Whichpointsarereassigned?k1k2k3

XY三個(gè)點(diǎn)重新分配k1k3k2

XY重新計(jì)算簇的均值k1k3k2

XY將簇中心點(diǎn)移到新的簇均值點(diǎn)上k2k1k3

把14個(gè)人分成3組只有一個(gè)屬性：年齡初始的centroids是1、20、40右邊的表是完成步驟1、2后的結(jié)果彩色的列表示各個(gè)簇中的點(diǎn)離中心點(diǎn)的最短距離ClusterC1C2C3CentroidValue12040P1101939P2321737P3541535P4871232P5981131P61110929P71211828P81312727P93736173P104342233P114544255P124948299P1351503111P1465644525age

重新計(jì)算centroid，得到5,12,和48重新計(jì)算每個(gè)實(shí)例與3個(gè)Cluster的距離P5更接近C2需要重新計(jì)算C1和C2的centroid，C3沒有變化不需要重新計(jì)算ClusterC1C2C3CentroidValue51248P1141147P232945P350743P483440P594339P6116137P7127036P8138135P937322511P104338315P114540333P124944371P135146393P1465605317age

3個(gè)Cluster的centroid是4,11,和48計(jì)算每個(gè)實(shí)例到Cluster的距離P4更接近C2需要重新計(jì)算C1和C2的centroid，C3沒有變化不需要重新計(jì)算ClusterC1C2C3CentroidValue41148P1131047P231845P351643P484340P595239P6117037P7128136P8139235P937332611P104339325P114541343P124945381P135147403P1465615417ageTheK-MeansAlgorithm–舉例3個(gè)Cluster的centroid是3,10和48計(jì)算每個(gè)實(shí)例到Cluster的距離沒有任何變化算法不再迭代ClusterC1C2C3CentroidValue31048P112947P230745P352543P485240P596139P6118137P7129236P81310335P937342711P104340335P114542353P124946391P135148413P1465625517age討論

k-平均值方法的變種

52055k-中心點(diǎn)聚類方法k-平均值算法對孤立點(diǎn)很敏感!因?yàn)榫哂刑貏e大的值的對象可能顯著地影響數(shù)據(jù)的分布.k-中心點(diǎn)(k-Medoids):不采用簇中對象的平均值作為參照點(diǎn),而是選用簇中位置最中心的對象,即中心點(diǎn)(medoid)作為參照點(diǎn).012345678910012345678910012345678910012345678910k-中心點(diǎn)聚類方法找聚類中的代表對象(中心點(diǎn))PAM(PartitioningAroundMedoids,1987)首先為每個(gè)簇隨意選擇選擇一個(gè)代表對象,剩余的對象根據(jù)其與代表對象的距離分配給最近的一個(gè)簇;然后反復(fù)地用非代表對象來替代代表對象，以改進(jìn)聚類的質(zhì)量

PAM

對于較小的數(shù)據(jù)集非常有效,但不能很好地?cái)U(kuò)展到大型數(shù)據(jù)集k-中心點(diǎn)聚類方法基本思想：首先為每個(gè)簇隨意選擇選擇一個(gè)代表對象;剩余的對象根據(jù)其與代表對象的距離分配給最近的一個(gè)簇然后反復(fù)地用非代表對象來替代代表對象,以改進(jìn)聚類的質(zhì)量聚類結(jié)果的質(zhì)量用一個(gè)代價(jià)函數(shù)來估算,該函數(shù)評估了對象與其參照對象之間的平均相異度為了判定一個(gè)非代表對象Orandom是否是當(dāng)前一個(gè)代表對象Oj的好的替代,對于每一個(gè)非代表對象p,考慮下面的四種情況：

第一種情況：p當(dāng)前隸屬于代表對象Oj.如果Oj被Orandom所代替,且p離Oi最近,i≠j,那么p被重新分配給Oi

第二種情況：p當(dāng)前隸屬于代表對象Oj.如果Oj被Orandom代替,且p離Orandom最近,