《看見到洞見》系列文章匯聚、分享的是綠盟科技創新中心對于數據分析在安全領域應用的技戰術思考與經驗，力求由淺入深層次遞進，實戰到方法論雙線剖析。此文為系列文章之引子第二篇，深入淺出的對常用的數據分析和機器學習的算法進行介紹。

在上一篇中，我們介紹了幾種常用的監督學習方法。在本篇中，我們介紹無監督學習方法中的聚類方法。聚類是在高維度的未標注數據中尋找特征的一系列方法。其思想是按照某個特定標準（如距離準則）把一個數據集分割成不同的類或簇，使得同一個簇內的數據對象的相似性盡可能大，同時不在同一個簇中的數據對象的差異性也盡可能的大。即聚類后同一類的數據盡可能聚集到一起，不同數據盡量分離。由于聚類算法不需要有標簽的數據，所以聚類算法在很多領域得到了廣泛的應用，如模式識別、數據分析、圖像處理、市場研究、客戶分割、Web文檔分類等。本篇將介紹K-means聚類，層次聚類和DBSCAN聚類三種聚類算法。

文章目錄

????????K-means聚類

• 層次聚類算法

• DBSCAN

K-means聚類

K-means聚類算法是一種應用非常廣泛的聚類方法，是一種劃分聚類方法。其基本思想為：給定一個包含n個對象的數據集，K-means聚類算法可以構建數據的k個劃分，每個劃分就是一個簇，并且滿足：

????1、每個簇至少包含一個對象。

????2、每個對象必須屬于并且僅屬于一個簇。

K-means算法的流程如圖 1所示。

當結果簇是密集的，而且簇和簇之間的區別比較明顯時，K-means的效果較好。對于大數據集，K-means是相對可伸縮的和高效的，它的復雜度是O(nkt)，其中，n是對象的個數，k是簇的數目，t是迭代的次數。

K-means的最大問題是要求先給出k的個數。k的選擇一般基于經驗值和多次實驗結果。對于不同的數據集，k的取值沒有可借鑒性。另外，K-means對孤立數據點是敏感的，少量噪聲數據就能對平均值造成極大的影響。

層次聚類算法

與K-means算法不同，層次聚類算法不再產生單一聚類，而是產生一個聚類層次，也就是說產生一棵層次樹。層次聚類算法最多包含n步，其中，n是數據集中對象的數量。每一步執行的操作就是在前面步驟的聚類基礎上生成新聚類。層次聚類算法的流程如圖 2所示。

1、將每個對象歸為一類, 共得到n類，每類僅包含一個對象。類與類之間的距離就是它們所包含的對象之間的距離。

2、找到最接近的兩個類并合并成一類，于是總的類數少了一個。

3、重新計算新的類與所有舊類之間的距離。

4、重復第2步和第3步，直到最后合并成一個類為止（此類包含了n個對象）。

由于這種聚類算法迭代合并所有分類，所以這種層次聚類稱為“凝聚”法。也有一種“劃分”層次聚類法，與“凝聚”相反，它先將所有對象放在同一類中，并不斷劃分成更小的類，劃分法一般很少使用。

DBSCAN

（Density-Based Spatial Clustering of Applications with Noise，具有噪聲的基于密度的聚類方法）

DBSCAN是一種基于密度的空間聚類算法。該算法將具有足夠密度的區域劃分為簇，并能夠在具有噪聲的空間數據庫中發現任意形狀的簇。

DBSCAN算法基于一個事實：一個聚類可以由其中的任何核心對象唯一確定。等價可以表述為：任一滿足核心對象條件的數據對象p，數據集D中所有從p密度可達的數據對象o所組成的集合構成了一個完整的聚類C，且p屬于C。

算法流程可以描述為：掃描整個數據集，找到任意一個核心點，對該核心點進行擴充。擴充的方法是尋找從該核心點出發的所有密度相連的數據點（注意是密度相連）。遍歷該核心點的鄰域內的所有核心點（因為邊界點是無法擴充的），尋找與這些數據點密度相連的點，直到沒有可以擴充的數據點為止。最后聚類成的簇的邊界節點都是非核心數據點。之后就是重新掃描數據集（不包括之前尋找到的簇中的任何數據點），尋找沒有被聚類的核心點，再重復上面的步驟，對該核心點進行擴充直到數據集中沒有新的核心點為止。數據集中沒有包含在任何簇中的數據點就構成異常點。

DBSCAN算法的顯著優點是聚類速度快且能夠有效處理噪聲點和發現任意形狀的空間聚類。與K-means算法比較，DBSCAN算法不需要輸入要劃分的聚類個數。但是由于它直接對整個數據庫進行操作，且進行聚類時使用了一個全局性的表征密度的參數，因此也具有兩個比較明顯的弱點：

????1、當數據量增大時，要求較大的內存支持，I/O消耗也很大。

????2、當空間聚類的密度不均勻、聚類間距差相差很大時，聚類質量較差。

小結：本篇介紹了無監督學習的聚類算法中常用到的三種方法。至此機器學習算法方面的介紹也暫告一段落。

轉自網站：綠盟科技博客

網站鏈接：http://blog.nsfocus.net/

文章鏈接：http://blog.nsfocus.net/machine-learning-algorithm2/

版權歸原作者所有，轉載僅供學習使用，不用于任何商業用途，如有侵權請留言聯系刪除，感謝合作。

數據與算法之美

用數據解決不可能

長按掃碼關注

總結

以上是生活随笔為你收集整理的看见到洞见之引子（二）机器学习算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。