A novel ant-based clustering algorithm using the kernel method

A novel ant-based clustering algorithm integrated with the kernel (ACK) method is proposed. There are two aspects to the integration. First, kernel principal component analysis (KPCA) is applied to modify the random projection of objects when the algorithm is run initially. This projection can create rough clusters and improve the algorithm’s efficiency. Second, ant-based clustering is performed in the feature space rather than in the input space. The distance between the objects in the feature space, which is calculated by the kernel function of the object vectors in the input space, is applied as a similarity measure. The algorithm uses an ant movement model in which each object is viewed as an ant. The ant determines its movement according to the fitness of its local neighbourhood. The proposed algorithm incorporates the merits of kernel-based clustering into ant-based clustering. Comparisons with other classic algorithms using several synthetic and real datasets demonstrate that ACK method exhibits high performance in terms of efficiency and clustering quality.     

Entropy‐based metrics in swarm clustering

Ant‐based clustering methods have received significant attention as robust methods for clustering. Most ant‐based algorithms use local density as a metric for determining the ants' propensities to pick up or deposit a data item; however, a number of authors in classical clustering methods have pointed out the advantages of entropy‐based metrics for clustering. We introduced an entropy metric into an ant‐based clustering algorithm and compared it with other closely related algorithms using local density. The results strongly support the value of entropy metrics, obtaining faster and more accurate results. Entropy governs the pickup and drop behaviors, while movement is guided by the density gradient. Entropy measures also require fewer training parameters than density‐based clustering. The remaining parameters are subjected to robustness studies, and a detailed analysis is performed. In the second phase of the study, we further investigated Ramos and Abraham's (In: Proc 2003 IEEE Congr Evol Comput, Hoboken, NJ: IEEE Press; 2003. pp 1370–1375) contention that ant‐based methods are particularly suited to incremental clustering. Contrary to expectations, we did not find substantial differences between the efficiencies of incremental and nonincremental approaches to data clustering. © 2009 Wiley Periodicals, Inc.     

A large-scale performance study of entropy-based image thresholding techniques using new SAD metric

The paper presents a novel method to measure the performance of entropy-based image thresholding techniques using a new Sum of Absolute value of Differences (SAD) metric in the absence of ground-truth images. The metric is further applied to estimate the parameters of generalized Renyi, Tsallis, Masi entropy measures and the optimal threshold automatically from the image histogram. This leads to a new entropy-based image thresholding algorithm with three variants—one for each generalized entropy. The SAD metric and proposed method are first validated using ground-truth images HYTA dataset. The SAD metric is compared with misclassification error metric, Jaccard and SSIM indices and is found to exhibit consistent behavior. It is further observed that the proposed new method with SAD metric produces same or less misclassification errors than the older algorithms. Inspired by the success of the results, a large-scale performance analysis of 8 image thresholding algorithms over diverse datasets containing 621 images is carried out. The investigation reveals that the variant of the new algorithm with Tsallis, Renyi and Masi entropies segment images better than others.

     

一种基于广义互信息的图像配准算法

互信息作为图像配准中的相关度矩阵有着广泛的应用,通常采用的是基于Shannon熵的互信息。采用一个广义的信息熵——Renyi熵,提出了一种基于广义互信息的图像配准方法。在全局搜索阶段,采用q取较小值的Renyi熵,此时,Renyi熵可以消除局部极值,再通过局部优化方法对当前的局部最优解进行局部寻优,以找到全局最优解;在局部优化阶段,使用基于q→1时的Renyi熵的归一化互信息测度作为目标函数。实验结果表明:相对于归一化互信息图像配准算法,基于Renyi熵的互信息配准算法有良好的配准效果,且提高了配准速度。     

一种蚁群聚类算法

