1 个不稳定版本
| 0.1.0 | 2019年11月25日 |
|---|
#1115 在 算法
1.5MB
474 行
clusterphobia - 为害怕聚类的人提供的 Rust 包
此包基于在 C# 中最初在以下仓库中开发的想法和算法
https://github.com/paulchernoch/HilbertTransformation
要了解理论，请参阅 clusterphobia GitHub 仓库中的 SLASH.pdf
https://github.com/paulchernoch/clusterphobia
项目目标
Clusterphobia 旨在为数据的 可扩展、高维、无监督、平面、单分类 提供聚类工具。
- 可扩展性：库的一个基本特性是使用希尔伯特曲线（来自 hilbert 包）来加速 k-最近邻搜索。此算法的复杂度与维数的数量成线性关系，而许多其他算法的复杂度随着维数的增加而指数增长。算法的部分运行时间与 N Log N 成正比，其中 N 是正在聚类的点的数量。
- 高维 - 该算法可以处理高达一万个维度的数据。
- 无监督 - 聚类在未标记的数据上执行。
- 平面 - 算法将项目分组为平面、互斥的类别集合，而不是层次结构。
- 单 - 每个项目被分配一个单个类别。项目不能属于多个类别。
将使用两种主要方法来聚类数据
- 自底向上，单链接层次聚类
- 自底向上，基于密度的聚类
功能区域
完成后，此包将具有以下主要功能区域
- 数据准备：调整原始数据，直到坐标值是相等的、非负整数。调整包括缩放、移位和加权每个维度。对于表示为词袋的文档，将使用新颖的随机变换。 (一些变换由 Hilbert 包提供。)
- 点表示：将准备好的数据转换为适合聚类算法的
Points。 (ThePoint结构在 Hilbert 包中定义，并使用优化的欧几里得距离公式，这对于最近邻搜索至关重要。) - 关联分析 - 使用 希尔伯特曲线 对
Point数据进行分析，并得出关联距离和密度阈值。这些值对于聚类算法至关重要。（如果两点之间的距离小于 关联距离，则假定它们属于同一簇。如果一个点集落在半径不超过 密度阈值 的区域内，则认为Point密度足够高，从而强制进行聚类。） - 簇表示 - 一个
Clustering包含分区方案中每个类别的Cluster。它支持将点添加到簇中、重新分类它们以及合并簇等操作。Clustering是聚类过程的主要输出。 - 簇相似度 - 为了测试和迭代地细化维度、缩放因子、阈值和可调参数的选择，你需要能够比较一个完美辅助的解决方案和未辅助的聚类。这个库提供了一个优化后的 B-Cubed 测量方法，其运行时间是线性的（而不是二次的）。
- 聚类算法 - 这些算法将一组
Points排列成一个Clustering。 - 问题数据 - 相同的测试数据集在许多论文中都出现过，因为它们包含许多聚类算法都无法处理的特征，例如螺旋线、含噪声的簇或部分重叠的簇。这个库中的算法将被调整以解决尽可能多的问题。
目前正在工作
以下功能已准备就绪
- 一些数据准备转换（来自 hilbert 库），包括
IntegerDataRange和FloatDataRange。 - Hilbert 曲线转换、排列和排序（来自 hilbert 库）
Point结构与优化的距离公式（来自 hilbert 库）Clustering结构，可用于构建和修改分类方案。BCubed结构，可用于表示相似度度量并计算两个簇之间的相似度（对于单元测试和调整至关重要）。
簇相似度
关于簇相似度的算法在文献中非常多。没有一种算法能够完美处理所有边缘情况。一种能够很好地处理许多常见用例且运行成本不高的度量方法被称为 B-Cubed，这个名字取自其创建者的首字母。自最初提出以来，其他人也对其进行了修改。
B-Cubed 测量方法是在 1998 年的这篇论文中提出的
[1] A. Bagga 和 B. Baldwin。 基于实体跨文档共指引用的向量空间模型。在计算语言学协会第 36 届年会论文集 - 第 1 卷，ACL ‘98，第 79-85 页，1998。
以下论文比较了许多聚类算法，并发现根据四个正式约束，B-Cubed 是最好的
- 簇同质性
- 簇完整性
- 杂乱无章
- 簇大小与数量
[2] 《基于正式约束的外部聚类评估指标比较》由 Enrique Amigo、Julio Gonzalo、Javier Artiles、Felisa Verdejo 撰写，他们是西班牙马德里联合国教育、科学和文化组织语言与信息系统系的成员，2009 年 5 月 11 日
以上内容可在以下链接找到：http://nlp.uned.es/docs/amigo2007a.pdf
随后的论文确定了一个 B-Cubed 表现不佳的用例：不平衡数据集，其中一个簇占主导地位
[3] 《将自适应 B-CUBED 指标应用于不平衡数据集》由 Jose G. Moreno 和 Gael Dias 撰写，他们是法国诺曼底大学的成员。
本文提出了B-Cubed的改进版本，但增加的复杂性显著增加了处理时间，因此这里没有采用这些改进。这里使用的算法定义取自最后一篇论文的2.1节，其中使用F-measure公式（调和平均）将精度和召回率合并成一个数值。（改进版本在2.2节。）
𝔽 = F-measure (final similarity measure)
ℙ = Precision (a measure of homogeneity)
ℝ = Recall (a measure of completeness)
α = Weighting factor (defaults to 0.5)
ℕ = Number of points
k = Number of categories (varies between the π and π* Clusterings)
i = category index
πᵢ = cluster solution for the ith category
π*ᵢ= gold standard for the ith category
g₀ = tests whether two items share the same category in the clustering
g*₀= tests whether two items share the same category in the gold standard
𝟙 α 𝟙 - α
━━━━━ ═ ━━━━━ + ━━━━━
𝔽 ℙ ℝ
b³ b³ b³
k
ℙ 𝟙 ⎲ 𝟙 ⎲ ⎲
b³ ═ ━━━ ⎳ ━━━━━ ⎳ ⎳ g*₀(xⱼ,xₗ)
ℕ i=1 |πᵢ| xⱼ∈πᵢ xₗ∈πᵢ
k
ℝ 𝟙 ⎲ 𝟙 ⎲ ⎲
b³ ═ ━━━ ⎳ ━━━━━ ⎳ ⎳ g₀(xⱼ,xₗ)
ℕ i=1 |π*ᵢ| xⱼ∈π*ᵢ xₗ∈π*ᵢ
( 𝟙 ⟺ ∃l:xᵢ∈πₗ ∧ xⱼ∈πₗ
g₀(xᵢ,xⱼ) ═ <
( 𝟘, otherwise
( 𝟙 ⟺ ∃l:xᵢ∈π*ₗ ∧ xⱼ∈π*ₗ
g*₀(xᵢ,xⱼ) ═ <
( 𝟘, otherwise
如果看到三重嵌套求和符号让您感到犹豫并说“这要运行很长时间”，那也是我的反应。内部两个循环执行一种二次矩计算，试图了解根据一种方案共享同一簇的项目中有多少比例在另一种方案中也共享匹配的簇，反之亦然。以下是一个例子。
1 2 3 4
A A B B
┍━━━━━━━━━┓
1 A│ ✓✓ │
2 A│ ✓✓ │
3 B│ ✓✓ │
4 B│ ✓✓ │
┗━━━━━━━━━┛
在这个例子中
- 第一次聚类将项目1、2、3、4都放在同一个簇中。
- 第二次聚类将1和2放在簇A中，3和4放在簇B中。
- 网格显示第二个聚类中每个点属于哪个簇，以及继续聚在一起点的对用勾号（✓）标记。
测量第二次聚类对第一次聚类项目的影响，就是计算网格中的勾号数量。B-Cubed的全度量通过每个簇的大小对度量进行归一化。
我发现的一个优化是，如果两个项目最终落在同一个簇中，将有四个勾号，但如果三个匹配，将有九个勾号，依此类推。因此，如果您有一个列表，列出了第二次聚类中点映射到的所有类别，以及每个类别中有多少项目最终落在该类别中，那么您只需对这些计数求平方和。
我找到了另一个技巧——您可以在单次遍历中完成这个操作！保持每个类别中计数平方和的运行总和，如果您看到某个计数从一增加到二，那么您只需添加一和四之间的差值，即三。如果从二增加到三，平方和的增加是9 - 4 = 5。差异始终是2 * previous_count + 1。
无论如何，这就是我将二次算法降低为线性算法的方法。
即将推出...
接下来要实现的功能是链接分析。
依赖关系
~9–20MB
~267K SLoC