基于类间距离参数估计的文本聚类评价方法

文本聚类评价算法运用统计学当中的参数估计方法,根据类间距离信息对其分布规律中的数字特征进行参数估计。基于估计的结果确定类间距离合理的取值范围,将不合理的聚类进行调整,并通过聚类有效性判断函数最终确认调整结果。该算法有效地提高聚类结果的准确性,井为聚类算法的选择与分析提供一种可行的方法。实验结果证明了其可行性与有效性。     

基于灰度空间特征的模糊C均值聚类图像分割

模糊C均值(FCM)聚类算法广泛用于图像的自动分割,但是该算法没有考虑像素的灰度和空间特征,对噪声十分敏感.因此提出一种改进的算法,在传统的FCM聚类的基础上,运用邻域像素的灰度相似度和聚类分布统计来构造新的隶属函数,对图像进行聚类分割.该方法不仅有效地抑制了噪声的干扰,而且把错分类的像素很容易的纠正过来.对两种类型的含噪图像的实验结果表明该方法对噪声具有很强的鲁棒性和对像素聚类的正确性.     

混合属性数据点集的特征权重优化方法研究

应用决策树方法来获取混合属性数据点集的“规则聚类区域”,利用“异类子聚类相离,同类子聚类相近”的原则来交替优化有序属性和无序属性的权重,提出了基于决策树划分的特征权重优化方法。该方法在一定程度上解决了有效获取数据子集的子聚类问题和混合属性数据点集的特征权重优化难题。仿真实验表明,该方法在优化混合属性数据点集的特征权重时是有效的。     

基于密度和对象方向聚类算法的改进

针对K-means算法所存在的问题进行了深入的研究,提出了基于密度和聚类对象方向的改进算法(KADD算法)。该算法采取聚类对象分布密度方法来确定初始聚类中心,然后根据对象的聚类方向来发现任意形状的簇。理论分析与实验结果表明,改进算法在不改变时间、空间复杂度的情况下能取得更好的聚类结果。     

基于模拟退火算法的传感器网络聚类方案

针对传感器网络聚类间能耗负载不均衡而引发的“能量热点”问题,提出一种在节点随机分布情况下构建能量负载均衡的聚类方法。网络中高于平均能量的节点率先成为候选首领,候选首领根据剩余能量、节点连通度以及当选首领的总时间来竞争聚首,普通节点首先依据信号强弱选择加入聚类,然后借鉴模拟退火算法动态调整所拥有的成员节点,直到所有聚类的能耗状态趋近均衡。仿真表明,与基于均匀分布假设的聚类方案相比,新方案具有能耗负载更均衡的聚类和更长的生命周期。     

基于密度和对象方向聚类算法的改进

针对K-means算法所存在的问题进行了深入的研究,提出了基于密度和聚类对象方向的改进算法(KADD算法).该算法采取聚类对象分布密度方法来确定初始聚类中心,然后根据对象的聚类方向来发现任意形状的簇.理论分析与实验结果表明,改进算法在不改变时间、空间复杂度的情况下能取得更好的聚类结果.     

障碍空间里基于密度的快速聚类算法

传统的聚类方法不能直接运用于分布空间内存在障碍物的数据的聚类.提出了一种障碍空间内基于密度的快速聚类算法DBCO来解决此类问题.DBCO中,在基于密度的聚类基础上引入了障碍模型,提出了一种保持数据间可见性的简化障碍的方法.为了使障碍模型不影响聚类质量,定义了障碍顶点距离、连接距离和判断距离来维持聚类的质量.另外,在聚类过程中,选择某一些代表点和拓展点而不是每一个点来对每一个聚类进行扩展,从而大大提高了聚类算法的效率.实验结果表明了DB-CO算法可以快速地得到高质量的聚类结果.     

高斯混合模型聚类中EM算法及初始化的研究