提出一种蚁群优化聚类算法,用于将N个对象优化分成K个不同的划分;该算法采用全局信息素更新策略和启发式信息构造聚类解,通过提高信息素在求解过程中的利用率加快了聚类速度,通过使用启发式信息提高了算法的搜索效率,使用均匀交叉算子改善了聚类解的质量;在几个模拟的数据集和UCI机器学习数据集上测试该算法的性能,并与其它几个启发式算法进行比较;计算结果表明该算法具有更好的解的质量,更少的函数估计次数和更少的运行时间.     

Information theoretic clustering

Clustering is an important topic in pattern recognition. Since only the structure of the data dictates the grouping (unsupervised learning), information theory is an obvious criteria to establish the clustering rule. The paper describes a novel valley seeking clustering algorithm using an information theoretic measure to estimate the cost of partitioning the data set. The information theoretic criteria developed here evolved from a Renyi entropy estimator (A. Renyi, 1960) that was proposed recently and has been successfully applied to other machine learning applications (J.C. Principe et al., 2000). An improved version of the k-change algorithm is used in optimization because of the stepwise nature of the cost function and existence of local minima. Even when applied to nonlinearly separable data, the new algorithm performs well, and was able to find nonlinear boundaries between clusters. The algorithm is also applied to the segmentation of magnetic resonance imaging data (MRI) with very promising results     

Note on the relationship between probabilistic and fuzzy clustering

In this short communication, based on Renyi entropy measure, a new Renyi information based clustering algorithm A is presented. Algorithm A and the well-known fuzzy clustering algorithm FCM have the same clustering track. This fact builds the very bridge between probabilistic clustering and fuzzy clustering, and fruitful research results on Renyi entropy measure may help us to further understand the essence of fuzzy clustering.This work was supported in part by the RGC CERG grant under project Hong Kong PolyU 5065/98E.     

Note on the relationship between probabilistic and fuzzy clustering

In this short communication, based on Renyi entropy measure, a new Renyi information based clustering algorithm A is presented. Algorithm A and the well-known fuzzy clustering algorithm FCM have the same clustering track. This fact builds the very bridge between probabilistic clustering and fuzzy clustering, and fruitful research results on Renyi entropy measure may help us to further understand the essence of fuzzy clustering.This work was supported in part by the RGC CERG grant under project HongKong PolyU 5065/98E     

高维数据的增量式聚类算法的距离度量选择研究

合适的距离度量函数对于聚类结果有重要的影响。针对大规模高维数据集,使用增量式聚类算法进行距离度量的选择分析。SpFCM算法是将大规模数据集分成小样本进行增量分批聚类,可在有限的计算机内存中获得较好的聚类结果。在传统的SpFCM算法的基础上,使用不同的距离度量函数来衡量样本之间的相似性,以得出不同的距离度量对SpFCM算法的影响。在不同的大规模高维数据集中,使用欧氏距离、余弦距离、相关系数距离和扩展的杰卡德距离来计算距离。实验结果表明,后3个距离度量相对于欧氏距离可以很大程度地提高聚类效果,其中相关系数距离可以得到较好的结果,余弦距离和扩展的杰卡德距离效果比较一般。     

基于Bagging的XML文档集成聚类研究

将集成学习方法应用到XML文档聚类中来改进传统聚类算法的不足。提出一种标签与路径相结合的XML文档向量模型,基于这个模型,首先对原始文档集进行多次抽样,在新文档集上进行K均值聚类,然后对得到的聚类中心集合进行层次聚类。在人工数据集和真实数据集上的实验表明,该算法在召回率和精确率上优于K均值算法,并且增强了其鲁棒性。     

基于数学形态学边缘检测的车牌字符分割算法

汽车牌照字符分割是车牌识别过程中的关键步骤,直接影响到字符识别的效果。传统的方法对车牌图像质量要求较高,且抗干扰能力较差。提出一种基于Renyi熵和数学形态学边缘检测的车牌字符投影分割算法,首先用二维Renyi熵最大阈值法对车牌图像做二值化处理,然后用形态学腐蚀运算进行边缘检测,再去除车牌边框,最后通过投影分割提取车牌字符。仿真实验表明,基于Renyi熵最大阈值法和数学形态学边缘检测车牌图像预处理使得车牌字符边缘清晰,降低了噪声的干扰,有利于进行字符投影分割。该算法分割速度快,鲁棒性好,可获得比传统方法更好的分割效果。     

