分群演算法 Cluster Analysis

Jockey Ng
4 min readJun 3, 2018

現今的市場是以顧客導向(Customer-Oriented)為主。在這競爭激烈的環境下,企業需要為顧客提 供適合的服務,以提升企業競爭力。因此,企業擁有更精確的顧客資訊,就可以制定較準確且有利 的策略。關聯規則(Association Rules)是從交易資料庫中挖掘大部分顧客的購買行為之不同產品之間 的關連性,更進一步的我們可以挖掘出顧客購買行為(Purchasing Behavior)模式和顧客特徵(Customer Profile)之間的關連性。建構及研發一個適合市場區隔(Market Segmentation)應用的多維度關聯規則探勘系統 (Multidimensional Association Rule Mining System)。利用條件式資料庫(Conditional Database)挖掘出包含顧客特徵與顧客購買行為的多維度關聯規則。結合集群(Clustering)的方法將數值屬性自動離散化(Discritization)。提供兩種不同角度的結果,可以提供決策者做市場區隔和制訂更為精確的市場策略:

  • 一個是在不同的客戶特徵下,去挖掘出經常被購買的產品 組合
  • 一個是在不同的產品組合之下,找出經常購買該產品的顧客特徵。

分群就像回歸一樣,有時候人們描述的是一種問題,有時候描述的是種演算法。分群演算法通常按照中心點或分層的方式對輸入資料進行歸併。所有的分群演算法都試圖找到資料的內在結構以便按照最大的共同點將資料進行歸類。

常見的分群演算法包含K-means演算法,階層式集群分析法(Hierarchical cluster analysis)和期望最大化演算法(Expectation Maximization / EM)。

階層式集群分析法(Hierarchical cluster analysis)

  • 根據觀察值或變項間的距離,將最相似物件結合在一起,以逐次聚合的方式 (agglomerative clustering),將觀察直分組。
  • 計算觀察值相似性最常用的方法是歐幾理得距離平方法(squared Euclidean distance)。歐幾理得距離平方法在計算觀察值的相異程度時,會隨著測量單位不同而 不同。

分群演算法屬於非監督式學習,通常被用於探索性的分析,是根據「物以類聚」的原理,將本身沒有類別的樣本聚整合不同的組,這樣的一組資料物件的集合叫做叢集,並且對每一個這樣的叢集進行描述的過程。它的目的是使得屬於同一叢集的樣本之間應該彼此相似,而不同叢集的樣本應該足夠不相似,常見的典型應用場景有客戶細分客戶研究市場細分價值評估。MLlib目前支援廣泛使用的KMmeans分群演算法。

案例:匯入訓練資料集,使用KMeans物件來將資料分群到兩個類別叢集當中,所需的類別叢集個數會被傳遞到演算法中,然後計算集內均方差總和(WSSSE),可以透過增加類別叢集的個數k來減小誤差。實際上,最佳的類別叢集數通常是1,因為這一點通常是WSSSE圖中的「低谷點」。

  • 載入和解析資料檔案
  • 設定反覆運算次數, e.g. 20
  • 設定類別叢集的個數, e.g. 2
  • 進行訓練
  • 統計分組錯誤的樣本比例

K-Means解析和實戰分群

分群演算法有時也被翻譯為叢集,其核心工作是將一組目標object劃分為許多個叢集,每個叢集之間的object盡可能相似,叢集與叢集之間的object盡可能相異。分群演算法是機器學習(或說是資料採擷更合適)中重要的一部分,除了最為簡單的K-Means分群演算法外,比較常見的還有層次法(CURE 、CHAMELEON等),網格演算法(STING、WaveCluster等),等等。

較權威的分群問題定義:所謂分群問題,就是指定一個元素集合D,其中每個元素具有n個可觀察屬性,使用某種演算法將D劃分成k個子集,要求每個子集內部的元素之間相異度盡可能低,而不同子集的元素相異度盡可能高。其中每個子集叫做一個叢集。

K-means分群屬於非監督式學習,以往的回歸,單純貝氏,SVM等都是有類別標籤y的,也就是說範例中已經列出了範例的分類。而分群的樣本中卻沒有指定y,只有特徵x,例如假設宇宙中的星星可以表示成3D空間中的點集(x , y , z)。分群的目的是找到每個樣本x潛在的類別y,並將同類別y的樣本x放在一起。例如上面的星星,分群後結果是一個個星團,星團裡面的點相互距離比較近,星團間的星星距離就比較遠了。

與分類不同,分類是範例式學習 (base),要求分類前明確各個類別,並斷言每個元素對映到一個類別。而分群是觀察式學習(Observational learning),在分群前可以不知道類別甚至不指定類別數量,是無監督學習的一種,目前分群廣泛應用於統計學,生物學,資料庫技術和市場行銷等領域,對應的演算法也非常多。

--

--