基于信息熵的相对离群点的检测方法:ENBROD

提出一种检测离散属性数据集中相对离群点的算法.目前已有的关于离群点的检测方法大多关注连续属性的数据集,由于离散属性值之间并没有类似于连续属性值之间那样固有的距离度量关系,故不能简单的把用于连续属性数据集的检测算法应用到离散属性数据集中来.本文首先引入了一种新的信息熵增量的概念--去一划分信息熵增量,通过形式化分析得到了其性质.然后,在去一划分信息熵增量的基础上,给出了每个对象所对应的相对离点群因子(ROF)的定义.每个对象的ROF是相对的,因为其只取决于这一对象的邻域.接着,提出了ENBROD算法来实现对ROF的计算.最后,通过实验说明当邻域大小较小时,ENBROD算法可以找到已存在的方法所找不到的相对离群点;而当邻域的大小足够大时,ENBROD算法寻找全局离群点的能力也与其他的一些离群点检测算法的能力相近.     

MapReduce编程模型下的上下文离群数据挖掘算法

目前,对于离群数据挖掘算法研究颇多,但对于离群数据挖掘结果可理解性和可解释性的研究相对较少。采用相关子空间,给出一种MapReduce编程模型下的上下文离群数据挖掘算法。该算法利用局部稀疏差异度,确定相关子空间,并计算其数据对象离群因子值;将离群因子和相关属性维,定义为数据对象的上下文信息,提高了数据对象的可理解性;选取离群因子最大的N个数据对象,作为上下文离群数据;利用MapReduce编程模型,实现了一种上下文离群数据并行挖掘算法;最后,采用UCI数据集,实验验证了该算法的可解释性和有效性。     

基于属性熵和加权余弦相似度的离群算法

离群点检测是数据挖掘的一个重要研究方向,大多数离群数据挖掘算法在应用到高维数据集时效率较低。给出了一种基于属性熵和加权余弦相似度的离群数据挖掘算法LEAWCD.该算法首先根据局部属性熵分析每个对象在其k-邻域内的局部离群属性,并依据各离群属性的属性偏离度自动设置属性权向量;其次使用对高维数据有效的余弦相似度经加权后度量各对象在k-邻域内的离群程度,实现高维局部离群点检测;最后采用国家天文台提供的天体光谱数据作为数据集,实验验证了LEAWCD算法具有伸缩性强和检测精度高等优点。     

一种高效的复杂信息系统增量式属性约简

文中提出一种离散和连续混合属性的复杂信息系统增量式属性约简算法.首先,将粒计算模型中的知识粒度在混合型信息系统下进行推广,提出了邻域知识粒度,并构造出基于邻域知识粒度的非增量式属性约简算法,然后在混合型信息系统下研究了邻域知识粒度随对象增加时的增量式计算,理论证明了该计算方式的高效性,最后提出了基于邻域知识粒度的混合信息系统增量式属性约简算法.UCI数据集的实验结果表明,所提出的算法在混合型信息系统中具有很高的增量式属性约简性能.     

一种基于子空间的两阶段离群点检测算法

将高维数据投影在子空间中,是解决"维灾"的有效途径之一。从提高挖掘效率的角度,给出一种新的基于子空间的两阶段离群检测算法,利用密度阈值筛选候选离群对象减少计算量。该算法首先,计算每个数据对象在每一维的密度比,所有维的密度比乘积取对数平均作为密度系数,并选取候选离群对象;其次,候选离群对象的邻居在每一个关联子空间中的偏离程度之积作为偏差比,密度系数与偏差比的乘积作为离群系数,并确定离群数据对象。由于仅计算候选离群对象的离群系数,因此有效地提高挖掘效率;最后,采用UCI数据集,实验验证了该算法不仅保证挖掘结果精度,而且有效提高了挖掘效率。     

基于MapReduce的并行加权k近邻与离群检测

利用MapReduce编程模型,提出一种并行的加权k近邻与离群检测方法 WKNNOM-MR.该算法首先对输入数据随机均匀采样,在样本数据集中采用信息熵计算各个属性的权值;然后在集群中的数据节点上对输入数据进行加权,并将其映射到Z-order空间填充曲线,给出了一种基于Z-order的加权k近邻查询方法;根据每个对象与其加权k近邻之间的距离计算离群因子,在兼顾最小距离与平均距离的基础上,给出离群点检测算法;最后在具有5个节点的Hadoop集群上实现该算法,并采用人工合成数据集、UCI标准数据集进行实验,结果验证了该算法的有效性、可扩展性和可伸缩性。     

基于PCA和多邻域粗糙集的肿瘤特征基因选择算法

针对邻域粗糙集采用全局邻域求解近似,存在计算时间复杂度高且无法对基因表达谱精确描述的问题,构造了基于主成分分析(PCA)和改进邻域粗糙集(NRS)算法的PNRS模型.首先采用PCA算法获得低维的特征基因空间;然后利用改进的多邻域粗糙集算法进行特征基因选择,即采用欧氏距离计算每列属性邻域值,选取所有属性邻域集合计算邻域决策系统的近似;最后采用启发式搜索算法选择特征基因子集.实验结果表明,PNRS模型能够在选择出较小的基因子集的情况下获得较高的分类精度,从而验证了该方法的有效性.     

一种基于面包含关系的GML空间离群面检测算法

为了研究基于空间拓扑关系的离群检测,提出了一种基于面包含关系的离群面检测算法DOR_IR.它采用算法PLI判断面包含关系,并把面包含的对象看作面对象的属性,建立面对象的密度连通集合,相应于"噪音"的面就是离群面.运用算法DOR-IR分别在人工数据集和真实数据集上进行了测试,实验结果表明,算法DOR_IR能有效挖掘基于拓扑包含关系的离群面.     

基于属性相关分析的离群数据并行挖掘算法

针对高维海量数据集中的局部离群数据,利用并行计算和属性相关性分析思想,给出了一种离群数据并行挖掘算法。该算法首先由主节点分配属性相关分析任务,各个子节点并行查找数据集中的冗余属性,将其冗余属性传回主节点,并由主节点删除;其次,主节点分配搜索任务,各子节点采用微粒群算法,并行搜索局部离群子空间;再次,由主节点对局部离群子空间合并计算后,确定全局离群数据;最后,在MPICH2-1.0.3的并行计算环境下,采用恒星光谱数据作为数据集,实验结果验证了算法的正确性和有效性。     

基于邻域漂移的点云法向估计算法研究

随着三维激光扫描仪的改进和普及,获取三维点云数据的方式越来越方便.法向量作为点云数据不可或缺的属性之一,在诸多算法中具有重要作用.由于受到噪声、离群点、非均匀采样等因素的影响,准确快速估计尖锐特征点的法向量仍然是具有挑战性的.提出基于邻域漂移的点云法向估计算法,实现准确快速地对尖锐特征点的法向进行估计.首先,对当前点的近邻点构造其邻域,所有近邻点所对应的邻域构成候选邻域集.利用协方差分析对候选邻域进行评价,并选取最优邻域用于最终的法向估计.实验结果表明本算法在法向估计的质量上与前沿算法持平,在运行速度上与传统PCA算法相近,可以最大程度兼顾法向质量与计算速度.