• 發行項

到 2015 2015年 8 月

30 卷數 8

測試回合-K-手段 + + 資料聚類

由 JamesMcCaffrey | 8 月 2015年 | 獲取的代碼: C# VB

James McCaffrey資料聚類是資料分組，以便類似專案被放置在一起的過程。一旦組合在一起，可以檢查資料的集群以看看是否有可能有用的關係。舉個例子，如果聚集了一大堆的銷售資料，每個群集中的資料資訊可能會洩露可用於有針對性的行銷的模式。

有幾種聚類演算法。一個最常見的稱為 k-均值演算法。有幾個變體這種演算法。這篇文章解釋了相對近期的變化稱為 k-手段 + + 演算法。

看一看在演示程式圖 1。在程式啟動與 20 的資料項目目，每個組成的以英寸為單位的一個人的身高和體重的磅。接下來的叢集數目設為 3。大部分資料的叢集化實例中必須由使用者指定的叢集數目。

K-手段 + + 聚類在行動
圖 1 K-手段 + + 聚類在行動

該演示程式然後對資料分類，使用 k-手段 + + 演算法。每個資料 20 項目會指派給一個群集識別碼為 0、 1 或 2。叢集指派會儲存在陣列，其中的陣列索引對應至資料的索引並陣列值就是叢集相關聯的識別碼。比方說，是示範資料最終叢集：

0 2 1 1 2 . . . 1

這表明資料項目目 0 (高度 = 65.0，重量 = 220.0) 是分配群集 0，資料項目目 1 分配給群集 2，資料項目目 2 被分配群集 1，等等。演示結束通過顯示分組由群集的資料。在這裡，揭示了一個非常清晰的模式。有八人中等身材和重的特點，與短的高度和重量輕、 七人和高度與中等重量的五人。

這篇文章假設你有至少中級程式設計技能，但不承擔你知道任何關於 k-手段 + + 演算法。演示程式使用 C# 編寫，但你不應該有太大困難到另一種語言，如 Python 或 JavaScript 代碼進行重構。演示代碼太長，無法顯示其全部內容，但完整的原始程式碼是本文附帶的代碼下載中提供。

理解了 K-手段 + + 演算法

K-手段 + + 演算法是一種變體的標準 k-均值演算法，所以為了了解 k-手段 + + 你必須首先瞭解週期性 k-均值。K-均值演算法有有趣的歷史，和有時被稱為勞合社的演算法。K-均值"k"是指團簇數目。在層次非常高的偽代碼中，最常見的標準 k-均值是看似簡單的:

pick k initial means
loop until no change
  assign each data item to closest mean
  compute new means based on new clusters
end loop

