论文部分内容阅读
在科学研究和工程应用中，稀有类的数据样本往往具有重要的研究价值。例如，在网络访问数据集中，绝大部分的数据样本是正常的网络访问，小部分的数据样本是网络入侵行为，而只占小部分的网络入侵行为往往更具有研究价值。 稀有类挖掘（Rare Category Mining）致力于发现并挖掘出不平衡数据集中有价值的稀有类样本。稀有类挖掘的具体研究问题可以分为两个方面:(1)稀有类探测（Rare Category Detection），旨在为无标签数据集中的每个类发现至少一个数据样本，以确定数据集中存在哪些类;(2)稀有类勘探(Rare Category Exploration)，旨在对已探测到且具有价值的某个稀有类样本，找到与其来自同一个稀有类的其他样本集合。 本文主要围绕稀有类探测和稀有类勘探两个问题展开，致力于解决以下三个主要挑战。 第一，现有的稀有类探测和稀有类勘探算法，相对于数据样本数量的时间复杂度为平方级甚至立方级，时间复杂度过高。 第二，现有稀有类探测算法和稀有类勘探算法在算法有效性上表现并不令人满意。具体而言，现有稀有类探测算法需要过多的贴标次数来发现数据集中所有的类，现有稀有类勘探算法的求准率和求全率有待提高。 第三，大部分现有的稀有类探测和稀有类勘探算法需要数据集的先验知识，数据集的先验知识往往难于甚至不可能事先获得。 本文针对以上挑战，分别给出了稀有类探测和稀有类勘探两个问题的解决方案。我们的算法利用小波变换的技术，在这两个问题上都首次达到了线性时间复杂度。本文的主要贡献如下： (1)本文提出了线性时间复杂度的稀有类探测算法iFRED。该算法使用连续小波变换来发现局部密度的突变，使算法时间复杂度低且有效性高。 (2)本文提出了线性时间复杂度的稀有类勘探算法FREE。该算法使用离散小波变换来缩小目标稀有类的搜索范围，使得算法时间复杂度低且有效性高。 (3)针对高维数据集的问题，本文提出了适用于稀有类挖掘的降维思想。该思想的核心为迭代发现稀有类的粗略形状和去掉发现的稀有类紧实性最差的维度这两个步骤，直到收敛或迭代次数达到阈值。