论文部分内容阅读
在现实生活中,我们常常会要处理一些不平衡的数据集,其中主要类的数据样本占据了数据集的绝大多数,而稀有类只拥有极少数的数据样本。与主要类相比,数据集中的稀有类在许多情况下往往是我们最为感兴趣的。例如,在网络入侵检测中,虽然绝大多数的网络访问都属于正常访问,但是也有少数访问属于我们需要关注的恶意攻击行为;在金融安全中,虽然绝大多数的金融交易都是合法的,但是也有少量交易属于危害极大的违法操作。因此,如何挖掘出这些数据集中的稀有类具有较高的研究价值与现实意义。在现有文献中,稀有类挖掘的任务分为两大类,即(1)为每个稀有类发现至少一个数据样本,以证明该稀有类的存在;(2)为每个稀有类找出全部的数据样本,以更好地理解该稀有类的性质。其中,第一类任务通常被称作“稀有类检测”,又可进一步分为“基于先验知识的稀有类检测”和“无先验知识的稀有类检测”;而第二类任务包括“稀有类分类”、“稀有类聚类”、以及本文提出的“稀有类勘探”。本文围绕稀有类挖掘的两大任务,分别研究了基于先验知识的稀有类检测问题、无先验知识的稀有类检测问题,并首次提出了“稀有类勘探”的研究问题,给出了相应的挖掘算法。本文的主要贡献有:(1)针对基于先验知识的稀有类检测问题,提出了首个具有密度不敏感特性的稀有类检测算法,即RADAR算法。该算法通过利用数据样本之问的反向k近邻关系来发现稀有类的边界点,从而达到发现稀有类数据样本的目的。大量实验证明,与现有方法相比,RADAR算法受稀有类密度的影响极小,更适合于处理包含多密度稀有类的数据集。另外,提出了RADAR算法改进版本,即CATION算法。该算法通过考察稀有类边界附近数据样本的反向k近邻个数上的变化,重新设计了选取稀有类边界点的方法,以帮助用户选取那些更为靠近稀有类内部的稀有类边界点,从而进一步提高发现稀有类数据样本的概率。大量实验证明,CATION算法的稀有类检测性能明显优于现有算法。(2)针对无先验知识的稀有类检测问题,鉴于现有方法的时间复杂度普遍偏高,提出了一种快速的解决方案,即CLOVER算法。该算法通过利用数据样本之间的互k近邻关系,将稀有类的数据样本与其他类型的数据样本区分开来。大量实验证明,相较现有方法,CLOVER算法有效地减少了运行时间,且在稀有类检测性能上具有明显优势。(3)针对稀有类挖掘的第二大任务,即找出每个稀有类的全体数据样本,鉴于现有的稀有类分类与稀有类聚类技术在应用时的制约与局限,本文首次提出“稀有类勘探”(Rare Category Exploration)这一新问题,即在给定一个已发现稀有类数据样本的基础上,如何准确找出该稀有类余下的数据样本。稀有类勘探的提出使得稀有类挖掘的两大任务之问形成了连续的应用场景,即稀有类检测帮助用户发现一个稀有类数据样本后,再由稀有类勘探来完成寻找该稀有类余下数据样本的工作。(4)针对稀有类勘探问题,本文提出了一种简单而性能优良的解决方案,即FRANK算法。该算法通过在给定的数据集上构造k近邻图,将稀有类勘探问题转化为从一个起始顶点出发、寻找目标稀有类在k近邻图中所对应的局部社区(Local Community)的问题,并采用一种贪心策略来完成局部社区检测。大量实验证明,与现有的稀有类分类与稀有类聚类算法相比,FRANK算法在寻找目标稀有类的数据样本时具有明显更高的查全率和查准率。