基于加权判别性异构邻域关系的加速属性约简用于邻域粗糙集

《Neurocomputing》：Accelerated Attribute Reduction Based on Weighted Discriminative Heterogeneous Neighborhood Relationships for Neighborhood Rough Sets

　　摘要
属性约简是邻域粗糙集中的重要任务，但传统方法通常需要构建完整的邻域结构并反复更新邻域，这导致在处理大规模数据时计算成本很高。本文从异质邻域关系的角度研究属性约简问题。我们证明了NRS的下近似和上近似完全可以由异质邻域对来确定，即具有不同决策标签的样本对。基于这一结果，在快速邻域计算框架下提出了异质邻域属性约简算法HNAR。HNAR通过异质对来维护近似信息，能够在降低计算成本的同时得到与FNC相同的约简结果。为进一步提升可扩展性，又提出了加权判别异质邻域属性约简算法WDHNAR。WDHNAR利用费希尔加权距离为每个样本构建加权判别三元组，并根据三元组分离增益进行正向选择，从而在信息量更强的三元组而非庞大的异质对集合上评估候选属性。在13个UCI数据集上的实验验证了HNAR的正确性与高效性，同时表明WDHNAR在约简时间、分类精度和约简规模之间取得了良好的平衡。参数敏感性分析及统计比较结果进一步证明了WDHNAR的稳定性与竞争力。

引言
粗糙集理论是一种处理不确定性和不一致数据的有效工具，但其经典模型依赖于等价关系，因此要求所有属性均为离散值。然而，现实世界的数据集往往包含连续属性，若在分析前对其进行离散化处理则不可避免地会导致信息损失。为解决这一问题，胡等人提出了邻域粗糙集模型，该模型通过距离度量和邻域半径来定义样本间的相似性，从而无需离散化即可直接处理连续数据和混合类型数据。得益于这一优势，邻域粗糙集在属性约简、分类、异常检测以及不确定性度量等领域得到了广泛的研究与应用。其中，属性约简是最基础的任务之一，其目标是为保留完整数据集的决策能力而找到最小的属性子集，从而消除冗余。不过，基于邻域粗糙集的属性约简计算成本会随着数据规模的增大而迅速上升，这促使人们开展了大量关于加速策略的研究。

一种加速策略是用替代性的粒度结构取代传统的邻域构建方式，通过使用更粗粒度的计算单元来减少距离计算的次数。夏等人提出了GBNRS模型，该模型通过迭代2均值聚类将数据集划分为颗粒球，并以纯颗粒球的中心作为正区域生成依据。李等人提出了k-GBNRS模型，该模型采用球形k均值算法生成具有自适应半径的颗粒球，从而加快属性约简速度。彭等人提出了VPGB模型，该模型放宽了纯度标准，允许包含纯度达到可调阈值的颗粒球，进而提高了对标签噪声的鲁棒性。张等人提出了RVGBGM模型，该模型直接根据决策类别确定颗粒球中心，避免了GBNRS中的重复分割过程。与基于颗粒球的粒度划分不同，夏等人还提出了GRRS模型，该模型利用决策树将特征空间划分为矩形子区域，完全无需距离度量。这些方法通过压缩样本维度显著降低了大规模数据集的计算量。然而，它们的加速效果并未延伸到属性维度：每次迭代时评估所有候选属性的成本依然不变，而且正如张等人所指出的，GBNRS在高维空间中会面临计算成本的急剧上升。

另一种策略则是保留经典的邻域粗糙集框架，但缩小邻域搜索范围。胡等人提出了FARNeMF算法，该算法利用正区域的单调增长特性，仅对边界样本进行邻域计算。刘等人提出了FHARA算法，该算法根据样本到参考点的距离将其划分为哈希桶；根据三角不等式，任何θ-邻域都必定位于该样本所在或其相邻的桶中，从而将搜索范围限制在最多三个桶内。王等人提出了EasiFFRA算法，该算法通过在邻域对称性基础上缓存边界区域样本，并跳过同标签样本的距离计算，进一步扩展了FHARA的功能。刘等人还提出了颗粒舱方法，该方法通过每个特征的极大值和极小值构造两个控制样本，并证明每个样本的实际邻域完全包含在它们的交集中。彭等人提出了FNC算法，该算法通过按单个属性对样本进行预排序，将计算复杂度从O(n2)降低到O(nlogn)，同时利用邻域的单调性将联合属性搜索限制在子属性邻域内。钱等人提出了一种方向性半邻域，该机制使搜索区域偏向于同类样本。尽管有了这些进展，当邻域半径较大时，搜索范围仍会扩大，效率提升效果也会减弱。

虽然上述策略主要着眼于邻域构建的成本问题，但属性评估函数的选择也会影响约简的质量和计算效率。依赖度在快速NRS约简中被广泛使用，因为它仅依赖于正区域信息，且能与基于正区域的加速策略自然结合；然而，它可能无法完全反映候选属性的区分能力。因此，人们提出了更多更复杂的评估标准，包括邻域自信息、邻域熵、邻域组合熵、邻域互补熵，以及吴黄两人提出的同时考虑特征相关性、冗余性和交互性的标准。这些标准虽然能产生质量更高的约简结果，但需要更多的邻域信息，从而带来额外的计算负担。此外，人们还通过基于MapReduce的分布式计算、三重采样策略以及针对动态数据集的增量机制来提升效率。

尽管各种方法的加速策略各不相同，但现有方法大多仍以某种形式保留着完整的邻域信息。在经典的邻域粗糙集框架中，无论是同质还是异质邻域关系都是通过完整的样本邻域来保留的；而在基于粒度的方法中，则通过颗粒纯度或投票一致性来保留类似的信息。因此，这些方法主要是加快了计算过程本身，并未直接解决一个更为根本的问题：究竟哪些邻域信息对约简才是真正至关重要的？在大规模应用场景中，这一问题尤为重要，因为同质邻域关系通常占据主导地位，会给内存和计算带来巨大负担。基于这一观察，本文从异质邻域关系的角度重新审视基于邻域粗糙集的属性约简问题，重点识别并优先考虑那些对局部类别分离最具关键作用的邻域信息。

本文的主要贡献如下：
(1) 我们证明了NRS的下近似和上近似完全可以由异质邻域关系来确定，为将约简计算限制在异质对上提供了理论依据。
(2) 基于FNC的滑动窗口机制，我们提出了HNAR算法。HNAR以异质邻域对作为近似更新和基于依赖度的正向约简的基本单位，无需构建完整邻域即可得到与FNC相同的约简结果。
(3) 我们进一步提出了WDHNAR算法，该算法通过用加权判别三元组替代对异质对的统一处理，使得正向选择能够聚焦于数量更少但信息量更高的异质关系，从而进一步提升效率。

本文的其余结构如下：第2节阐述理论基础，第3节介绍所提出的方法及其复杂度分析，第4节报告实验评估结果，第5节对全文进行总结。