模式識別非監(jiān)督學(xué)習(xí)方法聚類分析

模式識別非監(jiān)督學(xué)習(xí)方法聚類分析第1頁，課件共55頁，創(chuàng)作于2023年2月§1.1基本概念分類與聚類的區(qū)別分類：用已知類別的樣本訓(xùn)練集來設(shè)計分類器（監(jiān)督學(xué)習(xí)）聚類（集群）：用事先不知樣本的類別，而利用樣本的先驗知識來構(gòu)造分類器（無監(jiān)督學(xué)習(xí)）舉例：小孩區(qū)分桔子和蘋果第2頁，課件共55頁，創(chuàng)作于2023年2月相似性與距離聚類相似性：模式之間具有一定的相似性，這既表現(xiàn)在實物的顯著特征上，也表現(xiàn)在經(jīng)過抽象以后特征空間內(nèi)的特征向量的分布狀態(tài)上。聚類分析定義：對一批沒有標(biāo)出類別的模式樣本集，按照樣本之間的相似程度分類，相似的歸為一類，不相似的歸為另一類，這種分類稱為聚類分析，也稱為無監(jiān)督分類。模式識別高性價比安卓智能手機排行榜_熱門促銷智能手機推薦第3頁，課件共55頁，創(chuàng)作于2023年2月分類依據(jù)：一個樣本的特征向量相當(dāng)于特征空間中的一點，整個模式樣本集合的特征向量可以看成特征空間的一些點，點之間的距離函數(shù)可以作為模式相似性的度量，并以此作為模式的分類依據(jù)。聚類分析是按不同對象之間的差異，根據(jù)距離函數(shù)的規(guī)律進(jìn)行模式分類的。距離函數(shù)的定義特征向量的特性

第4頁，課件共55頁，創(chuàng)作于2023年2月聚類分析的有效性：聚類分析方法是否有效，與模式特征向量的分布形式有很大關(guān)系。若向量點的分布是一群一群的，同一群樣本密集（距離很近），不同群樣本距離很遠(yuǎn)，則很容易聚類；若樣本集的向量分布聚成一團，不同群的樣本混在一起，則很難分類；對具體對象做聚類分析的關(guān)鍵是選取合適的特征。特征選取得好，向量分布容易區(qū)分，選取得不好，向量分布很難分開。第5頁，課件共55頁，創(chuàng)作于2023年2月特征空間維數(shù)特征信息的冗余性：在對象分析和特征提取中，往往會提取一些多余的特征，以期增加對象識別的信息量。高維特征空間分析的復(fù)雜性：特征空間維數(shù)越高，聚類分析的復(fù)雜性就越高高維特征空間降維降維方法：相關(guān)分析：特征向量的相關(guān)矩陣R，分析相關(guān)性主成分分析：以正交變換為理論基礎(chǔ)獨立成分分析：以獨立性為基礎(chǔ)第6頁，課件共55頁，創(chuàng)作于2023年2月特征的表示數(shù)值表示：對于實際問題，為了便于計算機分析和計算，特征必須進(jìn)行量化。對不同的分析對象，量化方法是不一樣的。連續(xù)量的量化：用連續(xù)量來度量的特征，只需取其量化值，如長度、重量等。分級量的量化：度量分析對象等級的量，用有序的離散數(shù)字進(jìn)行量化，比如學(xué)生成績的優(yōu)，良，中，差可用1，2，3，4等量化表示。定性量的量化：定性指標(biāo)，沒有數(shù)量關(guān)系，也沒有次序要求。比如，性別特征：男和女，可用0和1來進(jìn)行表示。第7頁，課件共55頁，創(chuàng)作于2023年2月兩類模式分類的實例區(qū)分一攤黑白圍棋子選顏色作為特征進(jìn)行分類，用“1”代表白，“0”代表黑，則很容易分類；選大小作為特征進(jìn)行分類，則白子和黑子的特征相同，不能分類。第8頁，課件共55頁，創(chuàng)作于2023年2月§1.2相似性測度和聚類準(zhǔn)則

