機(jī)器學(xué)習(xí)之聚類(lèi)-隨堂課件算法

本課件包括演示文稿、示例、代碼、題庫(kù)、視頻和聲音等內(nèi)容，北風(fēng)網(wǎng)和講師擁有完全知識(shí)產(chǎn)權(quán)；只限于善意學(xué)習(xí)者在本課程使用，不得在課程范圍外向任何第三方散播。任何其他人或者機(jī)構(gòu)不得盜版、復(fù)制、仿造其中的創(chuàng)意和內(nèi)容，我們保留一切通過(guò)法律手段追究違反者的權(quán)利。課程詳情請(qǐng)咨詢微信公眾號(hào)：北風(fēng)教育官方網(wǎng)址：法律聲明上海育創(chuàng)網(wǎng)絡(luò)科技有限公司人工智能之機(jī)器學(xué)習(xí)聚類(lèi)算法主講人：June課上課下“九字”真言認(rèn)真聽(tīng)，善摘錄，勤思考多溫故，樂(lè)實(shí)踐，再發(fā)散四不原則不懶散惰性，不遲到早退不請(qǐng)假曠課，不拖延作業(yè)一點(diǎn)注意事項(xiàng)違反“四不原則”，不包就業(yè)和推薦就業(yè)課程要求嚴(yán)格是大愛(ài)寄語(yǔ)Jaccard相似度、Pearson相似度K-means聚類(lèi)聚類(lèi)算法效果評(píng)估(準(zhǔn)確率、召回率等)層次聚類(lèi)算法密度聚類(lèi)算法譜聚類(lèi)算法課程內(nèi)容聚類(lèi)就是對(duì)大量未知標(biāo)注的數(shù)據(jù)集，按照數(shù)據(jù)內(nèi)部存在的數(shù)據(jù)特征將數(shù)據(jù)集劃分為多個(gè)不同的類(lèi)別，使類(lèi)別內(nèi)的數(shù)據(jù)比較相似，類(lèi)別之間的數(shù)據(jù)相似度比較小；屬于無(wú)監(jiān)督學(xué)習(xí)聚類(lèi)算法的重點(diǎn)是計(jì)算樣本項(xiàng)之間的相似度，有時(shí)候也稱為樣本間的距離和分類(lèi)算法的區(qū)別：分類(lèi)算法是有監(jiān)督學(xué)習(xí)，基于有標(biāo)注的歷史數(shù)據(jù)進(jìn)行算法模型構(gòu)建聚類(lèi)算法是無(wú)監(jiān)督學(xué)習(xí)，數(shù)據(jù)集中的數(shù)據(jù)是沒(méi)有標(biāo)注的什么是聚類(lèi)閔可夫斯基距離(Minkowski)當(dāng)p為1的時(shí)候是曼哈頓距離(Manhattan)當(dāng)p為2的時(shí)候是歐式距離(Euclidean)當(dāng)p為無(wú)窮大的時(shí)候是切比雪夫距離(Chebyshev)相似度/距離公式1標(biāo)準(zhǔn)化歐式距離(StandardizedEuclideanDistance)相似度/距離公式2夾角余弦相似度(Cosine)KL距離(相對(duì)熵)相似度/距離公式3杰卡德相似系數(shù)(Jaccard)Pearson相關(guān)系數(shù)給定一個(gè)有M個(gè)對(duì)象的數(shù)據(jù)集，構(gòu)建一個(gè)具有k個(gè)簇的模型，其中k<=M。滿足以下條件：每個(gè)簇至少包含一個(gè)對(duì)象每個(gè)對(duì)象屬于且僅屬于一個(gè)簇將滿足上述條件的k個(gè)簇成為一個(gè)合理的聚類(lèi)劃分基本思想：對(duì)于給定的類(lèi)別數(shù)目k，首先給定初始劃分，通過(guò)迭代改變樣本和簇的隸屬關(guān)系，使的每次處理后得到的劃分方式比上一次的好(總的數(shù)據(jù)集之間的距離和變小了)聚類(lèi)的思想K-means算法，也稱為K-平均或者K-均值，是一種使用廣泛的最基礎(chǔ)的聚類(lèi)算法，一般作為掌握聚類(lèi)算法的第一個(gè)算法假設(shè)輸入樣本為T(mén)=X1,X2,...,Xm;則算法步驟為（使用歐幾里得距離公式）：選擇初始化的k個(gè)類(lèi)別中心a1,a2,...ak;對(duì)于每個(gè)樣本Xi，將其標(biāo)記位距離類(lèi)別中心aj最近的類(lèi)別j更新每個(gè)類(lèi)別的中心點(diǎn)aj為隸屬該類(lèi)別的所有樣本的均值重復(fù)上面兩步操作，直到達(dá)到某個(gè)中止條件中止條件：迭代次數(shù)、最小平方誤差MSE、簇中心點(diǎn)變化率K-means算法K-means算法過(guò)程記K個(gè)簇中心分別為a1,a2,...ak；每個(gè)簇的樣本數(shù)量為N1,N2,...,NK;使用平方誤差作為目標(biāo)函數(shù)(使用歐幾里得距離)，公式為：K-means算法要獲取最優(yōu)解，也就是目標(biāo)函數(shù)需要盡可能的小，對(duì)J函數(shù)求偏導(dǎo)數(shù)，可以得到簇中心點(diǎn)a更新的公式為：思考：如果使用其它距離度量公式，簇中心點(diǎn)更新公式是啥?K-means算法在迭代的過(guò)程中使用所有點(diǎn)的均值作為新的質(zhì)點(diǎn)(中心點(diǎn))，如果簇中存在異常點(diǎn)，將導(dǎo)致均值偏差比較嚴(yán)重比如一個(gè)簇中有2、4、6、8、100五個(gè)數(shù)據(jù)，那么新的質(zhì)點(diǎn)為24，顯然這個(gè)質(zhì)點(diǎn)離絕大多數(shù)點(diǎn)都比較遠(yuǎn)；在當(dāng)前情況下，使用中位數(shù)6可能比使用均值的想法更好，使用中位數(shù)的聚類(lèi)方式叫做K-Mediods聚類(lèi)(K中值聚類(lèi))K-means算法是初值敏感的，選擇不同的初始值可能導(dǎo)致不同的簇劃分規(guī)則為了避免這種敏感性導(dǎo)致的最終結(jié)果異常性，可以采用初始化多套初始節(jié)點(diǎn)構(gòu)造不同的分類(lèi)規(guī)則，然后選擇最優(yōu)的構(gòu)造規(guī)則K-means算法思考K-means算法的初值敏感缺點(diǎn)：K值是用戶給定的，在進(jìn)行數(shù)據(jù)處理前，K值是未知的，不同的K值得到的結(jié)果也不一樣；對(duì)初始簇中心點(diǎn)是敏感的不適合發(fā)現(xiàn)非凸形狀的簇或者大小差別較大的簇特殊值(離群值)對(duì)模型的影響比較大優(yōu)點(diǎn)：理解容易，聚類(lèi)效果不錯(cuò)處理大數(shù)據(jù)集的時(shí)候，該算法可以保證較好的伸縮性和高效率當(dāng)簇近似高斯分布的時(shí)候，效果非常不錯(cuò)K-means算法優(yōu)缺點(diǎn)基于scikit包中的創(chuàng)建模擬數(shù)據(jù)的API創(chuàng)建聚類(lèi)數(shù)據(jù)，使用K-means算法對(duì)數(shù)據(jù)進(jìn)行分類(lèi)操作，并獲得聚類(lèi)中心點(diǎn)以及總的樣本簇中心點(diǎn)距離和值K-means案例K-means案例解決K-Means算法對(duì)初始簇心比較敏感的問(wèn)題，二分K-Means算法是一種弱化初始質(zhì)心的一種算法，具體思路步驟如下：將所有樣本數(shù)據(jù)作為一個(gè)簇放到一個(gè)隊(duì)列中從隊(duì)列中選擇一個(gè)簇進(jìn)行K-means算法劃分，劃分為兩個(gè)子簇，并將子簇添加到隊(duì)列中循環(huán)迭代第二步操作，直到中止條件達(dá)到(聚簇?cái)?shù)量、最小平方誤差、迭代次數(shù)等)隊(duì)列中的簇就是最終的分類(lèi)簇集合從隊(duì)列中選擇劃分聚簇的規(guī)則一般有兩種方式；分別如下：對(duì)所有簇計(jì)算誤差和SSE(SSE也可以認(rèn)為是距離函數(shù)的一種變種)，選擇SSE最大的聚簇進(jìn)行劃分操作(優(yōu)選這種策略)選擇樣本數(shù)據(jù)量最多的簇進(jìn)行劃分操作二分K-Means算法二分K-Means算法解決K-Means算法對(duì)初始簇心比較敏感的問(wèn)題，K-Means++算法和K-Means算法的區(qū)別主要在于初始的K個(gè)中心點(diǎn)的選擇方面，K-Means算法使用隨機(jī)給定的方式，K-Means++算法采用下列步驟給定K個(gè)初始質(zhì)點(diǎn)：從數(shù)據(jù)集中任選一個(gè)節(jié)點(diǎn)作為第一個(gè)聚類(lèi)中心對(duì)數(shù)據(jù)集中的每個(gè)點(diǎn)x，計(jì)算x到所有已有聚類(lèi)中心點(diǎn)的距離和D(X)，基于D(X)采用線性概率選擇出下一個(gè)聚類(lèi)中心點(diǎn)(距離較遠(yuǎn)的一個(gè)點(diǎn)成為新增的一個(gè)聚類(lèi)中心點(diǎn))重復(fù)步驟2直到找到k個(gè)聚類(lèi)中心點(diǎn)缺點(diǎn)：由于聚類(lèi)中心點(diǎn)選擇過(guò)程中的內(nèi)在有序性，在擴(kuò)展方面存在著性能方面的問(wèn)題(第k個(gè)聚類(lèi)中心點(diǎn)的選擇依賴前k-1個(gè)聚類(lèi)中心點(diǎn)的值)K-Means++算法解決K-Means++算法缺點(diǎn)而產(chǎn)生的一種算法；主要思路是改變每次遍歷時(shí)候的取樣規(guī)則，并非按照K-Means++算法每次遍歷只獲取一個(gè)樣本，而是每次獲取K個(gè)樣本，重復(fù)該取樣操作O(logn)次，然后再將這些抽樣出來(lái)的樣本聚類(lèi)出K個(gè)點(diǎn)，最后使用這K個(gè)點(diǎn)作為K-Means算法的初始聚簇中心點(diǎn)。實(shí)踐證明：一般5次重復(fù)采用就可以保證一個(gè)比較好的聚簇中心點(diǎn)。K-Means||算法Canopy算法屬于一種“粗”聚類(lèi)算法，執(zhí)行速度較快，但精度較低，算法執(zhí)行步驟如下：給定樣本列表L=x1,x,2...,xm以及先驗(yàn)值r1和r2(r1>r2)從列表L中獲取一個(gè)節(jié)點(diǎn)P，計(jì)算P到所有聚簇中心點(diǎn)的距離(如果不存在聚簇中心，那么此時(shí)點(diǎn)P形成一個(gè)新的聚簇)，并選擇出最小距離D(P,aj)如果距離D小于r1，表示該節(jié)點(diǎn)屬于該聚簇，添加到該聚簇列表中如果距離D小于r2，表示該節(jié)點(diǎn)不僅僅屬于該聚簇，還表示和當(dāng)前聚簇中心點(diǎn)非常近，所以將該聚簇的中心點(diǎn)設(shè)置為P，并將P從列表L中刪除如果距離D大于r1，那么節(jié)點(diǎn)P形成一個(gè)新的聚簇直到列表L中的元素?cái)?shù)據(jù)不再有變化或者元素?cái)?shù)量為0的時(shí)候，結(jié)束循環(huán)操作Canopy算法Canopy算法得到的最終結(jié)果的值，聚簇之間是可能存在重疊的，但是不會(huì)存在某個(gè)對(duì)象不屬于任何聚簇的情況Canopy算法Canopy算法過(guò)程圖形說(shuō)明由于K-Means算法存在初始聚簇中心點(diǎn)敏感的問(wèn)題，常用使用Canopy+K-Means算法混合形式進(jìn)行模型構(gòu)建先使用canopy算法進(jìn)行“粗”聚類(lèi)得到K個(gè)聚類(lèi)中心點(diǎn)K-Means算法使用Canopy算法得到的K個(gè)聚類(lèi)中心點(diǎn)作為初始中心點(diǎn)，進(jìn)行“細(xì)”聚類(lèi)優(yōu)點(diǎn)：執(zhí)行速度快(先進(jìn)行了一次聚簇中心點(diǎn)選擇的預(yù)處理)不需要給定K值，應(yīng)用場(chǎng)景多能夠緩解K-Means算法對(duì)于初始聚類(lèi)中心點(diǎn)敏感的問(wèn)題Canopy算法常用應(yīng)用場(chǎng)景MiniBatchK-Means算法是K-Means算法的一種優(yōu)化變種，采用小規(guī)模的數(shù)據(jù)子集(每次訓(xùn)練使用的數(shù)據(jù)集是在訓(xùn)練算法的時(shí)候隨機(jī)抽取的數(shù)據(jù)子集)減少計(jì)算時(shí)間，同時(shí)試圖優(yōu)化目標(biāo)函數(shù)；MiniBatchK-Means算法可以減少K-Means算法的收斂時(shí)間，而且產(chǎn)生的結(jié)果效果只是略差于標(biāo)準(zhǔn)K-Means算法算法步驟如下：首先抽取部分?jǐn)?shù)據(jù)集，使用K-Means算法構(gòu)建出K個(gè)聚簇點(diǎn)的模型繼續(xù)抽取訓(xùn)練數(shù)據(jù)集中的部分?jǐn)?shù)據(jù)集樣本數(shù)據(jù)，并將其添加到模型中，分配給距離最近的聚簇中心點(diǎn)更新聚簇的中心點(diǎn)值循環(huán)迭代第二步和第三步操作，直到中心點(diǎn)穩(wěn)定或者達(dá)到迭代次數(shù)，停止計(jì)算操作MiniBatchK-Means算法基于scikit包中的創(chuàng)建模擬數(shù)據(jù)的API創(chuàng)建聚類(lèi)數(shù)據(jù)，使用K-means算法和MiniBatchK-Means算法對(duì)數(shù)據(jù)進(jìn)行分類(lèi)操作，比較這兩種算法的聚類(lèi)效果以及聚類(lèi)的消耗時(shí)間長(zhǎng)度K-Means和MiniBatchK-Means算法比較案例K-Means和MiniBatchK-Means算法比較案例混淆矩陣均一性完整性V-measure調(diào)整蘭德系數(shù)(ARI)調(diào)整互信息(AMI)輪廓系數(shù)(Silhouette)聚類(lèi)算法的衡量指標(biāo)均一性：一個(gè)簇中只包含一個(gè)類(lèi)別的樣本，則滿足均一性；其實(shí)也可以認(rèn)為就是正確率(每個(gè)聚簇中正確分類(lèi)的樣本數(shù)占該聚簇總樣本數(shù)的比例和)聚類(lèi)算法的衡量指標(biāo)1完整性：同類(lèi)別樣本被歸類(lèi)到相同簇中，則滿足完整性；每個(gè)聚簇中正確分類(lèi)的樣本數(shù)占該類(lèi)型的總樣本數(shù)比例的和V-measure：均一性和完整性的加權(quán)平均Randindex(蘭德指數(shù))(RI)，RI取值范圍為[0,1]，值越大意味著聚類(lèi)結(jié)果與真實(shí)情況越吻合。聚類(lèi)算法的衡量指標(biāo)-ARI其中C表示實(shí)際類(lèi)別信息，K表示聚類(lèi)結(jié)果，a表示在C與K中都是同類(lèi)別的元素對(duì)數(shù)，b表示在C與K中都是不同類(lèi)別的元素對(duì)數(shù)，

