基于局部敏感哈希的核心实例选择算法及其在特征选择加速中的应用

这篇研究论文提出了一种创新的基于局部敏感哈希(LSH)的核心实例选择算法(CISLSH)，通过构建桶索引矩阵(BIM)和投票机制，将相似实例高效划分至同一哈希投票桶(HashVoteBucket)，显著降低了特征选择算法的O(n2)计算复杂度。实验证明该方法在保证特征有效性的同时，能大幅提升模糊粗糙集(FRS)等特征选择算法的运算效率，为大规模数据处理提供了新思路。

　　

Highlight亮点

本文提出的CISLSH算法通过局部敏感哈希(LSH)技术，创新性地实现了：

1）开发新型LSH数据分区方法，最大化相似实例聚集；

2）从每个非空哈希投票桶精选核心实例；

3）应用于模糊粗糙集(FRS)特征选择加速，实验证实其既能显著提升计算效率，又能保持特征选择质量。

核心实例选择方法

基于算法1获得的数据分区B₁,B₂,...,B_n，我们从每个非空哈希投票桶B_q中选取核心实例：

• •

  定义桶中心为center(B_q)=1/|B_q|∑x_j∈B_qx_j

• •

  计算桶紧凑半径r_q=max{dist(x_j,center(B_q))}

  该方法确保所选实例既能代表桶内特征，又保持原始数据分布特性。

数值实验

采用UCI和KEEL数据库的20个公开数据集验证CISLSH有效性，其中不平衡比IR=N_mj/N_mn。结果显示：

• •

  相比传统方法，运行时间曲线呈指数级下降

• •

  在保持分类精度的前提下，最高可减少78%计算耗时

结论

CISLSH通过LSH函数族的多重映射构建桶索引矩阵，结合投票机制实现智能数据分区，最终精选的核心实例使FRS特征选择算法突破O(n²)复杂度瓶颈，为生物医学大数据分析提供了高效预处理工具。