局部加权最小二乘回归的重叠子空间聚类算法

针对大多数子空间聚类方法处理非线性数据时聚类效果不理想、不同子空间数据相似性较高及聚类发生错误时无法及时校验的问题,提出局部加权最小二乘回归的重叠子空间聚类算法.利用K近邻思想突出数据的局部信息,取代非线性数据结构,通过高斯加权的方法选择最相似的近邻数据点,得到最优表示系数.然后使用重叠概率模型判断子空间内数据的重叠部分,再次校验聚类结果,提高聚类准确率.在人造数据集和真实数据集上分别进行测试,实验表明,文中算法能够取得较理想的聚类结果.     

稀疏条件下的重叠子空间聚类算法

现有子空间聚类算法不能很好地平衡子空间数据的稠密性和不同子空间数据稀疏性的关系,且无法处理数据的重叠问题。针对上述问题,提出一种稀疏条件下的重叠子空间聚类(OSCSC)算法。算法利用L1范数和Frobenius范数的混合范数表示方法建立子空间表示模型,并对L1范数正则项进行加权处理,提高不同子空间的稀疏性和同一子空间的稠密性;然后对划分好的子空间使用一种服从指数族分布的重叠概率模型进行二次校验,判断不同子空间数据的重叠情况,进一步提高聚类的准确率。在人造数据集和真实数据集上分别进行测试,实验结果表明,OSCSC算法能够获得良好的聚类结果。     

基于二阶近邻的核子空间聚类

高维数据集的处理是计算机视觉领域的核心,子空间聚类是实现高维数据聚类使用最广泛的方法之一。传统的子空间聚类假定数据来自不同的线性子空间,且不同子空间的区域不重叠。然而,现实中的数据往往不满足这两个约束条件,使得子空间聚类的效果受到影响。为了解决这两个问题,引入核化子空间来解决子空间数据的非线性问题,引入子空间系数矩阵的二阶近邻来处理重叠的子空间问题。随后,设计了基于二阶近邻的核化子空间三步聚类算法,首先求取核化子空间数据的自相似系数,然后消除子空间的重叠区域,最后对系数矩阵进行谱聚类。将所设计的子空间聚类算法首先在人工数据集上进行了测试,随后在人脸、场景字符和生物医学3类数据集中共12个真实数据集上进行了实验。实验结果表明,所提算法相比最新的几种算法具有一定的优势。     

一种基于属性相关度的子空间聚类算法

与在所有特征空间寻找聚类不同,子空间聚类的目标是找到嵌在不同子空间的簇,是实现高维数据聚类的有效途径.传统聚类算法主要采用基于距离测量的方法进行聚类,难以处理高维数据.提出一种能够处理高维数据的子空间聚类算法(Attribute relevancy-based subspace clustering algorithm,ARSUB),将属性转化为频繁模式中的项集,将聚类问题转化为频繁模式挖掘问题,然后基于项目对间强相关的关系建立关系矩阵,以衡量任意两个项集之间的相关度,进而得到强相关的候选子空间.最后利用候选子空间进行聚类得到存在于不同子空间中的簇.在合成数据集与真实数据集的实验结果表明,这种方法具有较高的准确度和效率.     

一种基于区域划分的数据流子空间聚类方法

数据流子空间聚类的主要目的是在合理的时间段内准确找到数据流特征子空间中的聚类.现有的数据流子空间聚类算法受参数影响较大,通常要求预先给出聚类数目或特征子空间,且聚类结果不能及时反映数据流的变化情况.针对以上缺陷,提出一种新的数据流子空间聚类算法SC-RP,SC-RP无需预先给出聚类数目或特征子空间,对孤立点不敏感,可实现快速聚类,通过区域树结构记录数据流的变化并及时更新统计信息,进而根据数据流的变化调整聚类结果.通过在真实数据集与仿真数据集上的实验,证明了SC-RP在聚类精度和速度上优于现有的数据流子空间聚类算法,且对聚类数目及数据维度均具有良好的伸缩性.     