表示數(shù)據(jù)集中可以組成的對(duì)數(shù)調(diào)整蘭德系數(shù)(ARI，AdjustedRndIndex)，ARI取值范圍[-1,1]，值越大，表示聚類(lèi)結(jié)果和真實(shí)情況越吻合。從廣義的角度來(lái)將，ARI是衡量?jī)蓚€(gè)數(shù)據(jù)分布的吻合程度的。調(diào)整互信息(AMI，AdjustedMutualInformation)，類(lèi)似ARI，內(nèi)部使用信息熵聚類(lèi)算法的衡量指標(biāo)-AMI簇內(nèi)不相似度：計(jì)算樣本i到同簇其它樣本的平均距離為ai;ai越小，表示樣本i越應(yīng)該被聚類(lèi)到該簇，簇C中的所有樣本的ai的均值被稱為簇C的簇不相似度。簇間不相似度：計(jì)算樣本i到其它簇Cj的所有樣本的平均距離bij，bi=min{bi1,bi2,...,bik}；bi越大，表示樣本i越不屬于其它簇。輪廓系數(shù)：si值越接近1表示樣本i聚類(lèi)越合理，越接近-1，表示樣本i應(yīng)該分類(lèi)到另外的簇中，近似為0，表示樣本i應(yīng)該在邊界上；所有樣本的si的均值被成為聚類(lèi)結(jié)果的輪廓系數(shù)聚類(lèi)算法的衡量指標(biāo)-輪廓系數(shù)基于scikit包中的創(chuàng)建模擬數(shù)據(jù)的API創(chuàng)建聚類(lèi)數(shù)據(jù)，對(duì)K-Means算法和MiniBatchK-Means算法構(gòu)建的模型進(jìn)行評(píng)估K-Means和MiniBatchK-Means算法效果評(píng)估層次聚類(lèi)方法對(duì)給定的數(shù)據(jù)集進(jìn)行層次的分解，直到滿足某種條件為止，傳統(tǒng)的層次聚類(lèi)算法主要分為兩大類(lèi)算法：凝聚的層次聚類(lèi)：AGNES算法(AGglomerativeNESting)==>采用自底向上的策略。最初將每個(gè)對(duì)象作為一個(gè)簇，然后這些簇根據(jù)某些準(zhǔn)則被一步一步合并，兩個(gè)簇間的距離可以由這兩個(gè)不同簇中距離最近的數(shù)據(jù)點(diǎn)的相似度來(lái)確定；聚類(lèi)的合并過(guò)程反復(fù)進(jìn)行直到所有的對(duì)象滿足簇?cái)?shù)目。分裂的層次聚類(lèi)：DIANA算法(DIvisiveANALysis)==>采用自頂向下的策略。首先將所有對(duì)象置于一個(gè)簇中，然后按照某種既定的規(guī)則逐漸細(xì)分為越來(lái)越小的簇(比如最大的歐式距離)，直到達(dá)到某個(gè)終結(jié)條件(簇?cái)?shù)目或者簇距離達(dá)到閾值)。層次聚類(lèi)方法簡(jiǎn)單，理解容易合并點(diǎn)/分裂點(diǎn)選擇不太容易合并/分類(lèi)的操作不能進(jìn)行撤銷(xiāo)大數(shù)據(jù)集不太適合執(zhí)行效率較低O(t*n2)，t為迭代次數(shù)，n為樣本點(diǎn)數(shù)AGNES和DIANA算法優(yōu)缺點(diǎn)最小距離(SL聚類(lèi))兩個(gè)聚簇中最近的兩個(gè)樣本之間的距離(single/word-linkage聚類(lèi)法)最終得到模型容易形成鏈?zhǔn)浇Y(jié)構(gòu)最大距離(CL聚類(lèi))兩個(gè)聚簇中最遠(yuǎn)的兩個(gè)樣本的距離(complete-linkage聚類(lèi)法)如果存在異常值，那么構(gòu)建可能不太穩(wěn)定平均距離(AL聚類(lèi))兩個(gè)聚簇中樣本間兩兩距離的平均值(average-linkage聚類(lèi)法)兩個(gè)聚簇中樣本間兩兩距離的中值(median-linkage聚類(lèi)法)AGNES算法中簇間距離BIRCH算法(平衡迭代削減聚類(lèi)法)：聚類(lèi)特征使用3元組進(jìn)行一個(gè)簇的相關(guān)信息，通過(guò)構(gòu)建滿足分枝因子和簇直徑限制的聚類(lèi)特征樹(shù)來(lái)求聚類(lèi)，聚類(lèi)特征樹(shù)其實(shí)是一個(gè)具有兩個(gè)參數(shù)分枝因子和類(lèi)直徑的高度平衡樹(shù)；分枝因子規(guī)定了樹(shù)的每個(gè)節(jié)點(diǎn)的子女的最多個(gè)數(shù)，而類(lèi)直徑體現(xiàn)了對(duì)這一類(lèi)點(diǎn)的距離范圍；非葉子節(jié)點(diǎn)為它子女的最大特征值；聚類(lèi)特征樹(shù)的構(gòu)建可以是動(dòng)態(tài)過(guò)程的，可以隨時(shí)根據(jù)數(shù)據(jù)對(duì)模型進(jìn)行更新操作。優(yōu)缺點(diǎn)：適合大規(guī)模數(shù)據(jù)集，線性效率；只適合分布呈凸形或者球形的數(shù)據(jù)集、需要給定聚類(lèi)個(gè)數(shù)和簇直接的限制；層次聚類(lèi)優(yōu)化算法CURE算法(使用代表點(diǎn)的聚類(lèi)法)：該算法先把每個(gè)數(shù)據(jù)點(diǎn)看成一類(lèi)，然后合并距離最近的類(lèi)直至類(lèi)個(gè)數(shù)為所要求的個(gè)數(shù)為止。但是和AGNES算法的區(qū)別是：取消了使用所有點(diǎn)或用中心點(diǎn)+距離來(lái)表示一個(gè)類(lèi)，而是從每個(gè)類(lèi)中抽取固定數(shù)量、分布較好的點(diǎn)作為此類(lèi)的代表點(diǎn)，并將這些代表點(diǎn)乘以一個(gè)適當(dāng)?shù)氖湛s因子，使它們更加靠近類(lèi)中心點(diǎn)。代表點(diǎn)的收縮特性可以調(diào)整模型可以匹配那些非球形的場(chǎng)景，而且收縮因子的使用可以減少噪音對(duì)聚類(lèi)的影響優(yōu)缺點(diǎn)：能夠處理非球形分布的應(yīng)用場(chǎng)景采用隨機(jī)抽樣和分區(qū)的方式可以提高算法的執(zhí)行效率層次聚類(lèi)優(yōu)化算法基于scikit的API創(chuàng)建模擬數(shù)據(jù)，使用BRICH算法對(duì)數(shù)據(jù)進(jìn)行聚類(lèi)操作，并比較n_clusters參數(shù)的作用BRICH算法案例BRICH算法案例密度聚類(lèi)方法的指導(dǎo)思想:只要樣本點(diǎn)的密度大于某個(gè)閾值，則將該樣本添加到最近的簇中這類(lèi)算法可以克服基于距離的算法只能發(fā)現(xiàn)凸聚類(lèi)的缺點(diǎn)，可以發(fā)現(xiàn)任意形狀的聚類(lèi)，而且對(duì)噪聲數(shù)據(jù)不敏感。計(jì)算復(fù)雜度高，計(jì)算量大常用算法：DBSCAN密度最大值算法密度聚類(lèi)方法DBSCAN(Density-BasedSpatialClusteringofApplicationswithNoise)一個(gè)比較有代表性的基于密度的聚類(lèi)算法，相比于基于劃分的聚類(lèi)方法和層次聚類(lèi)方法，DBSCAN算法將簇定義為密度相連的點(diǎn)的最大集合，能夠?qū)⒆銐蚋呙芏鹊膮^(qū)域劃分為簇，并且在具有噪聲的空間數(shù)據(jù)商能夠發(fā)現(xiàn)任意形狀的簇。DBSCAN算法的核心思想是：用一個(gè)點(diǎn)的ε鄰域內(nèi)的鄰居點(diǎn)數(shù)衡量該點(diǎn)所在空間的密度，該算法可以找出形狀不規(guī)則的cluster，而且聚類(lèi)的時(shí)候事先不需要給定cluster的數(shù)量DBSCAN算法ε鄰域(εneighborhood，也稱為Eps)：給定對(duì)象在半徑ε內(nèi)的區(qū)域DBSCAN算法基本概念1密度(density)：ε鄰域中x的密度，是一個(gè)整數(shù)值，依賴于半徑εMinPts定義核心點(diǎn)時(shí)的閾值，也簡(jiǎn)記為M核心點(diǎn)(corepoint)：如果p(x)>=M,那么稱x為X的核心點(diǎn)；記由X中所有核心點(diǎn)構(gòu)成的集合為Xc，并記Xnc=X\Xc表示由X中所有非核心點(diǎn)構(gòu)成的集合。直白來(lái)講，核心點(diǎn)對(duì)應(yīng)于稠密區(qū)域內(nèi)部的點(diǎn)。噪音點(diǎn)(noisepoint)：集合中除了邊界點(diǎn)和核心點(diǎn)之外的點(diǎn)都是噪音點(diǎn)，所有噪音點(diǎn)組成的集合叫做Xnoi；直白來(lái)講，噪音點(diǎn)對(duì)應(yīng)稀疏區(qū)域的點(diǎn)。DBSCAN算法基本概念2邊界點(diǎn)(borderpoint):如果非核心點(diǎn)x的ε鄰域中存在核心點(diǎn)，那么認(rèn)為x為X的邊界點(diǎn)。由X中所有的邊界點(diǎn)構(gòu)成的集合為Xbd。直白來(lái)將，邊界點(diǎn)對(duì)應(yīng)稠密區(qū)域邊緣的點(diǎn)。DBSCAN算法基本概念3直接密度可達(dá)(directlydensity-reachable)：給定一個(gè)對(duì)象集合X，如果y是在x的ε鄰域內(nèi)，而且x是一個(gè)核心對(duì)象，可以說(shuō)對(duì)象y從對(duì)象x出發(fā)是直接密度可達(dá)的密度可達(dá)(density-reachable)：如果存在一個(gè)對(duì)象鏈p1,p2,..pm,如果滿足pi+1是從pi直接密度可達(dá)的，那么稱pm是從p1密度可達(dá)的密度相連(density-connected)：在集合X中，如果存在一個(gè)對(duì)象o，使得對(duì)象x和y是從o關(guān)于ε和m密度可達(dá)的，那么對(duì)象x和y是關(guān)于ε和m密度相連的DBSCAN算法基本概念4簇(cluster)：一個(gè)基于密度的簇是最大的密度相連對(duì)象的集合C；滿足以下兩個(gè)條件：Maximality：若x屬于C，而且y是從x密度可達(dá)的，那么y也屬于CConnectivity：若x屬于C，y也屬于C，則x和y是密度相連的DBSCAN算法流程算法流程：如果一個(gè)點(diǎn)x的ε鄰域包含多余m個(gè)對(duì)象，則創(chuàng)建一個(gè)x作為核心對(duì)象的新簇；尋找并合并核心對(duì)象直接密度可達(dá)的對(duì)象；沒(méi)有新點(diǎn)可以更新簇的時(shí)候，算法結(jié)束。算法特征描述:每個(gè)簇至少包含一個(gè)核心對(duì)象非核心對(duì)象可以是簇的一部分，構(gòu)成簇的邊緣包含過(guò)少對(duì)象的簇被認(rèn)為是噪聲DBSCAN算法優(yōu)缺點(diǎn)優(yōu)點(diǎn)：不需要事先給定cluster的數(shù)目可以發(fā)現(xiàn)任意形狀的cluster能夠找出數(shù)據(jù)中的噪音，且對(duì)噪音不敏感算法只需要兩個(gè)輸入?yún)?shù)聚類(lèi)結(jié)果幾乎不依賴節(jié)點(diǎn)的遍歷順序缺點(diǎn)：DBSCAN算法聚類(lèi)效果依賴距離公式的選取，最常用的距離公式為歐幾里得距離。但是對(duì)于高維數(shù)據(jù)，由于維數(shù)太多，距離的度量已變得不是那么重要DBSCAN算法不適合數(shù)據(jù)集中密度差異很大的情況MDCA(MaximumDensityClusteringApplication)算法基于密度的思想引入劃分聚類(lèi)中，使用密度而不是初始點(diǎn)作為考察簇歸屬情況的依據(jù)，能夠自動(dòng)確定簇?cái)?shù)量并發(fā)現(xiàn)任意形狀的簇；另外MDCA一般不保留噪聲，因此也避免了閾值選擇不當(dāng)情況下造成的對(duì)象丟棄情況。MDCA算法的基本思路是尋找最高密度的對(duì)象和它所在的稠密區(qū)域；MDCA算法在原理上來(lái)講，和密度的定義沒(méi)有關(guān)系，采用任意一種密度定義公式均可，一般情況下采用DBSCAN算法中的密度定義方式密度最大值聚類(lèi)算法(MDCA)最大密度點(diǎn)：MDCA概念1有序序列:根據(jù)所有對(duì)象與pmax的距離對(duì)數(shù)據(jù)重新排序密度閾值density0；當(dāng)節(jié)點(diǎn)的密度值大于密度閾值的時(shí)候，認(rèn)為該節(jié)點(diǎn)屬于一個(gè)比較固定的簇，在第一次構(gòu)建基本簇的時(shí)候，就將這些節(jié)點(diǎn)添加到對(duì)應(yīng)簇中，如果小于這個(gè)值的時(shí)候，暫時(shí)認(rèn)為該節(jié)點(diǎn)為噪聲節(jié)點(diǎn)。簇間距離：對(duì)于兩個(gè)簇C1和C2之間的距離，采用兩個(gè)簇中最近兩個(gè)節(jié)點(diǎn)之間的距離作為簇間距離。MDCA概念2聚簇距離閾值dist0：當(dāng)兩個(gè)簇的簇間距離小于給定閾值的時(shí)候，這兩個(gè)簇的結(jié)果數(shù)據(jù)會(huì)進(jìn)行合并操作。M值：初始簇中最多數(shù)據(jù)樣本個(gè)數(shù)MDCA算法聚類(lèi)過(guò)程步驟如下：將數(shù)據(jù)集劃分為基本簇；對(duì)數(shù)據(jù)集X選取最大密度點(diǎn)Pmax，形成以最大密度點(diǎn)為核心的新簇Ci，按照距離排序計(jì)算出序列Spmax,對(duì)序列的前M個(gè)樣本數(shù)據(jù)進(jìn)行循環(huán)判斷，如果節(jié)點(diǎn)的密度大于等于density0，那么將當(dāng)前節(jié)點(diǎn)添加Ci中；循環(huán)處理剩下的數(shù)據(jù)集X，選擇最大密度點(diǎn)Pmax，并構(gòu)建基本簇Ci+1，直到X中剩余的樣本數(shù)據(jù)的密度均小于density0使用凝聚層次聚類(lèi)的思想，合并較近的基本簇，得到最終的簇劃分；在所有簇中選擇距離最近的兩個(gè)簇進(jìn)行合并，合并要求是：簇間距小于等于dist0,如果所有簇中沒(méi)有簇間距小于dist0的時(shí)候，結(jié)束合并操作處理剩余節(jié)點(diǎn)，歸入最近的簇最常用、最簡(jiǎn)單的方式是：將剩余樣本對(duì)象歸入到最近的簇MDCA使用scikit的相關(guān)API創(chuàng)建模擬數(shù)據(jù)，然后使用DBSCAN密度聚類(lèi)算法進(jìn)行數(shù)據(jù)聚類(lèi)操作，并比較DBSCAN算法在不同參數(shù)情況下的密度聚類(lèi)效果密度聚類(lèi)算法案例密度聚類(lèi)算法案例密度聚類(lèi)算法案例譜聚類(lèi)是基于譜圖理論基礎(chǔ)上的一種聚類(lèi)方法，與傳統(tǒng)的聚類(lèi)方法相比：具有在任意形狀的樣本空間上聚類(lèi)并且收斂于全局最優(yōu)解的優(yōu)點(diǎn)。通過(guò)對(duì)樣本數(shù)據(jù)的拉普拉斯矩陣的特征向量進(jìn)行聚類(lèi)，從而達(dá)到對(duì)樣本數(shù)據(jù)進(jìn)行聚類(lèi)的目的；其本質(zhì)是將聚類(lèi)問(wèn)題轉(zhuǎn)換為圖的最優(yōu)劃分問(wèn)題，是一種點(diǎn)對(duì)聚類(lèi)算法。譜聚類(lèi)算法將數(shù)據(jù)集中的每個(gè)對(duì)象看做圖的頂點(diǎn)V，將頂點(diǎn)間的相似度量化為相應(yīng)頂點(diǎn)連接邊E的權(quán)值w，這樣就構(gòu)成了一個(gè)基于相似度的無(wú)向加權(quán)圖G(V,E)，于是聚類(lèi)問(wèn)題就轉(zhuǎn)換為圖的劃分問(wèn)題?；趫D的最優(yōu)劃分規(guī)則就是子圖內(nèi)的相似度最大，子圖間的相似度