17种常用的数据科学和挖掘聚类算法

基于模型/分布的聚类
概率建模

概率模型是由数据变量的联合分布参数化的生成数据模型：P(x1, x2, ..., xn, y1, y2, ...,yn|θ) 其中 X 是观察到的数据，y：潜在变量，θ a范围。

P(y1,…,yn|x1,…,xn, θ) = P(x1,…,xn, y1,…,yn|θ)(联合) / P(x1,…,xn|θ)(边际概率)

学习

学习阶段使用最大似然进行：

θML = argmax θ P(x1,…,xn|θ)

目的是找到一个使观测数据的概率最大化的参数 θ。

预测

P(xn+1, yn+1|x1,…,xn, θ)

目标是计算给定观察数据集的潜在属性的条件分布。

分类

目标是找到一个类，在给定学习参数 θ 的情况下，最大化未来数据的概率：

argmax c P(xn+1|θc )

概率建模中使用的一些标准算法是 EM 算法、MCMC 采样、连接树等。

11、GMM：高斯混合模型

在二维变量空间中，高斯分布是使用两个具有正态分布的随机变量构建的二元正态分布，每个变量都通过其均值和标准差进行参数化。

在我看来，高斯分布之所以如此重要，是因为它使计算（例如，线性代数计算）变得毫不费力。然而，它并不是实际应用的完美模型。


3d 空间中的高斯及其投影

高斯混合模型是一种半参数模型（有限数量的参数随数据增加。）用作软聚类算法，其中每个聚类对应于一个生成模型，旨在发现概率分布的参数（例如，平均值，给定集群的协方差、密度函数……）（它自己的概率分布控制每个集群）。学习的过程是将高斯模型拟合到数据点。高斯混合模型假设集群在 n 维空间中呈正态分布。


一维空间中的协方差矩阵和高斯公式

为了说明一维空间中的混合模型，假设有两个具有正态分布的信息源，其中从每个源收集了 n 个样本。为了估计每个高斯分布的平均值，取观测值的总和，然后将它们除以收集的样本数（经验平均值。），同样用于估计其他参数。

当有 k 个高斯模型时，问题就出现了，并且没有给出观测值来自何处的信息；弄清楚如何将点划分为 k 个簇并不容易。因此，几乎不可能估计每个高斯参数。但是，如果预定义了高斯参数（均值，方差），则可以解决此问题。

这就是 EM 方法试图解决的问题。

12、EM：聚类背景下的期望最大化
它是一种众所周知的拟合混合分布的算法，旨在在某些数据点不可用时（例如，未知参数、潜在值...... ）。在 GMM 的上下文中，直觉是在空间中随机放置 k 个高斯模型，并计算每个数据点对某个高斯模型的归属度。与硬聚类（例如，k-means）不同，该方法计算每个点成为某个聚类成员的概率。此外，这些值用于重新估计集群参数（例如，均值、协方差）以拟合分配给每个集群的点。

EM 被广泛用于解决诸如“隐藏数据”问题、隐藏马尔可夫模型等问题，其中存在一系列潜在变量，这些潜在变量取决于先前隐藏变量的状态。此外，每个观察都取决于相应隐藏变量的状态。


隐马尔可夫模型

πₖ是给定先前状态 k 的转移概率。箭头描述变量之间的依赖关系。

算法

EM算法由两个步骤组成，期望步骤和最大化步骤。

步骤 0：参数 thetas 的初始化。

E-Step：在这一步中，假设当前假设在质心μj和协方差下成立，通过计算每个潜在数据点的归一化期望值Wij （每个分布中数据点的权重）来估计观测值来自哪个分布集群 J 的矩阵Σj：



P(xi|K=j, θ)是多元正态分布Xi~N(μi, Σi) 的条件概率。

每个集群都有概率𝜋( prior )，可以根据训练数据集进行估计。



M-Step：使用从上一步获得的信息，M-Step 将使用新的最大似然假设更新均值μj和协方差Σj（或方差𝜎 ）的估计值，假设每个隐藏变量的值是期望值。


