无参数聚类边界检测算法的研究

为自动快速地提取聚类的边界点,减少输入参数对边界检测结果的影响,提出一种无参数聚类边界检测算法。该算法不需要任何参数,在生成的三角剖分图上计算每个数据点的边界度,用k-means自动计算边界度阈值,按边界度阈值将数据集划分为候选边界点和非候选边界点两部分,根据噪声点在三角剖分图中的性质去除候选边界点中的噪声点,最终检测出边界点。实验结果表明,该算法能快速、有效地识别任意形状、不同大小和密度聚类的边界点。     

一种高效的基于联合熵的边界点检测算法

为了快速有效地检测出聚类的边界点,提出一种将网格技术与联合熵相结合的边界点检测算法.该算法中网格技术用于快速查找数据集中聚类边界所在的网格范围,联合熵用于在边界落入的网格范围内准确识别聚类的边界点.实验结果表明.该算法能够在含有噪声点,孤立点的数据集上,有效地检测出聚类的边界,运行效率高.     

基于变异系数的边界点检测算法

为有效检测聚类的边界点,提出基于变异系数的边界点检测算法.首先计算出数据对象到它的k-距离邻居距离之和的平均值.然后用平均值的倒数作为每个点的密度,通过变异系数刻画数据对象密度分布特征寻找边界点.实验结果表明,该算法可在含有任意形状、不同大小和不同密度的数据集上快速有效检测出聚类的边界点,并可消除噪声.     

基于网格熵的边界点检测算法

为了快速有效地检测聚类的边界点,提出了网格熵的概念和基于网格熵的边界点检测算法Greb。该算法利用网格熵的大小来判定聚类的边界点,且只对数据集进行两遍扫描。实验结果表明,对含有任意形状、不同大小以及不同密度且带有噪声的数据集,该算法能快速有效地检测出聚类的边界点。     

基于引力的边界点检测算法

为有效地检测噪声数据集上聚类的边界点,提出一种新的边界模式检测算法Green(Gravity-Based Boundary Points Detecting Algorithm),该算法将数据集中的对象看成是空间中带质量的点,利用牛顿力学对对象进行受力分析并计算每个点的边界因子,根据边界点具有较大的边界因子这一事实提取出边界点.实验结果表明:Green能在含有不同形状、大小簇的噪声数据集上有效地检测出聚类的边界点,执行效率高.     

一种基于网格核密度的自适应边界点检测算法

为了快速有效的检测聚类的边界点,提出基于网格核密度的自适应边界点检测算法ADAPT(An Adaptive Grid Kernel-Density-Based BoundaryPoints Detecting Algorithm for Spatial Database with Noise),使用网格核密度更精确地拟合网格在其邻域内的密度,采用自适应选取网格近邻策略更好地反应对象的空间分布特征.实验结果表明:该算法可以在含有任意形状、不同大小和不同密度的数据集上快速有效地检测出聚类的边界点.     

基于统计信息的聚类边界模式检测算法

为有效地检测聚类的边界点,提出基于统计信息的边界模式检测算法。根据数据对象的k距离统计信息设定邻域半径,再利用对象邻域范围内邻居的k距离统计信息寻找边界点。实验结果表明,该算法可以有效地检测出任意形状、不同大小和不同密度聚类的边界点,并可以消除噪声。     

基于相对密度的孤立点和边界点识别算法

根据孤立点是数据集合中与大多数数据的属性不一致的数据,边界点是位于不同密度数据区域边缘的数据对象,提出了基于相对密度的孤立点和边界点识别算法(OBRD)。该算法判断一个数据点是否为边界点或孤立点的方法是:将以该数据点为中心、r为半径的邻域按维平分为2个半邻域,由这些半邻域与原邻域的相对密度确定该数据点的孤立度和边界度,再结合阈值作出判断。实验结果表明,该算法能精准有效地对多密度数据集的孤立点和聚类边界点进行识别。     

基于二路生成树的聚类边界检测算法

