面向混合数据集的聚类方法研究

主持人:江思源

参会老师:杨矫云

参会学生:李雨龙,刘硕,赵春阳,程坤,韩朋,段优,殷越,景波,江思源,刘杰,唐晨,滕越,贵芳,郭思伊

本次例会主要进行了答辩ppt的汇报。

论文题目:面向混合数据集的聚类方法研究

提纲:

1、本文工作简介 2、背景和研究现状 3、本文工作详情 4、总结和未来展望

本文工作简介:1.对课题的背景和研究现状进行分析 2.提出基于单纯形向量映射的聚类算法 3.提出基于熵加权的聚类算法 4.对算法进行实验和理论分析,证明提出算法的优越性

背景介绍:

聚类分析是数据挖掘中的一个主要的分析工具,可以发现数据中隐藏的信息或知识,在图像处理、模式识别、数据压缩、市场研究、文本分类等领域中得到了广泛的应用,给社会带来了巨大的经济效益。

研究现状:

现有的聚类算法大多局限于数值型数据集的聚类问题,例如K-Means算法[1]和EM算法[2],然而现实生活中的大多数数据集不仅包括数值型数据,还包括大量的分类型数据,如二值型和名义型等。混合型数据集的相似性度量方法与单一类型(数值型或分类型)的度量方法存在较大的差异,设计针对混合型数据的聚类算法非常迫切。

针对混合数据集的聚类算法大体可以分为两类:

1)为分类型和数值型数据分别设计不同的相似性度量,然后将这两部分相似性加权求和,例如K-Prototypes算法[3]。

2)将分类型属性全部转换为数值型属性,或者将数值型属性全部转换为分类型属性,然后应用于针对单一类型的数据聚类算法,例如SpectralCAT算法[4]。

面向混合型数据集的聚类算法仍然存在很多缺陷,需要我们不断探索。

然后介绍了聚类的定义、目标函数和数据集的表示。开始介绍基于单纯形向量映射的聚类算法。

基于单纯形向量映射的聚类算法的基本思想:首先,基于单纯形理论,将分类型属性数据映射到数值向量上,并确保同一属性的任意值映射后的向量在欧氏距离下距离相同,保留了分类型属性数据的特性。这样,分类型属性数据就可以与数值型数据统一处理。然后,将转换后的纯数值型数据应用到K-Means算法框架。

再介绍基于单纯形向量映射的聚类算法的向量映射策略、算法步骤和实验结果与分析。在6个UCI数据集上,基于单纯形向量映射的聚类算法均优于K-Prototype和传统映射聚类算法,将聚类结果的准确度分别提高2.70%和18.33%。

接下来介绍基于熵加权的聚类算法。基于熵加权的聚类算法的基本思想:首先,通过离散化策略将数值型属性数据离散化;然后基于信息熵理论提出针对分类型属性的加权策略,并设计分类型属性的相似性度量;最后,将针对分类型属性提出的相似性度量应用于离散化后的数据。

然后介绍基于熵加权的聚类算法的基于信息熵的属性加权策略、混合型属性的相似性度量、算法步骤和实验结果与分析。在UCI的6个混合型数据集上的实验表明,提出的基于熵加权相似性度量的聚类算法优于OCIL和K-Prototype方法,在聚类准确度上分别提高了2.13%和4.28%。

总结与展望:

基于单纯形向量映射的聚类算法,能统一处理分类型属性和数值型属性,能提高聚类准确度,增加了数据的维度,尤其当分类型属性的值域较大时,映射后数据的属性数目大大增加,这既增加了存储空间。

2、基于熵加权的聚类算法,能统一处理分类型属性和数值型属性,能提高聚类准确度,能够降低数据集的维度,由于相似性度量采用频率代替均值,不容易受孤立点影响。该算法的时间复杂度较高。

展望:

1、优化属性加权算法

2、降低算法的时间复杂度

[1]Macqueen J. Some Methods for Classification and Analysis of MultiVariate Observations[C]//Proc of Berkeley Symposium on Mathematical Statistics & Probability, 1965.

[2]Dempster A. Maximum likelihood from incomplete data via the EM algorithm[J]. Journal of the Royal Statistical Society, Series B, 1977, 39.

[3]Adriane B.S. Serapião, Guilherme S. Corrêa, Felipe B. Gonçalves, et al. Combining K-Means and K-Harmonic with Fish School Search Algorithm for data clustering task on graphics processing units[J]. Applied Soft Computing, 2016, 41(C):290-304.

[4]David G, Averbuch A. SpectralCAT: Categorical spectral clustering of numerical and nominal data[J]. Pattern Recognition, 2012, 45(1):416-433.

anyShare分享到:
This entry was posted in 例会. Bookmark the permalink.

发表评论