發行項
08/13/2015

本文章是由機器翻譯。

測試回合

使用類別公用程式進行資料叢集

資料聚類分析是將資料項目目放置到不同的組的過程 — — 集群 — — 在這種特定組中的專案是彼此相似和不同于那些在其他組中。聚類是機器學習技術，有很多重要的實際使用。例如，聚類分析可以用於確定哪些類型的專案，通常要購買在一起以便有針對性的廣告，可以針對消費者，或以確定哪些公司是類似這樣，可以預測股票市場價格。

聚類使用的最基本形式所謂的 k-均值演算法。(看我的文章，"檢測異常資料使用 k-均值聚類，" msdn.microsoft.com/magazine/jj891054.)不幸的是，只有在資料項目目完全數值的情況下可以使用 k-均值聚類。聚類分類資料（如顏色，可以帶值，如"紅色"和"藍色"）是一個具有挑戰性的問題。在這篇文章我介紹以前未發佈，（當然，我可以確定）聚類演算法我設計的可以處理數位或分類資料的專案或兩者的混合。我叫這種演算法貪心凝聚類別實用程式聚類 (GACUC) 以區別于其他許多聚類演算法。這篇文章會給你你需要實驗資料聚類分析，將群集功能添加到.NET 應用程式或系統，或創建一個功能強大的單獨資料聚類工具的所有資訊。

瞭解哪些聚類是和見到哪裡去在這篇文章的最佳方法是要看一看圖 1。在圖中所示的演示程式聚類五個虛擬資料項目目一小的套。資料項目目有時也稱為聚類術語中的元組。每個元組有三個分類屬性：顏色、長度和剛度。顏色可以上四個可能的值之一：紅色、藍色、綠色或黃色。長度可以是短期、中期或長期。剛性可以是虛假或真實。

圖 1 聚類分類資料在行動

該演示程式將原始字串資料轉換成整數形式進行更高效的處理。顏色，紅色、藍色、綠色和黃色被編碼為 0、 1、 2 和 3，分別。長度，短期、中期和長期被編碼為 0、 1、 2，分別。剛度，false 編碼為 0 和真正的被編碼為 1。所以，第一次的原始資料項目目，"紅色短 True，"被編碼為"0 0 1"。

許多聚類演算法，包括 GACUC，需要群集，以指定的數目。在這種情況下，群集的數量設置為 2。該演示程式然後使用 GACUC 找到最佳聚類的資料。在幕後，演算法開始由分別向集群 0 和 1，放入種子元組 0 和 4。聚類演算法然後逐一查看的元組，分配到群集的每個，生成的最佳的總體結果。因為它不使用任何類型的培訓資料，聚類稱為非監督的學習。後一種初步的聚類通行證，GACUC 演算法的執行精煉的通行證，努力改善的聚類。在此示例中發現沒有改善。

在內部，該演示程式定義聚類陣列的整數。陣列的索引指示一個元組的索引，並在陣列中儲存格的值指示群集。在圖 1，演算法所獲得的最佳聚類是 [0,0,1,1,1]，這意味著元組 0 （"紅色短真"）是在群集中 0; 元組 1 （"紅色長假") 是在群集中 0; 元組 2 ("藍色中等真實") 是在群集中 1 ；等等。該演示程式顯示最終的最佳群集中字串格式為了提高可讀性，並且還顯示稱為最好的聚類分析，在此示例中的 0.3733 類實用程式 (CU) 的關鍵度量。正如你所看到的類別實用程式是 GACUC 聚類演算法的關鍵。

本文假定您具有先進的程式設計技能與 C 家庭的語言，但並不假定你知道資料聚類的事。我編碼演示程式使用一種非物件導向方法與 C# 語言，但你不應該到物件導向或另一種語言的演示代碼重構太麻煩了。我已刪除了所有正常的錯誤檢查明確。演示的程式碼太長，目前其整體在這篇文章，所以我專注于使您能夠修改以滿足您自己的演示代碼的 GACUC 演算法需要。該演示程式的完整原始程式碼是可在 archive.msdn.microsoft.com/mag201305TestRun。

實用程式類

資料聚類涉及解決兩個主要問題。第一個問題，定義到底是什麼使好聚類的資料。第二個問題要確定有效的技術來搜索通過所有可能的聚類的組合以找到最好的一個。實用程式類位址的第一個問題。銅是一個聰明的指標，定義了聚類的善良。銅的小值指示差聚類雖然較大的值指示更好的群集。據我已經能夠確定，銅首次定義是由 M。格魯克和 J.杜仲 1985年研究論文題為"資訊、不確定性和類別的實用程式"。