聚类的边界是一种有用的模式,为有效地提取聚类的边界点,提出c-层近邻概念,将c-层近邻应用于二路生成树,能快速计算出每个对象的反向近邻值,从而根据反向近邻值提取聚类的边界。提出的基于二路生成树的边界检测算法(DBMST)在综合数据集和真实数据集的实验结果表明,该算法在含有噪声/孤立点的数据集上,能够快速有效地识别出聚类的边界。     

噪声数据集上的边界点检测算法

为了有效检测聚类的边界点,提出了结合对象的密度及其Eps-邻域中数据的分布特点进行的边界点检测技术和边界点检测算法 ——BOUND。实验结果表明,BOUND能在含有不同形状、大小簇的噪声数据集上有效地检测出聚类的边界点,并且执行效率高。     

Model-based evaluation of clustering validation measures

A cluster operator takes a set of data points and partitions the points into clusters (subsets). As with any scientific model, the scientific content of a cluster operator lies in its ability to predict results. This ability is measured by its error rate relative to cluster formation. To estimate the error of a cluster operator, a sample of point sets is generated, the algorithm is applied to each point set and the clusters evaluated relative to the known partition according to the distributions, and then the errors are averaged over the point sets composing the sample. Many validity measures have been proposed for evaluating clustering results based on a single realization of the random-point-set process. In this paper we consider a number of proposed validity measures and we examine how well they correlate with error rates across a number of clustering algorithms and random-point-set models. Validity measures fall broadly into three classes: internal validation is based on calculating properties of the resulting clusters; relative validation is based on comparisons of partitions generated by the same algorithm with different parameters or different subsets of the data; and external validation compares the partition generated by the clustering algorithm and a given partition of the data. To quantify the degree of similarity between the validation indices and the clustering errors, we use Kendall's rank correlation between their values. Our results indicate that, overall, the performance of validity indices is highly variable. For complex models or when a clustering algorithm yields complex clusters, both the internal and relative indices fail to predict the error of the algorithm. Some external indices appear to perform well, whereas others do not. We conclude that one should not put much faith in a validity score unless there is evidence, either in terms of sufficient data for model estimation or prior model knowledge, that a validity measure is well-correlated to the error rate of the clustering algorithm.     

A clustering algorithm with affine space-based boundary detection

Clustering is an important technique in data mining. The innovative algorithm proposed in this paper obtains clusters by first identifying boundary points as opposed to existing methods that calculate core cluster points before expanding to the boundary points. To achieve this, an affine space-based boundary detection algorithm was employed to divide data points into cluster boundary and internal points. A connection matrix was then formed by establishing neighbor relationships between internal and boundary points to perform clustering. Our clustering algorithm with an affine space-based boundary detection algorithm accurately detected clusters in datasets with different densities, shapes, and sizes. The algorithm excelled at dealing with high-dimensional datasets.     

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

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

考虑边界样本邻域归属信息的粗糙K-means增量聚类算法

在原有数据聚类结果的基础上,如何对新增数据进行归属度量分析是提高增量式聚类质量的关键,现有增量式聚类算法更多地是考虑新增数据的位置分布,忽略其邻域数据点的归属信息.在粗糙K-means聚类算法的基础上,针对边界区域新增数据点的不确定性信息处理,提出一种基于邻域归属信息的粗糙K-means增量式聚类算法.该算法综合考虑边界区域新增数据样本的位置分布及其邻域数据点的类簇归属信息,使得新增数据点与各类簇的归属度量更为合理;此外,在增量式聚类过程中,根据新增数据点所导致的类簇结构的变化,对类簇进行相应的合并或分裂操作,使类簇划分可以自适应调整.在人工数据集和UCI标准数据集上的对比实验结果验证了算法的有效性.     

基于改进边界距离变换的路径提取算法研究*