EM算法是参数估计的重要方法,其算法核心是根据已有的数据来迭代计算似然函数,使之收敛于某个最优值。EM算法收敛的优劣很大程度上取决于其初始参数。运用EM算法来实现高斯混合模型聚类,如何初始化EM参数便成为一个关键的问题。在比较其他的初始化方法的基础上,引入“binning”法来初始化EM。实验结果表明,应用binning法来初始化EM的高斯混合模型聚类优于其它传统的初始化方法。     

基于Zipf分布的网格密度峰值聚类算法

网格密度峰值聚类在兼顾密度峰值聚类算法可识别任意形状类簇的基础上,通过数据集的网格化简化整体计算量,成为当前备受关注的聚类方法.针对大规模数据,如何进一步区分稠密与稀疏网格,减少网格密度峰值聚类中参与计算的非空网格代表点的数量是解决“网格灾难”的关键.结合以网格密度为变量的概率密度分布呈现出类Zipf分布的特点,提出一种基于Zipf分布的网格密度峰值聚类算法.首先计算所有非空网格的密度并映射为Zipf分布,根据对应的Zipf分布筛选出稠密中心网格和稀疏边缘网格;然后仅对稠密中心网格进行密度峰值聚类,在自适应确定潜在聚类中心的同时减少欧氏距离的计算量,降低算法复杂度;最后通过对稀疏边缘网格的处理,进一步优化类簇边界并提高聚类精度.人工数据集和UCI数据集下的实验结果表明,所提出算法对大规模、类簇交叉数据的聚类具有明显优势,能够在保证聚类精度的同时降低时间复杂度.     

基于聚类分解的高维度量空间索引B~ -Tree

为了提高索引性能,高维度量空间索引通常采用K-Means等聚类技术来获取数据的分布信息.但是,已知的工作需要根据经验来确定聚类参数,缺乏对聚类与查询性能之间关系的理论分析.提出了一种基于聚类分解的高维度量空间B~ -tree索引,通过聚类分解,对数据进行更细致的划分来减少查询的数据访问.对聚类与查询代价的关系进行了讨论,通过查询代价模型,给出了最小查询代价条件下的聚类分解数目等理论的计算方法.实验显示,提出的索引方法明显优于iDistance等度量空间索引,最优聚类分解数的估计接近实际最优查询时所需的聚类参数.     

一种基于MST的自适应优化相异性度量的半监督聚类方法

针对混合属性空间中具有同一(或相近)分布特性的带类别标记的小样本集和无类别标记的大样本数据集,提出了一种基于MST的自适应优化相异性度量的半监督聚类方法。该方法首先采用决策树方法来获取小样本集的"规则聚类区域",然后根据"同一聚类的数据点更为接近"的原则自适应优化建构在该混合属性空间中的相异性度量,最后将优化后的相异性度量应用于基于MST的聚类算法中,以获得更为有效的聚类结果。仿真实验结果表明,该方法对有些数据集是有改进效果的。为进一步推广并在实际中发掘出该方法的应用价值,本文在最后给出了一个较有价值的研究展望。     

An improved overlapping k-means clustering method for medical applications

Data clustering has been proven to be an effective method for discovering structure in medical datasets. The majority of clustering algorithms produce exclusive clusters meaning that each sample can belong to one cluster only. However, most real-world medical datasets have inherently overlapping information, which could be best explained by overlapping clustering methods that allow one sample belong to more than one cluster. One of the simplest and most efficient overlapping clustering methods is known as overlapping k-means (OKM), which is an extension of the traditional k-means algorithm. Being an extension of the k-means algorithm, the OKM method also suffers from sensitivity to the initial cluster centroids. In this paper, we propose a hybrid method that combines k-harmonic means and overlapping k-means algorithms (KHM-OKM) to overcome this limitation. The main idea behind KHM-OKM method is to use the output of KHM method to initialize the cluster centers of OKM method. We have tested the proposed method using FBCubed metric, which has been shown to be the most effective measure to evaluate overlapping clustering algorithms regarding homogeneity, completeness, rag bag, and cluster size-quantity tradeoff. According to results from ten publicly available medical datasets, the KHM-OKM algorithm outperforms the original OKM algorithm and can be used as an efficient method for clustering medical datasets.     