一、相似性的測度歐氏距離:

表征兩個模式樣本在特征空間中的Euclid距離，模式X和Z間的距離愈小，則愈相似注意：X和Z的量綱必須一致

消除量綱不一致對聚類的影響：特征數(shù)據(jù)的正則化（也稱標(biāo)準(zhǔn)化、歸一化），使特征變量與量綱無關(guān)。第9頁，課件共55頁，創(chuàng)作于2023年2月馬氏距離：表征模式向量X與其均值向量m之間的距離平方，C是模式總體的協(xié)方差矩陣，引入?yún)f(xié)方差矩陣，排除了樣本之間的相關(guān)性。歐式距離中，如果特征向量中某一分量的值非常大，那么就會掩蓋值小的項所起到的作用，這是歐式距離的不足；當(dāng)采用馬氏距離，就可以屏蔽這一點。因為相關(guān)性強的一個分量，對應(yīng)于協(xié)方差矩陣C中對角線上的那一項的值就會大一些。再將這一項取倒數(shù)，減小該影響。當(dāng)協(xié)方差為對角矩陣時，各特征分量相互獨立；當(dāng)協(xié)方差為單位矩陣時，馬氏距離和歐氏距離相同。第10頁，課件共55頁，創(chuàng)作于2023年2月其中分別是樣本向量的第k個分量；當(dāng)m＝2時，明氏距離就是歐氏距離；當(dāng)m＝1時，就是街坊（cityblock)距離：

一般化的明氏距離第11頁，課件共55頁，創(chuàng)作于2023年2月角度相似性函數(shù)：表征了模式向量x和z之間夾角的余弦，反映了幾何上的相似性，當(dāng)坐標(biāo)系旋轉(zhuǎn)或者尺度變換，夾角余弦測度均保持不變（對位移和線性變換不成立）如果x和z的分量用二值來表示，0表示不具有某種特征，1表示具有某種特征，則夾角余弦測度表示x和z具有共有特征數(shù)目的相似性測度。第12頁，課件共55頁，創(chuàng)作于2023年2月二、聚類準(zhǔn)則的確定

試探法

憑直觀和經(jīng)驗，針對實際問題選擇相似性測度并確定此相似性測度的閾值，然后選擇一定的訓(xùn)練樣本來檢驗測度和閾值的可靠程度，最后按最近鄰規(guī)則指定某些模式樣本屬于某一個聚類類別。舉例：對于歐氏距離，它反映了樣本間的近鄰性，但將一個樣本分到不同類別時，還必須規(guī)定一距離測度的閾值準(zhǔn)則作為聚類的判別準(zhǔn)則第13頁，課件共55頁，創(chuàng)作于2023年2月

聚類準(zhǔn)則函數(shù)法

聚類就是將樣本進(jìn)行組合分類以使類別可分性為最大，因此聚類準(zhǔn)則應(yīng)是反映類別間相似性（或可分性）的函數(shù)；同時，類別又由一個個樣本組成，因此類別的可分性與樣本間的差異性直接相關(guān)?；诖?，聚類準(zhǔn)則函數(shù)J，應(yīng)是模式樣本集{x}和模式類別{Sj,j=1,2,…,c}的函數(shù)，即第14頁，課件共55頁，創(chuàng)作于2023年2月J代表了分屬于c個聚類類別的全部模式樣本與其對應(yīng)類別模式均值之間的誤差平方和；對于不同的聚類形式，J值是不同的，聚類的目的是：使J值達(dá)到極??；由此可見：聚類分析轉(zhuǎn)化為尋找準(zhǔn)則函數(shù)極值的最優(yōu)化問題；此種聚類方法通常稱為最小方差劃分，適用于各類樣本密集且數(shù)目相差不多，而不同類間的樣本又明顯分開的情況（圖例解釋）—把握類內(nèi)距離與類間距離的問題；聚類準(zhǔn)則函數(shù)有許多其他形式。第15頁，課件共55頁，創(chuàng)作于2023年2月§1.3基于試探的聚類搜索算法一、按最鄰近規(guī)則的簡單試探法

