基于子空间聚类的高维数据可视分析方法综述

随着信息技术的飞速发展和大数据时代的来临,数据呈现出高维性、非线性等复杂特征。对于高维数据来说,在全维空间上往往很难找到反映分布模式的特征区域,而大多数传统聚类算法仅对低维数据具有良好的扩展性。因此,传统聚类算法在处理高维数据的时候,产生的聚类结果可能无法满足现阶段的需求。而子空间聚类算法搜索存在于高维数据子空间中的簇,将数据的原始特征空间分为不同的特征子集,减少不相关特征的影响,保留原数据中的主要特征。通过子空间聚类方法可以发现高维数据中不易展现的信息,并通过可视化技术展现数据属性和维度的内在结构,为高维数据可视分析提供了有效手段。总结了近年来基于子空间聚类的高维数据可视分析方法研究进展,从基于特征选择、基于子空间探索、基于子空间聚类的3种不同方法进行阐述,并对其交互分析方法和应用进行分析,同时对高维数据可视分析方法的未来发展趋势进行了展望。     

基于k最相似聚类的子空间聚类算法

子空间聚类是聚类研究领域的一个重要分支和研究热点,用于解决高维聚类分析面临的数据稀疏问题。提出一种基于k最相似聚类的子空间聚类算法。该算法使用一种聚类间相似度度量方法保留k最相似聚类,在不同子空间上采用不同局部密度阈值,通过k最相似聚类确定子空间搜索方向。将处理的数据类型扩展到连续型和分类型,可以有效处理高维数据聚类问题。实验结果证明,与CLIQUE和SUBCLU相比,该算法具有更好的聚类效果。     

一种基于数据流的软子空间聚类算法

针对高维数据的聚类研究表明,样本在不同数据簇往往与某些特定的数据特征子集相对应.因此,子空间聚类技术越来越受到关注.然而,现有的软子空间聚类算法都是基于批处理技术的聚类算法,不能很好地应用于高维数据流或大规模数据的聚类研究中.为此,利用模糊可扩展聚类框架,与熵加权软子空间聚类算法相结合,提出了一种有效的熵加权流数据软子空间聚类算法——EWSSC(entropy-weighting streaming subspace clustering).该算法不仅保留了传统软子空间聚类算法的特性,而且利用了模糊可扩展聚类策略,将软子空间聚类算法应用于流数据的聚类分析中.实验结果表明,EWSSC 算法对于高维数据流可以得到与批处理软子空间聚类方法近似一致的实验结果.     

基于Krylov子空间方法的网络入侵数据聚类

网络信息安全中的数据具有维数高、规模复杂等特性。网络入侵检测需要对网络入侵信息进行合理的分析,筛选出危险的带有攻击性的行为。随着数据维数的不断升高,传统的基于距离的聚类分析方法不再适用。针对此,本文提出一种基于Krylov子空间方法的高维数据聚类分析算法,首先将高维数据投影到低维空间,实现数据的降维,再用基于遗传算法的K-means算法在低维空间中进行数据的聚类,避免了数据属性的丢失,同时也提高了高维数据聚类分析的效率。最后,使用KDD Cup 99数据进行实验,实验验证了方法的有效性和精确性。     

基于子空间差异的投影聚类算法

针对传统K-means型软子空间聚类技术中子空间差异度量定义的困难问题，提出一种基于概率距离的子空间差异表示模型，以此为基础提出一种自适应的投影聚类算法。该方法首先基于子空间聚类理论提出一个描述各簇类所关联的软子空间之间的相异度公式；其次，将其与软子空间聚类相结合，定义了聚类目标优化函数，并根据局部搜索策略给出了聚类算法过程。在合成和实际数据集上进行了一系列实验，结果表明该算法引入子空间比较可以为簇类学习更优的软子空间；与现有主流子空间聚类算法相比，所提算法大幅度提升了聚类精度，适用于高维数据聚类分析。     

基于分治法的高维大数据集模糊聚类算法

将高维的大数据集随机分成若干个子集，对每个子集聚类采用一种基于遗传算法的高维数据模糊聚类方法。该方法引入了一个模糊非相似矩阵来表示高维样本之间的非相似程度，并将高维样本随机初始化到二维平面，利用遗传算法迭代优化二维样本的坐标值，实现二维样本之间的欧氏距离向样本间的模糊非相似度的趋近。将得到的最优的二维样本用模糊C-均值聚类(FCM)算法聚类，克服了聚类有效性对高维样本空间分布的依赖。实验仿真表明，该算法有较好的聚类效果，且极大地提高了聚类的速度。     

面向高维特征缺失数据的K最近邻插补子空间聚类算法