銅的數學計算公式第一眼看是有點令人生畏的：

但該方程是比看來其實簡單。在等式，大寫 C 是整體聚類；小寫 m 是的集群；數大寫的 P 是指"概率"；大寫 A 指屬性（如顏色）；大寫 V 意味著屬性值（如紅色）。除非你是一位數學家，計算類實用程式是最好的理解的示例。假設要聚簇索引的資料集顯示的是在圖 1，和您想要計算的聚類銅：

k = 0
Red      Short    True
Red      Long     False
k = 1
Blue     Medium   True
Green    Medium   True
Green    Medium   False

第一步是計算 P(Ck)，這是每個群集的概率。 K = 0，因為有五個中繼資料組，其中兩名是在群集 0，P(C0) = 2/5 = 0.40。同樣，P(C1) = 3/5 = 0.60。

第二步是計算方程，稱為無條件概率一詞中的最後一雙求和。計算是 N 條款，其中 N 是在資料組中，不同的屬性值的總數，是這樣的總和：

Red: (2/5)^2 = 0.1600
Blue: (1/5)^2 = 0.0400
Green: (2/5)^2 = 0.1600
Yellow: (0/5)^2 = 0.0000
Short: (1/5)^2 = 0.0400
Medium: (3/5)^2 = 0.3600
Long: (1/5)^2 = 0.0400
False: (2/5)^2 = 0.1600
True: (3/5)^2 = 0.3600
Unconditional sum = 1.3200

第三步是計算中期雙求和，稱為條件概率條件。有 m 款項（其中 m 是集群的數量），每個都有 N 條款。

K = 的 0 計算去：

Red: (2/2)^2 = 1.0000
Blue: (0/2)^2 = 0.0000
Green: (0/2)^2 = 0.0000
Yellow: (0/2)^2 = 0.0000
Short: (1/2)^2 = 0.2500
Medium: (0/2)^2 = 0.0000
Long: (1/2)^2 = 0.2500
False: (1/2)^2 = 0.2500
True: (1/2)^2 = 0.2500
Conditional k = 0 sum = 2.0000

K = 的 1 的計算是：

Red: (0/3)^2 = 0.0000
Blue: (1/3)^2 = 0.1111
Green: (2/3)^2 = 0.4444
Yellow: (0/3)^2 = 0.0000
Short: (0/3)^2 = 0.0000
Medium: (3/3)^2 = 1.0000
Long: (0/3)^2 = 0.0000
False: (1/3)^2 = 0.1111
True: (2/3)^2 = 0.4444
Conditional k = 1 sum = 2.1111

最後一步是結合根據銅方程計算所得的款項：

CU = 1/2 * [ 0.40 * (2.0000 - 1.3200) + 0.60 * (2.1111 - 1.3200) ]
   = 0.3733

詳細的解釋了到底為什麼銅措施聚類的善良令人著迷，但不幸的是在這篇文章的範圍之外。關鍵的一點是對於任何包含分類資料的資料集的群集，就可能要計算一個值，描述了如何好的聚類是。

尋找最佳的聚類分析

定義一個方式測量聚類良善之後, 第二個問題，以解決任何聚類演算法中就要到了要通過所有可能集聚為最佳聚類搜索技術。一般是不可行的檢查資料集的每個可能的聚類。例如，為資料集與僅 100 元組和 m = 2 群集中，有 2 ^100 / 2! = 2 ^99 可能集聚。即使你某種程度上可以審查每秒 1 兆集聚，它要大約 190 億年來檢查每個可能的聚類。（相比之下，估計的宇宙的年齡是大約 140 億年。

不同的聚類演算法使用不同的技術來搜索通過所有可能的集聚。 GACUC 演算法使用什麼叫做一個貪婪的凝聚方法。想法是開始由播種與單個元組的每個群集，然後，為每個剩餘的元組，確定哪些群集 k'，如果的當前元組被添加到它，將會產生的最佳整體聚類。然後的當前元組實際上分配給群集 k'。這種技術並不能保證最優的聚類分析將會被發現，但實驗表明技術通常產生合理的良好聚類。 GACUC 演算法所產生的最終聚類取決於作為種子元組和在其中剩餘的元組被分配到群集的順序選擇了哪個 m 元組。

