本文章是由機器翻譯。
資料叢集
資料聚類使用樸素貝葉斯推理
資料聚類是一種機器學習技術，有很多重要的實際應用，如分組銷售資料以揭示消費者購買的行為，或對網路資料進行分組，洞察溝通模式。 聚類的資料也是有助於確定異常的資料點。 在這篇文章中，我提出一個完整的 C# 程式用於將群集功能添加到軟體系統或用於創建一個功能強大的單獨聚類實用程式，可以使用作為基礎。
有很多不同的聚類演算法，部分因為聚類演算法的有效性取決於某種程度上正在聚集資料的特徵。 最常用的演算法稱為 k-均值聚類。 不幸的是，這種演算法是僅適用于數位資料項目目。 與此相反的是，我將在本文仲介紹的聚類演算法基於一種稱為樸素貝葉斯推理、 分類或數值資料的技術。 這裡介紹的聚類演算法中使用的所有想法都是眾所周知的雖然整體演算法和具體執行，盡我所知，尚未發佈之前。 我呼籲此演算法和其執行反覆運算樸素貝葉斯推理凝聚聚類 (INBIAC) 以區別于其他群集技術。 樸素貝葉斯推理是很常用的技術，用於執行資料分類，但一般不知道還可以用於樸素貝葉斯資料聚類。
瞭解在我朝這篇文章的最佳方法是要看一看圖 1。 該演示程式開始按生成八個亂數據元描述的位置 （城市、 郊區或農村），收入 （低、 中、 高或很高） 和政治 （自由或保守） 8 假設人。 該程式然後將原始字串資料載入到記憶體中，並將資料轉換成 int 值，以便有效地處理。 例如，（"農村，""Low"、"保守"） 的最後一個元組存儲為 （2、 0、 1）。
.png)
圖 1 資料聚類使用樸素貝葉斯推理
許多聚類演算法，包括 INBIAC，需要群集，以指定的數目。 在這裡，變數 numClusters 設置為 3。 該演示程式簇的資料，然後顯示的最終聚類分析 [2、 0、 2、 1、 1、 2、 1、 0]。 在幕後，演算法分別種子 0、 1 和 2 元、 1、 6 和 0，與組。 然後將其餘的五個元組的每個分配，一次，一個到群集。 這種類型的演算法稱為集聚。
無需培訓資料或使用者干預是必需的因為聚類有時被稱為"無監督的學習"。聚類陣列中的每個索引表示元組和陣列中的值是一個群集 id。 所以元組 2 ("郊區，""VeryHigh"、"保守"） 被指派以群集 0，元組 1 （"農村"、"中型"、"保守") 分配給群集 2，等等。
該演示程式完成通過在群集的表單中顯示最初的原始資料。 正如您所看到的最後的聚類似乎是合理的。 並且如果你看看原始資料，我認為你也同意設法集群資料手動，甚至對於很小的資料集，將極其困難。
本文假定您具有先進的程式設計技巧與 C 家庭的語言，但不承擔你有經驗與樸素貝葉斯推理或聚類演算法。 在所示的演示程式圖 1 是一個 C# 主控台應用程式。 我編碼它而無需使用物件導向技術，因此您可以更輕鬆地重構不完全支援物件導向的語言。
我刪除了所有的錯誤檢查，以保持盡可能清晰的想法。 演示程式的代碼是演算法的太長，目前其整體在這篇文章，所以我將重點介紹解釋的關鍵部件。 該演示程式的完整原始程式碼是可在 archive.msdn.microsoft.com/mag201303INBIAC。
程式結構
整體的程式結構，與一些評論和 WriteLine 語句刪除，列在圖 2。
圖 2 聚類程式結構
using System;
using System.Collections.Generic;
namespace ClusteringBayesian
{
class ClusteringBayesianProgram
{
static Random random = null;
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin data clustering using Naive Bayes demo\n");
random = new Random(6); // Seed of 6 gives a nice demo
int numTuples = 8;
Console.WriteLine("Generating " + numTuples +
"tuples of location-income-politics data");
string[] rawData = MakeData(numTuples);
Console.WriteLine("\nRaw data in string form is:\n");
ShowData(rawData, numTuples);
string[] attNames = new string[] { "Location", "Income", "Politics" };
string[][] attValues = new string[attNames.Length][];
attValues[0] = new string[] { "Urban", "Suburban", "Rural" };
// Location
attValues[1] = new string[] { "Low", "Medium", "High", "VeryHigh" };
// Income
attValues[2] = new string[] { "Liberal", "Conservative" };
// Politics
Console.WriteLine("Loading raw data into memory\n");
string[][] tuples = LoadData(rawData, attValues);
Console.WriteLine("Converting raw data to int form and" +
"storing in memory\n");
int[][] tuplesAsInt = TuplesToInts(tuples, attValues);
Console.WriteLine("Data in int form is:\n");
ShowData(tuplesAsInt, numTuples);
int numClusters = 3;
int numTrials = 10; // Times to get good seed indexes (different tuples)
Console.WriteLine("\nSetting numClusters to " + numClusters);
Console.WriteLine("\nInitializing Naive Bayes joint counts with " +
"Laplacian smoothing");
int[][][] jointCounts = InitJointCounts(tuplesAsInt, attValues,
numClusters);
int[] clusterCounts = new int[numClusters];
Console.WriteLine("\nBegin clustering data using Naive Bayes " +
"(with equal priors) ");
int[] clustering = Cluster(tuplesAsInt, numClusters, numTrials,
jointCounts, clusterCounts, true);
Console.WriteLine("Clustering complete");
Console.WriteLine("\nClustering in internal form is:\n");
for (int i = 0; i < clustering.Length; ++i)
Console.Write(clustering[i] + " ");
Console.WriteLine("Raw data displayed in clusters is:\n");
DisplayClustered(tuplesAsInt, numClusters, clustering, attValues);
Console.WriteLine("\nEnd demo\n");
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
} // Main
// Other methods go here
} // class
} // ns
我用Visual Studio2010 來創建 C# 主控台應用程式命名為 ClusteringBayesian。 在解決方案資源管理器視窗中我重命名檔 program.cs，然後從更具描述性的 ClusteringBayesian 到program.cs，其中自動重命名的單個類，然後從。 我刪除了不需要的範本生成引用.NET 命名空間 ； 請注意該程式具有幾個依賴項和需要只有 Systems.Collections.Generic 的命名空間。
我宣佈命名類範圍隨機物件隨機。 此物件用於生成隨機的原始資料，並確定要用於種子每個群集的元組。 在 Main 方法中，我具現化隨機使用種子值為 6，只是因為這將生成一個漂亮的演示。
該演示程式的下幾行使用 MakeData 和 ShowData 的説明器方法來生成和顯示八行虛擬資料。 MakeData 調用 sub-helper 方法 MakeParty、 MakeLocation、 MakeIncome 和 MakePolitics。 如果您想要嘗試與特定硬編碼資料元組，可以替換此代碼，例如：
int numTuples = 4;
string[] rawData = new string[] { "Urban,VeryHigh,Liberal",
"Rural,Medium,Conservative", "Urban,Low,Liberal",
"Suburban,Medium,Liberal" };
下一步，演示程式 hardcodes 屬性名稱位置、 收入和政治。 在某些情況下，例如，如果您的原始資料是一個標頭的文字檔中，或在一個 SQL 表的列名稱，您可能想要掃描您的資料並以程式設計方式確定的屬性名稱。
此演示還程式 hardcodes 的屬性值，市區、 郊區和農村的位置 ； Low、 中、 高收入 ； VeryHigh 自由党和保守黨的政治。 再次，在某些情況下，您可能要掃描您以程式設計方式確定屬性值的原始資料。
該演示程式調用説明器方法 LoadData 原始字串資料載入到一個陣列的陣列在記憶體中。 對於非常大的資料集，這不可能。 在這種情況下您需要一次載入的資料塊或逐一查看外部存儲的原始資料一個行一次。
雖然它也可以直接使用原始字串資料，它是更有效率的編碼為類型 int 的資料進行處理 所以下, 一步，説明器方法 TuplesToInts 接受字串陣列的陣列、 陣列通過掃描、 將每個字串轉換為一個從零開始的索引，和將所有資料都存儲在一個陣列的陣列類型 int。 再次，非常大的資料集，您可能需要一次讀取原始資料線和屬性值轉換為 int 上飛。
該演示程式通過設置兩個參數值，準備的聚類常式。 參數 numClusters 是要生成的簇的數目。 一般情況下，資料聚類是一個探索的過程，您必須進行試驗具有不同值的 numClusters (雖然有一些令人著迷技術可以以程式設計方式確定群集的最佳數目）。 在參數 numTrials 由聚類常式生成時使用的初始聚類，我稍後會解釋。
聚類方法需要兩個數組的計數指定元組在任何給定的時間舉行的 INBIAC 演算法。 陣列 jointCounts 存儲具有特定屬性值和特定群集的群集元組的數目。 JointCounts 陣列是有點棘手，和我會于短期內更詳細地解釋它。 但在 jointCounts 中的每個值初始化為 1 作為一部分稱為拉普拉斯平滑的貝葉斯技術的重要一步。 第二個數組，clusterCounts，保存在任何給定的時間分配給每個群集的元組的數目。 ClusterCounts 的索引表示一個群集，並且值為相關聯的計數。
聚類是通過群集方法執行的。 群集方法返回一個陣列，將編碼哪個群集分配給每個元組。 通過顯示聚類的陣列，並將其展示分組由群集使用 helper 方法 DisplayClustered 的原始資料，得出結論認為該演示程式。
樸素貝葉斯推理
使您能夠修改演示代碼，以滿足您自己需要瞭解的 INBIAC 演算法的關鍵理解樸素貝葉斯推理。 樸素貝葉斯是最好的例子解釋。 假設您有八個元組中所示圖 1 和您想要將每個元組放入三個集群之一：
[0] Suburban VeryHigh Liberal
[1] Rural Medium Conservative
[2] Suburban VeryHigh Conservative
[3] Suburban Low Liberal
[4] Suburban High Liberal
[5] Suburban Low Conservative
[6] Urban Low Liberal
[7] Rural Low Conservative
首先，假定每個群集接收單個種子元組 （在後面我們會解釋的方式） 以便元 1 組被分配到群集 0、 6 元組分配第一組，和元組 0 分配給第二組。 有幾種方法來表示這種聚集，但 INBIAC 演算法將以陣列的形式存儲的資訊：
[ 2, 0, -1, -1, -1, -1, 1, -1 ]
此陣列中的陣列索引是元組、 陣列值是群集，和值為-1 指示關聯的元組還沒有分配到群集。 所以，在概念上，聚類在這一點是：
c0 : Rural Medium Conservative (tuple 1)
c1 : Urban Low Liberal (tuple 6)
c2 : Suburban VeryHigh Liberal (tuple 0)
現在的目標是指定的第一個未分配的元組，群集元到三之一 （郊區，VeryHigh，保守），2 組。 樸素貝葉斯計算該元組 2 屬於群集 0、 1 和 2，，然後將該元組分配給該群集具有最大的概率的概率。 表示具有象徵意義，如果群集 0 X = (郊區，VeryHigh，保守） 和 c0 主張，我們希望：
P(c0 | X)
P(c1 | X)
P(c2 | X)
第一次的概率可以讀作"概率的群集 0 給定 X 值"。現在，一會兒和我一起承擔。 若要計算這些條件概率，您必須計算術語叫局部概率 (PP)。 為每個條件要麼計算後，每個群集的概率等於所有分音的總和除以該群集的部分。 象徵意義：
P(c0 | X) = PP(c0 | X) / [PP(c0 | X) + PP(c1 | X) + PP(c2 | X)]
P(c1 | X) = PP(c1 | X) / [PP(c0 | X) + PP(c1 | X) + PP(c2 | X)]
P(c2 | X) = PP(c2 | X) / [PP(c0 | X) + PP(c1 | X) + PP(c2 | X)]
P(c0 | 部分概率X） 是：
PP(c0 | X) = P(Suburban | c0) *
P(VeryHigh | c0) *
P(Conservative | c0) *
P(c0)
= count(Suburban & co) / count c0 *
count(VeryHigh & co) / count c0 *
count(Conservative & c0) / count c0 *
P(c0)
這些方程來自貝葉斯理論並不是在所有明顯。 在樸素貝葉斯的"幼稚"一詞是指每個部分的概率的概率術語被假定為數學上的獨立，這會導致很多簡單計算比如果概率條件是數學上的依賴。
上學期，P(c0)，是"群集 0 概率"。這一術語有時稱為事先和可以計算兩種方式之一。 一種方法是在這種情況下承擔平等普賴厄斯，P(c0) = P(c1) = P(c2) = 1/3。 另一種方式是不承擔平等的先驗並使用指定的元組的當前計數中的案例 P(c0) = count(c0) / (count(c0) + count(c1) + count(c2))。 INBIAC 演算法，最好假定平等普賴厄斯。
計算公式需要所謂的聯合通知。 例如，count(Suburban & c0) 是分配的元組，其中群集是 c0，元組位置是郊區的計數。
如果你回看看當前的聚類，您會看到有一個問題：這點，唯一的第三個種子元組分配給群集，count(Suburban & c0) 為 0，這使得整個部分概率出零一 0，詞。 若要避免此問題，聯合計數所有用初始化值為 1。 這稱為拉普拉斯平滑。 拉普拉斯平滑也將添加到條件概率 （但不是無條件概率一詞） 的分母 3 的簇，數量。 所以為 c0 局部修正的計算方法是：
PP(c0 | X) = P(Suburban | c0) *
P(VeryHigh | c0) *
P(Conservative | c0) *
P(c0)
= count(Suburban & co) / (count c0 + 3) *
count(VeryHigh & co) / (count c0 + 3) *
count(Conservative & c0) / (count c0 + 3) *
1 / numClusters
= (1 / 4) * (1 / 4) * (2 / 4) * (1 / 3)
= 0.0104
同樣，c1 和 c2 的局部概率是：
PP(c1 | X) = count(Suburban & c1) / (count c1 + 3) *
count(VeryHigh & c1) / (count c1 + 3) *
count(Conservative & c1) / (count c1 + 3) *
1 / numClusters
= (1 / 4) * (1 / 4) * (1 / 4) * (1 / 3)
= 0.0052
PP(c2 | X) = count(Suburban & c2) / (count c2 + 3) *
count(VeryHigh & c2) / (count c2 + 3) *
count(Conservative & c2) / (count c2 + 3) *
1 / numClusters
= (2 / 4) * (2 / 4) * (1 / 4) * (1 / 3)
= 0.0208
為每個群集要麼已計算出後，很容易計算為每個群集來將元 1 組分配給群集所需的概率。 下面是計算結果：
P(c0 | X) = PP(X | c0) / [PP(X | c0) + PP(X | c1) + PP(X | c2)]
= 0.0104 / (0.0104 + 0.0052 + 0.0208)
= 0.2857
P(c1 | X) = PP(X | c1) / [PP(X | c0) + PP(X | c1) + PP(X | c2)]
= 0.0052 / (0.0104 + 0.0052 + 0.0208)
= 0.1429
P(c2 | X) = PP(X | c0) / [PP(X | c0) + PP(X | c1) + PP(X | c2)]
= 0.0208 / (0.0104 + 0.0052 + 0.0208)
= 0.5714
元組分配給群集機率最大，在這種情況下是群集 c2。
概括地說，若要將一個元組分配給群集中，為每個群集的局部概率計算使用已分配的元組的聯合計數。 要麼用來計算該元組屬於每個群集的概率。 元組被分配給該群集具有最大的概率。
關鍵資料結構
有幾種方法來存儲 INBIAC 聚類演算法所使用的各種資料。 圖 3 顯示大部分的演示程式所使用的資料結構。 陣列 jointCounts 用來計算局部概率，反過來用於計算反過來用來將一個元組分配給群集的群集概率。 有一個聯合計數為屬性值和群集的每個組合。 這樣，演示，因為有 9 個屬性值 （市區、 郊區、...... 保守） 和三個集群，有 9 * 3 = 27 聯合進行計數。 在 jointCounts 中的第一個索引指示屬性、 第二個索引指示的屬性值和第三項索引指示群集。 例如，jointCounts [1] [3] [2] 持有的收入 (1) VeryHigh (3) 而群集是 (2) 指定元組數。
.png)
圖 3 關鍵資料結構
聚類的陣列進行編碼如何將元組分配給群集。 聚類的陣列的索引表示一個元組，而儲存格的值表示一個群集。 例如，如果群集 [0] = 2，則元 0 組分配給第二組。 儲存格的值為-1 指示關聯的元組還沒有分配到群集。
執行的聚類方法
方法群集中列出圖 4。 該方法接受作為投入 tuplesAsInt 陣列 （可以聚簇索引的資料）、 numClusters （群集使用的數量）、 numTrials （，將初始元組分配給群集）、 jointCounts （如前所述）、 clusterCounts （分配給每個群集的元組的數目需要如果計算與非平等普賴厄斯） 和 equalPriors (一個布林值，該值指示如何計算每個群集的概率計算局部概率時)。
圖 4 方法群集
static int[] Cluster(int[][] tuplesAsInt, int numClusters,
int numTrials, int[][][] jointCounts, int[] clusterCounts,
bool equalPriors)
{
int numRows = tuplesAsInt.Length;
int[] clustering = new int[numRows];
for (int i = 0; i < clustering.Length; ++i)
clustering[i] = -1;
int[] goodIndexes = GetGoodIndexes(tuplesAsInt, numClusters, numTrials);
for (int i = 0; i < goodIndexes.Length; ++i)
{
int idx = goodIndexes[i];
clustering[idx] = i;
}
for (int i = 0; i < goodIndexes.Length; ++i)
{
int idx= goodIndexes[i];
for (int j = 0; j < tuplesAsInt[idx].Length; ++j)
{
int v = tuplesAsInt[idx][j];
++jointCounts[j][v][i]; // Very tricky indexing
}
}
for (int i = 0; i < clusterCounts.Length; ++i)
++clusterCounts[i];
for (int i = 0; i < tuplesAsInt.Length; ++i)
{
if (clustering[i] != -1) continue; // Tuple already clustered
double[] allProbabilities = AllProbabilities(tuplesAsInt[i],
jointCounts, clusterCounts, equalPriors);
int c = IndexOfLargestProbability(allProbabilities);
clustering[i] = c; // Assign tuple i to cluster c
for (int j = 0; j < tuplesAsInt[i].Length; ++j)
{
int v = tuplesAsInt[i][j];
++jointCounts[j][v][c];
}
++clusterCounts[c];
} // Main loop
return clustering;
}
方法群集開始由聚類陣列分配記憶體，並分配值為-1 中每個儲存格，以指示沒有群集已分配給關聯的元組。 下一步，説明器方法 GetGoodIndexes 調用，以獲取最大限度地從彼此不同的元組的索引。 不久我將解釋方法 GetGoodIndexes。 方法群集下一步使用合適的索引初始化聚類的陣列，然後更新的 jointCounts 和 clusterCounts 的陣列。
主要加工迴圈遍歷每個訂單的資料元組和計算的當前元組屬於每個群集使用 AllProbabilities 方法的概率。 然後的機率最大索引是使用 helper IndexOfLargestProbability 來確定的。 因為群集都是從零開始的該指數也是最佳的群集中，和它用來分配給群集 (聚類陣列） 中的當前元組和更新的 jointCounts 和 clusterCounts 的陣列。
因為處理迴圈開始時始終在元組 [0]，這有效地給更多權重低編號索引的元組。 另一種方法是以遍歷的元組的順序是隨機的。 請注意，INBIAC 演算法分配基於最大概率的群集成員身份的元組。 此外可以計算，並返回這些最大概率的平均值。 這是信心的群集分配的措施。 然後可以調用的群集所產生的最高信心的調用製作了若干倍和返回的聚類方法。
我經常用的另一個選擇是進行後處理方法嘗試並生成更好的群集的群集所生成的聚類結果。 偽代碼中的理念是：
loop n times
select a random tuple index
unassign the tuple from its curr cluster
assign the tuple using non-equal priors computation
end loop
INBIAC 建立群集分配一個元組一次通過查找群集的當前元組的召回屬於概率最大的風險。 概率計算使用平等普賴厄斯，即假定每個群集的概率都是相等。 但聚類後, 有可用現在詳細資訊有關如何可能是每個群集，和資訊可以用於可能改進的聚類結果。 代碼下載實現名為的方法改進此選項使用。
越來越好的初始種子元組
INBIAC 演算法種子具有單個元組的每個群集。 它是重要的是這些種子元組應盡可能從彼此不同。 有很多聚類演算法所使用的不同的措施。 方法 GetGoodIndexes 生成一組隨機候選索引，然後計算總人數的元組的屬性的不同，稱為海明距離度量。 這一過程是反復的 numTrials 倍，並返回具有最大的不同的元組的索引。
例如，請考慮在資料圖 1。 假設候選索引為 0、 1、 2。 相應的資料元組是：
[0] Suburban VeryHigh Liberal
[1] Rural Medium Conservative
[2] Suburban VeryHigh Conservative
三個職位 ； 在不同的元組 [0] 和 [1] 在一個位置 ； 不同的元組 [0] 和 [2] 和兩個職位，3 + 1 + 2 = 6 總增量的元組 [1] 和 [2] 各不相同。 偽代碼，在 GetGoodIndexes 的方法是：
init a result array
loop numTrials times
generate numClusters distinct random tuple indexes
compute their dissimilarity
if curr dissimilarity > greatest dissimilarity
greatest dissimilarity = curr dissimilarity
store curr indexes into result array
end if
end loop
return result array
您可能希望考慮替代的方法。 一個高級的選項是觀察該屬性的收入 — — 用值Low、 中等、 高和 VeryHigh — — 本質上是數值。 因此，您可以修改方法 GetGoodIndexesLow和 VeryHigh 之間的差異大於Low與介質之間的差異。
有趣的小小問題都會生成不同的候選種子元組索引。 由 GetRandomIndexes 説明器方法來執行此操作。 在偽代碼，該方法的工作方式：
init a dictionary to store result indexes
init a result array
set count = 0
while count < numClusters
generate a random tuple index
if index not in dictionary
add index to result set
add index to dictionary
increment count
end if
end while
return result
這種技術是相當強力的方法，但它一直在為我在實踐中。
總結
這篇文章，以及代碼的演示程式，應該給你一個堅實的基礎試驗與樸素貝葉斯群集和叢集服務功能添加到軟體系統。我開發了一個有極大的資料集，其中包含數值和分類資料的專案上工作時的聚類演算法的 INBIAC。我發現現有的聚類工具是速度太慢，根本沒有工作或給成績差。這裡介紹的演算法可以處理分類和數值資料 （如果數值資料冷藏到類別）、 可以處理海量資料集和速度非常快。
如前所述在導言中，研究表明沒有單一的最好的聚類演算法，但相反，您必須使用不同的演算法，以獲得最佳效果進行試驗。聚類分析基於樸素貝葉斯推理探索資料集的能力可以是您的技能集寶貴的補充。
博士。James McCaffrey 麥卡弗裡為伏資訊科學 Inc.，他在管理工作在華盛頓雷德蒙的微軟校園軟體工程師的技術培訓工作。他曾經參與過多項 Microsoft 產品的研發，包括 Internet Explorer 和 MSN Search。他是作者的".NET 測試自動化食譜"（Apress，2006年），並可以在達成 jammc@microsoft.com。
感謝以下技術專家對本文的審閱中：DanLiebling