自适应的软子空间聚类算法

软子空间聚类是高维数据分析的一种重要手段.现有算法通常需要用户事先设置一些全局的关键参数,且没有考虑子空间的优化.提出了一个新的软子空间聚类优化目标函数,在最小化子空间簇类的簇内紧凑度的同时,最大化每个簇类所在的投影子空间.通过推导得到一种新的局部特征加权方式,以此为基础提出一种自适应的k-means型软子空间聚类算法.该算法在聚类过程中根据数据集及其划分的信息,动态地计算最优的算法参数.在实际应用和合成数据集上的实验结果表明,该算法大幅度提高了聚类精度和聚类结果的稳定性.     

融入无监督度量学习的稀疏子空间聚类模型

子空间聚类任务中的无标记数据具有维度高、数据分布分散等特点,传统方法对数据预处理未进行详细地针对化设计且大多使用欧氏距离度量数据间的相似性,使聚类性能提升受限.因此,本文提出融入无监督度量学习的稀疏子空间聚类模型,该算法将距离度量与子空间聚类联合到同一框架,设计由两步组成的聚类过程.该方法对原始数据进行度量学习并重构了稀疏子空间聚类模型,使数据预处理不再是一个单独的步骤,最大限度地将输入的无标记数据之间相似度提高,有效提升了子空间聚类性能、加强了模型泛化能力.我们在真实公开数据集上进行实验测试,实验结果表明该方法优于现有的子空间聚类算法,具有良好的聚类性能.     

基于三支决策的多视图低秩稀疏子空间聚类算法

多视图子空间聚类是一种从子空间中学习所有视图共享的统一表示, 挖掘数据潜在聚类结构的方法. 作为一种处理高维数据的聚类方法, 子空间聚类是多视图聚类领域的研究热点之一. 多视图低秩稀疏子空间聚类是一种结合了低秩表示和稀疏约束的子空间聚类方法. 该算法在构造亲和矩阵过程中, 利用低秩稀疏约束同时捕捉了数据的全局结构和局部结构, 优化了子空间聚类的性能. 三支决策是一种基于粗糙集模型的决策思想, 常被应用于聚类算法来反映聚类过程中对象与类簇之间的不确定性关系. 本文基于三支决策的思想, 设计了一种投票制度作为决策依据, 将其与多视图稀疏子空间聚类组成一个统一框架, 从而形成一种新的算法. 在多个人工数据集和真实数据集上的实验表明, 该算法可提高多视图聚类的准确性.     

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

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

高维分类属性的子空间聚类算法

高维分类数据的处理一直是数据挖掘研究所面临的巨大挑战.传统聚类算法主要针对低雏连续性数据的聚类,难以处理高维分类属性数据集.本文提出一种处理高维分类数据集的子空间聚类算法(FP-Tree-based SUBspace clustering algorithm,FPSUB),利用频繁模式树将聚类问题转化为寻找属性值的频繁模式发现问题,得到的频繁模式即候选子空间,然后基于这些子空间进行聚类.针对真实数据集的实验结果表明,FPSUB算法比其他算法具有更高的准确度.     

Discovering pattern-based subspace clusters by pattern tree

Traditional clustering models based on distance similarity are not always effective in capturing correlation among data objects, while pattern-based clustering can do well in identifying correlation hidden among data objects. However, the state-of-the-art pattern-based clustering methods are inefficient and provide no metric to measure the clustering quality. This paper presents a new pattern-based subspace clustering method, which can tackle the problems mentioned above. Observing the analogy between mining frequent itemsets and discovering subspace clusters, we apply pattern tree – a structure used in frequent itemsets mining to determining the target subspaces by scanning the database once, which can be done efficiently in large datasets. Furthermore, we introduce a general clustering quality evaluation model to guide the identifying of meaningful clusters. The proposed new method enables the users to set flexibly proper quality-control parameters to meet different needs. Experimental results on synthetic and real datasets show that our method outperforms the existing methods in both efficiency and effectiveness.     

