面向非平衡类问题的k近邻分类算法

针对k近邻（kNN）方法不能很好地解决非平衡类问题,提出一种新的面向非平衡类问题的k近邻分类算法。与传统k近邻方法不同,在学习阶段,该算法首先使用划分算法（如K-Means）将多数类数据集划分为多个簇,然后将每个簇与少数类数据集合并成一个新的训练集用于训练一个k近邻模型,即该算法构建了一个包含多个k近邻模型的分类器库。在预测阶段,使用划分算法（如K-Means）从分类器库中选择一个模型用于预测样本类别。通过这种方法,提出的算法有效地保证了k近邻模型既能有效发现数据局部特征,又能充分考虑数据的非平衡性对分类器性能的影响。另外,该算法也有效地提升了k近邻的预测效率。为了进一步提高该算法的性能,将合成少数类过抽样技术（SMOTE）应用到该算法中。KEEL数据集上的实验结果表明,即使对采用随机划分策略划分的多数类数据集,所提算法也能有效地提高k近邻方法在评价指标recall、g-mean、f-measure和AUC上的泛化性能;另外,过抽样技术能进一步提高该算法在非平衡类问题上的性能,并明显优于其他高级非平衡类处理方法。     

基于共享反K近邻的局部离群点检测算法

离群点检测和分析离群模式隐含的特征是离群点挖掘的重要研究内容.现有离群点检测算法存在两个明显的不足:根据离群度检测离群点,难以确定离群点的数量;忽略了与离群点邻接的聚类信息,不能提供解析离群模式的有效证据.为此,提出一种基于共享反K近邻的离群点检测算法,首先定义了一种对密度和维数变化不敏感的共享反K近邻相似度,然后应用聚类方法将数据集划分为聚类簇和包含离群点的离群簇,从而获取数据集中的离群点及解析离群点的聚类结构.仿真结果表明,反K近邻算法比现有方法更能精确地检测数据集中的局部离群点,具有很好的控制性能.     

基于K-近邻树的离群检测算法

为适应数据集分布形状多样性以及克服数据集密度问题,针对已有算法对离群簇检测效果欠佳的现状,提出了一种基于K-近邻树的离群检测算法KNMOD(outlier detection based on K-nearest neighborhood MST).算法结合密度与方向因素,提出一种基于K-近邻的不相似性度量,然后带约束切割基于此度量构建的最小生成树从而获得离群点.算法可以有效地检测出局部离群点以及局部离群簇,与LOF、COF、KNN及INFLO算法的对比结果也证实了算法的优越性能.     

基于相对密度和流形上k近邻的聚类算法

针对传统的基于欧氏距离的相似性度量不能完全反映复杂结构的数据分布特性的问题,提出了一种基于相对密度和流形上k近邻的聚类算法。基于能描述全局一致性信息的流形距离,及可体现局部相似性和紧密度的k近邻概念,通过流形上k近邻相似度度量数据对象间的相似性,采用k近邻的相对紧密度发现不同密度下的类簇,设计近邻点对约束规则搜寻k近邻点对构成的近邻链,归类数据对象及识别离群点。与标准k-means算法、流形距离改进的k-means算法进行了性能比较,在人工数据集和UCI数据集上的仿真实验结果均表明,该算法能有效地处理复杂结构的数据聚类问题,且聚类效果更好。     

基于反k近邻的流数据离群点挖掘算法

基于局部离群因子的增量挖掘算法需要多次扫描数据集。反k近邻适用于度量离群程度,根据该性质提出基于反k近邻的流数据离群点挖掘算法（SOMRNN）。采用滑动窗口模型更新当前窗口,仅须进行一次扫描,提高了算法效率。通过查询过程实现在任意指定时刻对当前窗口进行整体查询,及时捕捉数据流概念漂移现象。实验结果证明,SOMRNN具有适用性和有效性。     

一种改进的基于反k近邻的流数据离群点检测算法

现有反k邻域的流数据离群点挖掘算法存在一些不足之处,即需要遍历每个数据对象,计算复杂度较高,稳定性较差。为了解决这些问题,本文提出一种改进的基于反k近邻的离群点检测算法OL-ORND。该算法采用细胞邻域思想,加入伪反k邻域点概念（反k邻域为空集的点对象）,增加了算法的严密性,从而大大提高了算法的效率和准确率。实验表明,算法具有较好的性能。     