原來這選擇種子元為每個群集組並非微不足道。一個幼稚的辦法是，只需選擇隨機元組作為種子。然而，如果種子元組彼此相似，由此產生的聚類將是可憐。用於選擇種子元組更好的方法是選擇盡可能從彼此不同的 m 元組。這裡是哪裡類別實用方便再來 — — 可以計算任何潛在的候選種子元組集合的銅，並與最佳銅（最大值，意思最不同）的元組集合可以用作種子的元組。作為之前，它是一般不可行的檢查每個可能的組的種子元組，這樣的做法是一再選擇 m 隨機的元組，計算的隨機的那些元組，銅並使用的一組具有最佳的銅作為種子。

程式的總體結構

所示在中運行的演示程式的 Main 方法圖1，與一些 WriteLine 語句和注釋刪除，列在 圖 2。我用Visual Studio2010 Microsoft.NET framework 4，但演示的代碼有無顯著關係dencies 和任何的Visual Studio的支援.NET Framework 2.0 或更高版本應該很好地工作。為簡單起見，我創建了一個單 C# 主控台應用程式名為聚類分類；你可能想要實現群集作為一個類庫。

圖 2 總體程式結構

using System;
using System.Collections.Generic;
namespace ClusteringCategorical
{
  class ClusteringCategoricalProgram
  {
    static Random random = null;
    static void Main(string[] args)
    {
      try
      {
        random = new Random(2);
        Console.WriteLine("\nBegin category utility demo\n");
        string[] attNames = new string[] { "Color", "Length", "Rigid" };
        string[][] attValues = new string[attNames.Length][];
        attValues[0] = new string[] { "Red", "Blue", "Green", "Yellow" };
        attValues[1] = new string[] { "Short", "Medium", "Long" };
        attValues[2] = new string[] { "False", "True" };
        string[][] tuples = new string[5][];
        tuples[0] = new string[] { "Red", "Short", "True" };
        tuples[1] = new string[] { "Red", "Long", "False" };
        tuples[2] = new string[] { "Blue", "Medium", "True" };
        tuples[3] = new string[] { "Green", "Medium", "True" };
        tuples[4] = new string[] { "Green", "Medium", "False" };
        Console.WriteLine("Tuples in raw (string) form:\n");
        DisplayMatrix(tuples);
        int[][] tuplesAsInt = TuplesToInts(tuples, attValues);
        Console.WriteLine("\nTuples in integer form:\n");
        DisplayMatrix(tuplesAsInt);
        int numClusters = 2;
        int numSeedTrials = 10;
        Console.WriteLine("Initializing clustering result array");
        int[] clustering = InitClustering(tuplesAsInt);
        int[][][] valueCounts = InitValueCounts(tuplesAsInt, attValues,
          numClusters);
        int[][] valueSums = InitValueSums(tuplesAsInt, attValues);
        int[] clusterCounts = new int[numClusters];
        Console.WriteLine("\nBeginning clustering routine");
        Cluster(tuplesAsInt, attValues, clustering, valueCounts,
          valueSums, clusterCounts, numSeedTrials);
        double cu = CategoryUtility(valueCounts, valueSums,
          clusterCounts);
        Console.WriteLine("\nCategory Utility of clustering = " +
          cu.ToString("F4"));
        DisplayVector(clustering);
        Refine(20, tuplesAsInt, clustering, valueCounts, valueSums,
          clusterCounts);
        Console.WriteLine("Refining complete");
        DisplayVector(clustering);
        Console.WriteLine("\nFinal clustering in string form:\n");
        DisplayClustering(numClusters, clustering, tuples);
        cu = CategoryUtility(valueCounts, valueSums, clusterCounts);
        Console.WriteLine("\nFinal clustering CU = " + cu.ToString("F4"));
        Console.WriteLine("\nEnd demo\n");
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
      }
    } // Main
    // All other methods here
  } // class Program
} // ns

在圖 2，方法群集執行基本的 GACUC 聚類演算法的一個反覆運算。變數 numSeedTrials 設置為 10，傳遞給的常式的確定分配給每個群集的初始種子元組。方法提煉，試圖找到聚類產生一個更好的類別公用程式執行資料 post-clustering 經過。

關鍵資料結構

雖然它是可能因為聚類方法需要計算類別實用程式多次通過遍歷每個元組中的資料集，計算的類別上飛的一組資料的實用程式，更好的方法是存儲屬性值的元組中的時間分配給群集在任何給定的點的計數。圖 3 顯示大部分的 GACUC 演算法所用的金鑰資料結構。