重复 E 和 M 步骤，直到对数似然函数收敛。


对数似然函数


对数似然图

利用每次迭代后似然性单调增加的事实，该算法更有可能收敛到最优值。

为了演示 EM 算法，让我们考虑从三个高斯模型（a、b、c）生成的观察结果。由于每个样本都是未标记的，因此目标是估计这三个高斯模型的参数，以将每个点标记为特定的高斯分布。为了估计这些参数，三个高斯模型被随机放置在一维数据集空间中。

1、计算从具有以下密度函数的三个高斯模型生成的每个数据点的似然性。


2、E-Step：对于每个数据点，计算其权重 wi(ai, bi, ci)。


3、 M-Step：此时可以估计每个模型的均值和方差。


4、估计概率。


5、重复 E 和 M 步骤，直到对数似然函数收敛。

具有 3 个集群的 1d GMM。


具有 3 个集群的 2d GMM。

优点

• 它为混合分布生成有效的参数估计。
• 实现起来非常简单。
  

缺点

• 为 k（混合模型的数量）选择一个初始值，就像在 k-means 中一样。
• 对初始值敏感，导致结果不同。
• 可能收敛到局部最优解。
• 收敛可能很慢。
  

13、DMM：狄利克雷混合物模型


狄利克雷过程

Dirichlet 过程是一个随机过程，它在离散分布（概率度量）上产生分布，用于定义贝叶斯非参数（未固定的参数集。例如，~无限数量的参数。）模型。狄利克雷分布是一个连续多元密度函数，由具有正分量的浓度/精度参数/向量 (α₁, …, αₖ) 和基本分布 H: DP(α, H) 参数化。它就像一个 Beta 分布（例如，Coinflip），用于两个以上的结果。


联合分布的图形模型

k维狄利克雷：(π₁, π₂, …, πₖ) ~Dirichlet(α₁, α₂,…, αₖ)

Thetas 是独立的参数，并且在 H 上均匀分布，目标是在给定观测值 xi 的情况下推断参数 θ 和潜在变量。


不同α > 1值的狄利克雷分布和样本

• α = (1, 1, 1)，该图表示均匀分布
• α > (1, 1, 1)，该图表示单峰分布
• 0 < α < (1, 1, 1)，该图表示多峰分布
  

不同α < 1值的狄利克雷分布和样本

狄利克雷分布的一大特性是，当合并两个不同的分量（πi，πj）时，它会产生一个边缘分布，即通过对参数（αi，αj）求和而参数化的狄利克雷分布。它类似于降维的思想。此属性称为折叠。另一个性质是可以证明具有伽马分布的随机变量遵循狄利克雷分布。

π是经常使用著名的断棍示例描述的概率。为了解释这些值，一根长度为一个单位的棍子用于随机生成一个介于 0 和 1 之间的数字（棍子的最大长度），在该数字处棍子将被折断。一旦生成了，就可以在长度π处折断棍子，该长度表示来自 Beta 分布的随机值，其中 1 和 α 作为参数：π ～ Beta(1,α)。通过打破那根棍子，它将生成一个概率质量函数 (PMF)，其中两个结果的概率分别为π和1-π。两根木棍可以类似地进一步折断，因此所有木棍的长度之和必须等于 1。而且这个过程可以无限重复。


断棍的例子


y 轴表示后验的预期混合权重 ( πi )。x 轴表示组件的数量

狄利克雷分布通常在主题建模和 LDA（潜在{隐藏主题}狄利克雷{狄利克雷分布}分配）的上下文中进行解释。LDA 的工作原理是将许多文档聚集成包含相似词的主题，而无需事先了解这些主题。LDA 通过从两个分布（按文档分布主题，按主题分布单词）中采样来构建文档。


联合分布的图形模型

在 LDA 中，每个主题在词上都有一个多项分布 (H)，每个文档都是从参数化为α的狄利克雷分布 ( π ) 中采样的，每个词 (xi) 是从具有参数化的多项分布的隐藏主题 (Zi) 中采样的π。

