一种带线性约束的最小生成树聚类方法

提出了一种带线性约束的最小生成树聚类方法,目标是聚合在空间上大致呈线性密集分布的对象.方法的基本过程是,用线性率阈值约束最小生成树打断边的选取,尽可能使每次打断都能割取出一个满足线性率大于该阈值的子树(类),直至所有合适子树都被割取,残余子树则被抛弃.对自构建数据和真实世界中地震数据的聚类实验证明了该方法的有效性和实用性.     

改进最小生成树的建筑模型数字化重构仿真

为了更加直观地表现建筑形态，提出基于最小生成树的建筑模型数字化重构方法。利用地球坐标系表示采集到的建筑信息，将射线向量引入到地球平面中，去除与平面没有关联的数据，降低数据维度；采用K-means算法确定聚类中心，以相似性为依据完成分类，提高数据的有序性；经过几何和投影变换，令重构后的模型满足人眼视觉需求；建立建筑布局图，确定节点和边集合，计算两个节点间的欧氏距离，对所有边赋予权重，权值最小的边即为最小生成树；将最小生成树的寻优过程转换为建筑模型重构过程，选用Kruskal搜索算法设置初始节点和初始边，设定迭代停止条件，确保建筑模型结构被完全搜索到，实现建筑模型数字化重构。仿真结果表明，所提方法能够提高建筑数据处理效率，重构后建筑模型与实际建筑物的相似度较高。     

一种基于图金字塔的聚类算法

传统的k-means方法和层次聚类算法,当数据集出现离群点或簇间存在交叠时会产生错误聚类结果。受小波多分辨率分析启发,提出一种基于图金字塔的聚类算法。首先输入数据集的类别数目K,并对数据点构建最小生成树;然后按节点的度数与最短邻边的长度计算优先级;接着,按优先级由高到低遍历最小生成树,进行节点间的合并;最后输出由合并节点构成的聚类结果。在人工合成和真实数据集上的实验结果表明,与k-means方法和层次聚类法相比,该方法的聚类结果不受离群点和簇间有交叠的影响,具有较高的稳定性。     

基于密度的最小生成树聚类算法研究

基于密度的方法是一种相当有效的聚类方法,能够发现任意形状的聚类,对噪声数据不敏感,但是聚类结果严重依赖于用户参数的合理选择。针对其存在的问题,将最小生成树理论与基于密度的方法相结合,提出了一种基于密度的最小生成树聚类算法。通过构造、分割最小生成树得到确定样本空间划分的最小生成子树;根据子树特性,产生局部密度参数;并对生成子树进行局部密度聚类。理论分析和应用结果表明。该算法不仅体现了基于密度聚类方法的优点,聚类结果不依赖于用户参数的选择,使数据聚类更合理,特别是对大型数据库非常有效;也体现了数据分区的思想,使其可以并行执行,进一步提高了信息处理的时空效率和性能。     

基于稀疏差异度的聚类方法在信息分类中的应用

针对文本信息聚类中的高属性维稀疏数据聚类问题，采用计算对象间稀疏特征差异度来度量文本对象之间的相关度，结合最小生成树的方法来进行聚类分析，提出一种基于稀疏特征差异度的聚类方法，通过实例表明，该算法对于多关键字匹配的文本信息分类十分有效，并可根据关键字的重要程度进行加权计算，使聚类更加符合实际情况。该算法将在高维稀疏数据挖掘中有着重要应用。     

基于网格最小生成树的聚类算法选择

为得到好的聚类效果,需要挑选适合数据集簇结构的聚类算法。文中提出基于网格最小生成树的聚类算法选择方法,为给定数据集自动选择适合的聚类算法。该方法首先在数据集上构建出网格最小生成树,由树的数目确定数据集的潜在簇结构,然后为数据集选择适合所发现簇结构的聚类算法。实验结果表明该方法较有效,能为给定数据集找出适合其潜在簇结构的聚类算法。     

基于高维空间稀疏最小生成树自适应覆盖模型的一类分类算法

最小生成树数据描述( MSTCD)在刻画高维空间样本点分布时,将所有图形的边作为新增虚拟样本以提供目标类样本分布描述,这种描述存在分支多、覆盖模型复杂的问题.针对该问题,依据特征空间中同类样本分布的连续性规律,文中提出基于稀疏最小生成树覆盖模型的一类分类算法.该方法首先构建目标类数据集的稀疏k近邻图表示,通过递归图分割...     

基于最小生成树的密度聚类算法研究