基于模糊蚁群的加权蛋白质复合物识别算法

针对蚁群融合模糊C-means （FCM）聚类算法在蛋白质相互作用网络中进行复合物识别的准确率不高、召回率较低以及时间性能不佳等问题进行了研究,提出一种基于模糊蚁群的加权蛋白质复合物识别算法FAC-PC（algorithm for identifying weighted protein complexes based on fuzzy ant colony clustering）。首先,融合边聚集系数与基因共表达的皮尔森相关系数构建加权网络;其次提出EPS（essential protein selection）度量公式来选取关键蛋白质,遍历关键蛋白质的邻居节点,设计蛋白质适应度PFC（protein fitness calculation）来获取关键组蛋白质,利用关键组蛋白质替换种子节点进行蚁群聚类,克服蚁群算法中因大量拾起放下和重复合并过滤操作而导致准确率和收敛速度过慢的缺陷;接着设计SI（similarity improvement）度量优化拾起放下概率来对节点进行蚁群聚类进而获得聚类数目;最后将关键蛋白质和通过蚁群聚类得到的聚类数目初始化FCM算法,设计隶属度更新策略来优化隶属度的更新,同时提出兼顾类内距和类间距的FCM迭代目标函数,最终利用改进的FCM完成复合物的识别。将FAC-PC算法应用在DIP数据上进行复合物的识别,实验结果表明FAC-PC算法的准确率和召回率较高,能够较准确地识别蛋白质复合物。     

熵加权多视角核K-means算法

在基于视角加权的多视角聚类中,每个视角的权重取值对聚类结果的精度都有着重要的影响。针对此问题,提出熵加权多视角核K-means(EWKKM) 算法,通过给每个视角分配一个合理的权值来降低噪声视角或无关视角对多视角聚类的影响,进而提高聚类的精度。EWKKM算法中,首先用核矩阵表示不同的视角,给每个视角分配一个权重;然后,利用信息熵计算出各个视角的熵权重;最后,按照定义的目标函数对各个视角的权重进行优化,使用核K-means进行多视角聚类。在UCI数据集及人工数据集进行实验,实验结果表明熵加权多视角核K-means算法能够为每个视角分配一个最优的权重值,聚类的精确度优于已有的聚类算法,具有更稳定的聚类结果。     

基于信息熵的异类多种群蚁群算法

提出了一种基于信息熵的异类多种群蚁群算法。算法使用多个异类种群的蚂蚁子群体同时进行优化计算,引入信息熵来表示蚂蚁种群的进化程度,根据蚂蚁子群体间的信息熵来决定子群体间的信息交流策略,包括选择信息交流的对象和调节信息交流的周期以及信息更新策略,以取得各蚂蚁子群体中解的多样性和收敛性之间的动态平衡。基于旅行商问题的实验证明,该算法具有很好的全局搜索能力、收敛速度以及解的多样性。     

改进萤火虫优化算法的Renyi熵污油图像分割

针对传统Renyi熵方法在分割污油图像时存在图片差距大、无法根据不同图片进行最优分割的问题,提出改进萤火虫算法对二维Renyi熵分割算法中的α值进行寻优来解决上述问题。分析了采集的污油图片特点以及对污油图片进行分割的必要性;针对多目标寻优精度不高和后期收敛速度较慢的问题,对萤火虫算法进行了改进,并对初始萤火虫位置进行混沌优化处理,使结果达到全局最优;利用基于改进萤火虫算法的Renyi熵图像分割算法对采集的污油图片进行阈值分割实验,并与二维Renyi熵分割、粒子群算法(PSO)Renyi熵分割方法进行比较。实验结果表明:本文提出的算法可以有效地对污油区域进行分割,能够快速地实现复杂图像的精确处理。     

