本章目錄01

無監督學習概述02K-means聚類03密度聚類和層次聚類04聚類的評價指標1.無監督學習概述01

無監督學習概述02K-means聚類03密度聚類和層次聚類04聚類的評價指標1.無監督學習方法概述

監督學習和無監督學習的區別1.無監督學習方法概述聚類（Clustering）如何將教室里的學生按愛好、身高劃分為5類？降維（DimensionalityReduction）如何將將原高維空間中的數據點映射到低維度的空間中？關聯規則（AssociationRules）很多買尿布的男顧客，同時買了啤酒，可以從中找出什么規律來提高超市銷售額？推薦系統（Recommendersystems）很多客戶經常上網購物，根據他們的瀏覽商品的習慣，給他們推薦什么商品呢？主要的無監督學習方法1.無監督學習方法概述主要算法K-means、密度聚類、層次聚類聚類主要應用市場細分、文檔聚類、圖像分割、圖像壓縮、聚類分析、特征學習或者詞典學習、確定犯罪易發地區、保險欺詐檢測、公共交通數據分析、IT資產集群、客戶細分、識別癌癥數據、搜索引擎應用、醫療應用、藥物活性預測……1.無監督學習方法概述聚類案例1.醫療醫生可以使用聚類算法來發現疾病。以甲狀腺疾病為例。當我們對包含甲狀腺疾病和非甲狀腺疾病的數據集應用無監督學習時，可以使用聚類算法來識別甲狀腺疾病數據集。1.無監督學習方法概述聚類案例2.市場細分為了吸引更多的客戶，每家公司都在開發易于使用的功能和技術。為了了解客戶，公司可以使用聚類。聚類將幫助公司了解用戶群，然后對每個客戶進行歸類。這樣，公司就可以了解客戶，發現客戶之間的相似之處，并對他們進行分組。1.無監督學習方法概述聚類案例3.金融業銀行可以觀察到可能的金融欺詐行為，就此向客戶發出警告。在聚類算法的幫助下，保險公司可以發現某些客戶的欺詐行為，并調查類似客戶的保單是否有欺詐行為。1.無監督學習方法概述聚類案例4.搜索引擎百度是人們使用的搜索引擎之一。舉個例子，當我們搜索一些信息，如在某地的超市，百度將為我們提供不同的超市的選擇。這是聚類的結果，提供給你的結果就是聚類的相似結果。1.無監督學習方法概述聚類案例5.社交網絡比如在社交網絡的分析上。已知你朋友的信息，比如經常發email的聯系人，或是你的微博好友、微信的朋友圈，我們可運用聚類方法自動地給朋友進行分組，做到讓每組里的人們彼此都熟識。2.K-means聚類01

無監督學習概述02K-means聚類03密度聚類和層次聚類04聚類的評價指標聚類的背景知識--基本思想圖中的數據可以分成三個分開的點集(稱為簇)，一個能夠分出這些點集的算法，就被稱為聚類算法。聚類算法示例2.K-means聚類2.K-means聚類K-均值算法(K-means)算法概述K-means算法是一種無監督學習方法，是最普及的聚類算法，算法使用一個沒有標簽的數據集，然后將數據聚類成不同的組。K-means算法具有一個迭代過程，在這個過程中，數據集被分組成若干個預定義的不重疊的聚類或子組，使簇的內部點盡可能相似，同時試圖保持簇在不同的空間，它將數據點分配給簇，以便簇的質心和數據點之間的平方距離之和最小，在這個位置，簇的質心是簇中數據點的算術平均值。距離度量閔可夫斯基距離(Minkowskidistance)

歐氏距離：2.K-means聚類K-means算法流程1.選擇K個點作為初始質心。2.將每個點指派到最近的質心，形成K個簇。3.對于上一步聚類的結果，進行平均計算，得出該簇的新的聚類中心。4.重復上述兩步/直到迭代結束：質心不發生變化。2.K-means聚類初始化質心K-means算法流程首先，初始化稱為簇質心的任意點。初始化時，必須注意簇的質心必須小于訓練數據點的數目。因為該算法是一種迭代算法，接下來的兩個步驟是迭代執行的。2.K-means聚類K-means算法流程