A k-means type clustering algorithm for subspace clustering of mixed numeric and categorical datasets

Almost all subspace clustering algorithms proposed so far are designed for numeric datasets. In this paper, we present a k-means type clustering algorithm that finds clusters in data subspaces in mixed numeric and categorical datasets. In this method, we compute attributes contribution to different clusters. We propose a new cost function for a k-means type algorithm. One of the advantages of this algorithm is its complexity which is linear with respect to the number of the data points. This algorithm is also useful in describing the cluster formation in terms of attributes contribution to different clusters. The algorithm is tested on various synthetic and real datasets to show its effectiveness. The clustering results are explained by using attributes weights in the clusters. The clustering results are also compared with published results.     

Robust projected clustering

Projected clustering partitions a data set into several disjoint clusters, plus outliers, so that each cluster exists in a subspace. Subspace clustering enumerates clusters of objects in all subspaces of a data set, and it tends to produce many overlapping clusters. Such algorithms have been extensively studied for numerical data, but only a few have been proposed for categorical data. Typical drawbacks of existing projected and subspace clustering algorithms for numerical or categorical data are that they rely on parameters whose appropriate values are difficult to set appropriately or that they are unable to identify projected clusters with few relevant attributes. We present P3C, a robust algorithm for projected clustering that can effectively discover projected clusters in the data while minimizing the number of required parameters. P3C does not need the number of projected clusters as input, and can discover, under very general conditions, the true number of projected clusters. P3C is effective in detecting very low-dimensional projected clusters embedded in high dimensional spaces. P3C positions itself between projected and subspace clustering in that it can compute both disjoint or overlapping clusters. P3C is the first projected clustering algorithm for both numerical and categorical data.     

基于概率模型的非均匀数据聚类算法

针对传统K-means型算法的"均匀效应"问题,提出一种基于概率模型的聚类算法。首先,提出一个描述非均匀数据簇的高斯混合分布模型,该模型允许数据集中同时包含密度和大小存在差异的簇;其次,推导了非均匀数据聚类的目标优化函数,并定义了优化该函数的期望最大化（EM）型聚类算法。分析结果表明,所提算法可以进行非均匀数据的软子空间聚类。最后,在合成数据集与实际数据集上进行的实验结果表明,所提算法有较高的聚类精度,与现有K-means型算法及基于欠抽样的算法相比,所提算法获得了5%~50%的精度提升。     

Algorithm to determine ε-distance parameter in density based clustering

The well known clustering algorithm DBSCAN is founded on the density notion of clustering. However, the use of global density parameter ε-distance makes DBSCAN not suitable in varying density datasets. Also, guessing the value for the same is not straightforward. In this paper, we generalise this algorithm in two ways. First, adaptively determine the key input parameter ε-distance, which makes DBSCAN independent of domain knowledge satisfying the unsupervised notion of clustering. Second, the approach of deriving ε-distance based on checking the data distribution of each dimension makes the approach suitable for subspace clustering, which detects clusters enclosed in various subspaces of high dimensional data. Experimental results illustrate that our approach can efficiently find out the clusters of varying sizes, shapes as well as varying densities.     

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

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

Document clustering using synthetic cluster prototypes

The use of centroids as prototypes for clustering text documents with the k-means family of methods is not always the best choice for representing text clusters due to the high dimensionality, sparsity, and low quality of text data. Especially for the cases where we seek clusters with small number of objects, the use of centroids may lead to poor solutions near the bad initial conditions. To overcome this problem, we propose the idea of synthetic cluster prototype that is computed by first selecting a subset of cluster objects (instances), then computing the representative of these objects and finally selecting important features. In this spirit, we introduce the MedoidKNN synthetic prototype that favors the representation of the dominant class in a cluster. These synthetic cluster prototypes are incorporated into the generic spherical k-means procedure leading to a robust clustering method called k-synthetic prototypes (k-sp). Comparative experimental evaluation demonstrates the robustness of the approach especially for small datasets and clusters overlapping in many dimensions and its superior performance against traditional and subspace clustering methods.     

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

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