基于人工蜂群的三支k-means聚类算法

聚类在数据挖掘技术中起着至关重要的作用。传统的聚类算法都是硬聚类算法,即对象要么属于一个类,要么不属于一个类,在处理不确定数据时,强制划分会带来决策错误。三支k-means聚类算法可以对边界不确定数据进行更加合理的分类,但仍然存在对初始聚类中心敏感的问题。为解决这一问题,将人工蜂群算法与三支k-means聚类算法相结合,提出了一种基于人工蜂群的三支k-means聚类算法。通过定义类内聚集度函数和类间离散度函数来构造蜜源的适应度函数,引导蜂群向高质量的蜜源进行全局搜索。利用蜂群之间不同角色的相互协作与互换,对数据集进行多次迭代聚类,找到最优的蜜源位置,作为初始聚类中心,并在此基础上交替迭代聚类。实验证明,该方法对聚类结果的性能指标有所提高。在UCI数据集上的实验验证了该算法的有效性。     

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

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

基于ε邻域的三支决策聚类分析

传统的聚类方法大都是二支决策，即决策一个元素属于一个类或者不属于一个类。然而在处理不确定性信息时，强制将其中的元素划分到一个类中，往往容易带来较高的决策风险。三支决策聚类将确定的元素放入核心域中，将不确定的元素放入边界域中延迟决策，可以有效地降低决策风险。利用数学形态学中膨胀与腐蚀的思想，提出了一种使用样本的[ε]邻域将二支聚类转化为三支聚类的方法。该方法在二支聚类的结果上，利用每个类中元素的[ε]邻域收缩得到核心域，扩张得到边界域。在UCI数据集上的实验结果显示该方法可以降低聚类结果的DBI，提高聚类结果的平均轮廓系数和准确率。     

基于局部半径的三支DBSCAN算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种经典的基于密度的聚类算法，它通过两个全局参数即半径Eps和最少点数MinPts,能够对任意形状的数据进行聚类，并自动确定类个数。但是，使用全局半径的DBSCAN对于密度不均匀数据集的聚类效果较差，且无法对重叠数据集进行聚类。因此，定义了密度递减原则和局部半径，并根据k-近邻距离自动确定局部半径，从而提出了基于局部半径的DBSCAN算法(LE-DBSCAN);然后，通过考虑近邻的标签，对二支聚类结果的临界点和噪声点进行重新划分，从而提出了基于局部半径的三支DBSCAN算法(LE3W-DBSCAN)。将LE-DBSCAN和LE3W-DBSCAN与该领域的相关算法在UCI数据集和人工数据集上进行对比，实验结果表明，所提算法在常用的硬聚类指标和软聚类指标上都具有较好的表现。     

自动确定聚类中心的数据竞争算法

针对数据竞争算法采用欧式距离计算相似度、人为指定聚类簇数以及聚类中心无法准确自动确定等问题,提出了一种自动确定聚类中心的数据竞争聚类算法。引入了数据场的概念,使得计算出的势值更加符合数据集的真实分布;同时,结合数据点的势能与局部最小距离形成决策图完成聚类中心点的自动确定;根据近邻原则完成聚类。在人工以及真实数据集上的实验效果表明,提出的算法较原数据竞争算法具有更好的聚类性能。     

粗糙的方向性模糊聚类算法

根据高维数据具有方向性的特征,结合概率模糊聚类算法与粗糙集理论提出了一种粗糙的方向性模糊聚类算法。该算法在概率模糊聚类算法中引入了数据方向相似性函数,能对不确定数据进行处理。在算法中利用粗糙集中的下近似集与边界集来确定目标对象函数,属于下近似集的数据在聚类时是确定的,属于边界的数据具有模糊性。实验结果表明,该算法能有效地对高维的方向性数据进行聚类。     

基于q近邻的不完备数据三支决策聚类方法

聚类是数据挖掘的重要技术之一,在许多实际应用领域,由于数据获取限制,数据误读,随机噪音等原因会造成大量的缺失数据,形成数据集的不完备性,而传统的聚类方法无法直接对这类数据集进行聚类分析。针对数值型数据,提出了一个基于三支决策的不完备数据聚类方法。首先找到不完备数据对象的q个近邻,使用q个近邻的平均值填充缺失的数据;然后在"完备的"数据集上使用基于密度峰值的聚类方法得到簇划分,对每个簇中含有不确定性的数据对象,使用三支决策的思想将其划分到边界域中。三支决策聚类结果采用区间集形式表示,通常一个簇被划分成正域、负域和边界域部分,可以更好地描述软聚类结果。在UCI数据集和人工数据集上的实验结果展示了算法的有效性。     

