基于最小生成树启发的聚类异常检测技术

### 基于最小生成树启发的聚类异常检测技术 #### 1. 异常检测方法概述 在数据挖掘领域，异常检测是一项重要任务。目前主要有基于距离、基于密度和基于聚类的异常检测方法。 - **基于距离的异常检测**：适用于检测简单结构数据集中的全局异常值，即包含一个或多个密度相似的聚类的数据集。但对于具有复杂结构的真实世界数据集，不同部分可能具有非常不同的特征，这种方法可能无法找到所有有趣的异常值。 - **基于密度的异常检测**：为解决基于距离方法的不足，Breunig 等人提出了局部异常因子（LOF）的概念，通过比较对象周围的局部密度与相邻对象的局部密度来判断对象的异常程度。具体步骤为： 1. 计算数据集中每个对象的 LOF 值。 2. 根据 LOF 值对所有对象进行排序。 3. 将 LOF 值最大的前 n 个对象标记为异常值。 不过，精确计算每个数据对象的 LOF 值计算量较大。为解决此问题，Jin 等人提出使用微聚类的概念来高效挖掘大型数据库中基于 LOF 的前 n 个异常值。此外，还有一些扩展和改进方法，如基于连通性的异常因子（COF）、局部异常积分（LOCI）和空间局部异常度量（SLOM）等。LOF 和 LOCI 的主要区别在于，前者使用 k 近邻，而后者使用 ε - 邻域。 - **基于聚类的异常检测**：基于距离和基于密度的异常检测算法对某些参数的设置非常敏感。而聚类算法可以在一定程度上帮助解决这个问题。聚类算法的主要目标是通过优化某些标准（如最小化簇内距离和最大化簇间距离）来找到聚类。作为副产品，小群体中的数据项通常可以被视为异常值（噪声），需要去除以提高聚类的可靠性。 经典的聚类算法，如 k - 均值算法或 PAM，依赖于围绕某些“中心”对数据点进行分组，当聚类的边界不规则时效果不佳。而基于图论的方法，如基于最小生成树（MST）的聚类算法，可以找到具有不规则边界的聚类。 #### 2. 最小生成树（MST）相关概念 最小生成树是一个连通的加权图，没有封闭路径，包含数据集中的每个点，并且总权重最小。如果为每条边分配一个表示两个端点之间距离的权重，那么 MST 中的任何边都是连接两个子树的最短距离，这就是 MST 的割属性。因此，移除最长的边对应于选择分割点来形成聚类。 基于 MST 的聚类算法最初由 Zahn 提出，至今已得到广泛研究。一些基于 MST 的异常检测技术也被提出，认为通过切割 MST 中最长的边形成的最小聚类中的数据点可能是异常值。但这些基于 MST 的聚类算法计算量非常大，时间复杂度从 O(NlogN) 到 O(N²)。 最近，一种具有近似线性性能的基于 MST 的聚类算法被开发出来，其 CPU 高效的 MST 聚类算法包括三个阶段： 1. **构建简单生成树**：为后续操作提供基础结构。 2. **使用改进的 K - 均值算法（DHCA）**：生成接近真实最小生成树的生成树，以快速识别最长的边。 3. **利用 MST 的割和循环属性进行聚类**：完成数据的聚类操作。 对于给定的数据集，DHCA 从 K 个随机选择的中心开始，将每个点分配到其最近的中心，创建 K 个分区。然后，对于每个分区，递归地选择 K 个随机中心，并在每个分区内继续聚类过程，直到分区中的元素数量低于 K + 2。此时，可以通过暴力最近邻搜索更新每个数据项到该分区中其他数据项的距离。这种策略确保空间上接近的点可能位于同一分区。 #### 3. 改进的 MST 异常检测算法 大多数基于 MST 的聚类算法需要首先构建完整的 MST，对于现代大型数据库来说，这计算量非常大。因此，提出了一种新的方案来促进现代大型数据库中基于 MST 的高效异常检测。其核心思想是，如果能够快速找到 MST 中的最长边，就无需计算与最短边相关的精确距离值。在一些情况下，分隔聚类（包括噪声聚类）的最长边数量可能远少于较短边的数量，此时如果能在找到大多数较短边之前快速识别最长边，就可以减少距离计算的数量，使其小于 O(N²)。 ##### 3.1 简单思路 基于通过顺序初始化和 DHCA 更新构建的接近真实 MST 的生成树，搜索具有最大值的边（潜在最长边候选），并将其切断以形成两个分区。如果一个分区中的数据项数量不超过 p，则检查是否存在另一个权重较小的边跨越由该潜在最长边候选连接的两个分区。这可以通过不超过 p(N - p) 次距离计算来完成。如果结果表明不存在这样的边，则将这些数据项声明为异常值；否则，记录更新（即用跨越两个分区的权重较小的边替换潜在最长边候选），并在 MST 中开始另一次最长边候选的搜索。 ##### 3.2 检测局部异常值 考虑到数据集可能具有复杂结构，不同部分的密度特征可能差异很大，仅基于数据点之间的简单距离来衡量异常程度是不够的。因此，进一步为每个异常候选计算 LOF 值，直到发现所需数量的异常值。 为了提高 LOF 计算效率，可以利用近年来为高维特征空间提出的许多索引结构，如 iDistance。iDistance 包括三个步骤： 1. **数据分区**：将数据聚类成一组分区。 2. **确定参考点**：为每个分区