A clustering algorithm for multiple data streams based on spectral component similarity

We propose a new algorithm to cluster multiple and parallel data streams using spectral component similarity analysis, a new similarity metric. This new algorithm can effectively cluster data streams that show similar behaviour to each other but with unknown time delays. The algorithm performs auto-regressive modelling to measure the lag correlation between the data streams and uses it as the distance metric for clustering. The algorithm uses a sliding window model to continuously report the most recent clustering results and to dynamically adjust the number of clusters. Our experimental results on real and synthetic datasets show that our algorithm has better clustering quality, efficiency, and stability than other existing methods.     

基于自适应蚁群聚类的入侵检测

针对蚁群聚类算法在聚类结果中出现部分数据划分不够准确的问题,提出一种基于信息熵调整的自适应混沌蚁群聚类改进算法。该算法通过优化过程中种群的信息熵来衡量演化的程度,自适应地调整信息素更新策略。每一次迭代结束时,使用混沌搜索算子在当前全局最优解附近搜索更好的解。而随着算法的进行,混沌算子搜索范围逐渐缩小,这样混沌算子在蚁群搜索的初期起到防止陷入局部最优的作用,在蚁群搜索后期起到提高搜索精度的作用,从而得到更好的聚类结果。使用KDD Cup 1999入侵检测数据集所作的仿真实验结果表明,聚类效果改进明显,并能有效提高入侵检测的检测率、降低误检率。     

基于区域比例的聚类方法

为了改善DBSCAN参数敏感性和对密度分布不均数据对象聚类质量不高的问题,提出了一种基于DBSCAN算法的改进聚类方法。算法使用K最近邻的均值距离度量密度,中心点选取当前密度最大点,并以中心点为核心点扩展种子队列,直至由给定的密度比例因子所决定的密度边缘。为了改善聚类质量,提出了候选核心点,并使用给定的半径比例因子发现核心点。在实验中,利用数据集对该算法进行了测试,测试结果证明了该改进算法的参数鲁棒性,和在聚类密度分布不均数据集时的较好性能。     

不确定近似骨架蚁群聚类算法在滑坡危险性预测中的研究与应用

受不确定因素降雨难以准确处理的制约以及蚁群聚类算法在搜索空间容易陷入局部最优解和搜索速度慢的特征影响,为了提高滑坡危险性预测的精度,提出一种不确定近似骨架蚁群聚类算法。首先采用Gauss点概率模型来描述不确定数据,对不确定数据进行相似性度量;其次引入信息素重分配和自适应动态变量实现蚁群聚类算法局部信息素和全局信息素更新,提高蚁群聚类算法搜索速度,加载遗传算法避免蚁群聚类算法过早陷入局部最优;最后结合近似骨架理论,构建不确定近似骨架蚁群聚类算法模型,缩减迭代次数,快速搜索出聚类结果。在UCI真实数据集和延安宝塔区滑坡实验数据集上的实验结果显示,不确定近似骨架蚁群聚类 算法具有较高的聚类质量,预测精度达到93.3%,验证了算法在滑坡危险性预测中的可行性。     

基于层次聚类树的点曲面视点相关绘制

针对点曲面的视点相关绘制问题,提出了一个新的表面基层次聚类简化算法。区别于普遍采用的空间剖分基策略,该算法的显著优势在于能够运用法向锥半角误差标准有效跟踪曲面的起伏变化,并以此为聚类简化过程提供可靠的全局误差控制。离线简化阶段,连同各种预定义的聚类约束条件,算法构造了点曲面模型的连续层次多分辨率表达。实时绘制阶段,层次可见性裁剪以及优化的树遍历提高了系统的整体性能。此外,通过引入附加的轮廓增强机制,在较大的屏幕投影误差和较高的模型简化率情况下,系统仍然能够保证较好的绘制视觉质量。