两种基于图论的聚类算法改进(英文)

近年来,基于图论的聚类算法被广泛地应用在数据聚类和图像分割之中。聚类任务主要是挖掘一组给定数据隐含的分布规律和结构信息,而图像分割则是将一幅图像划分为若干互不交迭区域的过程。主要讨论两种比较流行的基于图论的聚类算法,即基于有向树的数据聚类算法和基于最小生成树的图像分割算法。创新在于:(1)改进基于有向树的数据聚类算法,将其应用于图像分割;(2)改进基于最小生成树的图像分割算法,将其应用于数据聚类。在人工数据和实际图像数据上的实验结果表明,改进的有向树算法可以很好地分割图像并保留图像中足够的细节,而改进的最小生成树聚类算法能比较好地聚类具有流形结构的人工数据。     

模糊聚类在特征选取中的应用

提出了一种基于模糊聚类算法的高维特征选取方法。首先,利用Bhattacharyya距离过滤样本类别无关的特征;然后,基于递归特征剔除过程,提出了基于模糊迭代自组织数据分析技术(Interactive self-organizing dataanalysis technique,ISODATA)聚类方法,以样本与聚类中心的加权距离作为可分性指标,产生候选特征子集;最后,以候选特征子集分类和聚类的接受者操作特征曲线下面积(Area under the receiver operating characteristiccurve,AUC)值和正确率作为目标函数,确定最佳特征子集。将该方法用于选取5个基因表达谱数据集的特征基因,结果显示该方法所选特征具有较好的分类和聚类能力,说明了提出的特征选取方法的有效性。     

一种基于语义相似度的文本聚类算法

文本聚类在很多文本挖掘和信息检索系统中发挥着重要的作用。现有的聚类算法大多数都是基于向量空间模型,文档集合中出现的单词词频作为特征项。这些算法都存在数据维数过高、聚簇难以描述的问题,而且忽略了单词间的语义联系。本文提出了一种基于语义相似度的文本聚类算法——TCU SS(Text clustering usingsem an ticsim ilarity)算法。TCU SS算法将文档表示成概念列表,有效地解决了数据维数高和聚簇描述难的问题,并给出如何利用概念列表进行聚簇描述的方法。TCU SS算法利用两个概念列表中单词间的语义相似度作为文档间相近程度的度量,并以图为基础进行聚类分析,避免有些聚类算法对聚簇形状的限制。实验证明,TCU SS算法提高了聚类质量。     

特征加权的阴影C均值聚类新算法(英文)

将特征加权的划分聚类方法应用在阴影集的框架中阴影聚类产生的核心区和边界区的样本对每一个类的质心有不同的影响。通过集成特征权重,加权计算的公式引入到聚类算法中。权重指数的选择对于好的聚类结果非常关键,而且权重随着每次迭代划分而更新。文中给出了算法的收敛性,并且使用了可行的聚类有效性指标。在合成数据集和真实数值数据集上的不同特征权重的实验结果表明,该加权算法优于其他不加权算法。     

一种基于多维空间超球体的快速聚类算法

提出了一种基于多维空间超球体的快速聚类算法。这种算法结合密度聚类和层次聚类两种思想。首先利用密度聚类方法将小范围内的数据对象聚合成超球体,然后再按照层次聚类中的凝聚思想,根据超球体之间的位置关系产生最终聚类。实验表明,该算法对于数值型数据集不仅在效率、噪声敏感性等方面均有较好的表现,同时还可以通过诸如“双环测试”等带有刁难性的特殊测试集。以往,常常简单的以距离来刻画的数据间“相似性”,而所提出的快速聚类算法则改由超球体之间连接的紧密程度来描述这种性质。实验表明,这种修改使得算法的性能得到了很好的改善。     

基于LOFC时间窗分割算法的航迹聚类研究

针对传统聚类算法在聚类过程中缺乏时间信息而仅考虑三维坐标点的聚类,同时未考虑航空器运行速度和航向变化对聚类结果的影响,以及由于二次雷达机载设备、地面设备和信号遮挡等原因造成的实测数据源中存在离群点异常数据,离群点很难被有效识别出来从而使得非正常航迹点的影响放大,得不到理想的聚类效果等问题。本文提出LOFC算法,引入时间窗分割概念,将航空器进场平均速度值和航向变化值作为确定聚类簇大小的影响因子对进场航空器航迹点数量进行分割,引入离群点检测以及离群点剔除率等概念对离群点进行识别和剔除。对进场二次雷达数据仿真分析,从仿真结果中可以看出,新算法能有效地对离群点进行识别和剔除,当影响因子α取值为0.7时,航迹的曲率最小,得到的中心航迹的平滑程度最佳,验证了新算法对于聚类和离群点识别与剔除具有可行性和优越性。     

基于多层相似性用户聚类的推荐算法

为了降低数据稀疏性的影响,提高推荐系统的推荐生成质量,提出了一种基于多层相似性用户聚类的协同过滤推荐算法。该算法采用新的多层用户相似性度量,并将推荐过程分成了离线和在线两个部分。离线时,算法对基本用户数据进行预处理,并对基本用户聚类;在线时,算法利用已有的用户聚类寻找目标用户最近邻居,并产生推荐。实验表明,该算法不仅加快了推荐生成速度,而且提高了推荐质量,降低了约6%的平均绝对误差。     

流数据复杂聚类查询处理算法