多层自动确定类别的谱聚类算法

自动确定聚类数和海量数据的处理是谱聚类的关键问题。在自动确定聚类数谱聚类算法的基础上,提出了一种能处理大规模数据集的多层算法。该算法的核心思想是把大规模数据集根据一定的相关性逐级进行合并,使之成为小数据集,再对分组后的小数据集用自动确定类别的谱聚类算法聚类,最后逐层进行拆分并微调, 完成全部数据的聚类。实验证明该算法的聚类效果很好。     

自动确定聚类中心的密度峰值算法

密度峰值聚类算法（Density Peaks Clustering,DPC）,是一种基于密度的聚类算法,该算法具有不需要指定聚类参数,能够发现非球状簇等优点。针对密度峰值算法凭借经验计算截断距离[dc]无法有效应对各个场景并且密度峰值算法人工选取聚类中心的方式难以准确获取实际聚类中心的缺陷,提出了一种基于基尼指数的自适应截断距离和自动获取聚类中心的方法,可以有效解决传统的DPC算法无法处理复杂数据集的缺点。该算法首先通过基尼指数自适应截断距离[dc],然后计算各点的簇中心权值,再用斜率的变化找出临界点,这一策略有效避免了通过决策图人工选取聚类中心所带来的误差。实验表明,新算法不仅能够自动确定聚类中心,而且比原算法准确率更高。     

基于Seeds集和成对约束的半监督三支聚类集成

聚类集成使用合适的策略融合多个具有差异性的基聚类成员,能够有效提高聚类结果的稳定性、鲁棒性和准确率。当前聚类集成的研究较少利用已知的先验信息,面对复杂数据时难以刻画对象与类簇之间明确的归属关系。因此,提出一种基于Seeds集和成对约束的半监督三支聚类集成方法。首先,基于已有的标签信息提出一种新的三支标签传播算法构造基聚类成员;其次,提出一种半监督三支聚类集成框架集成基聚类成员,构造出一致性相似矩阵,并利用成对约束信息对该矩阵进行优化调整;最后,将三支谱聚类作为一致性函数对相似矩阵进行聚类,得到最终集成结果。在多个UCI真实数据集上的实验结果表明,与基于类簇的相似分区算法（CSPA）、超图分区算法（HGPA）、元类簇算法（MCLA）、标签传播算法（LPA）、Cop-Kmeans等半监督聚类集成算法相比,所提方法的归一化互信息（NMI）、调整兰德系数（ARI）和F测度在绝大多数据集上取得了最优值,获得了相对更好的聚类集成结果。     

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

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

基于数据约减的聚类有效性分析

聚类分析中利用有效性指标判断数据集的正确类数极易受到噪声数据、类之间分离性以及聚类算法的影响,所确定类数的正确性难以得到保证.为克服这个问题,以文献[1]中的数据约减方法为基础,对原数据集和约减后的数据集利用有效性指标进行正确类数判别.实验表明:该方法能增大类之间的分离性,有效判断数据集的最优类数.     

基于隶属比的聚类有效性指标

针对模糊聚类需要预知最佳聚类个数的问题,提出了一种新的基于隶属比的聚类有效性指标V_new,首先根据经典有效性指标的设计思路,充分考虑数据集合的隶属度矩阵特征和几何空间分布,通过重新定义类内距和类间距的方式,推导出基本的有效性指标;其次,定义隶属比的概念,放大基本有效性指标的计算值;最后,为了避免隶属比对有效性指标造成过分影响而失去意义,引入分类个数进行抑制. 理论分析和仿真实验表明,通过对相同数据集进行分析处理,与经典的XB指标相比V_xb,新指标V_new具有更高的准确率和可靠性,在类间有重叠数据的情况下也能够做出正确的划分,具有一定的推广价值.     

Interval set clustering