基于反向K近邻的孤立点检测算法

提出了基于反向K近邻（RKNN）的孤立点检测算法ODRKNN。ODRKNN算法用每个数据点的反向k近邻个数来衡量该数据点的偏离程度,在综合数据集和真实数据集上的实验结果表明,该算法能有效地检测出孤立点,且算法的效率高于算法LOF和LSC的效率.     

PODKNN:面向大数据集的并行离群点检测算法

针对现有离群点检测算法在运用于大规模数据集时时间效率较低的问题,提出一种基于K近邻的并行离群点检测算法PODKNN (Parallel Outlier Detection Based on K-nearest Neighborhood)。该算法利用划分策略对数据集进行预处理,在规模较小的子集中寻找K近邻并计算离群度,最后合并结果并遴选出离群点,设计算法过程使其符合MapReduce的编程模型,实现并行化,从而提高了离群点检测算法处理大规模数据的计算效率。实验结果表明,PODKNN具有较高的加速比及较好的扩展性。     

基于局部加权重构的化工过程数据恢复算法

针对化工过程数据中存在缺失数据的问题,在保持局部数据结构特征的基础上提出了基于局部加权重构的化工过程数据恢复算法。通过定位缺失的数据点并以符号NaN(Not a Number)标记,将缺失的数据集分为完备数据集和不完备数据集。不完备的数据集按照完整性的大小依次找到它们在完备数据集中相应的k个近邻,根据误差平方和最小的原则,求出k个近邻相应的权值,用k个近邻及相应的权值重构出缺失的数据点。将该算法应用在不同缺失率下的两种化工过程数据中并与望最大化主成分分析(EM-PCA)法和平均值(MA)两种传统的数据恢复算法相比较,该算法的恢复数据误差最小,并且计算速度相比EM-PCA算法平均提高了2倍。实验结果表明,局部加权重构的化工过程数据恢复算法可以有效地对数据进行恢复,提高了数据的利用率,适用于非线性化工过程缺失数据的恢复。     

近邻感知的标签噪声过滤算法

基于k近邻的标签噪声过滤对近邻参数k的选取较敏感.针对此问题,文中提出近邻感知的标签噪声过滤算法,可有效解决二分类数据集的类内标签噪声的问题.算法分开考虑正类样本和负类样本,使分类问题中的标签噪声检测问题转化为两个单类别数据的离群点检测问题.首先通过近邻感知策略自动确定每个样本的个性化近邻参数,避免近邻参数敏感的问题.然后根据噪声因子将样本分为核心样本与非核心样本,并把非核心样本作为标签噪声候选集.最后结合候选样本的近邻标签信息,进行噪声的识别与过滤.实验表明,文中方法的噪声过滤效果和分类预测性能均较优.     

Fast outlier detection for very large log data

Density-based outlier detection identifies an outlying observation with reference to the density of the surrounding space. In spite of the several advantages of density-based outlier detections, its computational complexity remains one of the major barriers to its application.The purpose of the present study is to reduce the computation time of LOF (Local Outlier Factor), a density-based outlier detection algorithm. The proposed method incorporates kd-tree indexing and an approximated k-nearest neighbors search algorithm (ANN). Theoretical analysis on the approximation of nearest neighbor search was conducted. A set of experiments was conducted to examine the performance of the proposed algorithm. The results show that the method can effectively detect local outliers in a reduced computation time.     

障碍空间中基于并行蚁群算法的k近邻查询

为解决障碍空间中的k近邻查询问题,提出一种基于改进的并行蚁群算法的k近邻查询方法（PAQ）。首先,利用不同信息素种类的蚁群实现并行查询k近邻;其次,增加时间因素作为路径长短的判断条件,以最直接地呈现蚂蚁的搜索时间;然后,重新定义初始信息素浓度,以避免蚂蚁的盲目搜索;最后,引入可视点将障碍路径分割为多段欧氏路径,选择可视点进行概率转移,并改进启发函数,以促使蚂蚁朝着更为正确的方向搜索,避免算法过早陷入局部最优。与WithGrids相比,当数据点个数小于300时,对于线段障碍,算法运行时间平均缩短约91.5%;对于多边形障碍平均缩短约78.5%。实验结果表明,该方法在数据规模较小时的运行时间具有明显的优势,且可以处理多边形障碍。     