针对高维特征缺失数据在聚类过程中面临的因数据高维引发的维度灾难问题和数据特征缺失导致的样本间有效距离计算失效问题,提出一种面向高维特征缺失数据的K最近邻（KNN）插补子空间聚类算法KISC。首先,利用高维特征缺失数据的子空间下的近邻关系对原始空间下的特征缺失数据进行KNN插补;然后,利用多次迭代矩阵分解和KNN插补获得数据最终可靠的子空间结构,并在该子空间结构进行聚类分析。在6个图像数据集原始空间的聚类结果表明,相较于经过插补后直接进行聚类的对比算法,KISC算法聚类效果更好,说明子空间结构能够更加容易且有效地识别数据的潜在聚类结构;在6个高维数据集子空间下的聚类结果显示,KISC算法在各个数据集的聚类性能均优于对比算法,且在大多数据集上取得了最优的聚类精确度（ACC）和标准互信息（NMI）。KISC算法能够更加有效地处理高维特征缺失数据,提高算法的聚类性能。     

基于单元区域的高维数据聚类算法

高维数据空间维数较高,数据点分布稀疏、密度平均,从中发现数据聚类比较困难,而用基于距离的方法进行高维数据聚类,维数的增多会使得计算对象间距离的时间开销增大. CAHD(clustering algorithm of high-dimensional data)算法首先采用双向搜索策略在指定的n维空间或其子空间上发现数据点密集的单元区域,然后采用逐位与的方法为这些密集单元区域进行聚类分析.双向搜索策略能够有效地减少搜索空间,从而提高算法效率,同时,聚类密集单元区域只用到逐位与和位移两种机器指令,使得算法效率得到进一步提高.算法CAHD可以有效地处理高维数据的聚类问题.基于数据集的实验表明,算法具有很好的有效性.     

高维数据流聚类及其演化分析研究

基于数据流数据的聚类分析算法已成为研究的热点．提出一种基于子空间的高维数据流聚类及演化分析算法CAStream，该算法对数据空间进行网格化，采用近似的方法记录网格单元的统计信息，并将潜在密集网格单元快照以改进的金字塔时间结构进行存储，最后采用深度优先搜索方法进行聚类及其演化分析．CAStream能够有效处理高雏数据流，并能发现任意形状分布的聚类．基于真实数据集与仿真数据集的实验表明，算法具有良好的适用性和有效性．     

基于可变加权的高维数据子空间聚类算法研究

高维数据的稀疏性和"维灾"问题使得多数传统聚类算法失去作用,因此研究高维数据集的聚类算法己成为当前的一个热点.子空间聚类算法是实现高维数据集聚类的有效方法之一.介绍并实现了基于可变加权的高维数据子空间聚类算法SCAD和EWKM,并分别对人造数据、现实数据等数据集进行测试,根据测试结果进行分析,对比两种算法的性能及适用场合.     

子空间聚类算法的研究新进展

高维数据聚类是聚类技术的难点和重点,子空间聚类是实现高维数据集聚类的有效途径,它是在高维数据空间中对传统聚类算法的一种扩展,其思想是将搜索局部化在相关维中进行.该文从不同的搜索策略即自顶向下策略和自底向上策略两个方面对子空间聚类算法的思想进行了介绍,对近几年提出的子空间聚类算法作了综述,从算法所需参数、算法对参数的敏感度、算法的可伸缩性以及算法发现聚类的形状等多个方面对典型的子空间聚类算法进行了比较分析,对子空间聚类算法面临的挑战和未来的发展趋势进行了讨论.     

Locality sensitive hashing for sampling-based algorithms in association rule mining

Association rule mining is one of the most important techniques for intelligent system design and has been widely applied in a large number of real applications. However, classical mining algorithms cannot process very large databases in a reasonable amount of time. The sampling approach that processes a subset of the whole database is a viable alternative. Obviously, such an approach cannot extract perfectly accurate rules. Previous works have tried to improve the accuracy by removing “outliers” from the initial sample based on global statistical properties in the sample. In this paper, we take the view that the initial sample may actually consist of multiple possibly overlapping subsets or clusters. It is more reasonable to apply data clustering techniques to the initial sample before outlier removal is performed on the resulting clusters, so that outliers are removed based on local properties of individual clusters. However, clustering transactional data with very high dimensions is a difficult problem by itself. We solve this problem by interpreting locality sensitive hashing as a means for data clustering. Previously proposed algorithms may be then optionally used to remove the outliers in the individual clusters. We propose several concrete algorithms based on this general strategy. Using an extensive set of synthetic data and real datasets, we evaluate our proposed algorithms and find that our proposals exhibit better accuracy or execution time, or both, than previously proposed algorithms.     

Fast Dimension-based Partitioning and Merging clustering algorithm