传统DBSCAN算法对密度分布不均匀的不平衡数据集的聚类效果并不理想,同时传统算法的聚类结果对邻域半径(Eps)以及核心点阈值(MinPts)敏感。针对以上问题,改进了传统算法,提出了一种基于最小生成树的密度聚类算法(MST-DBSCAN)。由于对象之间的距离对聚类结果影响较大,为了更好地表示对象之间的距离特性,首先使用相互可达距离(mutual reachability distance)代替传统算法中的欧氏距离,表示数据集中对象与对象之间的距离,解决因密度分布不均匀导致效果不佳的问题;为了建立对象与对象之间的联系,同时保留对象之间的距离特性,引用Prim算法对数据集中的所有对象构建最小生成树;其次根据指定的簇的数目及最小簇对象数数目参数对得到的最小生成树进行剪枝;根据剪枝的结果,将剪枝后的各个部分进行聚类。在公开的UCI数据集上的实验结果表明,提出的MST-DBSCAN算法与现有DBSCAN、OPTICS、KANN-DBSCAN算法相比,在密度分布不均匀的数据集上聚类效果有所提升并且较原有传统算法有较高的聚类准确性。     

基于最小生成树的不平衡数据集聚类算法

采用传统不平衡数据集聚类算法直接对数据集编码树进行构建，而未对数据集密度特征进行提取，造成传统算法数据聚类效果差，因此提出了基于最小生成树的不平衡数据集聚类算法。先利用数据区域密度的敏感性，提取数据密度特征，再利用提取的数据集密度特征构建编码树，并计算不平衡聚类状态下的数据集，最后基于最小生成树实现不平衡数据集聚类。设计对比实验，实验结果表明该研究算法聚类效果最好，具有研究价值。     

基于连通距离和连通强度的BIRCH改进算法

为解决利用层次方法的平衡迭代规约和聚类（BIRCH）算法聚类结果依赖于数据对象的添加顺序，且对非球状的簇聚类效果不好以及受簇直径阈值的限制每个簇只能包含数量相近的数据对象的问题，提出一种改进的BIRCH算法。该算法用描述数据对象个体间连通性的连通距离和连通强度阈值替代簇直径阈值，还将簇合并的步骤加入到聚类特征树的生成过程中。在自定义及iris、wine、pendigits数据集上的实验结果表明，该算法比多阈值BIRCH、密度改进BIRCH等现有改进算法的聚类准确率更高，尤其在大数据集上比密度改进BIRCH准确率提高6个百分点，耗时降低61%。说明该算法能够适用于在线实时增量数据，可以识别非球形簇和体积不均匀簇，具有去噪功能，且时间和空间复杂度明显降低。     

虚拟现实场景中基于八叉树的网格简化方法

在基于顶点聚类的网格简化算法中,通常对网格模型进行八叉剖分来建立一棵顶点树以表示整个网格模型的数据结构;但顶点在空间上分布的不均匀导致了顶点树的不平衡,增加了顶点树的深度。针对上述问题,论文提出了基于紧凑八叉树的剖分方法。该方法在虚拟现实场景中表现了较好的效果。     

基于成功回路的凹多面体的剖分算法

提出了一种对任意凹多面体不添加顶点的凸剖分方法,该算法首先把凹多面体抽象为无向图,无向图的顶点为多面体的顶点,边为多面体的棱和对角棱,权值为棱或对角棱的长度,然后根据普利姆算法构造最小生成树的思想来构造一个成功回路,利用该回路对多面体进行剖分。重复执行此过程,直到剖分后的所有多面体都是非凹的。该算法能够对多面体进行不添加顶点的剖分,同时可以对任意凹多面体多面体进行剖分,包括含有空洞的凹多面体。     

结合拓扑持续性和热扩散理论的3维模型分割

目的 针对已有的3维模型分割方法人为设定过多参数的问题,提出了一种基于拓扑持续性和热亲和度矩阵的3维模型分割方法,只需给定分割部件数即可自动完成分割。方法 首先通过拓扑持续性处理3维模型的热核签名,选取生存期最长的几个特征点作为模型被分割部件的显著特征点,对于模型躯干等无法通过生长周期选取特征点的部件,则选取热核签名的最小值所对应的顶点作为显著特征点,从而获得模型的初始聚类中心;然后使用不同的扩散时间所对应的热亲和度矩阵进行k-means聚类,并根据聚类中心的偏移距离等参数筛选聚类结果,从而获得3维模型的分割结果。结果 选取人体模型进行分割实验,并与其他方法进行对比分析。结果表明,所提出的热亲和度的计算时间明显优于常用的测地距离和幂指数核;相比基于拓扑持续性和基于测地距离的聚类,本文方法可以正确分割模型的各个部件并获得恰当的分割边界。此外,本文方法针对姿态不同的同一非刚体3维模型可以取得一致性的分割结果,而且对模型表面噪声具有较好的鲁棒性。结论 和已有方法相比,本文的基于拓扑持续性和热亲和度矩阵的3维模型分割方法可以在给定分割部件的前提下自动选定聚类中心并获得恰当的分割边界,并广泛适用于常见动物模型的分割。     

