:::

自動決定最佳化分群數量:X-means / Determin the Optimal Number of Clusters: X-means

image

能夠自動決定分群數量的演算法,除了層疊K平均分群法之外,Weka裡面還有另一個分群法也能做到類似的目的,那就是X-means。X-means為每個分群結果計算貝氏資訊準則BIC Score,以此決定是否要將資料分成更多群。跟層疊K平均分群法一樣,它可以讓使用者選定分群數量的可能範圍。然而實際使用幾次後,我發現X-means的分群數量偏少,而且原理也不如層疊K平均分群法使用的Calinski-Harabasz指標(CH指標)容易解釋。因此比起X-means,我個人還是比較推薦使用層疊K平均分群法。本投影片的內容參考了X-means原論文[x-means] 1.x-means简介


投影片 / Slide

我以Google簡報的檔案匯出成PPTX,再備份到以下位置:

Weka中使用X-means / X-means in Weka

image

Weka預設並沒有包含X-means分群演算法,必須使用套件安裝來安裝「XMeans」套件才行。關於在Weka中安裝套件的做法,請參考「Weka下載與套件安裝教學」這篇。


小結 / In closing

好的,寫完X-means之後這篇,我在去年年底演講的投影片跟工作的記錄就告一段落了。去年年底開始我做了很多分析技術的研究。有些做了一半,結果並不讓人滿意,像是對數線性模式分析的分析太過複雜。有些當時研究了半天覺得這方向不好,後來又找尋跟容易的做法,例如從時間序列分析與預測的ARIMA轉變成用Weka實作多變項時間序列預測的機器學習。一路整理下來,也可以看到分析技術的小小成長吧。

不過我得說的是,其實這些分析技術並不新,相關的理論與應用都已經百花鳴放。我所做的事情大多只是把做法整理得比較簡單、容易讓未來的自己跟其他人使用而已。

可惜的是,這些分析技術跟我的畢業論文,並沒有什麼直接的關係。真正的資料分析方法,是要依據研究問題跟資料特性來選擇,並且是以迭代的方式探索、驗證、再探索、再驗證的方式,找出研究希望得到的答案。因此這一系列的資料分析方法,都只能算是入門操作手冊而已。

不管怎麼說,把它記錄在blog中供大家參考,也給自己的成長留下記錄,這才是我把它整理在blog的主要理由吧。


這一篇X-means分群演算法的介紹就談到這裡了。你是否還知道其他的分群演算法呢?像是SOM或大家很常用的階層分群法?你通常使用什麼分群演算法呢?歡迎在下面的留言處與我分享你的看法,或是在AddThis分享工具上按讚、分享到Facebook等社群媒體。感謝你的耐心閱讀,讓我們下次見囉!