儘管它簡單的外觀，標準 k-均值演算法是，事實上，很微妙的和執行是出奇的複雜。假設要叢集化的資料組成 20 所示的資料項目 [圖 1, ，具有 k 設為 3。第一個步驟是選取三個資料項目做為初始平均值。常用的方法是隨機播放的資料項目目。假設三個隨機選定資料項目目是專案 2 (59.0，110.0) 群集 0，1，群集的平均數 4 (75.0，150.0) 專案和專案 6 (68.0，230.0) 第二組的平均數的平均數。

在主要處理迴圈中，每個資料項目是審查和分配給群集與最接近的意思。所以，資料項目目 0 (65.0，220.0) 會被分配到群集 2 因為專案 0 接近 (68.0，230.0) 比其他兩個手段。每個剩餘 19 資料項目目將分配給群集。請注意，最初被選為手段的資料項目會分配到正確的群集，因為距離將是 0。

每個資料項目目分配到集群之一後，計算一個新的意思，為每個群集。假設該群集 0 目前包含只是三個數據項: (59.0, 110.0), (70.0, 210.0), (61.0, 130.0).將新的均值為此群集:

( (59 + 70 + 61)/3, (110 + 210 + 130)/3 ) =
(190/3, 450/3) =
(63.3, 150.0)

將同樣的計算集群 1 和 2 的新手段。通知新的手段並不一定實際資料項目目之一了。從技術上講，每一個新的手段是"質"，但是"中庸"一詞常用。

後計算新的手段，每個資料項目是再次檢查與分配給群集與最接近的新意思。反覆運算的更新群集，更新意味著過程持續進行直到群集分配沒有變化。

這一切聽起來相對簡單，但很多可以去錯與標準 k-均值演算法的一個簡單實現。尤其是，壞選型的最初手段可以到穩定，或兩者都導致極差資料聚類分析，或一個很長的運行時。事實證明，良好的初步手段是那些不會互相靠近。K-手段 + + 演算法選擇初始意味著不接近對方，然後使用標準的 k-均值演算法的聚類。

K-手段 + + 初始化機制

在高級別偽代碼 k-手段 + + 初始化機制選擇意味著:

select one data item at random as first mean
loop k-1 times
  compute distance from each item to closest mean
  select an item that has large distance-squared
    as next initial mean
end loop

再次，偽代碼非常簡單。K-手段 + + 初始化機制所示圖 2。有九個資料點，每個都有兩個元件。團簇數目設置為 3，因此 3 資料項目必須選擇作為初始的手段。

K-手段 + + 初始化機制
圖 2 K-手段 + + 初始化機制

在圖圖 2 顯示 k-手段 + + 初始化過程後兩個三個的初步手段已選定。首字母的意思是在 (3，6) 隨機選定。計算距離平方從每個其他 8 個數據專案到第一的意思，然後使用該資訊，第二個初始的意思是在 (4，3) (在我很快解釋的方式) 被選中。

要選擇一個資料項目目作為第三個初始平均，計算了從每個資料點到其最接近平均值的平方的距離。距離顯示為虛線。使用這些距離平方的值，選擇第三個意思資料項目與小距離平方的值已被選中，低概率和資料項目目與大距離平方的值已經被選中的可能性很大。這種技術有時被稱為比例健身選擇。

比例的健身選擇是 k 的心-手段 + + 初始化機制。有幾種方法來執行比例健身選擇。該演示程式使用一種叫做輪盤賭選擇技術。在高級別的偽代碼中，輪盤賭選擇的一種形式是:

p = random value between 0.0 and 1.0
create an array of cumulative probabilities
loop each cell of cum prob array
  if cum[i] >= p
    return i
  end if
end loop

一個具體的例子將説明澄清輪盤賭選擇。關聯的值 (30.0、 10.0、 40.0 20.0) 假設有四個候選項目 (0、 1、 2、 3)。值的總和是 20.0 + 40.0 + 10.0 + 30.0 = 100.0。比例的健身選擇將選擇專案 0 與概率 20.0/100.0 = 0.20; 選擇專案 1 與概率 10.0/100.0 = 0.10; 選擇專案 2 與概率 40.0/100.0 = 0.40; 和選擇專案 3 與概率 30.0/100.0 = 0.30。

如果選擇的概率都作為 (0.20，0.10，0.40，0.30) 存儲在一個陣列中，累積概率可以存儲在一個陣列值 (0.20、 0.30、 0.70、 1.00)。現在，假設使用值 0.83 生成一個隨機的 p。如果 i 是累計機率陣列的陣列索引時我中學 = 0，[i] = 0.20 這並不是大於 p = 0.83，因此 i 遞增為 1。現在中學 [i] = 0.30，大於仍然不 p，所以 i 遞增為 2。現在中學 [i] = 0.70，大於仍然不 p，所以 i 遞增為 3。現在中學 [i] = 1.00，大於 p，因此我 = 3 傳回做為選取的項目。

通知的累積概率之間的距離不同，與對應于這些專案與更高的概率的選擇的差異較大。

綜上所述，k-手段 + + 演算法選擇的初步手段，那麼方法不一樣，然後使用標準的 k-均值演算法對群集資料。初始化過程使用比例的健身選擇，可以採用多種方式實現。演示專案用途輪盤賭輪選擇。

程式的整體結構

演示程式，與一些少量的編輯，以節省空間，整體結構在圖 3。若要創建該演示程式，我發起Visual Studio，創建一個新 C# 主控台應用程式專案命名為 KMeansPlus。演示程式有沒有重大的 Microsoft.NET 框架依賴關係，因此，任何較新版本的Visual Studio將工作。

圖 3 程式的整體結構

using System;
using System.Collections.Generic;
namespace KMeansPlus
{
  class KMeansPlusProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin k-means++ demo");
      // All program code here
      Console.WriteLine("End k-means++ demo");
      Console.ReadLine();
    }
    public static int[] Cluster(double[][] rawData,
      int numClusters, int seed) { . . }
    public static double[][] InitMeans(int numClusters,
      double[][] data, int seed) { . . }
    private static double[][] Normalized(double[][] rawData) { . . }
    private static double[][] MakeMatrix(int rows, int cols) { . . }
    private static bool UpdateMeans(double[][] data,
      int[] clustering, double[][] means) { . . }
    private static bool UpdateClustering(double[][] data,
      int[] clustering, double[][] means) { . . }
    private static double Distance(double[] tuple,
      double[] mean) { . . }
    private static int MinIndex(double[] distances) { . . }
    static void ShowData(double[][] data, int decimals,
      bool indices, bool newLine) { . . }
    static void ShowVector(int[] vector, bool newLine) { . . }
    static void ShowClustered(double[][] data, int[] clustering,
      int numClusters, int decimals)
  }
} // ns

