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

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

一种基于多重聚类的离群点检测算法

在LDOF算法的基础上,提出一种基于多重聚类的离群点检测算法PMLDOF。该算法针对局部离群度量计算量大的缺点,采用聚类剪枝技术作为减少计算量的方法;同时,为了避免将位于簇边缘的离群点错剪,算法利用多重聚类的差异性对簇的边缘点进行筛选。在对数据集进行剪枝后,计算剩余数据的局部离群度LDOF,并找出符合条件的离群数据点。实验结果表明,算法在时间复杂度和检测精度上具有更好的优越性。     

一种高效混合属性离群检测算法

离群检测是数据挖掘领域的一个重要内容,它为分析各种海量、复杂、含有噪声的数据提供了新的方法.对离群簇进行了定义并据此提出一种离群检测方法,该方法增量式地对原始数据集进行聚类,在得到的簇中寻找离群簇.根据提出的簇间差异性度量,新方法可处理混合属性数据集.同时探讨了参数取值.基于人工数据集和真实数据集上的实验表明,新方法检测离群点具有精度高、速度快的优点,适用于大规模数据集.     

基于聚类的离群点分析方法*

对于离群点的形成,不同的属性起着不同的作用,离群点在不同的属性域中,会表现出不同的离群特性,在大多数情况下,高维数据空间中的对象是否离群往往取决于这些对象在低维空间中的投影。针对如何将离群点按照形成原因分类的问题,引入离群属性和离群簇等概念,以现有离群挖掘技术为基础,提出了基于离群分类来进行离群点分析的方法,实现了基于聚类的离群点分类算法CBOC(cluster-based outlier classification),以揭示离群点的内涵知识。实验表明了该方法在实际应用中的有效性。     

一种不确定数据流子空间聚类算法

针对不确定数据流上的聚类问题提出一种不确定数据流子空间聚类算法UDSSC.该算法使用滑动窗口机制接收新到达的数据,剔除陈旧的数据;还引入子空间簇生成策略和新型离群点机制;系统建立了三个缓冲区分别存储新到来的元组、要进行聚类的元组和离群点元组,以此获得高质量的聚类结果.实验表明,UDSSC算法与同类型算法相比,具有更好的聚类效果、更低的时间复杂度和更强的扩展性.     

基于图像的重建点云离群点检测算法

基于图像重建出的三维点云模型通常会包含许多离群点,这些离群点可能孤立存在或密集聚集在一起形成点簇,也可能分布在模型周围甚至附着在模型表面。通过一种检测方法很难有效滤除多种分布状态的离群点,因此,提出了综合的离群点监测算法。首先通过空间距离剔除与模型主体较远的离群点,并通过构建空间拓扑关系加快离群点搜索速度;然后利用边界匹配法,将较小点簇分别与最大点簇进行对比,滤除模型周围离群点簇;最后采用改进的K-means算法,根据RGB颜色值特征对点云数据进行聚簇分类,结合已识别的离群点,检测和滤除附着在模型表面的离群点。仿真实验结果表明,此方法能够有效滤除点云模型中多种分布状态的离群点。     

基于改进密度峰值聚类算法的轨迹行为分析

为了深入挖掘校园无线网络轨迹行为数据信息,采用基于密度的聚类方法对校园内用户的轨迹行为进行特征聚类。由于基于密度的聚类算法通常采用距离作为相似性度量方式,为了有效衔接此类聚类算法,先将用户相似度矩阵通过转换函数转变为距离矩阵。引入离群点检测算法,将离群点检测算法与聚类算法相结合,减少参数的输入个数,增加聚类的聚合程度。改进后的聚类算法可以有效检测出数据轨迹的异常,帮助高校通过对学生上网记录的处理找到浏览信息与大部分同学不一致的人,缩小目标范围,进行有针对性的处理。通过定性分析和实验对比验证,确定两种基于离群点检测的共享最近邻的快速搜索密度峰值聚类适用于校园无线网络行为轨迹相似度矩阵的处理,邓恩指数等聚类内部指标及整体性能优于同类算法。     

基于层次聚类的离群点分析方法