Clustering multi-dense large scale high dimensional numeric datasets is a challenging task duo to high time complexity of most clustering algorithms. Nowadays, data collection tools produce a large amount of data. So, fast algorithms are vital requirement for clustering such data. In this paper, a fast clustering algorithm, called Dimension-based Partitioning and Merging (DPM), is proposed. In DPM, first, data is partitioned into small dense volumes during the successive processing of dataset dimensions. Then, noise is filtered out using dimensional densities of the generated partitions. Finally, merging process is invoked to construct clusters based on partition boundary data samples. DPM algorithm automatically detects the number of data clusters based on three insensitive tuning parameters which decrease the burden of its usage. Performance evaluation of the proposed algorithm using different datasets shows its fastness and accuracy compared to other clustering competitors.     

一种基于网格的增量聚类算法*

分析了现有基于网格的聚类算法,该算法具有高效且可以处理高维数据的特点,但传统网格聚类算法的聚类质量受网格划分的粒度影响较大。为此,提出了一种基于网格的增量聚类算法IGrid。IGrid算法具有传统网格聚类算法的高效性,且通过维度半径对网格空间进行了动态增量划分以提高聚类的质量。在真实数据集与仿真数据集上的实验结果表明,IGrid算法在聚类准确度以及效率上要高于传统的网格聚类算法。     

一种可信子空间标志方法*

在D-S证据理论的基础上,给出了可信子空间的定义及能够发现所有可信子空间的贪心算法CSL(creditable subspace labeling)。该方法迭代地发现原始特征空间的信任子空间集Cs。用户根据应用领域的需求, 对Cs中的每个可信子空间调用传统聚类算法发现聚类结果。实验结果表明,CSL具有正确发现原始特征空间的真实子空间的能力,为传统聚类算法处理高维数据空间聚类问题提供了一种新的途径。     

基于映射的高维数据聚类方法

通常,经典的数据聚类算法在低维情况下是有效的,但随着维数的增加,性能和效率都明显的下降,原因在于数据的复杂度是呈指数增长。本文提出了一个处理高维数据聚类的框架,并分析了该框架的性能。     

Linear manifold clustering in high dimensional spaces by stochastic search

Classical clustering algorithms are based on the concept that a cluster center is a single point. Clusters which are not compact around a single point are not candidates for classical clustering approaches. In this paper we present a new clustering paradigm in which the cluster center is a linear manifold. Clusters are groups of points compact around a linear manifold. A linear manifold of dimension 0 is a point. So clustering around a center point is a special case of linear manifold clustering. Linear manifold clustering (LMCLUS) identifies subsets of the data which are embedded in arbitrary oriented lower dimensional linear manifolds. Minimal subsets of points are repeatedly sampled to construct trial linear manifolds of various dimensions. Histograms of the distances of the points to each trial manifold are computed. The sampling corresponding to the histogram having the best separation between a mode near zero and the rest is selected and the data points are partitioned on the basis of the best separation. The repeated sampling then continues recursively on each block of the partitioned data. A broad evaluation of some 100 experiments over real and synthetic data sets demonstrates the general superiority of this algorithm over any of the competing algorithms in terms of accuracy and computation time. Its expected computational time is linearly proportional to the data set dimension and data set size. Its accuracy ranges from near 0.90 to 0.99 depending on the experiment and is generally much higher than the accuracy of the competing clustering algorithms.     

Combining supervised and unsupervised learning for data clustering

Clustering aims to partition a data set into homogenous groups which gather similar objects. Object similarity, or more often object dissimilarity, is usually expressed in terms of some distance function. This approach, however, is not viable when dissimilarity is conceptual rather than metric. In this paper, we propose to extract the dissimilarity relation directly from the available data. To this aim, we train a feedforward neural network with some pairs of points with known dissimilarity. Then, we use the dissimilarity measure generated by the network to guide a new unsupervised fuzzy relational clustering algorithm. An artificial data set and a real data set are used to show how the clustering algorithm based on the neural dissimilarity outperforms some widely used (possibly partially supervised) clustering algorithms based on spatial dissimilarity.     

云计算环境下基于分形的聚类融合算法研究

传统的聚类算法不适用于处理海量和高维数据。针对云计算环境下,利用集群系统的并行计算能力,实现海量数据的聚类问题,给出了云计算环境下基于分形维数的聚类融合算法。该算法首先对基于分形维数的聚类算法进行改进,使之更适用于并行计算,其产生聚类作为初始聚类成员;再结合投票算法的融合策略实现融合。最后,对基于分形维数的聚类融合算法在云计算环境下实现并行计算。通过在UCI数据集上的对比实验来验证该算法的有效性。     

一种基于相似性度量的高维数据聚类算法的研究

针对传统基于距离度量的聚类算法难以适合高维数据聚类以及高维数据之间相似度难定义的问题,提出了一种新的高维数据聚类算法.该算法基于一个能够更准确地表达出高维对象之间相似性的度量函数,首先计算对象两两之间的相似度并得出一个相似度矩阵,然后根据该相似度矩阵和阈值大小自底向上对数据进行聚类分析.实验结果显示,该算法能够获得质量更高的聚类结果,并且不受孤立点影响,对输入数据顺序也不敏感.