後載入到該範本代碼編輯器中的，在我在 Program.cs，檔右擊解決方案資源管理器視窗中改名為更具描述性的 KMeansPlusProgram.cs 和允許Visual Studio可以自動重命名類程式。在編輯器視窗頂部的範本生成的代碼，我刪除了所有對除了頂級的 System 命名空間和 Collections.Generic 命名空間的命名空間的引用。

Main 方法開始通過設置 20 個原始資料的專案:

double[][] rawData = new double[20][];
rawData[0] = new double[] { 65.0, 220.0 };
...
rawData[19] = new double[] { 61.0, 130.0 };

在非演示場景中可能會從一個文字檔或 SQL 資料庫中讀取資料。顯示原始資料使用一個名為 ShowData 的程式定義的説明器方法後, 資料被群集:

int numClusters = 3;
int[] clustering = Cluster(rawData,   numClusters, 0);

雖然有一些技巧，你可以用猜的最佳分類數，在一般情況下，您必須使用試驗和錯誤。聚類方法接受數位原始資料到群集中的陣列的陣列樣式矩陣; 集群使用數目 (可"k"，但"numClusters"的可讀性更好); 和用於隨機的種子值。

Main 方法最後顯示聚類陣列和顯示分組由群集的原始資料:

ShowVector(clustering, true);
ShowClustered(rawData, clustering, numClusters, 1);

我使用靜態方法，而不是物件導向的方法。聚類方法調用四個説明器方法。説明器方法正常化接受原始資料矩陣，並返回資料正常化，所有值都差不多都是同一數量級 (通常與-6.0 + 6.0) 的矩陣。方法 InitMeans 實現 k-手段 + + 初始化機制。方法 UpdateClustering 和 UpdateMeans 實作標準的 k-means 演算法的核心部分。

方法 InitMeans 和 UpdateClustering 都調用説明器方法返回兩個數據的各項之間的歐氏距離的距離。例如，如果一個資料元組是 3.0，9.0 (5.0) 和第二個元組是 2.0，6.0 (1.0)，這兩個專案之間的歐氏距離是:

Sqrt( (3-2)^2 + (9-6)^2 + (5-1)^2) ) =
Sqrt( 1 + 9 + 16 ) =
Sqrt(26) = 5.1

可以使用其他的距離定義。一般來說，k-均值和 k-手段 + + 用於群集嚴格數值資料，而不是分類資料。

執行 K-手段 + +

提出了聚類方法的代碼圖 4。聚類方法首先對原始資料進行正常化處理，以使資料項目 (如重量值在演示中) 中的大型元件不會左右更小的元件 (高度值)。演示使用高斯正常化。兩個常見的替代方法是最小最大正常化和數量級正常化。原始資料的正常化的設計替代是在預處理步驟中，然後將傳遞的歸一化的資料直接到群集的方法。

圖 4 方法群集

public static int[] Cluster(double[][] rawData,
 int numClusters, int seed)
{
  double[][] data = Normalized(rawData);
  bool changed = true;
  bool success = true;
  double[][] means = InitMeans(numClusters, data, seed);
  int[] clustering = new int[data.Length];
  int maxCount = data.Length * 10;
  int ct = 0;
  while (changed == true && success == true &&
    ct < maxCount)
  {
    changed = UpdateClustering(data, clustering, means);
    success = UpdateMeans(data, clustering, means);
    ++ct;
  }
  return clustering;
}

方法 InitMeans 實現 k-手段 + + 初始化機制並返回一組意味著是相距很遠的歐氏距離。在主要的聚類迴圈中，UpdateClustering 方法遍歷每個資料項目和將每個專案分配給群集最接近當前的手段/質心與相關聯。該方法返回 false，如果群集分配 (表明聚類完整) 沒有變化或者新的聚類將導致在沒有資料的項 (表示有什麼不對勁) 的群集中。替代方法是在零計數群集情況時引發異常。

方法 UpdateMeans 逐一查看分配給每個群集的資料，並計算新意思/質心為每個群集。該方法返回 false，如果不能計算一個或更多的手段，因為群集有沒有資料的專案。

主聚類迴圈使用一個計數檢查以防止無限迴圈。K-均值演算法通常穩定速度非常快，但該演算法將穩定根本沒有保證。MaxCount 的值設置為 10 倍的資料項目的數目，是任意的但我工作得很好在實踐中。

InitMeans 方法的定義的開頭:

public static double[][] InitMeans(int numClusters,
  double[][] data, int seed)
{
  double[][] means = MakeMatrix(numClusters, data[0].Length);
  List<int> used = new List<int>();
...

名為手段的局部陣列的陣列樣式矩陣保存的方法返回的行索引群集 ID，每一行都是一個陣列，它保存的元件相關聯的意思。< Int > 名為使用清單保存索引的資料已指派的項目做為初始方法讓可以防止重複的初始平均值。這種方法假定沒有資料的專案具有相同的值。當聚類，你如何處理重復資料專案取決於您的特定問題情況。對來源資料中刪除重複項的一種替代方法是重量重複的專案，可以通過它們的頻率。

接下來，第一次初始平均是選擇和存儲:

Random rnd = new Random(seed);
int idx = rnd.Next(0, data.Length);
Array.Copy(data[idx], means[0], data[idx].Length);
used.Add(idx);

第一次初始均值是隨機播放，從資料的所有專案。初始的手段現有資料項目目和他們有時被稱為中心點。

下一步，為迴圈構造選擇剩下的 k-1 意味著:

for (int k = 1; k < numClusters; ++k)
{
  double[] dSquared = new double[data.Length];
  int newMean = -1;
...

陣列綁帶認為每個資料項目和最接近的現有初始平均值之間平方的距離。變數 newMean 認為將是下一個初始平均資料項目的索引。接下來，檢查 (標準化) 的每個資料項目和它的綁帶值是計算和存儲:

for (int i = 0; i < data.Length; ++i)
{
  if (used.Contains(i) == true) continue;
  double[] distances = new double[k];
  for (int j = 0; j < k; ++j)
    distances[j] = Distance(data[i], means[k]);
  int m = MinIndex(distances);
  dSquared[i] = distances[m] * distances[m];
}

因為如果已使用的項目，到壁櫥平均值平方的距離會至本身的距離即 0 並不真的有必要核取以判斷資料的項目是否已使用做為初始的平均值。名為距離陣列會保存到目前為止已選取的現有 k 初始方法的每個從目前資料項目的歐幾里得距離。

記得在距離法的歐氏距離需要平方根的平方差之和資料項目目元件的總和。因為 k-手段 + + 中使用平方的距離、 InitMeans 現蕾後撤消在距離平方根操作。因此，您可以通過定義直接返回距離平方的方法來簡化代碼。

接下來，迴圈掃描通過輪盤賭選擇的累積概率被編寫:

double p = rnd.NextDouble();
double sum = 0.0;
for (int i = 0; i < dSquared.Length; ++i)
  sum += dSquared[i];
double cumulative = 0.0;
int ii = 0;
int sanity = 0;

生成一個介於 0.0 和 1.0 之間的隨機值與距離的平方和計算描述成比例的健身選擇節中所述。而不是顯式創建的累積概率陣列，它是更有效地生成當前的累積概率上飛。

每個累積概率計算並在一段時間檢查迴圈實現輪盤輪選擇:

while (sanity < data.Length * 2)
{
  cumulative += dSquared[ii] / sum;
  if (cumulative >= p && used.Contains(ii) == false)
  {
    newMean = ii; // the chosen index
    used.Add(newMean); // don't pick again
    break;
  }
  ++ii; // next candidate
  if (ii >= dSquared.Length) ii = 0; // past the end
  ++sanity;
}

While 迴圈進展直到累積概率值是大於或等於隨機 p 值。不過，因此如果所選的平均值是 「 使用 」 的清單 < int > 中，選取下一個可用的資料項目也不允許重複的初始平均值。如果 ii 索引執行資料的結尾，它會重設為 0。請注意如果初始的平均值為已選取的資料項目下, 一個可用的資料項目可能不會被下一個最可能的項目。

方法 InitMeans 得出結論通過保存選定的初始平均，並返回陣列的選定的手段:

...
    Array.Copy(data[newMean], means[k], data[newMean].Length);
  } // k, each remaining mean
  return means;
} // InitMean

InitMeans 方法的目的是尋求 k 不同資料項目要用作初始的手段。輪盤賭選擇並不能保證選擇的手段最大限度地有別于彼此，和有選擇的手段可能相當接近彼此的機會很小。因此，您可能想要重構方法 InitMeans，輪盤賭選擇被多次使用，生成候選集的手段，，然後返回包含的意思是彼此最不同的集合。

總結

這篇文章基於 2007年研究論文中，"K-手段 + +: 優點小心植入"D.Arthur 和 S.Vassilvitskii。通常是以研究論文案例幾乎會不提供任何實作詳細資料。然而，仔細闡述了如何 k-手段 + + 初始化工作和建立其行為的理論邊界。

Dr。James McCaffrey Redmond，華盛頓中的 Microsoft Research 的運作方式他曾在包括 Internet Explorer 和 Bing 的數個 Microsoft 產品。Dr。McCaffrey 可以到達 jammc@microsoft.com。

感謝以下的微軟研究院技術專家對本文的審閱: KirkOlynyk