Efficient approximate top-k mutual information based feature selection
Efficient approximate top-k mutual information based feature selection
复制标题
DOI：
10.1007/s10844-022-00750-4
复制
发表时间：
2022-10
影响因子：
3.4
通讯作者：
Md. Abdus Salam;Senjuti Basu Roy;Gautam Das
中科院分区：
文献类型：
--
作者：
Md. Abdus Salam;Senjuti Basu Roy;Gautam Das
特征选择是数据科学管道中的一个重要步骤，为这一步骤开发高效的算法至关重要。互信息（Mutual Information， MI）是用于特征选择的重要度量之一，根据互信息的降序对属性进行排序，保留top-k的属性。本工作的目标是开发一种新的度量方法——属性平均冲突，在不实际计算MI的情况下有效地近似顶属性。我们提出的方法是基于使用近似功能依赖的数据库概念来量化属性的MI等级，据我们所知，这在以前还没有研究过。我们用蒙特卡罗模拟证明了我们提出的措施的有效性。我们还使用具有数百万条记录的高维合成和真实数据集进行了广泛的实验。我们的结果表明，我们提出的方法在选择顶属性方面表现出完美的准确性，但比最先进的基线（包括计算互信息特征选择的精确方法，以及基于自适应随机抽样的方法）效率要高得多。我们还研究了所提出的新测度的上界和下界，并表明利用属性在特定排列中的边际频率可以得到更严格的上界。建议度量的边界可用于选择top-kattributes，而无需在一次遍历中对数据集进行完全扫描。我们在真实数据集上进行了实验评估，以证明该方法的准确性和有效性。
Feature selection is an important step in the data science pipeline, and it is critical to develop efficient algorithms for this step.Mutual Information(MI) is one of the important measures used for feature selection, where attributes are sorted according to descending score of MI, and top-k attributes are retained. The goal of this work is to develop a new measureAttribute Average Conflictto effectively approximate top-kattributes, without actually calculating MI. Our proposed method is based on using the database concept ofapproximate functional dependencyto quantify MI rank of attributes which to our knowledge has not been studied before. We demonstrate the effectiveness of our proposed measure with a Monte-Carlo simulation. We also perform extensive experiments using high dimensional synthetic and real datasets with millions of records. Our results show that our proposed method demonstratesperfectaccuracy in selecting the top-kattributes, yet is significantly more efficient than state-of-art baselines, including exact methods for computing Mutual Information based feature selection, as well as adaptive random- sampling based approaches. We also investigate the upper and lower bounds of the proposed new measure and show that tighter bounds can be derived by using marginal frequency of attributes in specific arrangements. The bounds on the proposed measure can be used to select top-kattributes without full scan of the dataset in a single pass. We perform experimental evaluation on real datasets to show the accuracy and effectiveness of this approach.