基于邻接图的离群数据聚类算法

离群数据是数据中的小模式,因其固有的少数据与稀疏性等特征,使得基于距离或基于统计等常规聚类方式不适用于对离群数据的分类。该文根据离群对象关键域子空间的重合度,定义了离群共享属性集与离群相似度等概念,提出-离群簇分析技术。通过构建离群邻接图并将其稀疏化,将-离群簇搜索与相应的离群邻接图的最大完全子图搜索一一对应,给出一种基于邻接图的离群数据聚类算法。算例及实验结果表明,该方法具有较高的效率及良好的直观性。     

基于局部信息熵的加权子空间离群点检测算法

离群点检测作为数据挖掘的一个重要研究方向,可以从大量数据中发现少量与多数数据有明显区别的数据对象,"维度灾殃"现象的存在使得很多已有的离群点检测算法对高维数据不再有效,针对这一问题,提出基于局部信息熵的加权子空间离群点检测算法SPOD,通过对数据对象在各维进行邻域信息熵分析,生成数据对象相应的离群子空间和属性权向量,对离群子空间中的属性赋以较高的权值,进一步提出子空间加权距离等概念,采用基于密度离群点检测的思想,分析计算数据对象的子空间离群影响因子,判断是否为离群点,算法能够有效地适应于高维数据离群点检测,理论分析和实验结果表明算法是有效可行的.     

基于相关子空间的高维离群数据检测算法

为了提高离群数据检测精度和效率,提出了一种基于相关子空间的离群数据检测算法。该算法首先根据数据局部密度分布特征得出稀疏度矩阵,通过高斯相似核函数放大稀疏度特征;然后计算各属性维中数据稀疏度相似因子,确定子空间向量及相关子空间,结合数据稀疏度和维度权值得出数据对象的离群因子,选取最大的若干个对象为离群数据;最后采用人工数...     

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

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

基于自适应的高对比性子空间的高维离群点检测

基于子空间解决高维离群点挖掘的问题已经引起人们的广泛关注,现有方法存在的主要问题是难以选取合适的子空间且选取计算量大、阈值等参数设置困难等。这些影响了检测精度和检测效率。利用高对比度子空间选取方法解决子空间选取问题,利用自适应方法解决阈值参数的确定问题,据此提出自适应的高对比性子空间离群点检测方法(AHiCS)。该方法利用统计检验算法选取高对比性子空间,在高对比性的子空间里自适应计算离群点得分,提高了离群点检测的精度与效率。理论和实验表明,该方法可以有效地挖掘高维离群点。     

基于相关子空间的多源离群检测算法

传统的离群检测方法多数源于单个数据集或多数据源融合后的单一数据集,其检测结果忽略了多源数据之间的关联知识和单数据源中的关键信息。为了检测多源数据之间的离群关联知识,提出一种基于相关子空间的多源离群检测算法RSMOD。结合[k]近邻集和反向近邻集的双向影响,给出面向多源数据的对象影响空间,提高了离群对象度量的准确性;在影响空间基础上,提出面向多源数据的稀疏因子及稀疏差异因子,有效地刻画了数据对象在多源数据中的稀疏程度,重新定义了相关子空间的度量,使其能适用于多源数据集,并给出基于相关子空间的离群检测算法;采用人工合成数据集和真实的美国人口普查数据集,实验验证了RSMOD算法的性能并分析了源于多数据集的离群关联知识。     

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

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

基于基尼指标加权的离群子空间与离群数据挖掘方法

针对大多数离群数据检测方法依赖于用户确定参数以及维灾现象,给出了一种基于基尼指标加权的离群子空间与离群数据挖掘方法。该方法通过计算各个维上去一划分的基尼指标值来生成数据对象的离群子空间及属性权向量,在子空间中采用基于统计离群数据挖掘的思想来挖掘离群数据;不需输入参数,结果更具客观性,并且能够适应高维离群数据挖掘;最后采用恒星光谱数据集,验证了可行性和有效性。     

基于遗传算法的α-离群约简搜索算法

离群数据挖掘与分析在网络入侵控制、信用卡检测、通信欺诈分析等诸多领域具有十分重要的意义。结合粗糙集理论的属性约简技术,定义了α-离群约简等概念,提出了一种以属性离群贡献率和离群划分相似水平为基础的基于遗传算法的α-离群约简算法。这种方法通过维数更小的属性子空间去获得相同或相近的离群数据集,使对离群数据来源及出现原因的分析和理解更加集中于较小的目标域。通过对现实数据集的实验表明,该算法可有效地产生出约简并具有较好的规模适应性。     