基于网格查询的局部离群点检测算法

针对基于密度的局部离群因子算法（LOF），需要计算距离矩阵来进行[k]近邻查寻，算法时间复杂度高，不适合大规模数据集检测的问题，提出基于网格查询的局部离群点检测算法。算法利用距离目标网格中的数据点最近的[k]个其他数据点，一定在该目标网格或在该目标网格的最近邻接网格中这一特性，来改进LOF算法的邻域查询操作，以此减少LOF算法在邻域查询时的计算量。实验结果证明，提出的LOGD算法在与原LOF算法具有基本相同的检测准确率的情况下，能够有效地降低离群点检测的时间。     

距离-关键字相似度约束的双色反k近邻查询方法

针对空间关键字双色反k近邻查询返回结果质量较低的问题,提出了基于距离-关键字相似度约束的双色反k近邻查询方法。首先,通过设置一个阈值将查询结果中质量较低的用户给过滤掉,从而避免了查询结果中出现空间距离相对较远的用户,保证了查询结果质量;然后,为支持该查询,提出了一种关键字多分辨率网格矩形树（KMG-Tree）索引来管理数据;最后,提出了基于Six-region算法的Six-region-optimize算法来提高查询处理效率。Six-region-optimize算法的查询效率相较baseline和Six-region算法分别平均提高了约85.71%和23.45%。基于真实时空数据进行实验测试和分析,实验结果验证了Six-region-optimize算法的有效性和高效性。     

基于共享近邻相似度的密度峰聚类算法

密度峰聚类是一种基于密度的高效聚类方法,但存在对全局参数d_c敏感和需要人工干预决策图进行聚类中心选择的缺陷。针对上述问题,提出了一种基于共享近邻相似度的密度峰聚类算法。首先,该算法结合欧氏距离和共享近邻相似度进行样本局部密度的定义,避免了原始密度峰聚类算法中参数d_c的设置;其次,优化聚类中心的选择过程,能够自适应地进行聚类中心的选择;最后,将样本分配至距其最近并拥有较高密度的样本所在的簇中。实验结果表明,在UCI数据集和模拟数据集上,该算法与原始的密度峰聚类算法相比,准确率、标准化互信息（NMI）和F-Measure指标分别平均提高约22.3%、35.7%和16.6%。该算法能有效地提高聚类的准确性和聚类结果的质量。     

基于最近邻相似度的孤立点检测及半监督聚类算法

传统的聚类算法是一种无监督的学习过程,聚类的精度受到相似性度量方式以及数据集中孤立点的影响,并且算法也没有很好的利用先验知识,无法体现用户的需求。因此提出了基于共享最近邻的孤立点检测及半监督聚类算法。该算法采用共享最近邻为相似度,根据数据点的最近邻居数目来判断是否为孤立点,并在删除孤立点的数据集上进行半监督聚类。在半监督聚类过程中加入了经过扩展的先验知识,同时根据图形分割原理对数据集进行聚类。文中使用真实的数据集进行仿真,其仿真结果表明,本文所提出的算法能有效的检测出孤立点,并具有很好的聚类效果。     

基于共享k-近邻与共享逆近邻的密度峰聚类

为了更好地解决密度不均衡问题与刻画高维数据相似性度量问题，提出一种基于共享[k]-近邻与共享逆近邻的密度峰聚类算法。该算法计算两个点的共享[k]-近邻数与共享逆近邻数，并结合欧氏距离来确定这两个点之间的共享相似度；将样本点与其逆近邻点的共享相似度之和定义为该点的共享密度，再通过共享密度选取聚类中心。通过实验证明，该算法在人工数据集和真实数据集上的聚类结果较其他密度聚类算法更加准确，并且能更好地处理密度不均衡问题，同时也提高了高维数据的聚类精度。