機器學習 習題答案匯 胡曉 第1-11章

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

6324157109111213814171615202118191.純度(Purity)將每個簇內(nèi)頻數(shù)最高的樣本類別作為正確的類簇，則每簇純度定義為，Purity參考算法A1的聚類結(jié)果，圖8.4聚類算法A2每個簇的純度分別為：Purity整個聚類的純度定義為，Purity算法A2聚類后整體純度為，Purity2.聚類熵針對每一個聚類簇KkEn式中,S表示聚類算法A1的類別數(shù)，pks是簇Xk中樣本屬于類Cs的概率。當Xk圖8.4聚類算法A2聚類結(jié)果每個簇的熵為，EntropyEntropy3.同質(zhì)性(Homogeneity)同質(zhì)性也叫均一性，一個類簇中僅有一個類別的樣本，均一性最高。相當于精確率，即被聚類的類簇中正確分類的樣本數(shù)占該類簇中的樣本數(shù)的比例,Accuracy假設K5為噪聲簇，圖8.4聚類算法A21有時，同質(zhì)性度量還用條件熵定義為h值，h=1-式中，H(KHH(C)=-式中，K表示聚類算法A2的簇數(shù)。n總是實例數(shù)，ns和nk分別表示類Cs和簇Kk的實例數(shù)，ns,kH(C)=-H4.完整性(Completeness)同類別的樣本被歸類到同一聚類簇中，則滿足完整性。相當于召回率，即每個聚類中正確分類的樣本數(shù)占該類別樣本的數(shù)量，Recall假設K5為噪聲簇，圖8.4聚類算法A2結(jié)果前41有時，完整性度量也用條件熵定義為h值，c=1-同質(zhì)性和完整性都是基于兩類別劃分間的條件熵：已知某一類別劃分后，計算另一類別劃分的不確定性程度，不確定性越小，兩個類別劃分越接近，h值或c值就越大。V-Measure，是同質(zhì)性和完整性的調(diào)和平均值(harmonicmean)，定義為v=5.蘭德指數(shù)和調(diào)整蘭德指數(shù)考慮X=xnn=1N中任意兩個互異樣本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給出計算過程：a其中，C23+b、c和SS+DS：同一簇中任取兩個樣本點來自同類和非同類，a+c=SS+SDa+a+可得a=21,b=27,c=18,d=144進一步制定混淆矩陣(PairConfusionMatrix),同簇非同簇同簇非同簇同類a=b=a+b同類212748非同類c=d=c+d非同類18144162a+cb+d39171基于a、b、(1)蘭德指數(shù)(RandIndex,RI)RI=(2)JaccardCoefficientJ(3)FewlkesandMallowsindexFM=上述三個系數(shù)的范圍是0,1，值越大，劃分越好。然而，即便隨機劃分，RI值也未必接近于0。于是1985年Hubert和Arabie提出調(diào)整蘭德指數(shù)：假設聚類算法A1和A2CC?CsumsCCCCsumsKnn?naK51006Knn?naK14005Knn?naK00202??????K00235Knn?naK11013sumsbb?bsums7644(4)調(diào)整蘭德指數(shù)(AdjustedRandIndex,ARI)ARI=采用調(diào)整蘭德指數(shù)是為了消除隨機標簽對于蘭德指數(shù)評估結(jié)果的影響。計算ARI的另一種方法是根據(jù)列聯(lián)表(contingencytable)，表中，nks表示同時落入Kk和Cs為此，基于列聯(lián)表的調(diào)整蘭德指數(shù)計算公式，ARI調(diào)整蘭德指數(shù)范圍是-1,1，負數(shù)代表聚類結(jié)果不好，越接近于1越好。對任意數(shù)量的聚類中心和樣本數(shù)，隨機聚類的ARI都非常接近于0。圖8.4示列的ARI的計算過程如下：a=a+c=a+ARI上述四個指數(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個簇，致使簇內(nèi)樣本距離盡可能小，簇間距離盡可能大。1.K均值聚類的基本步驟算法8.1是K均值聚類的偽代碼。首先，通常依據(jù)對樣本集的先驗知識選擇一個合適的K值。然后，對簇中心初始化處理。隨后進入迭代過程，直至收斂。K均值算法通常選擇如下幾種方式之一作為迭代收斂條件：算法8.1K均值聚類輸入：樣本集X∈Rd×N,X=過程：1、生成K個中心點μ2、重復下述過程直至收斂依據(jù)argmin1≤k≤KMD(xn,重新計算中心點μk修正中心點μk如果收斂,跳出循環(huán)至3，否則重復迭代3、終止。輸出：聚類結(jié)果K聚類中心不再有變化，或者變化很小，即max式中，ε為預設的一個非常小值。各樣本到對應簇中心距離之和SumSu類內(nèi)距離總和SOD不再發(fā)生變化。每輪迭代需要計算全部樣本點到所有質(zhì)心的距離，計算量大耗時。ElkanK-Means利用“兩邊之和大于等于第三邊”和“兩邊之差小于第三邊”兩個性質(zhì)減少不必要的距離計算。已知MD(μi,μj)，如果2MD2.K-means++算法在K均值聚類算法中，K個初始中心點對最后的聚類結(jié)果和運行時間有很大影響。如果完全隨機選擇，可能導致算法收斂較慢。K-means++算法對中心點選擇進行了優(yōu)化，優(yōu)化步驟如下：1)從樣本集中隨機選擇一個點作為第一個聚類中心μ1；2)計算所有樣本xn與已選擇的聚類中心的距離3)選擇一個距離較大樣本作為新的聚類中心；4)重復(2)和(3)直到選擇出K個聚類質(zhì)心。3.小批量K均值聚類當樣本數(shù)量非常大時，如10萬以上，傳統(tǒng)K-Means算法的計算量非常大，因為每輪迭代都要計算全部樣本點到所有質(zhì)心的距離。即便采用ElkanK-Means，計算量仍然很大。后來有人提出小批量K均值(MiniBatchK-Means)：1)從樣本集中隨機抽取小批量樣本分配給最近的質(zhì)心；2)更新質(zhì)心；3)重復1)和2)，直至達到收斂條件。相對于傳統(tǒng)K均值算法，小批量K均值得收斂速度提高了，但聚類精確度有所降低。盡管K均值算法普遍使用，但是始終存在K值選擇和初始聚類中心點選擇問題。為了避免這些問題，可以選擇另一種比較實用的聚類算法——層次聚類算法。8.3層次聚類層次聚類(hierarchicalclustering)是基于簇間的相似度的樹形聚類算法。一般有兩種劃分策略：自底向上的凝聚策略和自頂向下的分拆策略。1)凝聚策略。初始時將每個樣本點當做一個類簇，然后依據(jù)相似度準則合并相似度最大的類簇，直到達到終止條件。2)分拆策略。初始時將所有的樣本歸為一個類簇，然后依據(jù)某種相似度準則找出簇中最不相似的兩個樣本xi和xx1x2x3x4x5xxxxxx1.000.000.750.500.25相似度圖8.5基于凝聚策略的層次聚類示意圖凝聚筑巢(AgglomerativeNesting,AGNES)是一種自底向上的層次聚類算法。1.基本步驟1)每個樣本作為一個初始聚類簇；2)根據(jù)相似度準則將兩個最相似簇合并成一個聚類簇；3)重復2)直到滿足終止條件。如圖8.5所示，由顏色和形狀屬性構(gòu)成樣本的特征向量。在初始層，每個樣本之間存在一定差異，一個樣本一個葉節(jié)點，共6個簇。由于樣本x2和x3在“形狀”屬性上完全相同，“顏色”屬性上也相似，它們的相似度最高，所以把樣本x2和x3聚成同一簇。由此，經(jīng)過第一輪聚類后，得到5個簇：x1、x2,x3、x4、x5和x6；接下來，在這5個簇中合并兩個相似度最高的簇x1和x2,x在此聚類算法中，需要考慮兩個核心因素：簇間相似度和終止條件。2.簇間相似度依據(jù)相似度的不同定義，層次聚類算法主要有單鏈式、全鏈式、均鏈接和非鏈接四種。(1)單鏈式(single-linkage)簇類間距離定義為分處兩簇的樣本間的最小距離，DXiXj圖8.6單鏈式和全鏈式相似度計算XiXjXiXj(a)(b)(c)如圖8.6紅色雙箭頭表示兩簇XX圖8.6單鏈式和全鏈式相似度計算XXXX(a)(b)(c)(2)完全鏈接聚類(complete-linkage)簇類間距離定義為分處兩簇的樣本間的最大距離，D如8.6所示藍色雙箭頭表示兩簇Xi和X(3)均鏈接聚類(average-linkage)簇間距離定義為分處兩簇樣本間距離的平均值,D(4)非鏈接(ward-linkage)目標是每個類簇的方差最小。3.終止條件除了設置固定簇數(shù)量終止外，還可以設置距離上限：如果在某一輪迭代中，所有簇間距離都超過該閾值，則停止聚類。在采用這種停止準則時，隱含了一種假設：簇內(nèi)樣本在特征空間上距離很近，而異簇內(nèi)樣本間距離較大。算法8.2AGNES算法輸入：樣本集X∈Rd×N,X=過程：1、將每個樣本作為一個初始簇，即N個初始簇，X2、重復下述計算任意兩個簇間相似度，DM合并兩個相似度度最大的兩個簇，獲得新的聚類X1如果滿足終止條件,跳出循環(huán)至輸出；否則重復迭代輸出：聚類結(jié)果X8.3.2平衡迭代削減層次聚類平衡迭代削減層次聚類(BalancedIterativeReducingandClusteringUsingHierarchies,BIRCH)單次掃描樣本集構(gòu)建聚類特征樹(ClusteringFeatureTree,CFT)，隨后進行優(yōu)化(可選)即可完成聚類。運行速度快，適合數(shù)據(jù)量大、類別數(shù)較多的情況。1.聚類特征設用樣本集X=x1,x2,?,xNCF012345678910107684351029CF1=5,012345678910107684351029CF1CF25個樣本：2,6,6個樣本：6,5,CF1圖8.7聚類特征CF和可加性示列LS=SS是CF中所有樣本的特征值平方和,SS顯然，聚類特征CF有可加性。圖8.7加以說明。對于兩個不相交的簇Xi和Xj，已知，CFi=Mi,LSi,(1)簇質(zhì)心μ(2)簇半徑簇中樣本到質(zhì)心的平均距離，R=(3)簇直徑簇中兩兩樣本之間距離的平均值，D=一個CF擁有的樣本集構(gòu)成一個簇。CF存儲的是簇中所有樣本屬性的統(tǒng)計和，當給某個簇添加新樣本時，這新樣本的屬性值并入到了CF中，不再需要存儲到內(nèi)存。因此，BIRCH聚類在很大程度上對樣本集進行了壓縮。2.聚類特征樹生成和決策樹類似，聚類特征樹仍然分為：根節(jié)點、中間結(jié)點(枝節(jié)點)、葉節(jié)點。在構(gòu)造樹結(jié)構(gòu)之前，需要提前定義三個重要參數(shù)：(1)枝平衡因子β每個內(nèi)部節(jié)點不得多于β個分支，即樹中每個節(jié)點最多包含β個子節(jié)點，CFi,1≤i≤β，CF(2)葉平衡因子λ葉子節(jié)點允許包含的最大CF數(shù)；(3)空間閾值γ葉節(jié)點每個CF的超球體的最大半徑，所有類簇的半徑不得大于γ。下面簡單介紹聚類特征樹的生成過程：設樣本集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是否同處一個半徑γ的超球體。如果是，則把x2也放入sc1，圖8.8(c)，讀入樣本x3時，判斷x3是否與sc1處于同一超球體。如果是，則并入CF1。這里假設不是，則需要在根節(jié)點新增一個CF2和sc2來容納圖8.8(d)，讀入樣本x4時，設x4與x3在同一個超球體，將x4并入CF2圖8.8(e)，繼續(xù)讀入一系列能被sc1和sc2吸收樣本后，讀入了一個不能被sc1和sc2吸收的xi。由于β=2，所以，不能在根節(jié)點開設新CF3，只能向下分裂。設xi與根節(jié)點中的CF2最近，所以在CF2下生成兩個分支：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，此樹包含一個根節(jié)點RN和兩個葉節(jié)點(LN1和LN2)。請讀者注意：這里把下標重新進行了排列，實際樣本所屬關(guān)系與圖8.8一致。RN包含2個CF(CF1,CF2)。葉節(jié)點LN1擁有2個CF(CF3,圖8.9(b)，在讀入一個xj，xj距葉節(jié)點LN2最近。我們希望xj能被CF5,CF6或CF7接納。但是，xj不位于這三個子簇下三個超球體之內(nèi)，按圖8.8(c)步驟，需要在LN在LN2所有CF包括新增的CF8，找到兩個距離最大的CF作為兩個新葉子節(jié)點(LN2和LN3)的種子，然后將CF5細心的讀者會發(fā)現(xiàn)：出現(xiàn)了新問題——根節(jié)點出現(xiàn)了3個分支，不符合題設β=2的要求。怎么辦？方法與分裂葉節(jié)點一樣。從而獲得如圖8.9(c)的樹，此時樹的高度為3。此樹包括1個根節(jié)點、2個中間節(jié)點(非葉節(jié)點：NLN1和NLN2)、3個葉節(jié)點(LN1、LN2和LNCF此后，讀入樣本后，從上到下依次從根節(jié)點和中間節(jié)點尋找最近分支，最后在葉節(jié)點尋找最近的CF。直至掃描完所有樣本，建立一棵聚類特征數(shù)CFT當掃描完所有樣本，在內(nèi)存建立一棵CFT后，可以考慮進行如下優(yōu)化：(1).去除一些異常CF，異常CF包含樣本點很少，可以將其合并到最近的超球體；(2).利用其它聚類算法所有CF元組進行聚類，以便消除由于樣本讀入順序?qū)е碌牟缓侠淼臉浣Y(jié)構(gòu)，以及一些由于節(jié)點中CF個數(shù)限制導致的樹結(jié)構(gòu)分裂；至此，之前介紹的K-Means和BIRCH聚類算法一般只適用于凸樣本集。而密度聚類算法既可以適用于凸樣本集，也可以適用于非凸樣本集。8.4密度聚類密度聚類(Density-BasedSpatialClustering)是一種基于密度的聚類算法。8.4.1DBSCANDBSCAN(density-basedspatialclusteringofapplicationswithnoise)是密度聚類的一個具有代表性算法，通過樣本間的可連接性來定義相似性。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核心點、邊界點、噪聲點和密度直接可達若b∈Xnc?N?xxxxxxz圖8.10核心點、邊界點、噪聲點和密度直接可達一個邊界點可能同時落入多個核心點的N?在X中既不是核心點又不是邊界點的點為噪聲點，如圖8.10中藍色樣本點。由噪聲點構(gòu)成的集合記為X從圖8.10所示可知：核心點對應稠密區(qū)域內(nèi)部的點，邊界點對應稠密區(qū)域邊緣的點，而噪音點對應稀疏區(qū)域中的點。設xi,xj∈X，如果xi∈Xc,xj∈N?xi設有一系列樣本x1,x2,…,xk∈i=1,2,…,k-1，則稱xk是從x1密度可達的。仔細觀察圖8.10發(fā)現(xiàn)，盡管不可達x6，但是x1密度可達設xi,xj,xk∈X，若xj和xk上述概念歸結(jié)為：1個概念(密度)、2個參數(shù)(鄰域半徑和密度閾值)、3種類型點(核心點、邊界點和噪聲點)和4類關(guān)系(密度直達、密度可達、密度相連，非密度相連)。若非空集合Xk?X，如果它滿足：對于xi,xj∈X，(1)最大性：若xi∈(2)連接性：若xi,x則稱Xk是X的一個2.密度聚類過程圖8.11描繪了密度聚類的基本過程。圖中黑色填充點表示未被訪問的樣本，紅色邊框點表示已經(jīng)被訪問過，紫色填充點表示為噪聲點或臨時定位噪聲點，藍色填充點表示已經(jīng)決策為某簇的樣本，綠色填充點表示已經(jīng)決策為另外一簇的樣本。1)從X中隨機選擇一個未被訪問的樣本點。如果該點不是核心點(如圖8.11中xm)，將該點暫時標注為噪聲點，并另外選擇一個沒有被訪問過的樣本點；如果該點是核心點(如圖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、重復#參數(shù)估計在當前模型參數(shù)下，計算X中所有樣本后驗概率，p依次估計新的μk#估計后面參數(shù)時可以采用之前估計參數(shù)。如果達到最大循環(huán)次數(shù)或LLX3、X#開始聚類4、forn=1,2,…,N計算p將xn聚類到pendfor#結(jié)束聚類輸出：聚類結(jié)果X2)對Xk中所有尚未被處理的樣本(如圖8.11中xi)。如是核心點，則將N?xi中所有樣本并入Xk3)重復步驟2)，直至Xk不再有未被處理的樣本4)設置k=k+1，重復步驟1)~3)，直到8.4.2高斯混合聚類與K均值聚類相似，高斯混合模型(Gaussianmixturemodel,GMM)聚類將樣本聚類到子簇Xk,k=1,2,…,K。K均值基于距離聚類對圓形分布的樣本聚類效果好，而在3.4-3.5我們已經(jīng)介紹了學習高斯混合模型的算法。一旦獲得高斯混合模型，對X=x1,x2,?,xN，即可按算法8.38.5小結(jié)與拓展聚類是一種經(jīng)典無監(jiān)督學習方法，通過對無標記訓練樣本的學習，發(fā)掘和揭示數(shù)據(jù)集本身潛在的結(jié)構(gòu)與規(guī)律，即不依賴于訓練數(shù)據(jù)集的類標記信息。聚類算法與表征學習結(jié)合以便有效挖掘出實例間的復雜關(guān)系。近年來，隨著人工神經(jīng)網(wǎng)絡的發(fā)展，深度聚類(DeepClustering)也成為了聚類算法中的研究方向。利用神經(jīng)網(wǎng)絡強大的學習能力實現(xiàn)優(yōu)化表征學習和聚類。實驗八聚類實驗1．實驗目的1.1了解Scikit-learn提供的聚類算法相關(guān)函數(shù)；1.2掌握采用python對聚類算法(k-mean和高斯混合模型)編程能力。2．實驗環(huán)境平臺：Windows/Linux；編程語言：python3.實驗內(nèi)容3.1常見聚類算法性能比較實驗；3.2手寫數(shù)字聚類實驗。4.實驗步驟4.1聚類算法性能比較實驗首先，用make_blobs生成4個類中心的高斯分布數(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行取一個數(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)然后，分別用如下聚類算法進行聚類，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除外)對三個圓形分布數(shù)據(jù)進行聚類比較，如圖8.12的第二列。AGNES和DBSCAN能把圓環(huán)分布數(shù)據(jù)準確聚類，而kmeans和GMM卻不具備此聚類能力。本實驗代碼相對簡單，讀者可以應用以往實驗自行編寫。這里附上環(huán)形數(shù)據(jù)生成代碼。圖8.12幾種算法聚類結(jié)果比較圖8.12幾種算法聚類結(jié)果比較linkage=’average’linkage=’single’4.2手寫數(shù)字聚類算法性能分析首先，用PCA將64維數(shù)據(jù)降維成2維，手寫數(shù)字數(shù)據(jù)相關(guān)代碼見實驗五。reduced_data=PCA(n_components=2).fit_transform(data)然后，用k-means++對降維后的數(shù)據(jù)進行聚類，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