通过对每个文档进行分类，LDA 倾向于通过最大化其概率来使每个文档有意义，如下所示：



然而，最大化这个公式是相当昂贵的。因此，吉布斯采样用于最大化方程的每个参数（单词：x，主题：z…）。

14、LDA 算法

1、初始化主题数 k
2、将每个文档的每个单词随机分类为一个主题。
3、对每个文档进行迭代，并计算以下概率：



4、将每个单词重新分类到给定的主题。
5、重复直到前面的公式达到最大值。



优势

• 对于大型数据集非常高效和灵活。
• 算法的工作流程独立于其他任务。
  

缺点

• 主题数量 k 必须提前定义。
• 不相关的话题。
  

基于密度的聚类

在基于密度的聚类中，数据空间中的密集区域与密度较低的区域分开。如果某个位置的密度大于预定义的阈值，则将观测值分配给给定的集群。

对于一个集群中的给定观察，该点周围的局部密度必须超过某个阈值。局部密度由两个参数定义：圆的半径ε，该圆包含给定点周围一定数量的邻居，以及该半径周围的最小点数：minPts。

定义

eps -Neighborhood：给定点的半径为 eps 的圆的面积。

密度可达：点 p 被描述为从点 q 相对于 Eps 和 MinPoints 可达的密度，如果有一组点 (p1, p2, ..., pi,..., pn) 以这样的方式 pi+1 可以直接从圆周率。

直接密度可达：点 p 被描述为从点 q 相对于 Eps 和 MinPoints 的直接密度可达，当且仅当 p 属于半径为 Eps 的圆并且该圆的半径大于或等于 MinPoints。

密度连接：点 p 被描述为与点 q 相对于 Eps 和 MinPoints 的密度，当且仅当存在 从 p 和 q 密度可达的点 w 时。


可达性类型

优势

• 不需要簇数 k。
• 发现更复杂的星团形状（例如卫星形状的星团）。
• 异常值检测。
  

缺点

• 对拓扑连接的对象进行分类在计算上是不可行的。
• 不像 K-means 那样保持可扩展性。
• 对 EPS、MinPts 敏感
• 密度测量受采样数据点的影响。
  

15、DBSCAN：基于密度的基于噪声的应用程序空间聚类


DBSCAN 发现 4 个集群

它是迄今为止最流行的基于密度的聚类算法，在Google Scholar上被引用超过 41k 。中心思想是将观察结果划分为 3 种类型的点组：

1、核心点： ε-邻域有超过minPts个点。


minPts = 5

2、边界点：小于ε内的minPts但在核心点附近。

B点可以从核心点A到达。
3、 噪声或异常点：所有剩余点：不是核心点，并且距离不够近，无法从核心点到达。


解释

它首先随机选择一个尚未分配给集群的点。然后算法确定它是核心点还是异常值。一旦找到一个核心点，它的所有密度可达观测值都将被添加到一个集群中。之后，该算法将对每个可直接到达的点执行邻居跳转并将它们添加到集群中。如果添加了异常值，则将其标记为边界点。然后，该算法会选择另一个核心点并重复前面的步骤，直到所有点都被分配到集群或标记为异常值。

算法

• 随机选择一个点P。
• 在给定eps和minPts的情况下，发现从 P 密度可达的所有点。
• 检验 P 是否为核心点。将形成一个集群，其中至少有一个核心点、可到达的核心点及其所有边界。
• 重复前面的步骤，直到遍历完所有点。
  

优点

• 能够确定任意形状的簇。
• 对异常值的敏感性较低。
• 可作为异常值检测。
• 有效地处理任何大小的数据集。
  

缺点

• 对于高维数据集不能很好地扩展。
• 取决于几个超参数。
• 寻找不同密度的集群的问题。
• 仅适用于数值数据。
  

应用程序
它广泛用于异常检测、科学文献和其他应用。

16、ADBSCAN：自适应DBSCAN

顾名思义，该算法与前一种算法的不同之处在于，它根据每个集群的密度分布调整了Eps和MinPts的值。它会自动找到正确的 Eps 和 MinPts 值。

