一种高维混合属性数据聚类算法

在许多应用中,很多数据集都具有数值型和分类型数据的混合特征,k-prototype是针对这类数据聚类的经典方法之一,该方法是一种基于k-means和k-mode的聚类方法。在研究了现有的混合属性数据聚类方法之后,引入了一种新算法用于混合型数据聚类,不仅改进了prototype的选取方法,而且提出了一种新的针对混合型数据的相似度度量方式,基于此又提出了一种不同于k-prototype的数据到prototype的分配方式,采用类似层次聚类中凝聚聚类的思想进行聚类,通过在四个真实的混合型数据集上测试发现：与传统算法相比,算法提高了聚类的精度和稳定性。     

基于粗糙集的混合属性数据聚类算法

传统聚类方法将对象严格地划分到某一类,但是很多时候边界对象不能被严格地划分。基于粗糙集的k-means聚类算法和基于粗糙集的leader聚类算法,利用粗糙集理论将数据对象划分到一个簇的上近似集或下近似集当中,提供了一种新的处理不确定性的视角,很好地解决了这种边界不确定问题。但其缺点是不能处理混合属性数据,聚类结果对初值有明显的依赖性。针对这些算法存在的不足,给出了一种适用于混合属性数据的距离定义,对初始值的选取提出了改进办法,提出了一种基于粗糙集的混合属性数据聚类算法。仿真实验证明,在不确定聚类簇数的情况下,该算法的聚类准确率比传统k-means算法明显提高。     

基于密度的聚类中心自动确定的混合属性数据聚类算法研究

面对广泛存在的混合属性数据,现有大部分混合属性聚类算法普遍存在聚类 质量低、聚类算法参数依赖性大、聚类类别个数和聚类中心无法准确自动确定等问题,针对 这些问题本文提出了一种基于密度的聚类中心自动确定的混合属性数据 聚类算法.该算法通过分析混合属性数据特征,将混合属性数据分为数 值占优、分类占优和均衡型混合属性数据三类,分析不同情况的特征选取 相应的距离度量方式.在计算数据集各个点的密度和距离分布图基础 上,深入分析获得规律: 高密度且与比它更高密度的数据点有较大距离的数 据点最可能成为聚类中心,通过线性回归模型和残差分析确定奇异 点,理论论证这些奇异点即为聚类中心,从而实现了自动确定聚类中心.采 用粒子群算法(Particle swarm optimization, PSO)寻找最优dc值,通过参数dc能够计算得到 任意数据对象的密度和到比它密度更高的点的最小距离,根据聚类 中心自动确定方法确定每个簇中心,并将其他点按到最近邻的更高 密度对象的最小距离划分到相应的簇中,从而实现聚类.最终将本文 提出算法与其他现有的多种混合属性聚类算法在多个数据集上进行 算法性能比较,验证本文提出算法具有较高的聚类质量.     

混合属性数据k-prototypes聚类算法

在现实世界中经常遇到混合数值属性和分类属性的数据, k-prototypes是聚类该类型数据的主要算法之一。针对现有混合属性聚类算法的不足,提出一种基于分布式质心和新差异测度的改进的 k-prototypes 算法。在新算法中,首先引入分布式质心来表示簇中的分类属性的簇中心,然后结合均值和分布式质心来表示混合属性的簇中心,并提出一种新的差异测度来计算数据对象与簇中心的距离,新差异测度考虑了不同属性在聚类过程中的重要性。在三个真实数据集上的仿真实验表明,与传统的聚类算法相比,本文算法的聚类精度要优于传统的聚类算法,从而验证了本文算法的有效性。     

对类属性和混合属性数据聚类的一种有效的算法

聚类算法是数据挖掘中的重要方法,针对现有适用类属性和混合型属性的数据集聚类算法如k-modes算法、k-prototypes算法和模糊k-prototypes算法等的不足,提出一种新的方法——类属性分解法。这种方法有更高的稳定性和可靠性,并能有效地减少随机性。     

BIRCH混合属性数据聚类方法

数据聚类是数据挖掘中的重要研究内容。现实世界中的数据往往同时具有连续属性和离散属性,但现有大多数算法局限于仅处理其中一种属性,而对另一种采取简单舍弃的办法丢失聚类信息和降低聚类质量。一些能处理混合属性的算法又往往处理的属性过多,导致计算量的大增。提出了一种基于BIRCH算法的混合属性数据的聚类算法;在UCI数据集上的实验表明,文中提出的算法具有较好的性能。     