簇賦值2.K-means聚類K-means算法流程第三步：移動質心，因為上面步驟中形成的簇沒有優化，所以需要形成優化的簇。為此，我們需要迭代地將質心移動到一個新位置。取一個簇的數據點，計算它們的平均值，然后將該簇的質心移動到這個新位置。對所有其他簇重復相同的步驟。迭代更新2.K-means聚類K-means算法流程優化上述兩個步驟是迭代進行的，直到質心停止移動，即它們不再改變自己的位置，并且成為靜態的。一旦這樣做，k-均值算法被稱為收斂。

K-均值的代價函數（又稱畸變函數

Distortionfunction）為：

的2.K-means聚類K-means優化過程

使用平方誤差作為目標函數:

推導：2.K-means聚類K-means算法流程現在，這個算法已經收斂，形成了清晰可見的不同簇。該算法可以根據簇在第一步中的初始化方式給出不同的結果。收斂2.K-means聚類初始化質心簇賦值迭代更新收斂K-means算法流程總結2.K-means聚類K值的選擇

K-均值的一個問題在于，它有可能會停留在一個局部最小值處，而這取決于初始化的情況。為了解決這個問題，我們通常需要多次運行K-均值算法，每一次都重新進行隨機初始化，最后再比較多次運行K-均值的結果，選擇代價函數最小的結果。

代價函數值肘點聚類數量K2.K-means聚類K-means的優點原理比較簡單，實現也是很容易，收斂速度快。聚類效果較優。算法的可解釋度比較強。主要需要調參的參數僅僅是簇數K。2.K-means聚類K-means的缺點需要預先指定簇的數量；如果有兩個高度重疊的數據，那么它就不能被區分，也不能判斷有兩個簇；歐幾里德距離可以不平等的權重因素，限制了能處理的數據變量的類型；有時隨機選擇質心并不能帶來理想的結果；無法處理異常值和噪聲數據；不適用于非線性數據集；對特征尺度敏感；如果遇到非常大的數據集，那么計算機可能會崩潰。3.密度聚類和層次聚類01

無監督學習概述02K-means聚類03密度聚類和層次聚類04聚類的評價指標密度聚類-DBSCAN背景知識：如果S中任兩點的連線內的點都在集合S內，那么集合S稱為凸集。反之，為非凸集。密度聚類-DBSCANDBSCAN密度聚類與劃分和層次聚類方法不同，DBSCAN(Density-BasedSpatialClusteringofApplicationswithNoise)是一個比較有代表性的基于密度的聚類算法。它將簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的區域劃分為簇，并可在噪聲的空間數據庫中發現任意形狀的聚類。密度：空間中任意一點的密度是以該點為圓心，以掃描半徑構成的圓區域內包含的點數目。密度聚類-DBSCANDBSCAN使用兩個超參數：掃描半徑(eps)和最小包含點數(minPts)來獲得簇的數量，而不是猜測簇的數目。掃描半徑(eps):用于定位點/檢查任何點附近密度的距離度量，即掃描半徑。最小包含點數(minPts)：聚集在一起的最小點數（閾值），該區域被認為是稠密的。密度聚類-DBSCANDBSCAN算法將數據點分為三類：1.核心點：在半徑Eps內含有超過MinPts數目的點。2.邊界點：在半徑Eps內點的數量小于MinPts,但是落在核心點的鄰域內的點。3.噪音點：既不是核心點也不是邊界點的點。邊界點：若其鄰域內點不超過MinPts個核心點：鄰域內點的個數超過MinPtsEpsMinPts=53.密度聚類和層次聚類DBSCAN密度聚類的算法流程1.將所有點標記為核心點、邊界點或噪聲點；2.如果選擇的點是核心點，則找出所有從該點出發的密度可達對象形成簇；3.如果該點是非核心點，將其指派到一個與之關聯的核心點的簇中；4.重復以上步驟，直到所點都被處理過P1P2P3P4P5P6P7P8P9P10P11P12P13X1224566791353Y2143879951212123舉例：有如下13個樣本點，使用DBSCAN進行聚類密度聚類-DBSCANDBSCAN密度聚類的算法流程

