可理解的集羣化

Question

我有一個數據集。這個集合中的每個元素都由數字和分類變量組成。分類變量是名義和有序的。 此數據集中有一些自然結構。通常，專家使用他們的「專家知識」對數據集進行分組，例如我的分類，但是我想自動化這個集羣化過程。

大多數用於聚類的算法使用對象之間的距離（歐幾里得，馬哈拉諾迪斯等）以將它們分組成簇。但是對於混合數據類型很難找到一些合理的指標，即我們無法找到'玻璃'和'鋼'之間的距離。所以我得出結論，我必須使用條件概率P(feature = 'something' | Class)和一些依賴它們的效用函數。這對分類變量是合理的，並且假設它們正常分佈，它對數字變量可以正常工作。

因此，我很清楚像K-means這樣的算法不會產生好的結果。

此時我嘗試使用COBWEB算法，這完全符合我對使用條件概率的想法。但是，我面臨另一個障礙：集羣化的結果真的很難解釋，如果不是不可能的話。因此，我想獲得一些描述每個羣集的規則（例如if feature1 = 'a' and feature2 in [30, 60], it is cluster1），就像分類中的決策樹。

所以，我的問題是：

是否有混合數據類型的作品，併產生集羣的理解（和合理的人類）描述任何現有的集羣化算法。

附加信息：

據我瞭解我的任務就是在概念聚類的領域。由於研究領域的限制，我無法定義一個相似性函數（它是whoal項目的最終目標） - 它在形式化方面非常複雜和無情。據我瞭解，最合理的方法是COBWEB中使用的方法，但我不知道如何適應它，所以我可以得到一個集羣的難以置信的描述。

決策樹

至於有人建議，我想訓練對聚類輸出決策樹，從而獲得集羣的描述爲一組規則。但不幸的是，這個規則的解釋幾乎和原始聚類輸出一樣困難。首先，從根節點開始的幾個第一層規則確實有意義：更接近葉節點 - 我們有更少的感覺。其次，這些規則不符合任何專業知識。

因此，我得出的結論是聚類是一個黑盒子，它不值得試圖解釋它的結果。

此外

我有一個有趣的想法修改「決策樹迴歸」以某種方式的算法：計算組內方差calcualte一個category utility function的istead並把它作爲一個拆分條件。因此，我們應該有一個帶有葉子簇和簇描述的決策樹。但我並沒有試圖這樣做，我不確定準確性和其他一切。

Answer 1

對於大多數的算法，你會需要定義相似。它不需要是一個適當的距離函數（例如滿足三角不等式）。

K均值特別差，因爲它也需要計算意味着。所以如果你不能計算平均值或者使用與歐幾里得不同的距離函數，最好遠離它。

然而，考慮定義捕捉相似的領域知識的距離函數。它可以由其他距離函數組成，例如你可以使用歐幾里得距離的調和平均值（可能用一些比例因子加權）和類別相似度函數。

一旦你有一個像樣的相似度函數，算法一大堆會變得可用。例如DBSCAN (Wikipedia)或OPTICS (Wikipedia)。 ELKI可能會對你感興趣，他們有一個Tutorial on writing custom distance functions。

解讀是一個獨立的東西。 不幸的是，一些聚類算法會給你他們發現了什麼人類可讀的解釋。他們可能會給你諸如代表的東西（例如k-均值聚類的平均值），但只有更多。當然，你可以在下火車聚類輸出決策樹，並嘗試解釋決策樹從聚類教訓。因爲一個非常好的功能有關決策樹，是他們有些人理解的。但是就像支持向量機不會給你一個解釋一樣，大多數（如果不是全部的話）聚類算法也不會這樣做，對不起，除非你做這種後處理。此外，它實際上將與任何聚類算法，如果你想比較多種算法，它是一個很好的性質工作。

有去年發佈相關。它有點模糊和實驗性（在ECML-PKDD的研討會上），並且要求數據集以排名的形式具有相當廣泛的基礎事實。在這個例子中，他們使用顏色相似性排名和一些標籤。其核心思想是分析集羣和使用給定的地面實況（S）找到了最好的詮釋。他們試圖用它來例如說：「發現這個羣主要是基於對綠色這個特殊的陰影，所以它是不是很有趣，但其他羣集無法很好地解釋，就需要調查它更接近 - 也許算法發現了一些新這裏」。但它非常具有實驗性（研討會是針對研究型工作的）。你可以使用或者，只需使用你的特徵作爲基礎事實。那麼它應該檢測如果集羣可以容易地通過的東西，如說明「attribute5約爲0.4具有低方差」。但它不會強行創建這樣一個解釋！

• H.-P.克里格爾，E.舒伯特，A Zimek
  評價多集羣解決方案
  在第二MultiClust研討會：發現，總結和利用同期舉辦ECML PKDD 2011多個聚類。http://dme.rwth-aachen.de/en/MultiClust2011

Answer 2

對於異質的非​​歐幾里得數據向量，如您所描述的，hierarchical clustering algorithms通常效果最好。您所描述的條件概率條件可以合併爲用於執行集羣聚集或分割的屬性的排序。結果集羣的語義很容易描述。

Answer 3

解決此類聚類問題的常用方法是定義捕獲數據相關特徵的統計模型。可以通過使用混合模型（如在高斯混合模型中）來獲得聚類指派，然後找到對於特定數據點具有最高概率的混合成分。

在你的情況，每個例子是一個向量既有真實的又有分類的組件。一個簡單的方法是分別爲矢量的每個組件建模。

我生成了一個小示例數據集，其中每個示例都是一個兩維矢量。第一維是正態分佈的變量，第二個是五類選擇（見圖）：

有許多可用來對統計模型運行蒙特卡洛推理框架。 BUGS可能是最受歡迎的（http://www.mrc-bsu.cam.ac.uk/bugs/）。我創建在斯坦此模型（http://mc-stan.org/），它使用不同的採樣技術比的錯誤和爲更有效的許多問題：

data { 
    int<lower=0> N; //number of data points 
    int<lower=0> C; //number of categories 

    real x[N]; // normally distributed component data 
    int y[N]; // categorical component data 
} 
parameters { 
    real<lower=0,upper=1> theta; // mixture probability 
    real mu[2]; // means for the normal component 
    simplex[C] phi[2]; // categorical distributions for the categorical component 
} 

transformed parameters { 
    real log_theta; 
    real log_one_minus_theta; 
    vector[C] log_phi[2]; 
    vector[C] alpha; 

    log_theta <- log(theta); 
    log_one_minus_theta <- log(1.0 - theta); 

    for(c in 1:C) 
    alpha[c] <- .5; 

    for(k in 1:2) 
    for(c in 1:C) 
     log_phi[k,c] <- log(phi[k,c]); 
} 
model { 
    theta ~ uniform(0,1); // equivalently, ~ beta(1,1); 
    for (k in 1:2){ 
    mu[k] ~ normal(0,10); 
    phi[k] ~ dirichlet(alpha); 
    } 

    for (n in 1:N) { 
    lp__ <- lp__ + log_sum_exp(log_theta + normal_log(x[n],mu[1],1) + log_phi[1,y[n]], 
           log_one_minus_theta + normal_log(x[n],mu[2],1) + log_phi[2,y[n]]); 
    } 
} 

我編譯和運行該斯坦模型並用於從最終樣品的參數來計算每個混合組件下每個數據點的概率。然後我分配的每個數據點到該混合物中組分（簇）具有更高的概率來恢復下面的簇分配：

基本上，對於每個混合分量的參數會給你如果每個簇的核心特徵已經創建了適合您的數據集的模型。