機(jī)器學(xué)習(xí) 習(xí)題答案匯 胡曉 第1-11章

[在此處鍵入]第1章習(xí)題第1題垃圾分類：可回收物、有害垃圾、廚余垃圾和其他垃圾。重量屬性、濕度屬性、顏色屬性、形狀屬性、名稱屬性等。第2題模型性能評估主要是對模型性能優(yōu)良進(jìn)行評價(jià)，測度模型是否達(dá)到任務(wù)要求，不同任務(wù)通常設(shè)計(jì)不同評估函數(shù)；損失函數(shù)也叫代價(jià)函數(shù)，定義為整個(gè)訓(xùn)練集上所有樣本誤差的平均；目標(biāo)函數(shù)定義為優(yōu)化函數(shù)，等于代價(jià)函數(shù)+正則化項(xiàng)。第3題監(jiān)督學(xué)習(xí)，每個(gè)數(shù)據(jù)都有對應(yīng)標(biāo)簽。簡單說，通過數(shù)據(jù)+標(biāo)簽訓(xùn)練模型。非監(jiān)督學(xué)習(xí)，數(shù)據(jù)沒有對應(yīng)標(biāo)簽。簡單說，通過數(shù)據(jù)，獲得某種潛在函數(shù)。強(qiáng)化學(xué)習(xí)通過在智能體與環(huán)境的交互過程中智能體學(xué)習(xí)策略以達(dá)成回報(bào)最大化或?qū)崿F(xiàn)特定目標(biāo)。第4題自適應(yīng)學(xué)習(xí)率、小批量梯度下降、動(dòng)量第5題奧卡姆剃刀準(zhǔn)則：如無必要，勿增實(shí)體。（Entitiesshouldnotbemultipliedunnecessarily）羅生門現(xiàn)象(LeoBreiman)：處理問題時(shí)，往往各執(zhí)一詞，從而形成有利于自己的處理方式。機(jī)器學(xué)習(xí)中的羅生門現(xiàn)象與嶺回歸有關(guān)，沒有唯一解?！皼]有免費(fèi)的午餐”定理(NoFreeLunchTheorem，NFL)：在優(yōu)化算法中任何一個(gè)模型函數(shù)都不能解決所有問題。如果在一些訓(xùn)練樣本上表現(xiàn)好，那么在另一些訓(xùn)練樣本上表現(xiàn)不好。第6題0.5166．程序，略。第1題高斯分布對離群點(diǎn)非常敏感，擁擠現(xiàn)象影響明顯。參考教材圖2.13，采用學(xué)生t分布計(jì)算相似度。實(shí)現(xiàn)同一簇類點(diǎn)(距離較近)聚合更緊密，不同簇類間點(diǎn)更加疏遠(yuǎn)。第2題xXXXXXT第3題EEE第4題模仿例2.4，詳細(xì)過程略。第1題略。第2題提示：輸入圖像，計(jì)算直方圖，然后估計(jì)概率分布曲線。第3題稀少事件指在有限次試驗(yàn)中很少甚至不出現(xiàn)事件。以至于，稀少事件概率為零，實(shí)際上并不等于零。為避免這種不準(zhǔn)確的概率計(jì)算出現(xiàn)，可以采用“m-估計(jì)法”。例如0-1事件概率計(jì)算PNπ0和π1為專家直覺概率，即憑先驗(yàn)知識，出現(xiàn)0和1的概率應(yīng)該為π0第1題模仿例題4.1，詳細(xì)過程略。第2題設(shè)包含N個(gè)樣本的樣本集D=x1,y1,x2,y2,…,xN,PPP第3題ball-tree是對kd-tree的改進(jìn)，在數(shù)據(jù)維度較大時(shí)，kd-tree性能急劇下降，而ball-tree在高維數(shù)據(jù)情況下具有更好的性能。kd-tree采用二叉樹思想，最近鄰使用歐式距離（超球體），分割子空間為超方體。顯然，分割的超方體與搜索的超球體相交可能性大，而相交空間需要檢查；ball-tree，采用兩邊之和與第三邊大小進(jìn)行判斷，分割子空間也是超球體，所以分割區(qū)與搜索區(qū)相交部分減少。第1題略。第2題優(yōu)化問題存在約束條件，min拉格朗日函數(shù)定義為，F(xiàn)優(yōu)化問題存在不等式約束條件，min如果滿足KKT條件：?Fx,ββkλmλmgm其拉格朗日函數(shù)定義為，F(xiàn)第3題?第4題?J?J第5題?第1題設(shè)∑的特征向量和特征值分別是v和λ，即∑v=1v=?將2代入3得，λ?所以有，λN第2題設(shè)I∈RKKK第3題K第4題K第5題核函數(shù)均為正定函數(shù):?n∈N,i=1第1題略。第2題略。第3題定理：Hoeffding不等式設(shè)Z1,ZP第4題Booting是實(shí)現(xiàn)集成學(xué)習(xí)的一種機(jī)制；而AdaBoost（AdaptiveBoosting）是實(shí)現(xiàn)Boosting機(jī)制的一種方式。第5題CART與ID3和C4.5相同點(diǎn)：特征選擇、樹的?成和剪枝三個(gè)不揍。ID3和C4.5?于分類，CART既可?于分類，也可以實(shí)現(xiàn)回歸。第8章聚類 28.1聚類基本理論 28.1.1聚類的性質(zhì) 28.1.2相似性測度 38.1.3類簇中心 48.1.4聚類算法評價(jià)指標(biāo) 68.2K均值聚類 118.3層次聚類 138.3.1凝聚筑巢 138.3.2平衡迭代削減層次聚類 158.4密度聚類 188.4.1DBSCAN 188.4.2高斯混合聚類 208.5小結(jié)與拓展 21實(shí)驗(yàn)八聚類實(shí)驗(yàn) 21習(xí)題 24第8章聚類聚類是無監(jiān)督學(xué)習(xí)算法，其目的是把相似樣本歸為一類，不相似樣本歸為另一類。例如將動(dòng)物聚類，可以根據(jù)“腿屬性”聚類成無足動(dòng)物、兩腿動(dòng)物和四腿動(dòng)物。聚類算法大體可分為均值區(qū)域劃分聚類、層次聚類、密度聚類和譜聚類算法。層次聚類算法可追溯到1963年，最著名的k均值聚類算法則于1967年被提出，1995年提出的MeanShift算法于1995年用于聚類，譜聚類算法誕生于2000年左右。聚類概念聚類概念相似度測度：歐式距離，曼哈頓距離，閔可夫斯基距離，值差異測量類簇中心：K均值中心、基于密度的中心評價(jià)指標(biāo)：純度，聚類熵，同質(zhì)性，蘭德指數(shù)，輪廓系數(shù)算法K均值聚類：k層次聚類：凝聚筑巢，平衡迭代削減層密度聚類：DBSCAN，高斯混合聚類8.1聚類基本理論8.1.1聚類的性質(zhì)對樣本數(shù)據(jù)集X=x1,x2非空性：X圖8.圖8.1聚類示意X1X2X3X412全覆蓋：k=1K聚類簇Xk中樣本在某個(gè)屬性或某些屬性指導(dǎo)下彼此“相似”而物以類聚。異簇之間樣本“不相似”而敬而遠(yuǎn)之。實(shí)際上，聚類結(jié)果未必全滿足上述三個(gè)條件。如圖8.1所示，如果把圖中黑色點(diǎn)當(dāng)作噪聲樣本，顯然上述三個(gè)條件全滿足。如果不是噪聲點(diǎn)，1號黑色樣本點(diǎn)可能同時(shí)被劃歸為X2和8.1.2相似性測度1.相似度測度的性質(zhì)在聚類算法，樣本間相似度通常需要采用兩個(gè)樣本之間的“距離測度(DistanceMetric,DM)”進(jìn)行衡量。設(shè)兩個(gè)向量x=(x1,x2非負(fù)性，距離不能是負(fù)數(shù)：DMx同一性，具有相同屬性向量的兩個(gè)樣本的距離等于零：DMx無向性或?qū)ΨQ性，x到y(tǒng)與y到x的距離相等：DMx直遞性，三角不等式：DMx2.常見距離測度1)歐氏距離(Euclidean)DM2)曼哈頓距離(Manhattan)DM3)閔可夫斯基距離(Minkowski)DM式中，p=1時(shí)，閔氏距離即為曼哈頓距離；圖8.2閔可夫斯基圖8.2閔可夫斯基距離圖形xxlll-11-11(0,0)圖8.2顯示了二維空間中樣本點(diǎn)xi,1,xi,2取不同值時(shí)，與原點(diǎn)3.不同量綱間距離測度計(jì)算上述距離時(shí)，隱含一個(gè)假設(shè)：各屬性分量的量綱(單位)相同。然而如果屬性分量的單位不相同，則各分量的分布(期望，方差等特性)可能不同。舉個(gè)例子：二維樣本(身高,體重)，其中身高范圍是150~190厘米，體重范圍是50~60公斤。現(xiàn)有三個(gè)樣本：張三(180,50)，李四(190,50)，王五(180,60)。那么張三與李四之間的閔氏距離等于張三與王五之間的閔氏距離，但是身高的10厘米并不一定等價(jià)于體重的10公斤。針對量綱不同的屬性，通常采用兩種方式進(jìn)行標(biāo)準(zhǔn)化：1)采用每個(gè)屬性值的標(biāo)準(zhǔn)差進(jìn)行歸一DM式中，sn表示第n2)標(biāo)準(zhǔn)化屬性尺度是把所有屬性取值縮放到相同區(qū)間0,1x=3.值差異度量(ValueDifferenceMetric,VDM)無序?qū)傩圆捎弥挡町惗攘?VDM)。在K個(gè)類簇中，設(shè)ma,x是屬性a上取值為x的樣本數(shù)，ma,x,k表示在第k類樣本簇中屬性a上取值為x的樣本數(shù)，則屬性a上取值為x1和xVDM設(shè)樣本的d屬性向量中有dc個(gè)有序?qū)傩裕琩-dc個(gè)無序?qū)傩裕瑒t樣本x,yDM當(dāng)不同屬性重要性不同時(shí)，可乘權(quán)重系數(shù)wi≥0，8.1.3類簇中心類簇中心，又稱為簇質(zhì)心，定義為簇內(nèi)樣本分布中心，如圖8.1中每簇的中心點(diǎn)。然而，不同聚類算法定義各有差別，簡單分為兩種：1.K均值聚類簇中心設(shè)聚類結(jié)果為X1,X2,…,XK，第k類的樣本數(shù)量為Nk，則μ通過式8.7計(jì)算類簇中心符合最優(yōu)理論。2.基于密度的類簇中心AlexRodriguez和AlessandroLaio在Science期刊文章中提出：類簇中心周圍都是密度比其低的點(diǎn)，同時(shí)這些點(diǎn)距離該簇中心的距離相比于其他聚類中心最近。設(shè)樣本集X=x1,x2對于樣本xn，首先計(jì)算其局部密度ρn和距離(1)樣本xn的局部密度局部密度定義為以xn為中心、?為半徑的鄰域N?(xn)內(nèi)樣本點(diǎn)的數(shù)量(不包括1)硬截?cái)唳咽街校琁把鄰域半徑?稱為截?cái)嗑嚯x。2)高斯平滑截?cái)唳延?jì)算局部密度的目的為了依據(jù)密度大小尋找類簇中心，為此希望樣本點(diǎn)的局部密度盡可能不相等。顯然，高斯平滑截?cái)嗑哂袃蓚€(gè)優(yōu)點(diǎn)：(1)具有相同局部密度的概率??；(2)鄰域N?(2)距離d當(dāng)獲得X=xnn=1N的密度集ρnn=1N后，則xn的距離dd式中，IdXn=m|ρm>ρn然而，當(dāng)ρn=maxm∈IdXρd式中，IdX=1,2,?,N為樣本集圖8.3展示了一個(gè)決策類簇中心的例子，圖中樣本點(diǎn)為二維屬性向量。圖8.3(a)為28個(gè)樣本點(diǎn)分布。直觀上，容易發(fā)現(xiàn)點(diǎn)1和點(diǎn)10可作為類簇中心。dρ圖8.3(dρ圖8.3(a)二維樣本空間分布和(b)決策圖(ρn(a)(b)盡管ρ9和ρ10相差不大，但是d9和d10卻有很大差別：點(diǎn)9屬于點(diǎn)1的類簇(把點(diǎn)1作為大腿抱著)，在其附近還有幾個(gè)更高的局部密度的點(diǎn)，因此d9較??；此外，點(diǎn)26、27和28是孤立的，盡管有相對較高的距離值，但是它們的局部密度值很低。這些點(diǎn)稱為異常點(diǎn)，可當(dāng)作噪聲點(diǎn)，也可作為單個(gè)點(diǎn)構(gòu)成的簇。綜上所述，只有同時(shí)具有較高局部密度和距離的點(diǎn)才是非孤立點(diǎn)的類簇中心。8.1.4聚類算法評價(jià)指標(biāo)如圖8.4所示，假設(shè)兩種聚類算法A1和A2，對X=xC=K=為了表述方便，假設(shè)算法A1的聚類結(jié)果是期望結(jié)果，稱每個(gè)聚類為一個(gè)類；聚類算法A2的結(jié)果則需要進(jìn)行評價(jià)，稱每個(gè)聚類為一個(gè)簇。聚類算法A1聚類算法A1聚類算法A2CCCCKKKKK圖8.4聚類算法評價(jià)指標(biāo)620324114105791112138171615211819

6324157109111213814171615202118191.純度(Purity)將每個(gè)簇內(nèi)頻數(shù)最高的樣本類別作為正確的類簇，則每簇純度定義為，Purity參考算法A1的聚類結(jié)果，圖8.4聚類算法A2每個(gè)簇的純度分別為：Purity整個(gè)聚類的純度定義為，Purity算法A2聚類后整體純度為，Purity2.聚類熵針對每一個(gè)聚類簇KkEn式中,S表示聚類算法A1的類別數(shù)，pks是簇Xk中樣本屬于類Cs的概率。當(dāng)Xk圖8.4聚類算法A2聚類結(jié)果每個(gè)簇的熵為，EntropyEntropy3.同質(zhì)性(Homogeneity)同質(zhì)性也叫均一性，一個(gè)類簇中僅有一個(gè)類別的樣本，均一性最高。相當(dāng)于精確率，即被聚類的類簇中正確分類的樣本數(shù)占該類簇中的樣本數(shù)的比例,Accuracy假設(shè)K5為噪聲簇，圖8.4聚類算法A21有時(shí)，同質(zhì)性度量還用條件熵定義為h值，h=1-式中，H(KHH(C)=-式中，K表示聚類算法A2的簇?cái)?shù)。n總是實(shí)例數(shù)，ns和nk分別表示類Cs和簇Kk的實(shí)例數(shù)，ns,kH(C)=-H4.完整性(Completeness)同類別的樣本被歸類到同一聚類簇中，則滿足完整性。相當(dāng)于召回率，即每個(gè)聚類中正確分類的樣本數(shù)占該類別樣本的數(shù)量，Recall假設(shè)K5為噪聲簇，圖8.4聚類算法A2結(jié)果前41有時(shí)，完整性度量也用條件熵定義為h值，c=1-同質(zhì)性和完整性都是基于兩類別劃分間的條件熵：已知某一類別劃分后，計(jì)算另一類別劃分的不確定性程度，不確定性越小，兩個(gè)類別劃分越接近，h值或c值就越大。V-Measure，是同質(zhì)性和完整性的調(diào)和平均值(harmonicmean)，定義為v=5.蘭德指數(shù)和調(diào)整蘭德指數(shù)考慮X=xnn=1N中任意兩個(gè)互異樣本xn和SS：xn和xm在A1和ASSSD：xn和xm在A1屬于同類，但在A2屬于不同簇,SD=DS：xn和xm在A1屬于不同類簇，但在ADS=DD：xn和xm在A1和ADD=用a、b、c和d接下來，結(jié)合圖8.4給出計(jì)算過程：a其中，C23+b、c和SS+DS：同一簇中任取兩個(gè)樣本點(diǎn)來自同類和非同類，a+c=SS+SDa+a+可得a=21,b=27,c=18,d=144進(jìn)一步制定混淆矩陣(PairConfusionMatrix),同簇非同簇同簇非同簇同類a=b=a+b同類212748非同類c=d=c+d非同類18144162a+cb+d39171基于a、b、(1)蘭德指數(shù)(RandIndex,RI)RI=(2)JaccardCoefficientJ(3)FewlkesandMallowsindexFM=上述三個(gè)系數(shù)的范圍是0,1，值越大，劃分越好。然而，即便隨機(jī)劃分，RI值也未必接近于0。于是1985年Hubert和Arabie提出調(diào)整蘭德指數(shù)：假設(shè)聚類算法A1和A2CC?CsumsCCCCsumsKnn?naK51006Knn?naK14005Knn?naK00202??????K00235Knn?naK11013sumsbb?bsums7644(4)調(diào)整蘭德指數(shù)(AdjustedRandIndex,ARI)ARI=采用調(diào)整蘭德指數(shù)是為了消除隨機(jī)標(biāo)簽對于蘭德指數(shù)評估結(jié)果的影響。計(jì)算ARI的另一種方法是根據(jù)列聯(lián)表(contingencytable)，表中，nks表示同時(shí)落入Kk和Cs為此，基于列聯(lián)表的調(diào)整蘭德指數(shù)計(jì)算公式，ARI調(diào)整蘭德指數(shù)范圍是-1,1，負(fù)數(shù)代表聚類結(jié)果不好，越接近于1越好。對任意數(shù)量的聚類中心和樣本數(shù)，隨機(jī)聚類的ARI都非常接近于0。圖8.4示列的ARI的計(jì)算過程如下：a=a+c=a+ARI上述四個(gè)指數(shù)越大表明：A1和A26.輪廓系數(shù)(SilhouetteCoefficient,SC)xn的SCSC式中，a(xn)：為樣本xn到同一簇內(nèi)其它樣本的平均距離，體現(xiàn)了樣本xn的簇內(nèi)不相似度bXk(xn)：樣本xn到簇Kk內(nèi)樣本的平均距離，反映樣本xnb(xn)=SC(xn)接近1，則說明樣本xn聚類合理；SC(xn)所有樣本的SC的均值稱為聚類結(jié)果的輪廓系數(shù)。8.2K均值聚類K均值聚類算法(K-means)的基本思路：依據(jù)距離相似度將樣本集聚類成K個(gè)簇，致使簇內(nèi)樣本距離盡可能小，簇間距離盡可能大。1.K均值聚類的基本步驟算法8.1是K均值聚類的偽代碼。首先，通常依據(jù)對樣本集的先驗(yàn)知識選擇一個(gè)合適的K值。然后，對簇中心初始化處理。隨后進(jìn)入迭代過程，直至收斂。K均值算法通常選擇如下幾種方式之一作為迭代收斂條件：算法8.1K均值聚類輸入：樣本集X∈Rd×N,X=過程：1、生成K個(gè)中心點(diǎn)μ2、重復(fù)下述過程直至收斂依據(jù)argmin1≤k≤KMD(xn,重新計(jì)算中心點(diǎn)μk修正中心點(diǎn)μk如果收斂,跳出循環(huán)至3，否則重復(fù)迭代3、終止。輸出：聚類結(jié)果K聚類中心不再有變化，或者變化很小，即max式中，ε為預(yù)設(shè)的一個(gè)非常小值。各樣本到對應(yīng)簇中心距離之和SumSu類內(nèi)距離總和SOD不再發(fā)生變化。每輪迭代需要計(jì)算全部樣本點(diǎn)到所有質(zhì)心的距離，計(jì)算量大耗時(shí)。ElkanK-Means利用“兩邊之和大于等于第三邊”和“兩邊之差小于第三邊”兩個(gè)性質(zhì)減少不必要的距離計(jì)算。已知MD(μi,μj)，如果2MD2.K-means++算法在K均值聚類算法中，K個(gè)初始中心點(diǎn)對最后的聚類結(jié)果和運(yùn)行時(shí)間有很大影響。如果完全隨機(jī)選擇，可能導(dǎo)致算法收斂較慢。K-means++算法對中心點(diǎn)選擇進(jìn)行了優(yōu)化，優(yōu)化步驟如下：1)從樣本集中隨機(jī)選擇一個(gè)點(diǎn)作為第一個(gè)聚類中心μ1；2)計(jì)算所有樣本xn與已選擇的聚類中心的距離3)選擇一個(gè)距離較大樣本作為新的聚類中心；4)重復(fù)(2)和(3)直到選擇出K個(gè)聚類質(zhì)心。3.小批量K均值聚類當(dāng)樣本數(shù)量非常大時(shí)，如10萬以上，傳統(tǒng)K-Means算法的計(jì)算量非常大，因?yàn)槊枯喌家?jì)算全部樣本點(diǎn)到所有質(zhì)心的距離。即便采用ElkanK-Means，計(jì)算量仍然很大。后來有人提出小批量K均值(MiniBatchK-Means)：1)從樣本集中隨機(jī)抽取小批量樣本分配給最近的質(zhì)心；2)更新質(zhì)心；3)重復(fù)1)和2)，直至達(dá)到收斂條件。相對于傳統(tǒng)K均值算法，小批量K均值得收斂速度提高了，但聚類精確度有所降低。盡管K均值算法普遍使用，但是始終存在K值選擇和初始聚類中心點(diǎn)選擇問題。為了避免這些問題，可以選擇另一種比較實(shí)用的聚類算法——層次聚類算法。8.3層次聚類層次聚類(hierarchicalclustering)是基于簇間的相似度的樹形聚類算法。一般有兩種劃分策略：自底向上的凝聚策略和自頂向下的分拆策略。1)凝聚策略。初始時(shí)將每個(gè)樣本點(diǎn)當(dāng)做一個(gè)類簇，然后依據(jù)相似度準(zhǔn)則合并相似度最大的類簇，直到達(dá)到終止條件。2)分拆策略。初始時(shí)將所有的樣本歸為一個(gè)類簇，然后依據(jù)某種相似度準(zhǔn)則找出簇中最不相似的兩個(gè)樣本xi和xx1x2x3x4x5xxxxxx1.000.000.750.500.25相似度圖8.5基于凝聚策略的層次聚類示意圖凝聚筑巢(AgglomerativeNesting,AGNES)是一種自底向上的層次聚類算法。1.基本步驟1)每個(gè)樣本作為一個(gè)初始聚類簇；2)根據(jù)相似度準(zhǔn)則將兩個(gè)最相似簇合并成一個(gè)聚類簇；3)重復(fù)2)直到滿足終止條件。如圖8.5所示，由顏色和形狀屬性構(gòu)成樣本的特征向量。在初始層，每個(gè)樣本之間存在一定差異，一個(gè)樣本一個(gè)葉節(jié)點(diǎn)，共6個(gè)簇。由于樣本x2和x3在“形狀”屬性上完全相同，“顏色”屬性上也相似，它們的相似度最高，所以把樣本x2和x3聚成同一簇。由此，經(jīng)過第一輪聚類后，得到5個(gè)簇：x1、x2,x3、x4、x5和x6；接下來，在這5個(gè)簇中合并兩個(gè)相似度最高的簇x1和x2,x在此聚類算法中，需要考慮兩個(gè)核心因素：簇間相似度和終止條件。2.簇間相似度依據(jù)相似度的不同定義，層次聚類算法主要有單鏈?zhǔn)健⑷準(zhǔn)健⒕溄雍头擎溄铀姆N。(1)單鏈?zhǔn)?single-linkage)簇類間距離定義為分處兩簇的樣本間的最小距離，DXiXj圖8.6單鏈?zhǔn)胶腿準(zhǔn)较嗨贫扔?jì)算XiXjXiXj(a)(b)(c)如圖8.6紅色雙箭頭表示兩簇XX圖8.6單鏈?zhǔn)胶腿準(zhǔn)较嗨贫扔?jì)算XXXX(a)(b)(c)(2)完全鏈接聚類(complete-linkage)簇類間距離定義為分處兩簇的樣本間的最大距離，D如8.6所示藍(lán)色雙箭頭表示兩簇Xi和X(3)均鏈接聚類(average-linkage)簇間距離定義為分處兩簇樣本間距離的平均值,D(4)非鏈接(ward-linkage)目標(biāo)是每個(gè)類簇的方差最小。3.終止條件除了設(shè)置固定簇?cái)?shù)量終止外，還可以設(shè)置距離上限：如果在某一輪迭代中，所有簇間距離都超過該閾值，則停止聚類。在采用這種停止準(zhǔn)則時(shí)，隱含了一種假設(shè)：簇內(nèi)樣本在特征空間上距離很近，而異簇內(nèi)樣本間距離較大。算法8.2AGNES算法輸入：樣本集X∈Rd×N,X=過程：1、將每個(gè)樣本作為一個(gè)初始簇，即N個(gè)初始簇，X2、重復(fù)下述計(jì)算任意兩個(gè)簇間相似度，DM合并兩個(gè)相似度度最大的兩個(gè)簇，獲得新的聚類X1如果滿足終止條件,跳出循環(huán)至輸出；否則重復(fù)迭代輸出：聚類結(jié)果X8.3.2平衡迭代削減層次聚類平衡迭代削減層次聚類(BalancedIterativeReducingandClusteringUsingHierarchies,BIRCH)單次掃描樣本集構(gòu)建聚類特征樹(ClusteringFeatureTree,CFT)，隨后進(jìn)行優(yōu)化(可選)即可完成聚類。運(yùn)行速度快，適合數(shù)據(jù)量大、類別數(shù)較多的情況。1.聚類特征設(shè)用樣本集X=x1,x2,?,xNCF012345678910107684351029CF1=5,012345678910107684351029CF1CF25個(gè)樣本：2,6,6個(gè)樣本：6,5,CF1圖8.7聚類特征CF和可加性示列LS=SS是CF中所有樣本的特征值平方和,SS顯然，聚類特征CF有可加性。圖8.7加以說明。對于兩個(gè)不相交的簇Xi和Xj，已知，CFi=Mi,LSi,(1)簇質(zhì)心μ(2)簇半徑簇中樣本到質(zhì)心的平均距離，R=(3)簇直徑簇中兩兩樣本之間距離的平均值，D=一個(gè)CF擁有的樣本集構(gòu)成一個(gè)簇。CF存儲的是簇中所有樣本屬性的統(tǒng)計(jì)和，當(dāng)給某個(gè)簇添加新樣本時(shí)，這新樣本的屬性值并入到了CF中，不再需要存儲到內(nèi)存。因此，BIRCH聚類在很大程度上對樣本集進(jìn)行了壓縮。2.聚類特征樹生成和決策樹類似，聚類特征樹仍然分為：根節(jié)點(diǎn)、中間結(jié)點(diǎn)(枝節(jié)點(diǎn))、葉節(jié)點(diǎn)。在構(gòu)造樹結(jié)構(gòu)之前，需要提前定義三個(gè)重要參數(shù)：(1)枝平衡因子β每個(gè)內(nèi)部節(jié)點(diǎn)不得多于β個(gè)分支，即樹中每個(gè)節(jié)點(diǎn)最多包含β個(gè)子節(jié)點(diǎn)，CFi,1≤i≤β，CF(2)葉平衡因子λ葉子節(jié)點(diǎn)允許包含的最大CF數(shù)；(3)空間閾值γ葉節(jié)點(diǎn)每個(gè)CF的超球體的最大半徑，所有類簇的半徑不得大于γ。下面簡單介紹聚類特征樹的生成過程：設(shè)樣本集X=x1,x2,?,xN，β=2，λ=3,γ=τ。如圖8.8所示依次按(a)、(CF1x1sc1CF1

γsc2x2x1圖8.8聚類特征樹的生成過程(a)(b)(c)(CFxscCF

γscxx圖8.8聚類特征樹的生成過程(a)(b)(c)(d)(e)xscscxxCF

CF

scscscCF

CF

scscCF

CF

CF

CF

圖8.8(b)，讀入樣本x2，判斷x2與x1是否同處一個(gè)半徑γ的超球體。如果是，則把x2也放入sc1，圖8.8(c)，讀入樣本x3時(shí)，判斷x3是否與sc1處于同一超球體。如果是，則并入CF1。這里假設(shè)不是，則需要在根節(jié)點(diǎn)新增一個(gè)CF2和sc2來容納圖8.8(d)，讀入樣本x4時(shí)，設(shè)x4與x3在同一個(gè)超球體，將x4并入CF2圖8.8(e)，繼續(xù)讀入一系列能被sc1和sc2吸收樣本后，讀入了一個(gè)不能被sc1和sc2吸收的xi。由于β=2，所以，不能在根節(jié)點(diǎn)開設(shè)新CF3，只能向下分裂。設(shè)xi與根節(jié)點(diǎn)中的CF2最近，所以在CF2下生成兩個(gè)分支：CF3和CF4。之前CF2的子簇歸入CF3，x4落入CF4圖8.9聚類特征樹的生成過程——分支(a)(c)scscscscLNscLNCF

CF

RNCF

CF

CF

CF

CF

(b)scscscLNscLNCF

CF

RNCF

CF

CF

CF

scscCF

CF

scscscLNscLNCF

CF

RNCF

CF

CF

CF

scscCF

CF

CF

CF

CF

LNNN繼續(xù)讀入樣本能被sc1、sc2或sc3吸收，按上述規(guī)則一路走來波瀾不驚。之后形成了如圖8.9(a)所示的小樹CFT，樹的高度為2，此樹包含一個(gè)根節(jié)點(diǎn)RN和兩個(gè)葉節(jié)點(diǎn)(LN1和LN2)。請讀者注意：這里把下標(biāo)重新進(jìn)行了排列，實(shí)際樣本所屬關(guān)系與圖8.8一致。RN包含2個(gè)CF(CF1,CF2)。葉節(jié)點(diǎn)LN1擁有2個(gè)CF(CF3,圖8.9(b)，在讀入一個(gè)xj，xj距葉節(jié)點(diǎn)LN2最近。我們希望xj能被CF5,CF6或CF7接納。但是，xj不位于這三個(gè)子簇下三個(gè)超球體之內(nèi)，按圖8.8(c)步驟，需要在LN在LN2所有CF包括新增的CF8，找到兩個(gè)距離最大的CF作為兩個(gè)新葉子節(jié)點(diǎn)(LN2和LN3)的種子，然后將CF5細(xì)心的讀者會發(fā)現(xiàn)：出現(xiàn)了新問題——根節(jié)點(diǎn)出現(xiàn)了3個(gè)分支，不符合題設(shè)β=2的要求。怎么辦？方法與分裂葉節(jié)點(diǎn)一樣。從而獲得如圖8.9(c)的樹，此時(shí)樹的高度為3。此樹包括1個(gè)根節(jié)點(diǎn)、2個(gè)中間節(jié)點(diǎn)(非葉節(jié)點(diǎn)：NLN1和NLN2)、3個(gè)葉節(jié)點(diǎn)(LN1、LN2和LNCF此后，讀入樣本后，從上到下依次從根節(jié)點(diǎn)和中間節(jié)點(diǎn)尋找最近分支，最后在葉節(jié)點(diǎn)尋找最近的CF。直至掃描完所有樣本，建立一棵聚類特征數(shù)CFT當(dāng)掃描完所有樣本，在內(nèi)存建立一棵CFT后，可以考慮進(jìn)行如下優(yōu)化：(1).去除一些異常CF，異常CF包含樣本點(diǎn)很少，可以將其合并到最近的超球體；(2).利用其它聚類算法所有CF元組進(jìn)行聚類，以便消除由于樣本讀入順序?qū)е碌牟缓侠淼臉浣Y(jié)構(gòu)，以及一些由于節(jié)點(diǎn)中CF個(gè)數(shù)限制導(dǎo)致的樹結(jié)構(gòu)分裂；至此，之前介紹的K-Means和BIRCH聚類算法一般只適用于凸樣本集。而密度聚類算法既可以適用于凸樣本集，也可以適用于非凸樣本集。8.4密度聚類密度聚類(Density-BasedSpatialClustering)是一種基于密度的聚類算法。8.4.1DBSCANDBSCAN(density-basedspatialclusteringofapplicationswithnoise)是密度聚類的一個(gè)具有代表性算法，通過樣本間的可連接性來定義相似性。1.基本概念給定樣本集X=x1,稱N?z=xn∈X|DMz,xn≤?為z的半徑?稱鄰域N?z中樣本數(shù)量ρz=N圖8.10中，ρz=6，ρx1=4；如ρz>Xc為XX?x1x2x3x4x5x6z圖8.10核心點(diǎn)、邊界點(diǎn)、噪聲點(diǎn)和密度直接可達(dá)若b∈Xnc?N?xxxxxxz圖8.10核心點(diǎn)、邊界點(diǎn)、噪聲點(diǎn)和密度直接可達(dá)一個(gè)邊界點(diǎn)可能同時(shí)落入多個(gè)核心點(diǎn)的N?在X中既不是核心點(diǎn)又不是邊界點(diǎn)的點(diǎn)為噪聲點(diǎn)，如圖8.10中藍(lán)色樣本點(diǎn)。由噪聲點(diǎn)構(gòu)成的集合記為X從圖8.10所示可知：核心點(diǎn)對應(yīng)稠密區(qū)域內(nèi)部的點(diǎn)，邊界點(diǎn)對應(yīng)稠密區(qū)域邊緣的點(diǎn)，而噪音點(diǎn)對應(yīng)稀疏區(qū)域中的點(diǎn)。設(shè)xi,xj∈X，如果xi∈Xc,xj∈N?xi設(shè)有一系列樣本x1,x2,…,xk∈i=1,2,…,k-1，則稱xk是從x1密度可達(dá)的。仔細(xì)觀察圖8.10發(fā)現(xiàn)，盡管不可達(dá)x6，但是x1密度可達(dá)設(shè)xi,xj,xk∈X，若xj和xk上述概念歸結(jié)為：1個(gè)概念(密度)、2個(gè)參數(shù)(鄰域半徑和密度閾值)、3種類型點(diǎn)(核心點(diǎn)、邊界點(diǎn)和噪聲點(diǎn))和4類關(guān)系(密度直達(dá)、密度可達(dá)、密度相連，非密度相連)。若非空集合Xk?X，如果它滿足：對于xi,xj∈X，(1)最大性：若xi∈(2)連接性：若xi,x則稱Xk是X的一個(gè)2.密度聚類過程圖8.11描繪了密度聚類的基本過程。圖中黑色填充點(diǎn)表示未被訪問的樣本，紅色邊框點(diǎn)表示已經(jīng)被訪問過，紫色填充點(diǎn)表示為噪聲點(diǎn)或臨時(shí)定位噪聲點(diǎn)，藍(lán)色填充點(diǎn)表示已經(jīng)決策為某簇的樣本，綠色填充點(diǎn)表示已經(jīng)決策為另外一簇的樣本。1)從X中隨機(jī)選擇一個(gè)未被訪問的樣本點(diǎn)。如果該點(diǎn)不是核心點(diǎn)(如圖8.11中xm)，將該點(diǎn)暫時(shí)標(biāo)注為噪聲點(diǎn)，并另外選擇一個(gè)沒有被訪問過的樣本點(diǎn)；如果該點(diǎn)是核心點(diǎn)(如圖8.5中xn)，xmxnxnxxxxxxxxxxxxxxx(a)(b)(c)(d)(e)(f)xxxx(g)(h)(i)圖8.11密度聚類的基本過程xxxx(j)算法8.3GMM聚類輸入：數(shù)據(jù)集X∈Rd過程：1、初始化高斯混合模型參數(shù)w2、重復(fù)#參數(shù)估計(jì)在當(dāng)前模型參數(shù)下，計(jì)算X中所有樣本后驗(yàn)概率，p依次估計(jì)新的μk#估計(jì)后面參數(shù)時(shí)可以采用之前估計(jì)參數(shù)。如果達(dá)到最大循環(huán)次數(shù)或LLX3、X#開始聚類4、forn=1,2,…,N計(jì)算p將xn聚類到pendfor#結(jié)束聚類輸出：聚類結(jié)果X2)對Xk中所有尚未被處理的樣本(如圖8.11中xi)。如是核心點(diǎn)，則將N?xi中所有樣本并入Xk3)重復(fù)步驟2)，直至Xk不再有未被處理的樣本4)設(shè)置k=k+1，重復(fù)步驟1)~3)，直到8.4.2高斯混合聚類與K均值聚類相似，高斯混合模型(Gaussianmixturemodel,GMM)聚類將樣本聚類到子簇Xk,k=1,2,…,K。K均值基于距離聚類對圓形分布的樣本聚類效果好，而在3.4-3.5我們已經(jīng)介紹了學(xué)習(xí)高斯混合模型的算法。一旦獲得高斯混合模型，對X=x1,x2,?,xN，即可按算法8.38.5小結(jié)與拓展聚類是一種經(jīng)典無監(jiān)督學(xué)習(xí)方法，通過對無標(biāo)記訓(xùn)練樣本的學(xué)習(xí)，發(fā)掘和揭示數(shù)據(jù)集本身潛在的結(jié)構(gòu)與規(guī)律，即不依賴于訓(xùn)練數(shù)據(jù)集的類標(biāo)記信息。聚類算法與表征學(xué)習(xí)結(jié)合以便有效挖掘出實(shí)例間的復(fù)雜關(guān)系。近年來，隨著人工神經(jīng)網(wǎng)絡(luò)的發(fā)展，深度聚類(DeepClustering)也成為了聚類算法中的研究方向。利用神經(jīng)網(wǎng)絡(luò)強(qiáng)大的學(xué)習(xí)能力實(shí)現(xiàn)優(yōu)化表征學(xué)習(xí)和聚類。實(shí)驗(yàn)八聚類實(shí)驗(yàn)1．實(shí)驗(yàn)?zāi)康?.1了解Scikit-learn提供的聚類算法相關(guān)函數(shù)；1.2掌握采用python對聚類算法(k-mean和高斯混合模型)編程能力。2．實(shí)驗(yàn)環(huán)境平臺：Windows/Linux；編程語言：python3.實(shí)驗(yàn)內(nèi)容3.1常見聚類算法性能比較實(shí)驗(yàn)；3.2手寫數(shù)字聚類實(shí)驗(yàn)。4.實(shí)驗(yàn)步驟4.1聚類算法性能比較實(shí)驗(yàn)首先，用make_blobs生成4個(gè)類中心的高斯分布數(shù)據(jù)：[-1,-1],[-1,1],[1.5,-0.5],[1.5,0.5]。代碼8.1環(huán)形數(shù)據(jù)生成代碼importscipy.ioassiodefThreeCircles():

path=u'cluster_data/ThreeCircles.mat'

ThreeCircles=sio.loadmat(path)['ThreeCircles']

ThreeCircles=ThreeCircles[0::代碼8.1環(huán)形數(shù)據(jù)生成代碼importscipy.ioassiodefThreeCircles():

path=u'cluster_data/ThreeCircles.mat'

ThreeCircles=sio.loadmat(path)['ThreeCircles']

ThreeCircles=ThreeCircles[0::3,:]#每隔3行取一個(gè)數(shù)據(jù)

data=ThreeCircles

data=np.array([data[:,1],data[:,2],data[:,0]]).T#list與array互換

returndataX,y=make_blobs(n_samples=1000,n_features=2,centers=[[-1,-1],[-1,1],[1.5,-0.5],[1.5,0.5]], cluster_std=[[0.45,0.2],[0.25,0.5],0.25,0.3],random_state=10)然后，分別用如下聚類算法進(jìn)行聚類，KMeans(n_clusters=n_classes,random_state=random_state).fit_predict(X)GaussianMixture(n_components=n_classes,covariance_type="spherical",max_iter=50,random_state=random_state).fit_predict(X)AgglomerativeClustering(linkage="average",n_clusters=n_classes).fit_predict(X)Birch(n_clusters=n_classes,branching_factor=5,threshold=0.5).fit_predict(X)DBSCAN(eps=0.4,min_samples=9).fit_predict(X)在圖8.12第一列中，為上述5種聚類算法對這4類高斯分布數(shù)據(jù)的聚類結(jié)果。AGNES和DBSCAN把分布有重疊的樣本聚類成了一類。最后，通過上述算法(BIRCH除外)對三個(gè)圓形分布數(shù)據(jù)進(jìn)行聚類比較，如圖8.12的第二列。AGNES和DBSCAN能把圓環(huán)分布數(shù)據(jù)準(zhǔn)確聚類，而kmeans和GMM卻不具備此聚類能力。本實(shí)驗(yàn)代碼相對簡單，讀者可以應(yīng)用以往實(shí)驗(yàn)自行編寫。這里附上環(huán)形數(shù)據(jù)生成代碼。圖8.12幾種算法聚類結(jié)果比較圖8.12幾種算法聚類結(jié)果比較linkage=’average’linkage=’single’4.2手寫數(shù)字聚類算法性能分析首先，用PCA將64維數(shù)據(jù)降維成2維，手寫數(shù)字?jǐn)?shù)據(jù)相關(guān)代碼見實(shí)驗(yàn)五。reduced_data=PCA(n_components=2).fit_transform(data)然后，用k-means++對降維后的數(shù)據(jù)進(jìn)行聚類，class

sklearn.cluster.KMeans(n_clusters=8,

*,

init='k-means++',

n_init=10,

max_iter=300,

tol=0.0001,

verbose=0,

random_state=None,

copy_x=True,

algorithm='lloyd')init{‘k-means