基于遗传算法的高维离群点检测算法的改进

离群点检测在欺诈检测、网络鲁棒性分析和入侵检测等领域有着重要的应用.Aggarwal和Yu提出的基于子空间投影和遗传算法(GA)的离群点检测方法是处理高维数据的一个有效方法.由于该算法的交叉重组过程采用贪心策略选择子串,并且随着变异概率的改变可能导致发现不了一些有意义的离群数据.文中对该算法的交叉过程和变异过程进行改进,提出一种改进的算法,提高了检测的精度并且不受变异概率改变的影响.     

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.     

LOMA: A local outlier mining algorithm based on attribute relevance analysis

In this study, we propose a novel local outlier detection approach - called LOMA - to mining local outliers in high-dimensional data sets. To improve the efficiency of outlier detection, LOMA prunes irrelevance attributes and objects in the data set by analyzing attribute relevance with a sparse factor threshold. Such a pruning technique substantially reduce the size of data sets. The core of LOMA is searching sparse subspace, which implements the particle swarm optimization method in reduced data sets. In the process of searching sparse subspace, we introduce the sparse coefficient threshold to represent sparse degrees of data objects in a subspace, where the data objects are considered as local outliers. The attribute relevance analysis provides a guidance for experts and users to identify useless attributes for detecting outliers. In addition, our sparse-subspace-based outlier algorithm is a novel technique for local-outlier detection in a wide variety of applications. Experimental results driven by both synthetic and UCI data sets validate the effectiveness and accuracy of our LOMA. In particular, LOMA achieves high mining efficiency and accuracy when the sparse factor threshold is set to a small value.     

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

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

基于高对比度子空间的改进孤立森林方法

针对孤立森林通过随机选择属性进行数据空间分割,在面对高维数据时具有不可靠性这一问题,提出了一种基于高对比度子空间的改进孤立森林算法 （high contrast subspace isolation forest,HiForest）。首先,该方法基于子空间各属性边缘概率与联合概率间的偏差值,选取具有高对比度值的子空间;其次,在相关子空间中构建离群点检测能力更优的隔离树,多棵隔离树集成为隔离林,通过遍历数据点在隔离森林中的平均路径长度从而得到异常分数。基于ODDS数据集的实验表明,与传统的异常检测算法相比,HiForest在曲线下面积、查准率、召回率和F1-score评价指标上均有较明显的提升。因此,HiForest算法是一种适用于中高维数据集,检测精度更高的异常检测算法。     

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

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

Outliers detection in multivariate time series by independent component analysis

In multivariate time series, outlying data may be often observed that do not fit the common pattern. Occurrences of outliers are unpredictable events that may severely distort the analysis of the multivariate time series. For instance, model building, seasonality assessment, and forecasting may be seriously affected by undetected outliers. The structure dependence of the multivariate time series gives rise to the well-known smearing and masking phenomena that prevent using most outliers' identification techniques. It may be noticed, however, that a convenient way for representing multiple outliers consists of superimposing a deterministic disturbance to a gaussian multivariate time series. Then outliers may be modeled as nongaussian time series components. Independent component analysis is a recently developed tool that is likely to be able to extract possible outlier patterns. In practice, independent component analysis may be used to analyze multivariate observable time series and separate regular and outlying unobservable components. In the factor models framework too, it is shown that independent component analysis is a useful tool for detection of outliers in multivariate time series. Some algorithms that perform independent component analysis are compared. It has been found that all algorithms are effective in detecting various types of outliers, such as patches, level shifts, and isolated outliers, even at the beginning or the end of the stretch of observations. Also, there is no appreciable difference in the ability of different algorithms to display the outlying observations pattern.     

无线传感器网络中异常读数检测算法研究*

针对无线传感器网络的离群点检测算法由于没有充分考虑数据的时空关联性和网络的分布特性,导致检测精度低、通信量大和计算复杂度高等局限,提出了基于时空关联的分布计算与过滤的在线离群点检测算法。该算法在各传感器节点上利用传感器读数的时间关联性生成候选离群点,并利用空间关联性对候选离群点进行过滤得到局部离群点,最终将所有传感器节点上的局部离群点集中到sink节点上获得全局离群点。利用时空关联性提高了检测精度,利用分布计算与过滤减少了通信量和计算量,理论分析和实验结果均表明该算法优于现有算法。