基于密度权重Canopy的改进K-medoids算法

为了提高K-medoids算法的精度和稳定性,并解决K-medoids算法的聚类数目需要人工给定和对初始聚类中心点敏感的问题,提出了基于密度权重Canopy的改进K-medoids算法。该算法首先计算数据集中每个样本点的密度值,选择密度值最大的样本点作为第1个聚类中心,并从数据集中删除这个密度簇;然后通过计算剩下样本点的权重,选择出其他聚类中心;最后将密度权重Canopy作为K-medoids的预处理过程,其结果作为K-medoids算法的聚类数目和初始聚类中心。UCI真实数据集和人工模拟数据集上的仿真实验表明,该算法具有较高的精度和较好的稳定性。     

K-Means Clustering Versus Validation Measures: A Data-Distribution Perspective

K-means is a well-known and widely used partitional clustering method. While there are considerable research efforts to characterize the key features of the K-means clustering algorithm, further investigation is needed to understand how data distributions can have impact on the performance of K-means clustering. To that end, in this paper, we provide a formal and organized study of the effect of skewed data distributions on K-means clustering. Along this line, we first formally illustrate that K-means tends to produce clusters of relatively uniform size, even if input data have varied “true” cluster sizes. In addition, we show that some clustering validation measures, such as the entropy measure, may not capture this uniform effect and provide misleading information on the clustering performance. Viewed in this light, we provide the coefficient of variation (CV) as a necessary criterion to validate the clustering results. Our findings reveal that K-means tends to produce clusters in which the variations of cluster sizes, as measured by CV, are in a range of about 0.3–1.0. Specifically, for data sets with large variation in “true” cluster sizes (e.g., $ hbox{CV} ≫ 1.0$), K-means reduces variation in resultant cluster sizes to less than 1.0. In contrast, for data sets with small variation in “true” cluster sizes (e.g., $hbox{CV} ≪ 0.3$), K-means increases variation in resultant cluster sizes to greater than 0.3. In other words, for the earlier two cases, K-means produces the clustering results which are away from the “true” cluster distributions.      

基于动态邻域的三支聚类分析

目前,大多数聚类方法是二支聚类,即对象要么属于一个类,要么不属于一个类,聚类的结果必须具有清晰的边界。然而,将某些不确定的对象强制分配到某个类中将降低聚类结果的结构和精度。三支聚类是一种重叠聚类,它采用核心域和边界域来表示每个类别,较好地处理了具有不确定性对象的聚类问题。提出了一种使用样本邻域将二支聚类转化为三支聚类的方法。该方法利用二支聚类的结果和每个类中元素的邻域是否完全包含在该类中来对集合进行收缩,同时利用不在该类中的元素的邻域是否与该类有交集来进行扩张。收缩的区域称为核心域,扩张域和核心域的差集称为边界域。在UCI数据集上的实验结果显示,该方法在提高聚类结果的结构和F1值方面有较好的效果。     

一种新的聚类分析算法

给出了一种新的无监督聚类算法,但这种算法并非是基于目标函数的聚类算法,而是对数据直接设计一种迭代运算,以使数据在保持类特征的情况下进行重新组合最终达到分类的目的。通过对一类数据的实验表明,该算法在无监督给出类数方面具有较好的鲁棒性;另外,该算法在数据的准确归类、无监督聚类、确定性,以及对特殊类分布的适用性等方面均优于ＨＣＭ和ＦＣＭ算法,     

Fuzzy PCA-Guided Robust -Means Clustering