发现离群点并合理地解释离群点对数据挖掘结果的运用有重要意义,通过对离群点属性的检测可以发现其离群特性,进而更加准确地解释聚类结果。针对在聚类结果中出现的不同离群点及其特性,提出将层次聚类算法应用于离群点分析,通过元胞自动机距离变换算法实现凝固层次聚类,实现了簇间距离的度量;定义了演化周期上的平均度量距离,能够发现不同聚类层次上的离群点及其离群特性。该算法能够在得到聚类结果的同时,有效地解释离群点的属性,并具有较低的计算复杂度和并行计算以及向高维空间扩展的特性。通过试验数据进行了实证研究,验证了算法的有效性。     

加速大规模数据集的离群点检测

针对现有基于距离的离群点检测算法在处理大规模数据时效率低的问题,提出一种基于聚类和索引的分布式离群点检测(DODCI) 算法。首先利用聚类方法将大数据集划分成簇;然后在分布式环境中的各节点处并行创建各个簇的索引;最后使用两个优化策略和两条剪枝规则以循环的方式在各节点处进行离群点检测。在合成数据集和整理后的KDD CUP数据集上的实验结果显示,在数据量较大时该算法比Orca和iDOoR算法快近一个数量级。理论和实验分析表明,该算法可以有效提高大规模数据中离群点的检测效率。     

基于密度划分的离群点检测算法

目前,大部分离群点检测算法需要人工输入参数,不能同时检测出全局和局部离群点,不能有效处理密度不均匀数据。针对这些问题,提出一种基于密度划分的离群点检测算法DD-DBSCAN。主要创新包括:1)运用最小生成树的方法,新定义簇密度概念,将数据录入后划分成密度不等的簇,使算法能够处理密度分布不均匀的数据;2)采用"分而治之"的思想,对经过划分的数据集分别进行离群点检测,使得算法能够同时处理全局和局部离群点;3)通过在各个簇中自适应地计算所需参数值,算法不再需要人工输入参数(聚类半径(Eps)等)。通过在2D模拟数据集和Iris真实数据集上的实验表明,与DBSCAN算法比较,本文算法具有更高的覆盖率和正确率。     

高维数据集离群子空间特性研究

探讨对挖掘出的离群数据集进行解释与分析的有效方法。以粗糙集理论的属性约简技术为基础,定义了属性离群贡献度等概念对高维数据集离群特性进行了量化描述,提出了离群划分与离群约简思想以及离群数据关键属性域子空间分析方法,给出了一种离群约简算法并分析了算法复杂性。实验表明,这种方法可以有效地揭示离群数据产生来源,有助于对整体数据集的更全面理解,且提出的算法对于问题规模具有较好的适应性。     

一种基于关键域子空间的离群数据聚类算法

离群数据发现与分析是数据挖掘的重要组成部分,现有离群数据挖掘算法主要针对如何检测离群对象,缺乏对挖掘出的离群数据集进行解释与分析的有效方法.通过对离群数据来源及特性进行分析并结合粗糙集理论,定义了离群划分相似度的概念,提出了一种基于关键属性域子空间的离群数据聚类算法COKAS,该算法不仅揭示了离群数据子空间特性,进一步获取了扩展知识,而且有助于对整体数据集的理解.对两个多维数据集的实验结果表明,该算法具有良好的适应性及有效性.     

离群数据关键域子空间快速搜索技术

离群数据挖掘与分析在通信欺诈检测、疾病诊断和网络入侵检测等多个领域具有十分重要的意义。离群数据关键域子空间可以获得数据离群起源与特征等相应的延伸知识。通过对离群数据对象与其属性值的关系讨论并基于探索性数据分析方法,提出了一种离群数据关键域子空间实时快速搜索算法。实验结果表明提出的算法是有效的,可以满足大多数实时性检测与分析要求。     

基于局部图拉普拉斯约束的鲁棒低秩表示聚类方法

针对传统低秩表示聚类方法存在的稀疏性不足及噪声敏感等问题,提出了一种基于局部图拉普拉斯约束的鲁棒低秩表示聚类模型. 一方面,通过加入图像数据局部相似性的约束,在保持表示矩阵分块对角的特性下,增强了其稀疏性;另一方面,从数据相关性的角度分析了低秩表示模型的聚类性质, 通过采用鲁棒低秩表示模型,不仅降低了噪声的干扰,而且减弱了表示字典数据之间的线性相关性,从理论上保证了最终的邻接矩阵具有分块对角的良好聚类性质. 与传统低秩表示方法相比,本文得到的表示矩阵既保证了分块性质,又更加稀疏,仿真实验结果表明聚类效果有明显提升.     

Finding key attribute subset in dataset for outlier detection