總共15 則留言 ( 我要發問 , 隱藏留言 顯示留言 )

  1. 大神, 能不能用之前讲k-means时的例子(BMW)来解释下这个x-means, 之前那个k-means非常容易懂

    回覆刪除
    回覆
    1. 我不是很懂你的意思。
      如果只是使用x-means的方法進行分群的話,那應該也能夠得到數個分群結果,然後再用跟BMW差不多的方式來解釋例子不就可以了嗎?

      如果是不知道要怎麼解釋分群的結果的話,不妨參考我之前寫的「自動決定最佳化分群數量:層疊K平均分群法」
      http://blog.pulipuli.info/2017/10/k-determin-optimal-number-of-clusters.html
      這之中的「Step 3. 解釋分群」介紹了使用統計的方法來解釋分群

      另外也可以用特殊模式探勘(exceptional model mining)來找出分群的特性
      http://blog.pulipuli.info/2018/01/cortana-discovery-knowledge-in-your.html

      刪除
    2. 是这样,我记得用k-means时,是要看 sum of squared errors来决定这个model是好是坏,这个值越小越好;但是用 X-means 时是要看BIC-value,这个值也是越小越好,奇怪的是我看了你提供的这个关于BIC的资料 貝氏資訊準則BIC Score https://www.wikiwand.com/en/Bayesian_information_criterion (很有用),这个值会在数值前面加个负号。下面才是最重要的(抱歉我挺啰嗦的。。)

      以之前那个BMW为例,我想知道那种算法比较适合BMW这个例子,于是我先用 k-means分5个群,得到error数值为113.5多,然后用x-means以分群范围为5-10来算,得到分出 6个群的结果,BIC是 -413.3多; 然后我就想X-means认为在这个范围内 6个群是最好的,于是又用 K-means分6个群来看,得到的数值是 109.3多 < 113.5多,果然数值更好了。所以我认为可能X-means更好用,就想知道X-means的得出结果怎么看,怎想就连那个BIC都搞不清,网上实在是找不到检查X-means结果的教程,因此就在你这找点希望了。。。

      刪除
    3. 嗯,我懂你的問題了。
      你的問題老實說並不是X-means如何計算,而是對於何謂「最佳分群數量」有問題。

      -------------------

      不過我們還是先來回頭看看X-means的分群結果吧。

      說實話,我對X-means一點也不熟,所以BIC怎麼計算的,我也不清楚
      但在之前幾次的經驗中,X-means自動決定的分群數量,大多都是最小分群數或是最小分群數+1,就這樣停止了。
      這幾次的經驗都讓我覺得X-means很不穩定
      而且計算方式跟我們對K-means以距離來計算分群的概念不同,不好解釋

      你的問題中你使用了X-Means分群結果的數量去做K-means
      但是因為兩者是不同的演算法,所以他們的分群結果本身是不一樣的

      X-means Clustered Instances
      0 35 ( 35%)
      1 18 ( 18%)
      2 10 ( 10%)
      3 11 ( 11%)
      4 9 ( 9%)
      5 17 ( 17%)

      K-means Clustered Instances
      0 29 ( 29%)
      1 24 ( 24%)
      2 4 ( 4%)
      3 6 ( 6%)
      4 28 ( 28%)
      5 9 ( 9%)

      你看分群結果的數量就可以知道,儘管分群數量都是6,但兩者出來的結果是完全不一樣的
      因此你說X-means的6群好,但是卻用K-means來看sum of squared errors,以此作為分群結果好壞的指標,這個推論本身是錯誤的。

      -----------------------

      好,接下來我們要講重點:到底什麼是好的分群指標

      sum of squared errors (SSE)是計算每個資料與分群中心的距離,但這並不是一個好指標
      舉例來說,BMW汽車的資料來說,K=2時SSE=12.14,K=5時SSE=113.58,K=6時SSE=109.36
      若用SSE來看,那K=2分兩群就是最好的結果
      你真的覺得如此嗎?

      而且以SSE來說,最佳的分群數量,其實就是資料的個數。
      BMW的案例數量有100筆,那分100群的時候,SSE=0,最準
      但這樣的分群也沒有意義,不是嗎?

      -----------------------

      資料探勘界已經有相當多研究在探討「何謂最好的分群」的問題,稱之為Cluster validation 分群驗證
      大致上可從三個角度來看:分群內部的驗證、群與群之間的驗證、群與其他資料的差異性驗證
      SSE就是只考慮分群內部驗證的指標

      除此之外,許多學者從這些角度提出了不同的指標
      - Calinski-Harabasz
      - Index-I
      - Davies-Bouldin
      - Krzanowski-Lai
      - Figure of Merit
      而採用BIC指標的X-means也是類似的概念

      我之前比較有接觸的則是Weka也有實作的Calinski-Harabasz指標,也就是CascadeSimpleKMeans
      http://blog.pulipuli.info/2017/09/clustering.html

      -----------------------

      這些指標這麼多,究竟要選什麼指標好呢
      我想你應該腦袋充滿了這樣的問題

      先不論每種指標各有其背後的哲學思維,應當在不同的情境下使用合適的指標這件事情
      一旦當你用指標來決定分群結果好壞的時候
      你就陷入了工科的思維:

      分群技術對你來說只是數據上的操弄,除此之外別無意義

      我認為,分群有沒有效,是要用人文角度來思考:
      到底這個分群結果,有沒有讓我更容易理解這些資料,或是更容易把案例分成數群,以進行後續的分析

      以BMW分成5群來說,就算各個指標上都不是很好,但是分群結果容易解釋,那就是很好的應用
      反之,就算是指標數字再漂亮,分群結果讓你難以解釋資料,那也沒有什麼意義

      一個技術能不能有效,指標只是參考,最重要的是他能不能幫助人們
      而分群在這時候要扮演的角色,就是將資料的維度降低、讓人容易理解資料可能有的模式

      我想講的就是這些,至於BIC怎麼算,這我就幫不上忙了orz

      刪除
    4. 原来如此,看来我太依赖那些指标数值了。我重新看了你的K-means和cascadeKMeans的例子,发现主要还是要分析weka给出的分群结果以及为何weka如此分群,而不能太过在意它给的其它指标数值。我更倾向于使用X-means是因为我之前有个报告是将数据用K-means来分群,但总是不确定分群数,就想着也许X-means能帮我解决这个问题。我现在有个想法是:对我手上的一些数据(我自己实际上已经分类好的),分别用 K-means, X-means, Hierarchical Cluster, Bisecting K-means 和 K-medoids,也许也会用到cascadeKMeans(在看了你的例子之后)和其它算法来进行分群。我想测试这几种分群算法哪种能够更好的将我的数据分群。

      我暂时是这么打算的,weka的cluster那里有个评估选项--classes to clusters evaluation, 我在我的数据里多加一个属性叫class来标识 每行数据 所对应的实际所属class(也就是我自己之前正确分类好的)。根据这个评估方法,weka会先无视这个class属性,在对其他数据进行分群后,与这个class(正确分类)比较,除了分群结果外也会给出哪些数据(instance)被错误分群了。我想先以此来比较那几个分群算法哪个更合适我的数据。

      但是,有几个问题比较麻烦。首先,我的数据类型可能会被很多环境因数影响,需要做非常多的测试,这个我只能自己多做实验多分析了;
      最重要的是,想请教下你,weka能不能做 Bisecting K-means和K-medoids,网上实在没找到。如果weka实在不能做这两种算法,就只能用另一种数据勘探的软件叫ELKI,它似乎有比较全的算法,但要重新学。。。

      刪除
    5. 您好,

      您的問題分成兩個層面,一個可能跟你無關,另一個可能是比較跟你有關:

      1. Weka有沒有Bisecting K-means或K-medoids
      就我所知沒有

      如果你只是擔心資料太容易受到極端值影響分析
      你可以調整SimpleKMeans的距離演算法,從尤拉距離改成曼哈頓距離
      這時候極端值就比較不會成為獨立的分群
      但這個做法不算完美,K-medoids可能還是比較好的做法

      可惜Weka沒有實作K-medoids,我是用Python來做K-medoids的

      不過,我想你的問題也不是用那個分群演算法的層次
      而是你可能是個分類問題

      2. 如果你的資料已經有既有的答案了,那為何不要用分類呢?

      分群比較適合在你沒有答案,也就是沒有預先分類的時候處理的問題
      因為實際上分群並沒有正確答案,所以這也是我說指標僅供參考的原因
      分群結果沒有絕對的對或錯,只有能不能用的問題

      如果你已經有預先的答案了,然後希望機器能夠自動將資料分類為這些的預設答案中的其中一種,那就已經是分類問題了

      分類問題在處理資料時就不是像K-means一樣使用距離來做分群的算法
      而是根據訓練資料的答案來學習規則
      詳細請看我之前的教學:分類與預測:貝氏網路
      http://blog.pulipuli.info/2017/10/classification-and-prediction-bayesnet.html

      如果你是又不知道資料可以分成幾類,又想要將未來可能新增的資料分成數量
      那請看我之前的教學:分群與分類的整合應用:無監督分類器
      http://blog.pulipuli.info/2017/10/building-unsupervised-classification.html

      刪除
    6. 居然完全没想过用分类,谢谢,这些素材会很有帮助!

      刪除
    7. 不客氣,如果對分類有問題,可以換到該篇下面繼續發問喔。

      刪除
    8. 好嘞。

      不知道你有没有对Calinski-Harabasz 指数进行解释过的文章,或是其它相关的。因为我在同时用X-means和Cascading K-means做一些试验后觉得Cascading的分群更准确,我对X-means的BIC大概了解了, 但不是很懂 CH 决定 K 数的方法。。。

      刪除
    9. http://blog.pulipuli.info/2017/09/clustering.html
      這篇講「資料聚類:分群」的投影片有講到Calinski-Harabasz指標

      https://docs.google.com/presentation/d/1_8_AqCxImQZ1-3pOXqLcMMwPVZXPzFC6gu47U0MTLrg/edit#slide=id.g1d4436ec24_1_942

      CH詳細公式我也一起上傳了
      https://blog.pulipuli.info/2017/09/clustering.html?showComment=1526644560909#c660391870951351641

      可以參考看看

      刪除
    10. 你好。

      我认为WEKA 虽然挺好用的,但算法实在太少,不知道你有没有关于另一个相似的平台 ELKI的教程什么的,这里似乎有更加多的算法选项。ELKI的官方教程实在是没多大用处。。。

      刪除
    11. 啊,我不知道ELKI耶
      我只有寫過Weka的教學而已

      如果要其他的演算法,我會選擇直接去GitHub找可執行的source code來使用
      通常很多研討會的最新演算法都會選擇在GitHub發佈
      也會有附上測試案例,比較好操作

      至於圖形化的介面嘛
      那是給初學者用的,如果到了真的要比較演算法的時候,圖形化就不是很重要了

      刪除
    12. 这样。行, 那我再找找或是自己研究研究。

      刪除