圖 3 關鍵資料結構

陣列 valueCounts 持有由群集屬性值的數目。例如，valueCounts [0] [2] [1] 持有與屬性 0 的元組的數目（顏色）和 2 （綠色）當前已分配第一組的值。陣列 valueSums 持有計數，的總和跨所有群集，每個屬性值。例如，valueSums [0] [2] 持有的總次數與屬性 0 元組（顏色）和價值 2 （綠色），被分配到所有的群集。陣列 clusterCounts 存儲當前分配給每個群集的元組的數目。例如，如果 numClusters = 2 和 clusterCounts = [2，2]，然後有兩個元組分配給群集 0 和分配第一組的兩個元組。聚類的陣列進行編碼的轉讓到群集的元組。聚類索引表示一個元組和儲存格的值表示一個群集中，和值為-1 指示關聯的元組尚未分配到任何群集。例如，如果聚類 [2] = 1，則元 2 組分配第一組。

編碼 CategoryUtility 方法

計算類實用程式的方法的代碼不是從概念上來說是很困難的但它是有點棘手。該方法的定義開始：

static double CategoryUtility(int[][][] valueCounts, 
  int[][] valueSums,
  int[] clusterCounts)
{
  int numTuplesAssigned = 0;
  for (int k = 0; k < clusterCounts.Length; ++k)
    numTuplesAssigned += clusterCounts[k];
  int numClusters = clusterCounts.Length;
  double[] clusterProbs = new double[numClusters];   // P(Ck)
  for (int k = 0; k < numClusters; ++k)
    clusterProbs[k] = (clusterCounts[k] * 1.0) / numTuplesAssigned;

三個輸入陣列、 valueCounts、 valueSums 和 clusterCounts 被假定為持有有效的值，反映當前的群集中，在上一節中，在所述圖 3。此方法首先通過掃描通過 clusterCounts 陣列來計算當前分配給群集的元組的總次數。集群的數量可以推斷出的 clusterCounts 陣列的 Length 屬性，然後計算和存儲到本地陣列 clusterProbs 集群中的概率。

下一步是計算當前的聚類分析的單個無條件概率：

double unconditional = 0.0;
for (int i = 0; i < valueSums.Length; ++i)
{
  for (int j = 0; j < valueSums[i].Length; ++j)
  {
    double p = (valueSums[i][j] * 1.0) / numTuplesAssigned;
    unconditional += (p * p);
  }
}

無條件概率已進行計算後下, 一步是計算條件概率為每個群集：

double[] conditionals = new double[numClusters];
for (int k = 0; k < numClusters; ++k)
{
  for (int i = 0; i < valueCounts.Length; ++i)
  {
    for (int j = 0; j < valueCounts[i].Length; ++j)
    {
      double p = (valueCounts[i][j][k] * 1.0) / clusterCounts[k];
      conditionals[k] += (p * p);
    }
  }
}

現在，與每個群集在陣列 clusterProbs、無條件概率期限在無條件的變數和陣列條件陳述式中的條件概率術語的概率，可以確定的類別的聚類實用程式：

double summation = 0.0;
for (int k = 0; k < numClusters; ++k)
  summation += clusterProbs[k] * 
    (conditionals[k] - unconditional);
return summation / numClusters;
}

瞭解的 CU 功能行為的好方法是通過提供硬編碼集聚實驗與演示代碼。例如，您可以修改中的代碼圖 2 沿的行：

string[] attNames = new string[] { "Color", "Length", "Rigid" };
// And so on, as in Figure 1
int[][] tuplesAsInt = TuplesToInts(tuples, attValues);
int[] clustering[] = new int[] { 0, 1, 0, 1, 0 };
// Hardcoded clustering
double cu = CategoryUtility(valueCounts, valueSums, clusterCounts);
Console.WriteLine("CU of clustering = " + cu.ToString("F4"));

實現群集方法

類別實用程式中的方法的手，實施群集資料的一種方法是比較簡單的。在高級別的偽代碼，群集的方法是：

define an empty clustering with all tuples unassigned
determine m good (dissimilar) seed tuples
assign one good seed tuple to each cluster
loop each unassigned tuple t
  compute the CU for each cluster if t were actually assigned
  determine the cluster that gives the best CU
  assign tuple t to best cluster