This paper proposes a new approach to robust clustering, in which a robust $k$-means partition is derived by using a noise-rejection mechanism based on the noise-clustering approach. The responsibility weight of each sample for the $k$-means process is estimated by considering the noise degree of the sample, and cluster indicators are calculated in a fuzzy principal-component-analysis (PCA) guided manner, where fuzzy PCA-guided robust $k$-means is performed by considering responsibility weights of samples. Then, the proposed method achieves cluster-core estimation in a deterministic way. The validity of the derived cluster cores is visually assessed through distance-sensitive ordering, which considers responsibility weights of samples. Numerical experiments demonstrate that the proposed method is useful for capturing cluster cores by rejecting noise samples, and we can easily assess cluster validity by using cluster-crossing curves.      

基于改进K-medoids的聚类质量评价指标研究

为了更好地评价无监督聚类算法的聚类质量,解决因簇中心重叠而导致的聚类评价结果失效等问题,对常用聚类评价指标进行了分析,提出一个新的内部评价指标,将簇间邻近边界点的最小距离平方和与簇内样本个数的乘积作为整个样本集的分离度,平衡了簇间分离度与簇内紧致度的关系;提出一种新的密度计算方法,将样本集与各样本的平均距离比值较大的对象作为高密度点,使用最大乘积法选取相对分散且具有较高密度的数据对象作为初始聚类中心,增强了K-medoids算法初始中心点的代表性和算法的稳定性,在此基础上,结合新提出的内部评价指标设计了聚类质量评价模型,在UCI和KDD CUP 99数据集上的实验结果表明,新模型能够对无先验知识样本进行有效聚类和合理评价,能够给出最优聚类数目或最优聚类范围.     

面向主动学习的模糊核聚类采样算法

针对主动学习中构造初始分类器难以选取代表性样本的问题,提出一种模糊核聚类采样算法。该算法首先通过聚类分析技术将样本集划分,然后分别在类簇中心和类簇边界区域选取样本进行标注,最后依此构造初始分类器。在该算法中,通过高斯核函数把原始样本空间中的点非线性变换到高维特征空间,以达到线性可聚的目的,并引入了一种基于局部密度的初始聚类中心选择方法,从而改善聚类效果。为了提高采样质量,结合划分后各类簇的样本个数设计了一种采样比例分配策略。同时,在采样结束阶段设计了一种后补采样策略,以确保采样个数达标。实验结果分析表明,所提算法可以有效地减少构造初始分类器所需的人工标注负担,并取得较高的分类正确率。     

Graph-based clustering and ranking for diversified image search

In this paper, we consider the problem of clustering and re-ranking web image search results so as to improve diversity at high ranks. We propose a novel ranking framework, namely cluster-constrained conditional Markov random walk (CCCMRW), which has two key steps: first, cluster images into topics, and then perform Markov random walk in an image graph conditioned on constraints of image cluster information. In order to cluster the retrieval results of web images, a novel graph clustering model is proposed in this paper. We explore the surrounding text to mine the correlations between words and images and therefore the correlations are used to improve clustering results. Two kinds of correlations, namely word to image and word to word correlations, are mainly considered. As a standard text process technique, tf-idf method cannot measure the correlation of word to image directly. Therefore, we propose to combine tf-idf method with a novel feature of word, namely visibility, to infer the word-to-image correlation. By latent Dirichlet allocation model, we define a topic relevance function to compute the weights of word-to-word correlations. Taking word to image correlations as heterogeneous links and word-to-word correlations as homogeneous links, graph clustering algorithms, such as complex graph clustering and spectral co-clustering, are respectively used to cluster images into topics in this paper. In order to perform CCCMRW, a two-layer image graph is constructed with image cluster nodes as upper layer added to a base image graph. Conditioned on the image cluster information from upper layer, Markov random walk is constrained to incline to walk across different image clusters, so as to give high rank scores to images of different topics and therefore gain the diversity. Encouraging clustering and re-ranking outputs on Google image search results are reported in this paper.