图核同嗜度聚类与高维不确定数据约束子空间聚类算法

# 图核同嗜度聚类与高维不确定数据约束子空间聚类算法 ## 1. 聚类算法面临的挑战与新方法提出 数据聚类是数据挖掘中的重要技术，它通过将数据集划分为多个簇，使得同一簇内的对象比不同簇内的对象更相似。然而，传统聚类算法在处理不确定数据和高维数据时面临巨大挑战。 ### 1.1 传统聚类算法的困境 - **不确定数据**：在许多实际应用中，如基于位置的服务和传感器监测，由于数据源过时或测量不精确，数据的属性值可能在一定范围内变化，传统聚类算法难以处理这种不确定性。 - **高维数据**：高维数据的聚类通常在子空间中形成，子空间的搜索和簇的检测相互依赖，增加了聚类的难度。 ### 1.2 新方法的提出 为了解决这些问题，研究人员提出了多种聚类算法，包括基于图核同嗜度的聚类方法和基于约束的高维不确定数据子空间聚类算法 UFINDIT。 ## 2. 图核同嗜度聚类 ### 2.1 算法优势 为了解决主流聚类算法中“数据噪声敏感性”和“簇中心方差”的问题，提出了一种基于图核同嗜度的聚类方法。该方法能够从受噪声污染的数据中明确识别簇中心，通过应用度同嗜性消除离群点，有效简化了聚类过程。基于图核的概念，该方法可以捕捉数据中的长距离关系，并发现具有流形结构形状的簇。 ### 2.2 实验性能 在真实世界问题上的实验结果表明，该算法与几种主流的最先进方法相比，具有更好的有效性和鲁棒性。以下是不同数据库上的性能表现： | 数据库 | k-means | Linkage（Single） | Linkage（Average） | Linkage（Complete） | N-Cuts | AAS | DP | HK | | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | FRGC | 0.8995 | 0.7719 | 0.9544 | 0.9189 | 0.9575 | - | 0.9554 | 0.9703 | | Yale | 0.6183 | 0.3162 | 0.3698 | 0.5417 | 0.6145 | 0.551 | 0.3691 | 0.6843 | | ORL | 0.7518 | 0.623 | 0.7561 | 0.754 | 0.825 | 0.731 | 0.8174 | 0.8446 | | MNIST | 0.4461 | 0.0144 | 0.2988 | 0.3608 | 0.6234 | - | 0.246 | 0.6785 | | USPS | 0.5971 | 0.0153 | 0.1875 | 0.404 | 0.7911 | 0.309 | 0.6596 | 0.8114 | | Isolet | 0.7098 | 0.1254 | 0.6724 | 0.7095 | 0.7804 | 0.73 | 0.5740 | 0.803 | ## 3. 高维不确定数据约束子空间聚类算法 UFINDIT ### 3.1 相关工作回顾 FINDIT 是一种用于高维数据的经典子空间聚类算法，它采用维度导向距离（dod）作为不相似度度量，并通过维度投票确定每个簇的相关维度。FINDIT 由采样阶段、簇形成阶段和数据分配阶段三个阶段组成。 ### 3.2 UFINDIT 算法框架 UFINDIT 是基于 FINDIT 算法提出的，用于处理高维不确定数据的约束子空间聚类算法。其输入包括数据集、用户参数 Cminsize 和约束集 C。算法同样由采样阶段、簇形成阶段和数据分配阶段组成。 ```mermaid graph LR classDef startend fill:#F5EBFF,stroke:#BE8FED,stroke-width:2px classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px A([开始]):::startend --> B(采样阶段):::process B --> C(簇形成阶段):::process C --> D(数据分配阶段):::process D --> E([结束]):::startend ``` ### 3.3 维度导向距离扩展 为了处理不确定数据，将 FINDIT 的维度导向距离（dod）扩展为 udod，提出了两种不同的扩展方法： - **概率-based udod**：计算点 p 和 q 之间的距离小于距离阈值 ϵ 的概率，如果概率大于给定的 δ，则认为两点在该维度上“相等”。 - \(udod_{\epsilon}(p \to q) = |D_p| - \{d|P(|p(d) - q(d)| \leq \epsilon) \geq \delta, d \in D_p