end loop (each tuple)
return clustering

為簡單起見，群集方法逐一查看每個未分配的元組中的訂單，開始在元組 [0]。這有效地給與較低數量指標的元組更大的影響力。我經常使用一種方法是通過使用一個線性、同余、全週期的發電機逐一查看未賦值的元組按隨機順序或炒的順序。

演算法的驚奇地棘手的部分就找到 m 好種子元組。在高級別的偽代碼，GetGoodIndexes 的方法是：

loop numSeedTrials times
  create a mini-tuples array with length numClusters
  pick numClusters random tuple indexes
  populate the mini-tuples with values from data set
  compute CU of mini data set
  if CU > bestCU
    bestCU = CU
    indexes of best mini data set = indexes of data set
  end if
end loop
return indexes of best mini data set

這種方法使用的強力生成-檢查-如果-不使用方法，其中一直在為我在實踐中生成隨機元組索引。

因為群集將，一般情況下，方法返回好但不是最佳的聚類，GACUC 演算法（可選）調用一個提煉方法，嘗試重排的元組群集分配在努力找到更好的類別實用價值與聚類。在偽代碼，改進的方法是：

loop numRefineTrials times
  select a random tuple that is in a cluster with at least two tuples
  determine the random tuple's cluster
  select a second cluster that is different from curr cluster
  unassign tuple from curr cluster
  assign tuple to different cluster
  compute new CU
  if new CU > old CU
    leave the cluster switch alone
  else
    unassign tuple from different cluster
    assign tuple back to original cluster
  end if
end loop

有很多的您可以嘗試其他後處理提煉。前面的細化維護固定的數量的集群。一種可能性是定義一種允許群集，以增加或減少的數量的提煉方法。

GACUC 聚類演算法中一個關鍵的説明器方法是一種將一個元組分配給群集：

static void Assign(int tupleIndex, int[][] tuplesAsInt, 
  int cluster,  int[] clustering, 
  int[][][] valueCounts, int[][] valueSums,
  int[] clusterCounts)
{
  clustering[tupleIndex] = cluster;  // Assign
  for (int i = 0; i < valueCounts.Length; ++i)  // Update
  {
    int v = tuplesAsInt[tupleIndex][i];
    ++valueCounts[i][v][cluster];
    ++valueSums[i][v];
  }
  ++clusterCounts[cluster];  // Update
}

通知方法分配接受太多的參數；這是一個普遍使用靜態方法，而不是物件導向方法的弱點。方法分配修改的聚類的陣列，然後更新的陣列，舉行由群集（valueCounts）的每個屬性值的計數，每個屬性值的計數跨所有群集（valueSums）和分配給每個群集（clusterCounts）的元組的數目。方法取消分配是分配的本質上相反的。在方法中未指派的三個關鍵語句是：

clustering[tupleIndex] = -1;  // Unassign
--valueCounts[i][v][cluster]; // Update
--valueSums[i][v];            // Update
--clusterCounts[cluster];     // Update

總結

伴隨著這篇文章解釋的聚類演算法在這裡提出的 GACUC 以及代碼下載應你起床和運行如果你想要試驗資料聚類，將群集功能添加到應用程式中，或創建一個聚類的實用程式工具。與許多聚類演算法（包括 k-均值），不同的 GACUC 演算法可以很容易修改，處理數值資料或混合的數值和分類資料。這個想法是由 binning 它可輸出成類別預處理數位資料。例如，如果您的原始資料包含人的高度以英寸為單位來衡量，你能斌高度所以，值低於 60.0 是"短"值之間 60.0 和 74.0 是"中型"、和值大於 74.0 是"高大"。

有許多演算法可用於聚類分類的資料，包括依靠類別實用程式來定義聚類善良的演算法。然而，這裡介紹的演算法是相對比較簡單，已在實踐中行之有效，可應用於數位和分類資料和體重秤好的巨大的資料集。GACUC 資料聚類可以將寶貴的補充您的開發人員工具設置。

Dr。James McCaffrey 為伏資訊科學 Inc.，他在管理工作在微軟雷德蒙德，華盛頓州，校園的軟體工程師的技術培訓工作。他曾經參與過多項 Microsoft 產品的研發，包括 Internet Explorer 和 MSN Search。他是作者的".NET 測試自動化食譜"（Apress，2006 年），並可以在達成 jammc@microsoft.com。

由於以下的技術專家對本文的審閱：DanLiebling (Microsoft 研究)