自動決定最佳化分群數量：X-means / Determin the Optimal Number of Clusters: X-means
能夠自動決定分群數量的演算法，除了層疊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 Presentation
- 教學投影片其他格式： Power Point、 PDF、 OpenDocument Presnetation
我以Google簡報的檔案匯出成PPTX，再備份到以下位置：
- SlideShare 、 GitHub 、 OneDrive 、 Box 、 Mega 、 MediaFire 、 Google Drive
Weka中使用X-means / X-means in Weka
Weka預設並沒有包含X-means分群演算法，必須使用套件安裝來安裝「XMeans」套件才行。關於在Weka中安裝套件的做法，請參考「Weka下載與套件安裝教學」這篇。
小結 / In closing
好的，寫完X-means之後這篇，我在去年年底演講的投影片跟工作的記錄就告一段落了。去年年底開始我做了很多分析技術的研究。有些做了一半，結果並不讓人滿意，像是對數線性模式分析的分析太過複雜。有些當時研究了半天覺得這方向不好，後來又找尋跟容易的做法，例如從時間序列分析與預測的ARIMA轉變成用Weka實作多變項時間序列預測的機器學習。一路整理下來，也可以看到分析技術的小小成長吧。
不過我得說的是，其實這些分析技術並不新，相關的理論與應用都已經百花鳴放。我所做的事情大多只是把做法整理得比較簡單、容易讓未來的自己跟其他人使用而已。
可惜的是，這些分析技術跟我的畢業論文，並沒有什麼直接的關係。真正的資料分析方法，是要依據研究問題跟資料特性來選擇，並且是以迭代的方式探索、驗證、再探索、再驗證的方式，找出研究希望得到的答案。因此這一系列的資料分析方法，都只能算是入門操作手冊而已。
不管怎麼說，把它記錄在blog中供大家參考，也給自己的成長留下記錄，這才是我把它整理在blog的主要理由吧。
這一篇X-means分群演算法的介紹就談到這裡了。你是否還知道其他的分群演算法呢？像是SOM或大家很常用的階層分群法？你通常使用什麼分群演算法呢？歡迎在下面的留言處與我分享你的看法，或是在AddThis分享工具上按讚、分享到Facebook等社群媒體。感謝你的耐心閱讀，讓我們下次見囉！
大神， 能不能用之前讲k-means时的例子（BMW）来解释下这个x-means, 之前那个k-means非常容易懂
回覆刪除我不是很懂你的意思。
刪除如果只是使用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
是这样，我记得用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结果的教程，因此就在你这找点希望了。。。
嗯，我懂你的問題了。
刪除你的問題老實說並不是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
原来如此，看来我太依赖那些指标数值了。我重新看了你的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，它似乎有比较全的算法，但要重新学。。。
您好，
刪除您的問題分成兩個層面，一個可能跟你無關，另一個可能是比較跟你有關：
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
居然完全没想过用分类，谢谢，这些素材会很有帮助！
刪除不客氣，如果對分類有問題，可以換到該篇下面繼續發問喔。
刪除好嘞。
刪除不知道你有没有对Calinski-Harabasz 指数进行解释过的文章，或是其它相关的。因为我在同时用X-means和Cascading K-means做一些试验后觉得Cascading的分群更准确，我对X-means的BIC大概了解了， 但不是很懂 CH 决定 K 数的方法。。。
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
可以參考看看
好，感谢！
刪除你好。
刪除我认为WEKA 虽然挺好用的，但算法实在太少，不知道你有没有关于另一个相似的平台 ELKI的教程什么的，这里似乎有更加多的算法选项。ELKI的官方教程实在是没多大用处。。。
啊，我不知道ELKI耶
刪除我只有寫過Weka的教學而已
如果要其他的演算法，我會選擇直接去GitHub找可執行的source code來使用
通常很多研討會的最新演算法都會選擇在GitHub發佈
也會有附上測試案例，比較好操作
至於圖形化的介面嘛
那是給初學者用的，如果到了真的要比較演算法的時候，圖形化就不是很重要了
这样。行， 那我再找找或是自己研究研究。
刪除請加油吧！
刪除