一种基于图划分的混合属性数据聚类算法

实际应用中存在着大量同时具有数值型和符号型属性的混合属性数据,研究混合属性数据的聚类具有重要意义。经典聚类算法仅仅处理数值型数据或符号型属性数据,对混合属性数据往往无效。现有混合属性数据聚类算法分别将数值型属性和符号型属性数据单独计算,忽视了两种属性之间的相关性,聚类效果不理想。提出一种基于图划分的混合属性数据聚类算法。算法将一行属性值定义为一个图节点,计算图节点的相似性,采用一种自适应调节属性权重的方法,将数值和符号属性的相似性统一成一个互联合相似度矩阵。用图划分方法对数据进行聚类划分,通过迭代寻优的方法调整数据之间的契合度,从而求得类内相似度最大并寻得最优解。实验结果表明,混合属性聚类算法与其他方法相比具有明显的优势。     

一种改进的混合属性数据聚类算法

K-prototypes算法是处理混合属性数据的主要聚类算法,但是存在对初值敏感、参数依赖和易受噪声干扰等问题。为了克服以上缺点,该文对K-prototypes算法的初始中心点选择进行了研究与分析,提出了一种基于近邻法的初始中心点选择策略对算法进行改进,算法先利用近邻法获得初始中心点集和k值,然后进行K-prototypes运算,最后加入识别异常数据点的规则。改进后的算法成功解决了传统K-prototypes算法的缺陷,而且具有更好的分类精度和稳定性。经实验证明,改进算法是正确和有效的,明显优于传统的K-prototypes算法。     

混合属性数据集的基于近邻连接的两阶段聚类算法

面对混合属性数据集的数据预处理需求,本文在给出若干定义及相关性质之后,提出了一种基于近邻连接的两阶段聚类算法。为提高算法的时间效率,给出了算法改进的思路与技术。多个人工数据集和UCI标准数据集的仿真实验结果表明,对于一些具有明显聚类分布结构的数据集,该算法经常能取得比k-means算法和AP算法更好的聚类精度,说明它具有一定的有效性。为进一步推广并在实际中发掘出该算法的应用价值,最后给出了几点研究展望。     

混合属性数据集的聚类边界检测技术

为了满足数据分析中获取含有混合属性的数据集聚类的边界需求, 提出一种混合属性数据集的聚类边界检测算法(BERGE). 该算法利用模糊聚类隶属度定义边界因子以识别候选边界集, 然后运用证据积累的思想提取聚类的边界. 在综合数据集和真实数据集上的实验结果表明, BERGE 算法能有效地检测混合属性数据集、数值属性数据集以及分类属性数据集的聚类边界, 与现有同类算法相比具有更高的精度.     

类属数据的贝叶斯聚类算法

针对类属型数据聚类中对象间距离函数定义的困难问题,提出一种基于贝叶斯概率估计的类属数据聚类算法。首先,提出一种属性加权的概率模型,在这个模型中每个类属属性被赋予一个反映其重要性的权重;其次,经过贝叶斯公式的变换,定义了基于最大似然估计的聚类优化目标函数,并提出了一种基于划分的聚类算法,该算法不再依赖于对象间的距离,而是根据对象与数据集划分间的加权似然进行聚类;第三,推导了计算属性权重的表达式,得出了类属型属性权重与其符号分布的信息熵成反比的结论。在实际数据和合成数据集上进行了实验,结果表明,与基于距离的现有聚类算法相比,所提算法提高了聚类精度,特别是在生物信息学数据上取得了5%~48%的提升幅度,并可以获得有实际意义的属性加权结果。     

A novel attribute weighting algorithm for clustering high-dimensional categorical data

Due to data sparseness and attribute redundancy in high-dimensional data, clusters of objects often exist in subspaces rather than in the entire space. To effectively address this issue, this paper presents a new optimization algorithm for clustering high-dimensional categorical data, which is an extension of the k-modes clustering algorithm. In the proposed algorithm, a novel weighting technique for categorical data is developed to calculate two weights for each attribute (or dimension) in each cluster and use the weight values to identify the subsets of important attributes that categorize different clusters. The convergence of the algorithm under an optimization framework is proved. The performance and scalability of the algorithm is evaluated experimentally on both synthetic and real data sets. The experimental studies show that the proposed algorithm is effective in clustering categorical data sets and also scalable to large data sets owning to its linear time complexity with respect to the number of data objects, attributes or clusters.     