13121110987654321001234567891011P13P4P2P1P3P9P8P5P6P7P12P11P10對每個點計算其鄰域Eps=3內的點的集合。集合內點的個數超過MinPts=3的點為核心點。YX

密度聚類-DBSCANDBSCAN密度聚類的算法流程

13121110987654321001234567891011P13P4P2P1P3P9P8P5P6P7P12P11P10查看剩余點是否在核點的鄰域內，若在，則為邊界點，否則為噪聲點。邊界點

噪聲點XY

密度聚類-DBSCANDBSCAN密度聚類的算法流程

13121110987654321001234567891011P13P4P2P1P3P9P8P5P6P7P12P11P10將距離不超過Eps=3的點相互連接，構成一個簇，核心點鄰域內的點也會被加入到這個簇中。XY密度聚類-DBSCANDBSCAN的超參數DBSCAN超參數案例

圖片編號(a)(b)(c)(d)評價指標超參數eps=0.3minPts=10eps=0.1minPts=10eps=0.4minPts=10eps=0.3minPts=6估計的簇的數量31212估計的噪聲點18516213同一性0.95300.31280.00100.5365完整性0.88320.24890.05860.8623V-measure0.91700.02370.00200.6510ARI0.95170.267300.5414輪廓系數0.6255-0.36590.06110.3845(a)(c)(b)(d)這個案例中，當：eps=0.3，minPts=10的時候，DBSCAN達到最優效果。港口發現算法單拖船的作業規律比較清晰，出港后，全速駛向作業區域，在作業區域拖網作業，一個航次結束，全速駛向漁港，我們設計了一種基于DBSCAN和K-means的混合FindPort算法典型的單拖船一年的軌跡圖FindPort算法計算的漁港圖密度聚類應用通過單拖船軌跡推算港口范圍層次聚類層次聚類層次聚類假設簇之間存在層次結構，將樣本聚到層次化的簇中。層次聚類又有聚合聚類（自下而上）、分裂聚類（自上而下）兩種方法。因為每個樣本只屬于一個簇，所以層次聚類屬于硬聚類。背景知識：如果一個聚類方法假定一個樣本只能屬于一個簇，或簇的交集為空集，那么該方法稱為硬聚類方法。如果一個樣本可以屬于多個簇，或簇的交集不為空集，那么該方法稱為軟聚類方法。層次聚類AGENES聚合聚類分裂聚類edcc,d,ed,ea,b,c,d,ebaa,bDIANAStep0Step1Step2Step3Step4Step4Step3Step2Step1Step0層次聚類-聚合聚類聚合聚類開始將每個樣本各自分到一個簇；之后將相距最近的兩簇合并，建立一個新的簇；重復此操作直到滿足停止條件；得到層次化的類別。AGENES聚合聚類edcc,d,ed,ea,b,c,d,ebaa,bStep0Step4Step1Step2Step3聚類方向層次聚類-分裂聚類分裂聚類開始將所有樣本分到一個簇；之后將已有類中相距最遠的樣本分到兩個新的簇；重復此操作直到滿足停止條件；得到層次化的類別。DIANA分裂聚類edcc,d,ed,ea,b,c,d,ebaa,bStep4Step0Step3Step2Step1聚類方向4.聚類的評價指標01

無監督學習概述02K-means聚類03密度聚類和層次聚類04聚類的評價指標

4.聚類的評價指標

4.聚類的評價指標

4.聚類的評價指標ARI取值范圍為[?1,1]，值越大意味著聚類結果與真實情況越吻合。從廣義的角度來講，ARI衡量的是兩個數據分布的吻合程度參考文獻

[1]WongJAHA.AlgorithmAS136:AK-MeansClusteringAlgorithm[J].JournaloftheRoyalStatisticalSociety,1979,28(1):100-108.[2]EsterM.ADensity-BasedAlgorithmforDiscoveringClustersinLargeSpatialDatabaseswithNoise[J].P.conf.knowledgDiscovery&DataMining,1996.[3]AndrewNg.MachineLearning[EB/OL].StanfordUniversity,2014./course/ml[4]李航.統計學習