基于密度期望和有效性指标的尽均值算法

传统尽均值聚类算法虽然收敛速度快,但存在聚类数后无法预先确定,并且算法对初始中心点敏感的缺点。针对上述缺点,提出了基于密度期望和聚类有效性Silhouette指标的K-均值优化算法。给出了基于密度期望的初始中心点选取方案,将处于密度期望区间内相距最远的石个样本作为初始聚类中心。该方案可有效降低尽均值算法对初始中心点的依赖,从而获得较高的聚类质量。在此基础上,可进一步通过选择合适的聚类有效性指标Silhouette4指标分析不同后值下的每次聚类结果,确定最佳聚类数,则可有效改善k-值无法预先确定的缺点。实验及分析结果验证了所提出方案的可行性和有效性。     

基于宽度优先搜索的K-medoids聚类算法

针对传统K-medoids聚类算法对初始值敏感、中心点随机选择以及聚类精度不够高等缺点,在粒计算有效初始化的基础上,提出中心点宽度优先搜索策略. 首先,利用粒计算初始化获取K个有效粒子,遴选该K个粒子所对应的K个中心点作为K个初始中心点;然后,根据对象间的相似性分别对K个粒子中的对象建立以中心点为根节点的相似对象二叉树,通过宽度优先搜索遍历二叉树迭代出最优中心点, 同时采用簇间距离和簇内距离优化准则函数. 实验结果表明,所提算法在UCI中Iris和Wine标准数据集中测试,在有效缩短迭代次数的同时保证了算法聚类准确率.     

Multi-scale Clustering Analysis on Chinese Urbans based on Nighttime Light Image

Understanding spatial distribution of urban clusters at regional and national scales is increasingly important for many fields especially urban planning.Previous Studies have demonstrated urban built\|up areas can be derived from stable nighttime light satellite (DMSP\|OLS) images.Population and economic variables (i.e.GDP) have been proved significant positive correlations with nocturnal light brightness.However,less studies focused on the spatial distribution of extracted urban built\|up area.an improved DBSCAN algorithm is proposed to cluster the urban objects extracted from nighttime light image in different scales based on density,of which our urban spatial clusters are proved corresponding with urban agglomerations identified by statistical data.The traditional DBSCAN method is based on points which is not the same case with urban objects.The inclusion relation is refined,assuming that only if all the vertexes of each polygon are within the given distance,it is included in the area.Moreover,the parameters for the DBSCAN clustering model are determined by valleys of distances of every objects to classify urban spatial clusters.Besides,in a larger scale,the clustering results imply the different patterns of urban agglomerations on both sides of the Huhuanyong Line.      

基于粒计算的粗糙集聚类算法

针对传统K-means聚类算法初始聚类中心随机选取、不能处理边界对象、效率低、聚类精度低等问题, 提出了一种新的K-means聚类算法。算法引入粒计算理论, 并依据密度和最大最小距离法选择初始聚类中心, 避免初始聚类中心在同一个类中, 结合粗糙集, 通过动态调整上近似集和边界集的权重因子, 以解决边界数据的聚类问题; 最后采用类间距和类内距均衡化准则函数作为算法终止判断条件, 来得到更好的聚类效果。实验结果表明：该算法具有较高的准确率, 迭代次数较少, 并降低了对噪声的敏感程度。     

半直觉模糊图与应用

将对象作顶点集,用直觉模糊数刻画对象间的相关性和不相关性表示成直觉模糊边;建立了半直觉模糊图模型。定义了半直觉模糊图的生成子图、度、路径、相关截图、序关系、最大生成树等概念。给出基于半直觉模糊图的聚类分析算法,分析了算法的复杂度。结合经典实例作了基于半直觉模糊图的聚类分析,结果显示基于半直觉模糊图的聚类分析算法复杂度低于一般直觉模糊聚类算法。高效实用且自动化程度高。     

最小顶点覆盖快速降阶算法

通过定义判别函数来判别顶点覆盖作用的优劣,得出一个把顶点加入到最小顶点覆盖集的一般化规则,并得出该规则在多种具体情况下的应用定理,在此基础上给出了一个快速降阶算法,该算法能确定某些顶点应该在最小顶点覆盖中,某些顶点不应该在最小顶点覆盖中,达到降低原问题的规模和求解难度的目的.该算法既可以单独使用,又可以与算法结合来达到更好的结果,文中还给出了应用实例及其分析.