聚类新纪元：C#.NET 中的 CLOPE 算法
5.00/5 (7投票s)
在本文中，我们将阐述和讨论 CLOPE 数据挖掘聚类算法，该算法可以显著提高分类数据聚类的质量和效率，并可轻松用于推荐目的
- 下载 CLOPE.zip - 138.5 KB
- 下载 CLOPE_EXE.zip - 18.3 KB
- 下载 MOVIES.zip - 11.2 KB
- 下载 CLOPE_REF.zip - 76.8 KB
引言
在我之前的出版物中，我已经讨论了使用几种数据挖掘算法来完成各种任务的特定方面，这些任务通常无法在不执行实际聚类的情况下完成。
以下文章只是计算机科学和 IT 领域一项大型分析研究工作的一小部分，致力于利用聚类和其他数据挖掘算法来部署各种软件电子商务工具和组件，例如推荐引擎（RE），从而显著增加销售额，同时简化每个在线客户根据其个人偏好查找感兴趣产品和服务的流程。在本文中，我们将介绍一种全新的聚类算法，它是现有 k-means 和 c-means 算法的更有效替代方案，与目前已有的算法相比，可以实现更好的聚类。
此时，我们将更多地讨论使用传统 k-means 和模糊 c-means 聚类算法的缺点，以及使用 CLOPE 聚类算法本身的优点。
具体来说，在本文中，我们将阐述 CLOPE 聚类算法的广义解释，提供详细的指南，说明如何轻松地将其应用于完成推荐相关的任务。作为使用 CLOPE 算法的一个例子，我们将演示 C# 中实现该算法优化变体的代码，并讨论执行实际聚类所需的功能。
背景
在本节中，我们将以使用 CLOPE 聚类算法对分类数据进行实际聚类为例，该数据具有许多描述性属性，例如存储在电影和视频内容在线网络商店本地数据库中的电影数据集。
著名的 K-Means vs. 新型 CLOPE 聚类算法
在我们开始讨论之前，让我们花点时间仔细看看在使用 k-means 或 c-means 聚类来完成推荐任务时可能发现的特定问题。
K-means 聚类实际上是第一个被认为最适用于根据将 n 个观测值划分为 k 个独立簇来生成用户-项目推荐的算法。根据以下算法，每个特定簇通常由两对数据集组成，一个用于质心，另一个用于属于当前簇的项目。质心通常代表簇的中心项目，其特征与放入簇中的每个特定项目都非常相似。具体而言，在使用 k-means 聚类生成用户-项目推荐时，质心数据集（即簇的中心项目）通常代表一组用户，为其生成推荐项目列表。此外，让我们提醒一下，执行 k-means 聚类的要求是每个簇必须至少包含一个质心（即用户）和多个项目的数据集。
在一般情况下，我们最初给定一组观测值 O = { o1, o2, o3, ... , o(n-1), o(n) }，每个观测值具有各种特征。在这种情况下，我们假设观测值集包含用户或项目数据。
要执行 k-means 聚类，我们首先要做的是创建一个初始簇，其中第一个数据集 C(k) = { c1, c2, c3, ... , c(q-1), c(q) } 包含所有需要我们生成个性化推荐的用户，以及第二个数据集 I(k) = { i1, i2, i3, ... , i(s-1), i(s) }，包含所有将要推荐给用户集 Ck 的项目。这通常通过从整个观测集中过滤掉所有项目来完成。
由于已创建初始聚类，我们通过迭代循环计数器变量 k -> [0;Nk] 来启动 k-means 聚类过程。对于每个索引 k，我们检索一个聚类，对于当前聚类中的每个质心 j -> [0; q]，我们执行线性搜索以从第二个数据集中查找与当前质心 j 具有相似特征的项目。在执行线性搜索时，我们实际上计算数据集中每个项目与当前质心之间的欧几里德距离，仅选择那些与当前质心 j 距离最小的项目，并将它们附加到新构建聚类的数据集中。
最后，根据先前获得的数据，我们创建一个结果簇，该簇只有一个质心（即用户）和一组 m 个与目标簇质心具有最相似特征（例如最小距离）的项目。之后，我们继续处理列表中的下一个质心。我们继续进行 k-means 聚类过程，直到我们最终得到一个目标列表，其中包含一组只有一个质心（代表“用户”）和推荐给他们的数据集项的簇。
此外，还有一些改进允许我们使用 k-means 过程进行全面聚类，作为基于内容的推荐范式的一部分，生成用户到用户和项目到项目的推荐。第一个也是最明显的改进，允许进行全面聚类，是在创建初始聚类时，我们必须简单地将用户和项目数据结合在一起，并用观测集前半部分的用户或项目数据填充聚类中的第一个数据集，用观测集另一半的用户和项目填充第二个数据集。在执行 k-means 聚类时，对于每个新构建的聚类，我们实际上将找到的整个项目数据集打乱并拆分为两个子集。在这种情况下，第一个子集用作质心数据集，第二个子集则用作新构建聚类的项目数据集。
k-mean 聚类过程的第一个问题是，它通常使用欧几里得距离，以及（可选地）其他距离公式作为特定用户和项目相似性的度量。在执行实际聚类时，我们旨在根据上述公式找到距离最小的项目。在这种情况下，用户或项目的每个特征都表示为多维空间中向量的特定分量的数值。不幸的是，用户或项目的并非所有特征数据都可以表示为数值或量化。为了正确定义当前用户和项目之间的相似性度量，在许多情况下，我们必须使用稍微不同的、基于概率的方法来确定特定用户和项目之间的相似性。
执行 k-means 聚类的另一个缺点是无法处理具有多个描述性属性值并因此存储在多维数据结构中的分类数据。用户或项目拥有的描述性属性越多，聚类质量就越低，从而产生误导性推荐结果就越多。
最后，k-means 聚类算法具有 NP-hard 复杂性，这使得它无法用于聚类通常大量的推荐数据。这正是为什么目前 активно 使用只执行用户-项目聚类的算法变体，而 k-means 聚类的其他变体很少用于推荐目的。
CLOPE 聚类算法
根据传统 k-means 聚类算法中存在的许多潜在问题，很明显，为了进行更好的聚类并产生更高质量的推荐，我们需要另一种聚类算法，该算法将采用不同的方法来衡量其特征无法表示为数值的观测值的相似性，同时提供所需的聚类质量，并在计算复杂性方面低于上述复杂的 k-means 聚类算法。
在我们开始之前，让我们回顾一下，由 Yiling Yang、Xudong Guan 和 Jinyuan You 早在 2002 年提出并由 Nikolay Paklin 在 2017 年采纳的新的 CLOPE 算法，是执行任何类型推荐（例如用户到项目、用户到用户、项目到项目）的理想方法，因为与 k-means 聚类和其他已知算法不同，我们不再需要单独构建包含质心集和项目的聚类。根据 CLOPE 算法，我们使用具有单个数据集的聚类，将用户和项目数据结合在一起，正如本文前面已经讨论过的那样。
为了演示新的 CLOPE 算法，我们将使用包含 200 多个电影条目的本地电影数据库。每个特定条目将根据其通过一个以上描述性属性值确定的相似性被放入适当的聚类中。
此外，与 k-means 聚类不同，CLOPE 算法属于数据挖掘机器学习算法的整个类别，它精确地符合“过去相似的品味——未来相似的品味”范式。在大多数情况下，在学习阶段，我们通过使用本地电影数据库中所有现有用户和项目条目的大约 50% 来执行实际的聚类模型训练。根据 CLOPE 算法，另外 50% 的数据条目将实时分布在预定义的聚类之间。这意味着 CLOPE 聚类过程将确定代表用户或项目的每个数据条目将属于哪个特定聚类。然而，在本文的讨论中，我们将不演示实时使用 CLOPE 算法，而是执行全面聚类。
从文件加载数据
正如我们已经讨论过的，为了演示新的 CLOPE 聚类算法，我们将使用一个简单的电影平面数据库，该数据库由一个在线视频网络商店销售。在这种情况下，我们将不使用任何现有的 SQL 数据库引擎，因为我们将讨论的电影数据库非常简单，只包含一个电影实体。相反，我们将所有电影数据存储到一个纯文本文件中，其格式如下：
movies.txt
0#Gone With the Wind#1939#Clark Gable, Vivien Leigh#Blu-ray#Warner Home Video#Drama-Classics, Drama-Romantic Drama#2/2/2010#58.87
1#Dunkirk#2017#Fionn Whitehead, Tom Glynn-Carney#With DVD, Digital Theater System, 2 Pack#Warner Home Video#War-World War II#12/19/2017#32.79
正如您从上面的示例中看到的，每个记录中每个字段的值都由“#”字符分隔。每个电影记录包含以下字段：id、标题、年份、主演演员、特征、工作室、类型、发布日期和价格。正如我们已经讨论过的，这些属性中的大多数值都不是数值。这就是为什么我们将使用一种完全不同的方法来查找特定电影项目之间的相似性，而不是计算它们属性向量之间的欧几里得距离。
要在 C# 中从文件中读取每个电影的数据，我们将使用 `System.IO.FileStream` 创建一个简单的文件对象。之后，我们将使用 `System.IO.StreamReader` 实例化一个纯文本文件读取器对象。由于我们已经初始化了特定对象，我们将通过调用 `System.IO.StreamReader.ReadLine()` 方法迭代地检索文件的每一行。在每次迭代中，我们将通过将从文件中检索到的每一行拆分为由“#”字符分隔的一组值来实际解析它。从文本文件的每一行获得的一组值对应于特定电影条目的特定描述性属性（或只是数据字段）。然后，从每一行检索到的所有值都存储到应用程序的内部数据内存结构中，这些结构可供执行实际聚类的应用程序例程访问。这些内部数据结构将在“使用代码”部分的开头详细讨论。
初始化阶段
在初始化阶段，我们实际上正在准备目标聚类列表 {C}。为此，我们声明一个聚类列表，并放置 N 个由单个电影项目组成的预定义聚类。放置在预定义聚类中的电影项目的属性值将代表该聚类中所有电影项目共有的属性。为此，我们迭代电影数据集，进入每个电影项目 Ik，并对每个电影项目，对目标聚类列表执行另一系列迭代。对于每个聚类 Ci，我们检查当前电影 Ik 及其特定的唯一属性值是否尚未放置到目标列表中现有聚类中的一个。如果未放置，我们将当前电影项目 Ik 放置到当前聚类 Ci 中。否则，如果目标聚类列表已经包含一个特定的预定义聚类，该聚类包含一个电影项目，其属性值与当前电影项目的属性相似，那么我们就不创建新的预定义聚类，也不将当前电影放置到其中。相反，我们继续处理电影数据集中的下一个电影项目。由于我们已经获得了预定义聚类的目标列表，我们现在可以开始 CLOPE 聚类过程了。
CLOPE 的聚类方法
在我们开始执行聚类之前，让我们简要了解一下在聚类阶段构建的每个聚类的结构。与任何其他现有算法不同，CLOPE 使用一种完全不同的聚类方法。这意味着，在聚类阶段，我们将构建具有我们从未在执行 k-means 聚类时使用的结构的聚类。具体来说，目标列表中的每个聚类将只包含一个属于整个聚类的数据集。此外，每个聚类都由多个参数描述，例如聚类的宽度 - W(Ci)、高度 - H(Ci)、梯度 - G(Ci)、S(Ci) - 聚类矩形的面积等。
宽度参数 W(C) 通常表示由具有不同唯一属性值集的电影项目组成的组数。反过来，另一个高度参数 H(C) 被表示为聚类 C 中每个电影项目的出现次数之和，除以聚类宽度 - W(C)
，其中 H(Ci) - 聚类 Ci 的高度，W(Ci) - 聚类 Ci 的宽度，S(Ci) - 聚类 Ci 中每个不同电影项目的出现次数之和（例如，聚类 Ci 矩形的面积），O(Ik) - 电影项目 Ik 在聚类 Ci 中的出现次数；
实际上，簇高度 H(Ci) 的值是簇 Ci 中电影项目总数与具有独特属性值集（例如，具有完全不同属性值的各种项目数）的项目数之比。
反过来，由于我们已经获得了聚类高度的公式，现在我们可以通过使用下面所示的公式轻松找到聚类 Ci 的梯度：
，其中 G(Ci) - 聚类 Ci 的梯度，H(Ci) - 聚类 Ci 的高度，W(Ci) - 聚类 Ci 的宽度，r - 根式值（即 r 的幂次方）（r >= 2），作为排斥力值；
由于 H(Ci) 和 W(Ci) 的值不能小于 1，我们特意将这些值分配给初始化阶段创建的每个预定义聚类的 1。为了演示 CLOPE 算法中使用的聚类的几何意义，让我们绘制一个创建的单个聚类的直方图。
聚类 Ci 的直方图实际上是其估计特征的图形表示。单个聚类中的所有不同项目沿 O-X 轴按其出现次数递减顺序绘制，而每个项目 Ik 的出现次数值出现在直方图的 O-Y 轴上。根据以下表示，让我们找出聚类高度 H(Ci) 的值，该值估计为每个不同项目 S(Ci) 的出现次数之和除以聚类宽度 W(Ci) 的分数，如上所述。S(Ci) 的值对应于每个项目出现次数的总和，并且相当于聚类直方图矩形的面积。正如我们从上面显示的图 1 中可以看到的，直方图的第一列包含项目 i4 的三个条目，即 O(i4) = 3。显然，第二列包含项目 i5 的两个条目：O(i5) = 2。其余项目 i1、i3、i6 在聚类中只出现一次，这就是为什么它们的出现次数将如下：O(i1,i3,i6) = 1。通过这些值，我们现在可以轻松计算聚类 S(Ci) 中每个不同项目出现次数的总和 S(Ci) = 1 + 1 + 1 + 3 + 2 = 8。S(Ci) 的值通常也表示直方图上显示的聚类矩形 S(Ci) = 8。由于 S(Ci) = 8 和聚类宽度 W(Ci) = 5 的值已获得，我们现在可以轻松计算聚类高度 H(Ci) = 8 / 5 = 1.6。
根据 CLOPE 算法，H(C) 的值用作聚类过程本身质量的度量。H(C) 的值越大，从电影数据库中检索到的项目 Ik 与当前聚类 Ci 中的项目之间的相似性就越大。然而，仅仅依靠聚类高度 H(C) 的值来估计聚类质量是不够的。如果使用聚类梯度值（如上所示计算），效率会更高。我们将进一步使用梯度值计算 delta 值，这是聚类 Ci 的主要特征，表示聚类包含电影项目 Ik 的趋势。
为了说明使用 CLOPE 算法进行聚类的质量，并将其与使用 k-mean 聚类获得的类似结果进行比较，让我们仔细看看这两个聚类结果：
正如您从上面的直方图中看到的，图 2a 中显示的第一张直方图以 CLOPE 的形式展示了传统 k-means 聚类的结果，这样更容易与所讨论算法产生的聚类结果进行比较。
具体来说，此时，让我们根据图 2a,b 所示的特定聚类 H(C) 和 W(C) 值，调查第二和第三个聚类直方图的聚类结果。显然，聚类 { (i4,i5) (i4,i5,i6) } 和 { (i1,i2) (i1,i2,i3) } 具有相同的 H(C) 和 W(C) 值，因此这两个聚类的聚类质量完全相同。不同的情况是第一个 - { (i1, i2) (i1, i2, i3) (i1,i3,i4) } 和第四个聚类 - { (i1,i3,i4) (i4,i5) (i4,i5,i6) }。第一个聚类的直方图包含四个唯一的项目，其矩形面积等于 S(C) = 8 个项目，因此 H(C) = 2.0，H(C)/W(C)= 4。反过来，第四个聚类包含 W(C) = 5 个不同的项目，并且具有相同的矩形面积，等于 H(C) = 1.6，H(C)/W(C) = 0.32。显然，在这种情况下，CLOPE 聚类产生的结果聚类倾向于包含更多具有相同面积 H(C)=1.6, W(C) = 0.32 的项目，这很可能有利于更好的聚类质量。
，其中 Profit(Ci) - 全局利润目标函数的值，G(Ck) - 聚类 Ck 的梯度，估计为 G(Ck)=H(C) / W(C)^r，Ci - 聚类 Ci 中项目的总数，r - 排斥正则化系数。
通过将 r 作为函数的参数，我们调节单个聚类中事务的相似度级别，从而调节最终的聚类数量。这个系数通常在 CLOPE 算法的初始化阶段确定。参数 r 的值越大，相似度级别越低，结果将生成更多的聚类。
根据 CLOPE 算法的基本公式，在聚类过程中，我们旨在找到 Profit(Ci) -> max 的聚类变体。通过这种方式，我们基本上执行利润函数最大化任务。
然而，让我们事先回忆一下，至于执行实际的基于 CLOPE 的聚类，我们不会特别使用全局利润目标函数。相反，为了确定特定聚类和项目之间的相似性，我们将计算 delta 值，它是旧聚类和新构建聚类的梯度值之间的代数差。
聚类阶段
CLOPE 聚类算法的基本表示通常非常简单，具有以下步骤，可以轻松地表述如下：
- 初始化目标聚类列表 {C};
- 从电影数据集中检索下一个项目 Ik，k->[0;m]，如果数据集未结束，则转到步骤 3；
- 对于当前项目 Ik，如果不是聚类列表的末尾，则从目标列表中检索下一个聚类 Ci，i ->[0;n]，然后继续步骤 4；
- 将电影项目 Ik 放入当前聚类 Ci；
- 计算 Profit(Ci) 的值；
- 检查 Profit(Ci) 的值是否为最大值（例如，大于目前为止的最大利润值）。如果不是，则从目标列表中的当前聚类 Ci 中移除项目 Ik 并返回步骤 3。否则，返回步骤 2 处理下一个项目；
- 继续步骤 3-6，直到我们获得 Profit(Ci) 值为最大值的分布；
- 重复步骤 2-7，直到所有电影项目都分配到目标列表中的所有聚类中；
实际上，有机会不结合特定的聚类和项目以获得高质量的聚类结果。新的 CLOPE 聚类算法有一个非常重要的优化，可以线性化算法的总计算复杂性。由于这个优化，我们基本上不再需要将每个电影项目 Ik 与特定聚类 Ci 结合，然后计算全局利润值以确定聚类过程本身的适应度。
相反，我们将使用基于确定目标列表中每个特定簇及其关联项目的适应度的以下算法修改。
根据以下算法级别的优化，整个聚类过程可以修改和重新表述如下：
- 初始化目标聚类列表 {C};
- 从电影数据集中检索下一个项目 Ik，k->[0;m]，如果数据集未结束，则转到步骤 3；
- 对于当前项目 Ik，如果不是聚类列表的末尾，则从目标列表中检索下一个聚类 Ci，i ->[0;n]，然后继续步骤 4；
- 计算当前聚类 Ci 和我们将要放入聚类 Ci 的项目 Ik 元组的 delta 值；
-
检查 delta 值是否为整个聚类列表中可能的最大值。如果是，则将当前项目 Ik 放入聚类 Ci 并返回步骤 2。否则，转到步骤 3；
Delta 函数
要计算 delta 函数的值，我们需要执行以下步骤：
- 将聚类 Ci 的当前宽度 W(Ci) 赋给新宽度 W(Ci)_New = W(Ci)；
- 将聚类 S(Ci) 的当前大小增加 1，赋给新聚类 S(Ci)_New = S(Ci) + 1；
- 检查当前电影项目 Ik 是否尚未放入当前聚类 Ci；
- 如果是，则将新宽度 W(Ci)_New = W(Ci)_New + 1 增加 1；
- 计算并返回 delta 值：S(Ci)_New * 2 / W(Ci)_New^r - S(Ci) / W(Ci)^r；
在原始的 CLOPE 算法白皮书中，delta 的计算是针对包含多个项目而非单个项目的整个事务进行的。由于我们每次最多只向一个特定聚类放置一个电影项目，因此我们特意修改了 delta 函数值的计算规则。以下两个公式说明了使用原始和修改后的 delta 计算公式之间的差异：
，其中 Sn(Ci) - 每个不同电影项目出现次数之和（例如，聚类矩形的面积），Wn(Ci) - 电影项目 Ik 放入后聚类 Ci 的新宽度，S(Ci) - 聚类 Ci 的原始面积，W(Ci) - 聚类 Ci 的原始宽度，Nt - 事务数量。
正如您从第一个公式（左侧）中可以看到的，delta 值基本上计算为聚类 Ci 的梯度与电影项目 Ik 放入后同一聚类的梯度之间的差值。包含电影项目 Ik 的聚类 Ci 的宽度实际上与聚类 Ci 的原始宽度相差 1。
在执行基于 CLOPE 的聚类时，我们实际上旨在每次向当前聚类 Ci 中只放置一个电影项目。这就是为什么我们最初将 Nt 的值设为 1，并将其代入相同的原始公式（从左侧）。显然，我们将得到修改后的公式（从右侧），该公式将进一步用于计算仅添加一个项目时 delta 的值。
评估 CLOPE 算法
显然，CLOPE 算法的 delta 优化提供了计算复杂度的最高线性化，现在是 p = n x m，与 N^2 成正比，而不是 p = n x m x q 与 N^3 成正比。通过使用 delta 优化，与 CLOPE 算法的最初公式相比，我们实际上可以将复杂度线性化至少 N 倍。然而，通过分析原始和优化后的 CLOPE 算法，我发现了聚类过程本身至少存在两个严重问题。
计算相似度
正如我们已经讨论过的，为了计算一对聚类和电影项目之间的 delta 值，我们需要确定将要放置的电影项目与聚类本身的相似性。为了简化基本 CLOPE 算法的演示，我们将基于确定电影流派、主演演员和工作室等电影属性的相似性来执行聚类。具体来说，我们将比较这些属性的值，例如，如果属性值完全或部分匹配，则意味着两个电影项目是绝对相似的）。
然而，由于我们即将通过一个以上属性（最多三个属性）比较电影项目，因此我们将使用以下方法来计算电影项目 Ik 和 It 之间的总体相似度值，以防两个属性完全匹配：
- 将每个属性的最大可能相似度度量定义为 1 / 属性数量；
- 检查电影项目 Ik 中的第一个属性值是否等于电影项目 It 的相同属性值。如果是，则将 1 / 属性数量 的值添加到相似度变量中，否则转到步骤 5；
- 检查电影项目 Ik 中的第二个属性值是否等于电影项目 It 的相同属性值。如果是，则将 1 / 属性数量 的值添加到相似度变量中，否则转到步骤 5；
- 检查电影项目 Ik 中的第三个属性值是否等于电影项目 It 的相同属性值。如果是，则将 1 / 属性数量 的值添加到相似度变量中，否则转到步骤 5；
- 检查获得的相似性值是否大于或等于 1 / 属性数量 * 所需属性数量。如果是，则认为电影项目 Ik 和 It 相似，否则不相似。
要通过部分匹配比较特定属性，我们通常对这些属性值进行归一化，最后解析它们以比较它们的特定片段。在执行归一化时，我们实际上移除了特定的属性片段，因为这些片段在 90% 的电影项目中是常见的。要比较一对电影项目的属性值，我们解析它们以获得两个标签数组，这些标签由这些属性的原始字符串值中的一组字符分隔。如果这两个字符串包含相同的标签，我们假设这两个电影项目是相似的。
使用代码
Movies_DB 抽象数据类型 (ADT)
为了能够处理电影数据，我们需要声明一个抽象数据类型来定义每个电影实体。具体来说，我们将使用一个简化版的电影数据库，其中只包含一个电影实体，该实体包含多个描述性属性，例如数据库中每部电影的 { id, title, year, price, starring actors, studio, genre, release date, price }。
class Movie : IEquatable<Movie>
{
public Movie()
{
this.ID = "0"; this.Title = "\0"; this.Year = "\0"; this.Starring = "\0";
this.Features = "\0"; this.Studio = "\0"; this.Genre = "\0"; this.Release = "\0"; this.Price = "\0";
}
public Movie(string id, string title, string year,
string starring, string features, string studio, string genre, string release, string price)
{
this.ID = id; this.Title = title;
this.Year = year; this.Price = price;
this.Starring = starring; this.Features = features;
this.Studio = studio; this.Genre = genre; this.Release = release;
}
public bool IsNotEmpty()
{
return (this.ID != "\0" && this.Title != "\0" && this.Year != "\0" && this.Starring != "\0" &&
this.Features != "\0" && this.Studio != "\0" && this.Genre != "\0" && this.Release != "\0");
}
bool IEquatable<Movie>.Equals(Movie other)
{
var similarity = 0.00;
if (this.Genre == other.Genre ||
((this.GenreEqualsByPartialMatch(other)) &&
(this.m_PartialMatch == true)))
{
similarity += 0.33;
similarity += (this.Studio == other.Studio) ? 0.33 : 0;
similarity += (this.Starring == other.Starring) ? 0.33 : 0;
}
return (similarity >= m_AttribsRequired * 0.33);
}
public bool EqualIDs(Movie other)
{
return (this.ID == other.ID);
}
public bool StarringEquals(Movie other)
{
return (this.Starring == other.Starring);
}
public bool StudioEquals(Movie other)
{
return (this.Studio == other.Studio);
}
public bool GenreEquals(Movie other)
{
return (this.Genre == other.Genre);
}
public bool GenreEqualsByPartialMatch(Movie other)
{
return (new GenreComparer().Equals(this.Genre, other.Genre) != false);
}
public string ID { get { return m_ID; } set { m_ID = value; } }
public string Title { get { return m_Title; } set { m_Title = value; } }
public string Year { get { return m_Year; } set { m_Year = value; } }
public string Starring { get { return m_Starring; } set { m_Starring = value; } }
public string Features { get { return m_Features; } set { m_Features = value; } }
public string Studio { get { return m_Studio; } set { m_Studio = value; } }
public string Genre { get { return m_Genre; } set { m_Genre = value; } }
public string Release { get { return m_Release; } set { m_Release = value; } }
public string Price { get { return m_Price; } set { m_Price = value; } }
private string m_ID;
private string m_Year;
private string m_Studio;
private string m_Genre;
private string m_Title;
private string m_Starring;
private string m_Features;
private string m_Release;
private string m_Price;
public bool m_PartialMatch;
public Int32 m_AttribsRequired;
}
class MovieItemStats : IEquatable<MovieItemStats>
{
public MovieItemStats(Movie SrcMovie, Int32 occurrences)
{
this.Movie = SrcMovie; this.Occurrences = occurrences;
}
public bool Equals(MovieItemStats other)
{
return this.Movie.Genre == other.Movie.Genre;
}
public Movie Movie { get { return m_Movie; } set { m_Movie = value; } }
public Int32 Occurrences { get { return m_Occurrences; } set { m_Occurrences = value; } }
private Movie m_Movie;
private Int32 m_Occurrences;
}
class Movies : IEnumerable<Movie>, IEquatable<List<Movie>>
{
private List<Movie> m_Movies;
public Movies() { m_Movies = new List<Movie>(); }
public Movies(List<Movie> MoviesTarget)
{
m_Movies = MoviesTarget;
}
public bool Equals(List<Movie> other)
{
return m_Movies.SequenceEqual(other);
}
public Movie this[Int32 Index]
{
get { return m_Movies[Index]; } set { m_Movies[Index] = value; }
}
public void Add(Movie SrcMovie) { m_Movies.Add(SrcMovie); }
public Movies Take(Int32 Count)
{
return new Movies(m_Movies.Take(Count).ToList());
}
public Movies Skip(Int32 Count)
{
return new Movies(m_Movies.Skip(Count).ToList());
}
public bool SequenceEquals(Movies other)
{
return m_Movies.SequenceEqual(other);
}
public IEnumerator<Movie> GetEnumerator()
{
return m_Movies.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
class Cluster : IEquatable<Cluster>
{
public Movies m_Movies = new Movies();
public Cluster() { this.UpdateCluster(true); }
public Cluster(Movies SrcMovies)
{
this.Movies = SrcMovies; this.UpdateCluster(true);
}
private List<MovieItemStats> GetMoviesStats()
{
List<MovieItemStats> MovieStats = new List<MovieItemStats>();
for (Int32 Index = 0; Index < Movies.Count(); Index++)
{
Int32 SrcMovie_count = Movies.Where(Movie => Movie.GenreEquals(Movies[Index])).Count();
if (!MovieStats.Contains(new MovieItemStats(Movies[Index], SrcMovie_count)))
MovieStats.Add(new MovieItemStats(Movies[Index], SrcMovie_count));
}
return MovieStats;
}
private double GetHeight()
{
List<MovieItemStats> MovieStats = GetMoviesStats();
return MovieStats.Sum(Stats => Stats.Occurrences) / (double)MovieStats.Count();
}
private double GetWidth()
{
return GetMoviesStats().Count();
}
private void UpdateCluster(bool Initialize = false)
{
if (Initialize == true)
{
this.Width = this.Height = 1;
}
else
{
this.Width = GetWidth(); this.Height = GetHeight();
}
}
public void AddMovie(Movie SrcMovie, bool UpdateRequired = false)
{
m_Movies.Add(SrcMovie);
if (UpdateRequired == true)
this.UpdateCluster(false);
}
public bool Equals(Cluster other)
{
return this.Movies.SequenceEquals(other.Movies);
}
public Movies Movies { get { return m_Movies; } set { m_Movies = value; } }
public double Width { get { return m_Width; } set { m_Width = value; } }
public double Height { get { return m_Height; } set { m_Height = value; } }
private double m_Height;
private double m_Width;
}
}
从文件加载数据
正如我们已经讨论过的，我们使用的电影数据集是存储在纯文本文件格式 (*.txt) 中的本地电影数据库。此时，我们将演示实现从文本文件检索和解析电影数据的算法代码：
private static Movies LoadDataFromFile(string filename)
{
Movies Movies = new Movies();
using (System.IO.FileStream fsFile = new System.IO.FileStream(filename,
System.IO.FileMode.Open, System.IO.FileAccess.Read, System.IO.FileShare.Read))
{
using (System.IO.StreamReader fsStream = new System.IO.StreamReader(
fsFile, System.Text.Encoding.UTF8, true, 128))
{
string textBuf = "\0";
while ((textBuf = fsStream.ReadLine()) != null)
{
string[] entry = Regex.Split(textBuf, "#");
if (entry != null && entry.Count() > 0)
{
var param_aliases = typeof(Movie).GetProperties();
int index = 0; Movie mv = new Movie();
foreach (var param in param_aliases)
param.SetValue(mv, entry[index++]);
if (typeof(Movie).GetProperties().Count() > 0)
Movies.Add(mv);
}
}
}
}
return Movies.Count() > 0 ? Movies : null;
}
为了从文本文件中检索每个电影项目，我们初始化了 `System.IO.FileStream` 和 `System.IO.StreamReader` 对象，并使用 `System.IO.FileStream.ReadLine()` 方法读取文件中的每一行文本，并解析每一行以检索特定的属性值。然后，我们检索 `Movie` 类对象的属性列表，并将当前行中的每个值分配给 `Movie` 类对象的每个特定属性。
初始化
为了用预定义的聚类数量初始化目标聚类列表，我们实现了以下方法：
static Movies Init(string filename, bool partial_match, Int32 attribs_required)
{
Movies Movies = new Movies();
if ((Movies = LoadDataFromFile(filename)) != null)
{
if (m_Clusters != null && m_Clusters.Count() == 0)
{
List<Cluster> ClustersInitialSet = new List<Cluster>();
for (Int32 Index = 0; Index < Movies.Count(); Index++)
{
Movie SrcMovie = Movies[Index];
SrcMovie.m_PartialMatch = partial_match;
SrcMovie.m_AttribsRequired = attribs_required;
Cluster TargetCluster = new Cluster(new Movies(
new List<Movie>() { SrcMovie }));
if (!m_Clusters.Contains(TargetCluster))
m_Clusters.Add(TargetCluster);
}
m_Clusters.AddRange(ClustersInitialSet);
}
}
return Movies;
}
聚类
为了执行实际的聚类，这里有一系列方法，其中包含实现 CLOPE 聚类过程的代码片段。执行实际聚类的第一个方法是 `GetDelta` 方法，它执行 delta 值计算：
public static double GetDelta(Cluster SrcCluster, Movie SrcMovie)
{
double Width_New = SrcCluster.Width;
Int32 cluSizeNew = SrcCluster.Movies.Count() + 1;
if (!SrcCluster.Movies.Contains(SrcMovie))
Width_New = Width_New + 1;
return cluSizeNew * 2 / Math.Pow(Width_New, 2) -
SrcCluster.Movies.Count() / Math.Pow(SrcCluster.Width, 2);
}
实际聚类通过执行实现为 `Clusterize` 方法的代码来完成：
static void Clusterize(Movies Movies)
{
for (Int32 Index = 0; Index < Movies.Count(); Index++)
{
bool Exists = false;
List<Movies> MoviesList = m_Clusters.Select(Cluster => Cluster.Movies).ToList();
for (Int32 MoviessIndex = 0; MoviessIndex < MoviesList.Count() && !Exists; MoviessIndex++)
Exists = (MoviesList[MoviessIndex].Where(Movie
=> Movie.Equals(Movies[Index])).Count() > 0) ? true : false;
if (Exists == false)
{
double delta_max = -1; Int32 cluMaxIndex = -1;
for (Int32 Cluster = 0; Cluster < m_Clusters.Count(); Cluster++)
{
double delta = GetDelta(m_Clusters[Cluster], Movies[Index]);
if (delta > delta_max || delta_max == -1)
{
delta_max = delta; cluMaxIndex = Cluster;
}
}
m_Clusters[cluMaxIndex].AddMovie(Movies[Index], true);
}
}
}
数据归一化和解析
为了通过部分匹配计算特定电影项目之间的相似性，同时执行数据归一化，以下两个方法 `NormalizeGenre(...)` 和 `Equals(...)` 作为 `IEqualityComparer
class GenreComparer : IEqualityComparer<string>
{
public GenreComparer() { }
public List<string> NormalizeGenre(string genre_tags)
{
List<string> GenreTags = genre_tags.Split(new char[] { ' ', ',' },
StringSplitOptions.RemoveEmptyEntries).Distinct().
Where(Tag => Tag.Length > 1).ToList();
return GenreTags.Select(Tag => (Tag.IndexOf('-') > -1) ?
Tag.Substring(0, Tag.IndexOf('-')) : Tag).Distinct().ToList();
}
public bool Equals(string genre_tags1, string genre_tags2)
{
Int32 EqualsCount = 0;
List<string> tags_list1 = NormalizeGenre(genre_tags1);
List<string> tags_list2 = NormalizeGenre(genre_tags2);
if (tags_list1.SequenceEqual(tags_list2)) return true;
for (Int32 Index1 = 0; Index1 < tags_list1.Count(); Index1++)
for (Int32 Index2 = 0; Index2 < tags_list2.Count(); Index2++)
if (tags_list1[Index1].Equals(tags_list2[Index2])) EqualsCount++;
return (EqualsCount > 0) ? true : false;
}
public int GetHashCode(string obj)
{
throw new NotImplementedException();
}
}
我们还实现了一系列函数，用于执行各种服务操作，例如呈现聚类结果或检查每个聚类的有效性。
static bool IsValidCluster(Cluster TargetCluster)
{
bool isUnique = false;
Movie mvTarget = TargetCluster.Movies[0];
isUnique = TargetCluster.Movies.Skip(1).Where(Movie =>
Movie.Equals(mvTarget)).Count() == TargetCluster.Movies.Count() ? true : false;
return !isUnique;
}
static void PrintClusters()
{
Console.WriteLine("Clustering Statistics...");
Console.WriteLine("========================");
for (Int32 Index = 0; Index < m_Clusters.Count(); Index++)
{
bool IsValid = IsValidCluster(m_Clusters[Index]);
Console.WriteLine("Cluster {0}: (Valid: {1}, Movies: {2})", Index,
(IsValid == true) ? "Okey" : "Failed", m_Clusters[Index].Movies.Count());
}
Console.WriteLine("\nClustering Results...");
Console.WriteLine("=======================");
for (Int32 Index = 0; Index < m_Clusters.Count(); Index++)
{
Movies Movies = m_Clusters[Index].Movies;
Console.WriteLine("Cluster {0} (Genre: {1}) (Valid: {2}):",
Index, Movies[0].Genre, (IsValidCluster(m_Clusters[Index])) ? "Okey" : "Failed");
Console.WriteLine("==================================================================");
for (var Movie = 0; Movie < Movies.Count(); Movie++)
{
String movie_row = "\0";
var param_aliases = typeof(Movie).GetProperties();
foreach (var param in param_aliases)
movie_row += param.GetValue(Movies[Movie]).ToString() + " ";
Console.WriteLine("{0}", movie_row);
}
Console.WriteLine();
}
}
此 CLOPE .NET 应用程序的主要功能
static void Main(string[] args)
{
Console.WriteLine("CLOPE - Clustering Algorithm v.1.00a by Arthur V. Ratz @ CodeProject.Com");
Console.WriteLine("=====================================================================\n");
string filename = "\0";
string MatchOption = "\0"; bool PartialMatch = false;
Console.Write("Input data file name: "); filename = Console.ReadLine();
Console.Write("Input the number of required attributes: ");
Int32 AttribsRequired = Int32.Parse(Console.ReadLine());
Console.Write("Clusterize by partial match: (y/n)");
do
{
MatchOption = Console.ReadLine();
PartialMatch = ((MatchOption == "y") || (MatchOption == "yes")) ?
(((MatchOption != "n") && (MatchOption != "no")) ? true : false) : false;
} while (((MatchOption != "y") && (MatchOption != "yes")) &&
((MatchOption != "n") && (MatchOption != "no")));
Console.WriteLine("\n");
Clusterize(Init(filename, PartialMatch,
AttribsRequired)); PrintClusters(); Console.ReadKey();
Console.ReadKey();
}
关注点
在本文中，我们详细讨论了革命性的新 CLOPE 聚类算法。然而，并非所有读者可能感兴趣的话题都在本文中涵盖。也许一些编程和算法爱好者会花一些时间来评估此算法，通过实现算法的学习阶段并实时调查其特性，并将其与传统 k-means 聚类进行比较。此外，值得使用不同的数据集和各种属性值来研究以下算法。
历史
- 2018年4月27日 - 本文首次发布；