摘要
随着大数据时代的高速发展，指数型增长的数据对数据挖掘和机器学习领域带来了极大的压力，特征选择作为一种数据降维技术的典型代表成为在数据预处理过程中一个重要步骤。传统特征选择技术通过特征之间的相关性来选择目标特征的相关特征，缺乏预测模型的可解释性和鲁棒性。为了解决这个问题，因果特征选择被提出并得到了广泛关注。因果特征选择是在一个贝叶斯网络中，识别目标变量的马尔科夫毯(由目标变量的父子节点和配偶节点组成)，马尔科夫毯是目标变量的最小的特征子集且具有最大分类预测性。在已有的因果特征选择算法中，基于约束的分治类因果特征选择算法独立于分类器，数据需求量小，近年来有许多不同策略被提出。 然而，这些算法的条件独立性测试过程需要枚举条件子集的操作，具有指数级的时间复杂度。因此在高维数据中，现有的基于约束的因果特征选择算法有着效率上的缺陷,研究能够降低时间空间复杂度的轻型因果特征选择算法迫在眉睫。而对于一些具有流特征空间的动态高维数据，无法在算法运行前完全获取整体的特征空间，现有的在线因果特征学习算法在效率和准确率上也都存在问题，因此能处理动态高维数据的在线因果特征选择算法也是一个因果特征选择算法重要的研究方向。本文对轻型的因果特征选择问题进行了研究，并基于互信息提出新的因果特征选择算法。 本文的主要工作总结如下: 1.基于互信息提出了高维数据上的因果特征选择算法CFS-MI。该算法从理论上分析了目标变量与父子变量(Parentsandchildren,PC)的PC之间的互信息关系，以及目标变量与配偶之间的互信息关系，从而使用更简单的比较方式而不是枚举条件子集来衡量变量之间的关系。基于以上理论本文提出了一个基于互信息的轻型的因果特征选择算法CFS-MI,CFS-MI使用互信息来识别类变量的马尔科夫毯(Markovblanket,MB),在分析了互信息关系后，通过两两比较的方式将时间复杂度从指数级降低到平方级。在5个基准BN数据集和10个真实世界数据集上进行的广泛实验表明CFS-MI具有与其他算法可比较的甚至更高的准确率，且效率显著优于其他最先进的因果特征选择算法。 2.针对流式特征空间的特点，本文进一步提出了一种新的在线分治类MB学习算法(O-DC)。基于类变量的MB与其他变量之间互信息的差异，O-DC结合时序到达特征的特点，分别比较了新到达的特征与当前选择的PC之间的互信息。通过这种方式O-DC不仅大大降低了时间复杂度，而且解决了已有算法无法利用新特征来删除假配偶的问题，提高了准确率。最终，在5个基准BN数据集和10个真实世界数据集上进行的一系列实验验证了O-DC相比于6种最先进的分治类MB学习算法、4种在线特征选择算法和唯一的在线MB学习算法的效率和准确性。
NETL