它首先随机选择Eps的值。然后，它在数据集上运行 DBSCAN，如果找不到集群，它将Eps的值增加0.5。当算法找到一个集群（10% 的相似数据）时，它会从数据集中排除该集群。并且，该算法不断增加 Eps 的值以找到下一个集群。一旦算法成功完成扫描大约 95% 的数据，剩余的数据点将被宣布为异常值。

但是，ADBSCAN 需要数据集中的簇数的初始值。有关更多信息，请考虑阅读本文。

17、DENCLUE：基于DEN位置的CLU st E环

DENCLUE 应用核密度估计方法来估计生成数据样本的随机变量的未定义概率密度函数。该估计基于表示每个数据点的分布的核密度函数（例如，高斯密度函数）。然后，通过对它们求和（或积分）来计算所有先前函数的核密度估计。


基于样本分布的核密度估计（KDE）

核是一种数学函数，用于对数据点与其邻居之间的影响进行建模。此外，核密度函数具有以下属性：

• 非负性：K(x) ≥ 0
• 对称：K(x) = K(-x)
• 内核下的面积必须等于一个单位。
• 递减：K'(x) ≤ 0
  

不同类型的一维内核

DENCLUE 使用密度吸引子的概念，作为在周围形成簇的观察的代表。

具有两个密度吸引子的二维内核示例

有两种类型的集群：

• 中心定义的簇：它是通过将吸引到给定密度吸引子的点的密度分配来形成的。
• 任意形状的簇：由具有高密度（>给定阈值）的密度吸引子合并而成
  

算法

• 通过添加所有数据点的密度函数来估计数据空间的整体核密度函数。
• 通过识别构成估计密度函数的局部最大值的密度吸引子来形成簇。
• 使用爬山算法和估计的密度函数的梯度计算局部最大值。
  

优点

• 比 DBSCAN 快得多。
• 灵活适用于任意形状的集群。
• 适用于任何大小的数据集。
  

缺点

• 对于高维数据集不能很好地扩展。
• 取决于几个超参数。
• 仅适用于数值数据。
  

18、OPTICS聚类算法（Ordering Points To Identify Clustering Structure）

由于 DBSCAN 的性能取决于其参数设置，Optics 扩展了 DBSCAN，使其对参数设置和查找簇之间的结构不太敏感。直觉是，基于两个参数，高密度区域将在低密度区域之前首先被处理：

• 核心距离：至少包含 MinPts 观测值的最小半径 eps。
• 可达距离：使两个观测值密度可达的最小距离。
  

话虽如此，OPTICS根据它们的密度结构形成有序的观察簇。此外，它使用所有点的可达距离的计算值作为阈值，以分离数据和异常值（位于红线上方的点）。


算法

• 从数据集中选择一个随机数据点。
• 通过计算 eps-neighborhood 内的核心距离来判断所选点是否为核心点。
• 如果选择的点是核心点，那么对于彼此的观察，更新与之前选择的点的可达距离。此外，将新观察插入到 OrderSeeds 中，其中包含按可达距离排序的点。
• 如果所选点不是核心点，则移动到 OrderSeeds 中的下一个观测值，如果 OrderSeeds 为空，则移动到初始数据点中的下一个观测值。
• 重复直到遍历所有观察。
  

优点

• 能够发现内在和分层嵌套的聚类结构。
• 需要与 DBSCAN(eps 和minPts )相同数量的参数，但不需要 eps，这降低了算法的运行时复杂度。
• 能够找到具有不同密度的集群。
  

缺点

• 没有密度下降的集群的问题。
• 仍然对参数minPts敏感。
  

应用程序
光学可用于异常检测（发现异常值）。

异常检测

结论

在本文中，您了解了如何将聚类分析用作一种强大的技术来发现模式并从数据中提取见解。但是，决定是否选择给定的聚类算法取决于几个标准，例如聚类应用程序的目标（例如，主题建模、推荐系统……）、数据类型等。此外，数据挖掘团队有责任决定选择最适合他们需要的。

想试试 但又怕不成功

thx for sharing~