一种面向分类属性数据的聚类融合算法研究*

为了解决单一聚类算法存在结果不准确和随机性大,且现有算法对分类数据聚类时将其装换成数值型会产生误差等问题,提出了一种面向分类属性数据的聚类融合算法。算法利用原有分类属性值的差异产生聚类成员,然后采用相似度方法进行划分,通过寻求目标函数最小的划分来简化聚类过程。算法在UCI数据集上进行了验证,结果表明算法的效率和精度都优于现有算法,说明算法的设计和更新策略是有效的。     

Squeezer: An efficient algorithm for clustering categorical data

This paper presents a new efficient algorithm for clustering categorical data,Squeezer,which can produce high quality clustering results and at the same time deserve good scalability.The Squeezer algorithm reads each tuple t in sequence,either assigning t to an existing cluster (initially none),or creating t as a new cluster,which is determined by the similarities between t and clusters.Due to its characteristics,the proposed algorithm is extremely suitable for clustering data streams,where given a sequence of points,the objective is to maintain consistently good clustering of the sequence so far,using a small amount of memory and time.Outliers can also be handled efficiently and directly in Squeezer.Experimental results on real-life and synthetic datasets verify the superiority of Squeezer.     

基于k-prototypes的混合属性数据聚类算法

通过对基于K-prototypes算法对混合属性数据处理的聚类问题进行研究,改进了K-prototypes算法中分类属性相异度计算公式,使之能更加精确反映样本间的差异;在此基础上提出了一种用于处理混合属性数据的聚类算法,并将改进后的算法应用于英语借词数据的聚类分析中。实验结果表明,与K-prototypes算法相比,改进后的算法具有更好的稳定性和更高的精度。     

基于相关随机子空间的分类数据聚类集成

为了提升分类数据聚类集成的效果,提出了一种新的相关随机子空间聚类集成模型。该模型利用粗糙集理论将分类属性分解成相关和不相关子集,在相关属性子集上随机生成多个相关子空间并对分类数据进行聚类,通过集成多个较优且具差异性的聚类结果以获得最终的聚类划分。此外,将粗糙集约简概念应用于相关子空间属性数目的确定,有效地避免了参数对聚类结果的影响。UCI数据集实验表明,新模型的性能优于其他已有模型,说明了其有效性。     

基于改进GRC和集成技术的混合数据聚类算法

在分析现有混合属性数据聚类算法存在问题的基础上,选用基于图论的松弛聚类算法作为解决问题的“基石”;引入基于“Local Scale”思想的高斯核参数计算步骤,对基于图论的松弛聚类算法进行了自适应改进,并对其点对距离计算过程进行了面向混合属性的度量扩展。在上述两步改进的基础上,结合聚类集成技术,提出了一种新的混合属性数据聚类算法,并进行了实例验证,结果表明提出的算法具有较强的参数鲁棒性和较高的聚类精度。     

基于连通分量的分类变量聚类算法

针对分类变量相似度定义存在的不足, 提出一种新的相似度定义. 利用新的相似度定义, 将数据集抽象为无向图, 将聚类过程转化为求无向图连通分量的过程, 进而提出一种基于连通分量的分类变量聚类算法. 为了定量地分析该算法的聚类效果, 针对类别归属已知的数据集, 提出一种新的聚类结果评价指标. 实验结果表明, 所提出的算法具有较高的聚类精度和聚类效率.     

DCKPDP：改进k-prototype聚类的差分隐私混合属性数据发布方法

当前混合属性数据发布中隐私保护方法大多存在隐私保护效果不佳或数据效用较差的问题,采用差分隐私与优化的k-prototype聚类方法相结合,提出改进k-prototype聚类的差分隐私混合属性数据发布方法(DCKPDP)。为解决传统k-prototype聚类算法没有考虑不同数值型属性对聚类结果有较大影响的问题,利用信息熵为每个数值型属性添加属性权重;为解决聚类初始中心点人为规定或者由随机算法随机确定,导致聚类结果精确度不高的问题,结合数据对象的局部密度和高密度对聚类过程中初始中心点进行自适应选择;为解决数据信息泄露风险较高的问题,对聚类中心值进行差分隐私保护。实验结果表明,DCKPDP算法满足差分隐私保护所需的噪声量更小,数据的可用性更好。