資料和演算法的相愛相殺（二）：常見的聚類演算法

以下是資料與演算法相愛相殺的第二篇，常見的聚類演算法。如果按正常的資料和演算法知識體系，這時候應該講一下常用的資料查詢或演算法的數學基礎，但是觀眾老爺多是PM，恐不感興趣或沒有基礎。所以我就從應用和實戰的角度給大家直接上乾貨，在過程中介紹其用到的數學或計算機知識。

聚類演算法應該是大資料分析中最常見一類演算法，在一般網際網路公司中，哪怕不借助演算法，我們也經常需要對使用者、客戶進行分類，進行人群畫像，以支援差異化服務或營銷。所以說聚類這件事情我們一直在做，而藉助資料規模和演算法優勢則可以讓我們分類更加精準、多元、客觀。

常見的聚類演算法包括：層次化聚類演算法、劃分式聚類演算法、基於密度的聚類演算法、基於網格的聚類演算法、基於模型的聚類演算法等，以及現在比較火的基於粒度的聚類等。

我沒有打算做聚類演算法的科普，也不做其發展來龍去脈的論文，就從一般網際網路公司能用到，各位看官可以拿來就用的角度分享一下常見的演算法。

1、基於空間測距的k-means算法系列

k-means演算法是一種經典的分類演算法，它的基本原理是，視所有的資料為多維空間的點，如一名普通使用者（擁有：月消費頻次、消費金額、最近一次消費時間等眾多的消費資料），他每一個我們用於分析的資料都看作是一個維度。

這樣我們就得出了該使用者的位置，透過定義數個（即k個）中心點（中心點由機器隨機尋找），測算使用者與各中心點的距離並進行比較，將該使用者加入距離最近的中心點，這樣就形成了不同的圈層。

明眼的觀眾可能已經看到，如果某點對所有中心點距離的最小值存在相同的，那這個點應該加入哪個圈層呢？

這時候就原來的中心點變成圈層的幾何中心，從新測算距離，直到所有的點全包包含在某一個圈層中。

k-means演算法的優點是簡單高效、時間複雜度、空間複雜度都比較低，而且對於資料規模也不感冒，這對追求效率和消費者體驗的網際網路公司至關重要。

但是其需要預設k值，k值的選擇會很大程度上影響聚類，使用者資料缺失的情況對結果也有很大影響，同時對髒資料和離群值也很敏感。所以人們又改良了k-means演算法，具體如下，大家選擇學習。

為了解決預設k值不準確問題，延伸出了k-means++等眾多演算法。其基本原理是：在選擇初始中心之前，對所有資料進行一次計算，使得選擇的初始聚類中心之間的距離儘可能的遠，同時也減少了計算量。

2、基於空間測距的CURE演算法

層次聚類的核心原理是：先將每個物件作為一個組（簇），然後根據兩兩之間的距離合並這些原子組為越來越大的組，直到所有物件都在一個組中，或者條件滿足（達到了你想要的組個數）。

它的計算流程是：

每個物件作為一類，計算兩者這件最小距離>將兩個 合併成一個新類，形成新的中心>計算所有類之間的距離，然後兩兩合併>直到合併完成或達到要求。

常見的層次聚類演算法有：

CURE演算法、ROCK演算法

等，其基本原理都一樣，不過是各有所長。

3、基於密度劃分的DBSCAN演算法

上文中我們講到了基於空間距離的聚類演算法，這類演算法最終形成的多是“圓形”的元素類，而基於度劃分的DBSCAN演算法核心是：預先定義兩個變數，

一個表示球形的半徑，一個表示球形內的點。

只要一個區域中的點的密度（即：球內的點/球的體積）大過某個閾值，就把球形相近的點加到與之相近的聚類中去。

在DBSCAN中的點分為核心點：在球形範圍核心（稠密）的點；

邊界點：處於球形邊界之內，但離核心較遠的點，處於球形範圍之外的點。

DBSCAN也存在一定的缺陷，一方面是對於高維資料不能很好的反映，另一方面是在聚類密度不斷變化的資料集中，不能很好地反映整體聚類情況。

以上幾種演算法，基本夠PM們在日常使用，啟迪思維，方便交流。

除了以上幾種常用的聚類分析演算法之外，還有一些聚類演算法（均值漂移演算法、網格演算法、模型演算法），如果大家有時間可以查詢資繼續學習。