Detection of outlier from high dimensional dataset have found important applications in many fields, yet the unexpected time consumption is likely to hinder its practical use. Thus, it makes sense to build an efficient method for finding meaningful outliers and analyzing their intentional knowledge. In this paper, we utilize the concept of rough set to construct a method for outlying reduction, based on an outlier detection and analysis system. By defining outlying partition similarity, we can mine outliers on the key attribute subset rather than on the full dimensional attribute set of dataset, as long as the similarity between outlying partitions produced on them is large enough. For this purpose, we propose a novel method for finding the key attribute subset in dataset, which starts by seeking all outliers on the full attribute set, and then searches through all outlying attribute subsets for these points. After that, it turns out to be able to determine the key attribute subset in accordance with the similarity between outlying partitions. By experiments, we show that our method allows more efficient seeking of key attribute subset than the previous methods, thereby improving the feasibility of outlier detection.     

基于幂图的离群子空间搜索算法*

通过分析子空间搜索算法的研究现状以及存在的问题,提出基于幂图的离群子空间搜索算法。该方法主要讨论离群点产生的原因,能够找出单个对象的离群子空间,并根据离群子空间对离群点进行分类。在对幂图扩展的基础上进行剪枝,减少了存储量和计算量,算法性能得到很大的提高。采用实例说明了该算法,并通过实验证明了该算法的可行性和高效性。     

基于KNN图的空间离群点挖掘算法

空间数据集中离群数据与正常数据之间的非空间属性值相差较大。针对该情况,提出一种基于K-最邻近(KNN)图的空间离群点挖掘算法。该算法通过所有对象的K近邻关系构造KNN图,将相邻对象非空间属性值的差作为2个对象点间的边权值,利用裁边策略去掉权值较高的边,从而识别出空间离群点和离群区域。实验结果表明,该算法的时间性能优于POD算法。     

Robust dynamic process monitoring based on sparse representation preserving embedding

In this paper, a novel dimensionality reduction technique, named sparse representation preserving embedding (SRPE), is proposed by utilizing the sparse reconstruction weights and noise-removed data recovered from robust sparse representation. And a new dynamic process monitoring scheme is designed based on SRPE. Different from traditional manifold learning methods, which construct an adjacency graph from K-nearest neighbors or ɛ-ball method, the SRPE algorithm constructs the adjacency graph by solving a robust sparse representation problem through convex optimization. The delicate dynamic relationships between samples are well captured in the sparse reconstructive weights and the error-free data are recovered at the same time. By preserving the sparse weights through linear projection in the clean data space, SRPE is very efficient in detecting dynamic faults and very robust to outliers. Finally, through the case studies of a dynamic numerical example and the Tennessee Eastman (TE) benchmark problem, the superiority of SRPE is verified.     

Generating compact representations of static scenes by means of 3D object hierarchies

This paper presents a new heuristic algorithm for computing a compact hierarchical representation of the objects contained in a 3D static scene. The algorithm first builds a fully-connected adjacency graph that keeps the costs of grouping the different pairs of objects of the scene. Afterward, the graph’s minimum spanning tree is computed and its edges sorted in ascending order according to their cost. Next, from that sorted list, a cost-based clustering technique is applied, thus generating new objects at a higher level in the hierarchy. A new object can be defined after merging two or more objects according to their corresponding linking costs. The algorithm starts over by generating a new adjacency graph from those new objects, along with the objects that could not be merged before. The iterative process is applied until an adjacency graph with a single object is obtained. The latter is the root of the hierarchical representation. Balance and coherence of the hierarchy, in which spatially close objects are also structurally close, is achieved by defining an appropriate cost function. The proposed technique is evaluated upon several 3D scenes and compared to a previous technique. In addition, the benefits of the proposed technique with respect to techniques based on octrees and kd-trees are analyzed in terms of a practical application.     

基于属性子空间的孤立点内涵知识挖掘

孤立点通常都包含着重要的信息,挖掘出孤立点的内涵知识可以帮助用户更好地认知数据。通过给出的孤立点的原因属性子空间及其孤立度和孤立点的相似度等概念,提出了一个基于属性子空间的孤立点内涵知识挖掘算法,得到了每个孤立点的原因属性集,并结合聚类的思想把孤立点按照其相似性特征进行了分类,使每一类中的所有孤立点在一定精度下都具有相同的原因属性集。实验结果表明该算法是有效和实用的,且易用性较强。