給N個待分類的模式樣本，要求按距離閾值T分類到聚類中心算法過程：Step1：取任意的樣本xi作為一聚類中的初始值，如令z1=x1，計算若D21＞T，確定一新的聚類中心z2=x2否則x2∈以z1為中心的聚類；第16頁，課件共55頁，創(chuàng)作于2023年2月Step2：假如已有聚類中心z1和z2，計算若D31＞T和D32＞T，則確定一新的聚類中心z3=x3；Stepi：………第17頁，課件共55頁，創(chuàng)作于2023年2月討論這種方法的優(yōu)點：計算簡單，若模式樣本的集合分布的先驗知識已知，則可獲得較好的聚類結(jié)果。在實際中，對于高維模式樣本很難獲得準(zhǔn)確的先驗知識，因此只能選用不同的閾值和起始點來試探，并對結(jié)果進(jìn)行驗證。這種方法在很大程度上依賴于以下因素：第一個聚類中心的位置（初始化問題）待分類模式樣本排列次序（聚類樣本的選擇問題）距離閾值T的大?。ㄅ袥Q準(zhǔn)則問題）樣本分布的幾何性質(zhì)（樣本的固有特性問題）第18頁，課件共55頁，創(chuàng)作于2023年2月二、最大最小距離算法基本思想：根據(jù)實際問題選擇距離函數(shù)，以試探類間距離為最大作為預(yù)選出聚類中心的條件。核心就是：最大類間距離，最小類內(nèi)距離。算法過程描述：先按照距離最大最小的方法預(yù)選出聚類中心，在按照按最鄰近規(guī)則將模式分類到聚類中心。對于N個待分類的模式樣本，要求按最大最小距離法分類到聚類中心。Step1：選任意一模式樣本xi作為第一聚類中心z1第19頁，課件共55頁，創(chuàng)作于2023年2月Step2：選離z1最遠(yuǎn)距離的樣本xj作為第二聚類中心z2Step3：逐個計算各模式樣本與之間的距離，并選出其中的最小距離。Step4：在所有模式樣本的最小值中選出最大距離，若該最大值達(dá)到的一定分?jǐn)?shù)比值以上，則將相應(yīng)的樣本取為第三聚類中心。Stepi：………算法性能分析：算法復(fù)雜度增加，在選聚類中心過程中消耗較大的資源。第20頁，課件共55頁，創(chuàng)作于2023年2月§1.4系統(tǒng)聚類系統(tǒng)聚類：先把每個樣本作為一類，然后根據(jù)它們間的相似性或相鄰性聚合，類別由多到少，直到獲得合適的分類要求為止；相似性、相鄰性用距離表示。聚合的關(guān)鍵就是每次迭代中形成的聚類之間以及它們和樣本之間距離的計算，不同的距離函數(shù)會得到不同結(jié)果。兩類間距離計算準(zhǔn)則：(注意理解）1.最短距離：兩類中相距最近的兩樣本間的距離第21頁，課件共55頁，創(chuàng)作于2023年2月

2.最長距離：兩類中相距最遠(yuǎn)的兩個樣本間的距離。3.中間距離：最短距離和最長距離都有片面性，因此有時用中間距離。設(shè)ω1類和ω23類間的最短距離為d12，最長距離為d13，ω

23類的長度為d23，則中間距離為：上式推廣為一般情況：第22頁，課件共55頁，創(chuàng)作于2023年2月4.重心距離：均值間的距離5.類平均距離：兩類中各個元素兩兩之間的距離平方相加后取平均值第23頁，課件共55頁，創(chuàng)作于2023年2月6.離差平方和：設(shè)N個樣本原分q類，則定義第i類的離差平方和為：離差平方和增量：設(shè)樣本已分成ωp,ωq兩類，若把ωp,ωq合為ωr類，則定義離差平方增量：第24頁，課件共55頁，創(chuàng)作于2023年2月算法過程描述：

Step1：初始距離矩陣的計算D(0)說明：（1）距離矩陣元素的值是類與類之間的距離，距離的定義有多種。（2）距離矩陣，是對稱矩陣。對角上線的元值表示同類之間的距離，即為0。Step2：對于第n次迭代的距離矩陣D(n)進(jìn)行聚合第25頁，課件共55頁，創(chuàng)作于2023年2月

說明：距離矩陣中選擇距離最小的，如果有相同的可以任選其中一個，要忽略對角線上的元素；也可以把相同的全部聚合。Step3：根據(jù)第n次聚合結(jié)果，計算合并后的新類別之間的距離矩陣D(n+1)

說明：合并類的距離計算應(yīng)該符合距離的運算規(guī)則。若距離反映的是兩類的重心距離，那么合并后，應(yīng)該仍然反映的重心的距離。Step4：收斂性判決（距離閾值D的設(shè)定）說明：算法的收斂條件判斷準(zhǔn)則的確定。第26頁，課件共55頁，創(chuàng)作于2023年2月例1：如下圖所示（簡單的一維情況）1、設(shè)全部樣本分為6類，2、計算距離矩陣D(0)第27頁，課件共55頁，創(chuàng)作于2023年2月Ω1Ω2Ω3Ω4Ω5Ω6Ω10Ω290Ω31160Ω44916640Ω52543640Ω6642581190第28頁，課件共55頁，創(chuàng)作于2023年2月3、求最小元素：4、把Ω1,Ω3合并Ω7=(1,3)Ω4,Ω6合并Ω8=(4,6)5、作距離矩陣D(1)，按最小距離準(zhǔn)則Ω7Ω2Ω8Ω5Ω70Ω290Ω849160Ω525440第29頁，課件共55頁，創(chuàng)作于2023年2月6、若合并的類數(shù)沒有達(dá)到要求，轉(zhuǎn)3。否則停止。3、求最小元素：4、Ω8,Ω5,Ω2合并,ω9=（2,5,4,6）第30頁，課件共55頁，創(chuàng)作于2023年2月§1.5分解聚類分解聚類：把全部樣本作為一類，然后根據(jù)相似性、相鄰性分解。目標(biāo)函數(shù)為：兩類均值方差N：總樣本數(shù)，：ω1類樣本數(shù)：ω2類樣本數(shù)，第31頁，課件共55頁，創(chuàng)作于2023年2月分解聚類框圖初始分類調(diào)整分類方案最終結(jié)果目標(biāo)函數(shù)達(dá)到最優(yōu)？第32頁，課件共55頁，創(chuàng)作于2023年2月例2：已知21個樣本，每個樣本取二個特征，原始資料矩陣如下表：樣本號12345678910x10022445667x265534312101112131415161718192021-4-2-3-3-5100-1-1-3322021-1-2-1-3-5第33頁，課件共55頁，創(chuàng)作于2023年2月∴目標(biāo)函數(shù)∴解：第一次分類時計算所有樣本，分別劃到時的E值，找出最大E值對應(yīng)的樣本。1、開始時，第34頁，課件共55頁，創(chuàng)作于2023年2月

2、分別計算當(dāng)劃入時的E值把劃入時有第35頁，課件共55頁，創(chuàng)作于2023年2月然后再計算把劃入時對應(yīng)的E值，找出一個最大的E值。

一直計算下去…

把劃為的E值最大?！?/p>

E(1)=56.6再繼續(xù)進(jìn)行第二，第三次迭代…計算出E(2),E(3),…第36頁，課件共55頁，創(chuàng)作于2023年2月次數(shù)E值

156.6279.16390.904102.615120.116137.157154.108176.159195.2610213.0711212.01第37頁，課件共55頁，創(chuàng)作于2023年2月第10次迭代劃入時，E最大。于是分成以下兩類：∴每次分類后要重新計算的值。可用以下遞推公式：第38頁，課件共55頁，創(chuàng)作于2023年2月第39頁，課件共55頁，創(chuàng)作于2023年2月§1.6動態(tài)聚類——兼顧系統(tǒng)聚類和分解聚類一、動態(tài)聚類方法概要①先選定某種距離作為樣本間的相似性度量;②確定評價聚類結(jié)果的準(zhǔn)則函數(shù);③給出某種初始分類，用迭代法找出使準(zhǔn)則函數(shù)取極值的最好的聚類結(jié)果。第40頁，課件共55頁，創(chuàng)作于2023年2月選代表點初始分類分類合理否最終分類修改分類YN動態(tài)聚類框圖第41頁，課件共55頁，創(chuàng)作于2023年2月二、代表點（種子點）的選取方法：代表點就是初始分類的聚類中心數(shù)K

①憑經(jīng)驗選代表點，根據(jù)問題的性質(zhì)、數(shù)據(jù)分布，從直觀上看來較合理的代表點K;②將全部樣本隨機分成K類，計算每類重心，把這些重心作為每類的代表點;

③用前K個樣本點作為代表點。第42頁，課件共55頁，創(chuàng)作于2023年2月④按密度大小選代表點：

以每個樣本作為球心，以d為半徑做球形；落在球內(nèi)的樣本數(shù)稱為該點的密度，并按密度大小排序。首先選密度最大的作為第一個代表點，即第一個聚類中心。再考慮第二大密度點，若第二大密度點距第一代表點的距離大于d1（人為規(guī)定的正數(shù)）則把第二大密度點作為第二代表點，，否則不能作為代表點，這樣按密度大小考察下去，所選代表點間的距離都大于d1。d1太小，代表點太多，d1太大，代表點太小，一般選d1＝2d。對代表點內(nèi)的密度一般要求大于T。T>0為規(guī)定的一個正數(shù)。第43頁，課件共55頁，創(chuàng)作于2023年2月三、初始分類和調(diào)整①選一批代表點后，代表點就是聚類中心，計算其它樣本到聚類中心的距離，把所有樣本歸于最近的聚類中心點，形成初始分類，再重新計算各聚類中心，稱為成批處理法。②選一批代表點后，依次計算其它樣本的歸類，當(dāng)計算完第一個樣本時，把它歸于最近的一類，形成新的分類。再計算新的聚類中心，再計算第二個樣本到新的聚類中心的距離，對第二個樣本歸類。即每個樣本的歸類都改變一次聚類中心。此法稱為逐個處理法。③直接用樣本進(jìn)行初始分類，先規(guī)定距離d，把第一個樣品作為第一類的聚類中心，考察第二個樣本，若第二個樣本距第一個聚類中心距離小于d，就把第二個樣本歸于第一類，否則第二個樣本就成為第二類的聚類中心，再考慮其它樣本，根據(jù)樣本到聚類中心距離大于還是小于d，決定分裂還是合并。第44頁，課件共55頁，創(chuàng)作于2023年2月最佳初始分類：如圖所示，隨著初始分類K的增大，準(zhǔn)則函數(shù)下降很快，經(jīng)過拐點A后，下降速度減慢。拐點A就是最佳初始分類。第45頁，課件共55頁，創(chuàng)作于2023年2月四、K-均值算法：成批處理法例：已知有20個樣本，每個樣本有2個特征，數(shù)據(jù)分布如下圖第一步：令K=2，選初始聚類中心為樣本序號x1x2x3x4x5x6x7x8x9x10特征x10101212367特征x20011122266x11x12x13x14x15x16x17x18x19x2086789789896777788899第46頁，課件共55頁，創(chuàng)作于2023年2月第47頁，課件共55頁，創(chuàng)作于2023年2月第48頁，課件共55頁，創(chuàng)作于2023年2月因為所以