针对虚拟内窥镜中心路径提取算法时间效率不高的问题,通过改进边界距离变换,提出了中心路径的快速提取算法。首先建立最小距离场,在边界内推过程,仅扫描并处理与边界点面连接的点并对其设标记属性,每次向里剥离一层体素标记属性随之增加,直到对内部点集都置到边界的最小边界距离值（DFB）;然后找到DFB值不小于其所有面邻接点DFB值的体素点,即3D局部最大值;最后用最短路径相连3D局部最大值,形成中心线。实验结果表明,改进的中心路径提取算法的时间效率较传统距离变换算法有很大提高。     

改进的蚂蚁聚类算法*

提出了一种改进的基于对称点距离的蚂蚁聚类算法。该算法不再采用Euclidean距离来计算类内对象的相似性,而是使用新的对称点距离来计算相似性,在处理带有对称性质的数据集时,可以有效地识别给定数据集的聚类数目和合适的划分。在该算法中,用人工蚂蚁代表数据对象,根据算法给定的聚类规则来寻找最合适的聚类划分。最后用本算法与标准的蚂蚁聚类算法分别对不同的数据集进行了聚类实验。实验结果证实了算法的有效性。     

基于非参数核密度估计的密度峰值聚类算法*

针对密度峰值聚类算法CFSFDP(Clustering by fast search and find of density peaks)计算密度时人为判断截断距离和人工截取簇类中心的缺陷,提出了一种基于非参数核密度估计的密度峰值的聚类算法。首先,应用非参数核密度估计方法计算数据点的局部密度;其次,根据排序图采用簇中心点自动选择策略确定潜在簇类中心点,将其余数据点归并到相应的簇类中心;最后,依据簇类间的合并准则,对邻近相似子簇进行合并,并根据边界密度识别噪声点,得到聚类结果。在人工测试数据集和UCI真实数据集上的实验表明,新算法较之原CFSFDP算法,不仅有效避免了人为判断截断距离和截取簇类中心的主观因素,而且可以取得更高的准确度。     

点云的形状与曲线重建算法

针对平面无序带噪点云的曲线重建问题,给出了点云形状的定义并提出了构造点云形状的算法.该算法基于Delaunay三角剖分,在构造好点云的Delaunay三角剖分后对三角剖分进行细化,使得在点云中的点周围形成空间上的局部均匀采样;基于集合论中的基本概念定义点云中内点、外点和边界点,并且明确地定义了点云的形状,根据Delaunay三角剖分细化时,选择不同的参数得到不同层次的点云的形状;选择合适的参数得到相应形状后,通过薄化过程得到具有流形结构的曲线.实验结果表明,采用文中算法得到的重建曲线很好地反映了点云的形状,验证了该算法的有效性.     

基于K近邻和优化分配策略的密度峰值聚类算法

密度峰值聚类(density peak clustering, DPC)是一种简单有效的聚类分析方法.但在实际应用中,对于簇间密度差别大或者簇中存在多密度峰的数据集,DPC很难选择正确的簇中心;同时,DPC中点的分配方法存在多米诺骨牌效应.针对这些问题,提出一种基于K近邻(K-nearest neighbors,KNN)和优化分配策略的密度峰值聚类算法.首先,基于KNN、点的局部密度和边界点确定候选簇中心;定义路径距离以反映候选簇中心之间的相似度,基于路径距离提出密度因子和距离因子来量化候选簇中心作为簇中心的可能性,确定簇中心.然后,为了提升点的分配的准确性,依据共享近邻、高密度最近邻、密度差值和KNN之间距离构建相似度,并给出邻域、相似集和相似域等概念,以协助点的分配;根据相似域和边界点确定初始聚类结果,并基于簇中心获得中间聚类结果.最后,依据中间聚类结果和相似集,从簇中心到簇边界将簇划分为多层,分别设计点的分配策略;对于具体层次中的点,基于相似域和积极域提出积极值以确定点的分配顺序,将点分配给其积极域中占主导地位的簇,获得最终聚类结果.在11个合成数据集和27个真实数据集上进行仿真...