此文章由机器翻译。
数据聚类分析
数据聚类使用朴素贝叶斯推理
数据聚类是一种机器学习技术，有很多重要的实际应用，如分组销售数据以揭示消费者购买的行为，或对网络数据进行分组，洞察沟通模式。 聚类的数据也是有助于确定异常的数据点。 在这篇文章中，我提出一个完整的 C# 程序用于将群集功能添加到软件系统或用于创建一个功能强大的单独聚类实用程序，可以使用作为基础。
有很多不同的聚类算法，部分因为聚类算法的有效性取决于某种程度上正在聚集数据的特征。 最常用的算法称为 k-均值聚类。 不幸的是，这种算法是仅适用于数字数据项目。 与此相反的是，我将在本文中介绍的聚类算法基于一种称为朴素贝叶斯推理、 分类或数值数据的技术。 这里介绍的聚类算法中使用的所有想法都是众所周知的虽然整体算法和具体执行，尽我所知，尚未发布之前。 我呼吁此算法和其执行迭代朴素贝叶斯推理凝聚聚类 (INBIAC) 以区别于其他群集技术。 朴素贝叶斯推理是很常用的技术，用于执行数据分类，但一般不知道还可以用于朴素贝叶斯数据聚类。
了解在我朝这篇文章的最佳方法是要看一看图 1。 该演示程序开始按生成八个随机数据元描述的位置 （城市、 郊区或农村），收入 （低、 中、 高或很高） 和政治 （自由或保守） 8 假设人。 该程序然后将原始字符串数据加载到内存中，并将数据转换成 int 值，以便有效地处理。 例如，去年的元组的 （"农村"、"低""保守"） 存储为 （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 Studio 2010 来创建 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 的属性值，市区、 郊区和农村的位置 ； 低、 中、 高收入 ； 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
您可能希望考虑替代的方法。 一个高级的选项是观察该属性的收入 — — 用值低、 中等、 高和 VeryHigh — — 本质上是数值。 因此，您可以修改方法 GetGoodIndexes 低和 VeryHigh 之间的差异大于低与介质之间的差异。
有趣的小小问题都会生成不同的候选种子元组索引。 由 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。 我发现现有的聚类工具是速度太慢，根本没有工作或给成绩差。 这里介绍的算法可以处理分类和数值数据 （如果数值数据冷藏到类别）、 可以处理海量数据集和速度非常快。
如前所述在导言中，研究表明没有单一的最好的聚类算法，但相反，您必须使用不同的算法，以获得最佳效果进行试验。 聚类分析基于朴素贝叶斯推理探索数据集的能力可以是您的技能集宝贵的补充。
Dr。James McCaffrey 为伏信息科学 Inc.，他在管理工作在华盛顿雷德蒙的微软校园软件工程师的技术培训工作。他已为多种 Microsoft 产品效过力，包括 Internet Explorer 和 MSN Search。他是《.NET Test Automation Recipes》(Apress, 2006) 的作者，您可以通过以下电子邮箱地址与他联系：jammc@microsoft.com。
衷心感谢以下技术专家对本文的审阅：Dan Liebling