Rough k-means clustering describes uncertainty by assigning some objects to more than one cluster. Rough cluster quality index based on decision theory is applicable to the evaluation of rough clustering. In this paper we analyze rough k-means clustering with respect to the selection of the threshold, the value of risk for assigning an object and uncertainty of objects. According to the analysis, clusters presented as interval sets with lower and upper approximations in rough k-means clustering are not adequate to describe clusters. This paper proposes an interval set clustering based on decision theory. Lower and upper approximations in the proposed algorithm are hierarchical and constructed as outer-level approximations and inner-level ones. Uncertainty of objects in out-level upper approximation is described by the assignment of objects among different clusters. Accordingly, ambiguity of objects in inner-level upper approximation is represented by local uniform factors of objects. In addition, interval set clustering can be improved to obtain a satisfactory clustering result with the optimal number of clusters, as well as optimal values of parameters, by taking advantage of the usefulness of rough cluster quality index in the evaluation of clustering. The experimental results on synthetic and standard data demonstrate how to construct clusters with satisfactory lower and upper approximations in the proposed algorithm. The experiments with a promotional campaign for the retail data illustrates the usefulness of interval set clustering for improving rough k-means clustering results.     

面向聚类集成的基聚类三支筛选方法

当前聚类集成的研究主要是围绕着集成策略的优化展开,而针对基聚类质量的度量及优化却较少研究。基于信息熵理论提出了一种基聚类的质量度量指标,并结合三支决策思想构造了面向基聚类的三支筛选方法。首先预设基聚类筛选三支决策的阈值α、β,然后计算各基聚类中类簇质量的平均值,并把其作为各基聚类的质量度量指标,最后实施三支决策。决策策略为：当某个基聚类的质量度量指标小于阈值β时,删除该基聚类;当某个基聚类的质量度量指标大于等于阈值α时,保留该基聚类;当某个基聚类的质量度量指标大于等于β小于α时,重新计算该基聚类质量,并且再次实施上述三支决策直至没有基聚类被删除或达到指定迭代次数。对比实验结果表明,基聚类三支筛选方法能够有效提升聚类集成效果。     

一种改进的粗k 均值聚类算法

Lingras提出的粗K均值聚类算法易受随机初始聚类中心和离群点的影响,可能出现一致性和无法收敛的聚类结果.对此,提出一种改进的粗K均值算法,选择潜能最大的K个对象作为初始的聚类中心,根据数据对象与聚类中心的相对距离来确定其上下近似归属,使边界区域的划分更合理.定义了广义分类正确率,该指标同时考虑了下近似集和边界区域中的对象,评价算法性能更准确.仿真实验结果表明,该算法分类正确率高,收敛速度快,能够克服离群点的不利影响.     

Algorithms for additive clustering of rectangular data tables

The overlapping additive clustering model or principal cluster model is a model for two-way two-mode object by variable data that implies an overlapping clustering of the objects and a set of profiles (characteristic variable values for each cluster). The model values of the variables of an object are the sum of the profiles of its corresponding clusters. In the associated data analysis the data matrix at hand is approximated by an overlapping additive clustering model of a prespecified rank by minimizing a least squares loss function. Recently an algorithm has been proposed for this purpose. This algorithm is a sequential fitting strategy, also called the method of principal clusters (PCL). Theoretical and empirical evidence that the PCL algorithm may have problems in revealing the true structure underlying a data set will be presented. As a way out, three new algorithms to fit the principal cluster model to empirical data will be presented: two of an alternating least squares (ALS) type, orthogonally combined with two different starting strategies, and one based on simulated annealing (SA). In a simulation study it is demonstrated that all three new algorithms outperform the existing PCL algorithm. The amount of objects that belong to more than one cluster (the overlap) is further found to have a considerable influence on the algorithmic performance of the ALS algorithms, with low amounts of overlap requiring a different starting strategy than high ones. As a consequence, for the analysis of real data sets in practice, a hybrid approach will be presented consisting of one of the ALS algorithms initialized by means of the two starting strategies under study.     

基于区间阴影集的密度峰值聚类算法

为了减小模糊集及其诱导的经典阴影集之间存在的较大的不确定性差异,文中基于模糊熵提出阴影集模型——区间阴影集.由此提出基于区间阴影集的密度峰值聚类算法,优化经典密度峰值聚类算法的噪声检测策略.改进算法在原二支聚类结果的基础上摒弃原有检测策略,引入区间阴影集模型,并转化为三支聚类结果,达到噪声检测的目的.在经典人工数据集、UCI数据集上的对比实验表明,文中算法能将数据集中对象更合理地分配到相应类簇,对噪声数据具有良好的鲁棒性.