流数据上的连续查询,尤其连续聚类查询是流数据处理研究的难点.草图算法能够计算流数据上等值连接大小的高精度近似值,而直方图算法能够较精确地统计流数据的分布.本文结合这两种算法的优势,提出了一种能够高效处理流数据上复杂聚类查询的算法.理论和实验结果表明,该算法具有较高的精度和较小的空间复杂度.     

改进相似性度量的谱聚类算法

传统的谱聚类算法通常利用高斯核函数作为相似度函数,由于算法对核参数非常敏感,且难于确定一个合适的尺度参数。为解决该问题,通过改进相似度函数,给出了谱聚类算法。在人工数据集和UCI数据集上的仿真实验表明,该算法提高了聚类的准确度,提升谱聚类算法的性能。     

基于时空模型的快速视频显著区域检测

传统的视频显著区域检测方法运算量大且难以处理包含复杂运动的视频,本文提出一种基于时空模型的快速显著区域检测方法.该方法用一种新的模糊聚类算法对特征点的运动轨迹进行无监督聚类,对不同运动类型进行分类.在复杂运动情况下,该算法通过计算优化的聚类中心的个数以获得运动类型数,再将异常数据剔除后,生成运动显著图.而在空间显著区检测方面,则利用反差模型以及Gabor滤波器获得图像的静态显著图.在此基础上,还提出一种基于运动优先思想的时空混合方法,将运动和空间显著图动态合成视觉显著图.实验证明,该方法能够有效地提取视频显著区域,与传统的方法相比该方法平均耗时更少且更方便.     

基于非欧式距离的可能性C-均值聚类

改进型可能性C-均值聚类(Improved possib ilistic C-means,IPCM)是在综合了模糊C-均值聚类(Fuzzy C-means,FCM)和可能性C-均值聚类(Possib ilistic C-means,PCM)的基础上得到的。在IPCM的基础上,利用鲁棒统计观点和影响函数,引入一种新的距离度量以代替IPCM的目标函数中的欧式距离度量,提出了一种新的可能性C-均值聚类模型(A lternative improved possib ilistic C-means,A IPCM),并给出了该模型的具体实现算法。A IPCM具有良好的鲁棒性,更适合对含有噪声或野值的数据进行划分聚类。仿真实验表明,A IPCM能克服噪声敏感性问题,获得合适的聚类中心和高的聚类准确率。     

Parameter Optimization Method for Gaussian Mixture Model with Data Evolution

To learn from evolutionary experimental data points effectively,an evolutionary Gaussian mixture model based on constraint consistency（EGMM）is proposed and the corresponding method of parameter optimization is presented.Here,the Gaussian mixture model（GMM）is adopted to describe the data points,and the differences between the posterior probabilities of pairwise points under the current parameters are introduced to measure the temporal smoothness.Then,parameter optimization of EGMM can be realized by evolutionary clustering.Compared with most of the existing data analysis methods by evolutionary clustering,both the whole features and individual differences of data points are considered in the clustering framework of EGMM.It decreases the algorithm sensitivity to noises and increases the robustness of evaluated parameters.Experimental result shows that the clustering sequence really reflects the shift of data distribution,and the proposed algorithm can provide better clustering quality and temporal smoothness.     

基于证据理论聚类算法的故障诊断

为了正确高效地诊断故障,以并发故障为例,建立了基于证据理论聚类算法的诊断模型,提出了基于Dempster理论的聚类算法,该聚类算法既分析每个单类,还考虑单类的各种组合,并利用质心特性,将单类聚类原型推广为适合组合类特性的聚类原型。通过故障实例说明,本文模型既适合普通故障诊断,更适合并发故障诊断,且计算的时间复杂度较小。     

一种新的基于粒子群算法的聚类方法

建立了聚类分析问题的数学优化模型,提出了一种新的粒子群算法解决聚类问题。对基本粒子群优化算法作了改进,思路是将K-均值方法的结果作为一个粒子和利用新的分类中心调整粒子位置。对Iris植物样本数据的测试结果表明:4种粒子群算法的效果都比较好,特别是第3种改进的粒子群算法的效果更好,粒子群优化聚类技术很有潜力．     

关于哈密顿轨问题最小流模型的讨论

MasonIri论证了网络最小流问题可以在多项式时间内转换为哈密顿问题的模型与方法。本文利用一个反例指出了在该证明中使用的模型存在有不严格的地方。在此基础上,利用网络最小生成流的概念提出了一个修正模型,并证明了无环最小生成流问题可以在多项式时间内转换为哈密顿圈问题。文中最后指出,这一新的模型为解决在有向图内构造哈密顿轨的有效算法提供了一个新的思路和方法     

基于L1范数的k平面聚类算法设计

基于L2范数度量的k平面聚类(k-Plane Clustering,k PC)设计思想,本文提出了一种采用L1范数度量的聚类算法。由于在平面更新步骤中,所导出的优化问题是非凸的,文中给出了一种求解方法,即将非凸问题转化为有限个子集上的凸问题,为避免求解多个优化问题导致训练时间过长问题,本文还设计了一种新的优选策略,有限个子集的搜索任务可在线性时间内完成。本文所提出的方法只需要求解k个线性规划,而不再是k PC的求解特征值问题。在人工和UCI数据集上的实验结果表明:基于L1范数平面聚类算法的训练和测试时间更短,且在大多数数据集上均表现出了更好的聚类性能。     

举手表决法在基因分类中的应用

根据自然界中相互熟悉程度较高的是一类的特点,提出举手表决法。举手表决法需要的参数较少,且分类之前不需要定义类的个数。通过使用举手表决法进行基因分类时,得到较好的结果,从而反过来证明举手表决法在分类方面具有可行性。