基于簇内与簇间信息的混合数据聚类算法思考与推广

论文价格:150元/篇 论文用途:硕士毕业论文 Master Thesis 编辑:硕博论文网 点击次数:
论文字数:52551 论文编号:sb2022022117123443735 日期:2022-03-01 来源:硕博论文网
本文是一篇软件工程论文,在本阶段工作中,对混合数据聚类算法簇中心标称属性部分的表示进行研究,通过理论分析和实验验证提出了滤噪分布质心,在滤噪分布质心的基础上,结合簇内与簇间信息迭代统一量化标称属性和数值属性的权重。实验阶段对算法涉及的两个平衡参数进行了实验分析,在混合数据上对实验分析得出的推荐参数进行了验证,最后对 MCFCAW 算法的收敛速度进行比较分析。 

第 1 章  绪论

1.1  研究背景和意义
该研究来源于导师主持的江西省自然科学基金面上项目,聚类分析优化方法研究及其在复杂网络社团结构发现中的应用(No.20192BAB207019)。
近年来,随着万维网的巨大发展以及硬件和软件技术的进步,我们能够收集并存储多种类型的数据,例如客户点击数据,患者健康数据,TCP/IP 流量,GPS数据等,以支持决策。为提取大量数据中的有用信息,通常采用数据挖掘技术,如聚类、分类和频繁项集挖掘。在挖掘数据信息时,非监督的数据聚类分析是一类非常有效的方法。聚类方法已经成功的应用到多个领域,数据聚类的目标是基于相似性度量将数据对象进行分组以获得多个簇,每一个簇中包含的对象尽量相似,不同簇之间的数据对象尽量不相似。当前大多数聚类算法假设数据对象的属性是标称属性或数值属性,在现实生活中的数据对象常同时包含数值属性和标称属性,称之为混合数据,混合数据常出现在健康、市场、医疗、金融等行业。
软件工程论文参考
软件工程论文参考
......................

1.2  相关领域研究现状
1.2.1  基于划分的混合数据聚类算法研究现状
混合数据聚类算法可分为基于数据转化的混合数据聚类算法和直接用于混合数据的聚类算法。基于数据转化的聚类算法有离散化和数值编码两种方案,其将一类属性转化为剩下一类属性[16];而直接用于混合数据的基于划分的混合聚类算法不需要对属性进行转化。接下来主要介绍基于划分的混合数据聚类算法的相关研究。
基于数据转化方法对混合数据进行聚类,数据转化方法分为数值属性的离散化和标称属性的数值编码。数值属性的离散化可分为两大类:监督 vs 非监督。监督离散化方法包括 1RD[17],Adaptive Quantizers[18],ChiMerge (Kerber) [19],D-2 (Catlett)[20],Fayyad and Irani / Ting[21],Supervised MCC[22],Predictive Value Max[23]。非监督离散化方法包括等宽装箱法(Equal Interval Width),等频装箱法(Equal Frequency Intervals),Unsupervised MCC[22]。监督离散化方法需要数据的类标签,并不适合非监督的聚类算法。标称属性的数值编码有两类方式:基于领域知识(例如收入水平的划分[16]、年龄阶段的划分[24]),哑编码[16],简单编码[25]。非监督的离散化方法使用不合适的切点将导致潜在的数据信息损失[19];数值编码技术选择合适的标量 c 确定标称属性和数值属性的相对贡献是困难的[16]。
基于划分的混合数据聚类算法簇中心的标称属性部分可使用中心点、众数或分布质心表示。PAM 算法[26](k-medoids)算法使用中心点作为簇中心。Huang等[27][28]提出 k-prototypes 算法,该算法簇中心的标称属性部分使用众数,簇中心的数值属性部分使用均值。Ji 等[29]将 Kim 等[30]提出的模糊中心引入到硬聚类场景中,使得簇中心的标称属性使用分布质心表示,数值属性使用均值表示,其他的基于划分的混合数据聚类算法[31][32][33][34]也使用该簇中心。Ahmad 等[35]结合KMCMD 的[31]距离度量和 KHM[36]的目标函数提出一个对初始簇中心不敏感的混合数据聚类算法 KHMCMD,因而在进行簇中心的更新时较 Ji 等[29]的有所差异,但是簇中心的形式相似。使用中心点或众数表示簇中心的标称属性部分存在信息损失的问题,使用分布质心表示簇中心的标称属性部分存在纳入“噪声取值”的问题,这三种方案都会给出有偏差的簇内标称属性信息。 
........................

第 2 章  带滤噪分布质心与权重调整的混合数据聚类算法

2.1  引言
聚类是一种非常重要的数据分析方法,混合数据聚类分析仍然是当前一个具有挑战性的问题。本文针对混合数据聚类中簇中心的定义、不相似性的度量以及属性权重的量化等问题,提出了一种带滤噪分布质心与权重调整的混合数据聚类算法 MCFCAW。该算法定义了簇内标称属性滤噪分布质心,将其与均值相结合共同描述混合数据的簇中心,能更为准确地刻画簇内标称属性的取值分布,改善混合数据相似性度量效果,达到滤除簇内“噪声取值”的目的。同时,算法中引入了簇内与簇间信息自适应权重调整策略。该策略首先使用熵、离散系数分别量化标称属性、数值属性的簇内信息,采用海林格距离量化属性的簇间信息,统一量化标称属性和数值属性对聚类的贡献。其次,簇内同质性高且簇间异质性高的属性被认为是重要属性,聚类过程通过赋予重要属性相对更大权重的方式更新属性权重,并用于相似性度量以及目标函数优化。实验结果表明 MCFCAW 算法在 Accuracy、Precision、Recall 等常用聚类评价指标上表现更佳、收敛速度更快,能获得更好的混合数据聚类效果。
机器学习算法分为有监督算法和无监督算法,聚类属于无监督的机器学习技术,其将数据划分为多个簇,同一个簇中的数据尽可能相似,不属于同一个簇的数据尽可能不相似。许多算法只能处理只包含数值属性的数据或只包含标称属性的数据。数值属性的取值为实值,例如高度、宽度和长度等,而标称属性的取值只能为固定数量的标称值,例如颜色、种族、性别等。聚类算法使用某种相似性度量对数据进行划分,最简单的相似性度量是欧氏距离,但是其只能用于数值属性,不能够对标称属性进行相似性度量。当前大多数算法假设数据中所有的属性是标称属性或数值属性,在现实生活中的数据常同时包含数值属性和标称属性,称之为混合数据,混合数据常出现在健康、市场、医疗、金融等行业。当需要处理混合数据时,过去常常利用一些转换的方法将混合数据中的一种类型属性转化为剩下的属性类型,随后使用只能处理包含单一属性类型数据的传统聚类算法,然而,在大多数情况下,转换策略会导致信息的丢失,聚类结果与实事出现偏差。因此,研究出能够直接处理混合数据的聚类算法变得非常重要。
............................

2.2 相关工作
基于划分的聚类算法的区别在于簇中心的计算,例如聚类算法 k-Means[58][59]和 k-Modes[27]分别使用簇内数据的均值和众数,然而 k-Medoids 使用最中心的数据 点 作 为 簇 中 心 。 k-Medoids④的 第 一 个 实 现 是 PAM(Partitioning  Around Medoids)[26]算法。PAM 算法相对 k-Means 算法对噪声和离群点的鲁棒性更高,此外,PAM 算法结合混合数据距离函数能够直接处理混合数据。PAM 算法时间复杂度高,若将含有????????个数据点的数据集划分为????????个簇,其时间复杂度???????? (????????(???????? −????????)2),这使得 PAM 算法是高耗资源和时间的,
在现实生活中的数据常同时包含数值属性和标称属性,称之为混合数据。能够直接处理混合数据的主要算法有 k-prototypes[28]、IK-prototypes[29]和 EBK-prototypes[33]。k-prototypes⑤算法针对混合数据,提出了新的簇中心表示方法和数据点与簇中心距离的新定义。新的簇中心,数值属性部分使用均值表示,标称属性部分使用众数表示,然而提出的簇中心并不能很好的表示潜在的簇[13],原因如下:1)簇中心的标称属性使用众数将导致信息丢失,2)汉明距离并不能很好的量化含有多种取值标称属性的取值之间的相似性,因为汉明距离度量标称属性值之间的相似性时只能给出 0 或 1 的结果,该结果取决于标称属性值是否相等。IK-prototypes 算法将 Kim 等[30]提出的模糊中心引入到硬聚类场景中,使得簇中心的标称属性使用分布质心表示,数值属性使用均值表示,但使用分布质心表示簇中心的标称属性部分存在纳入“噪声取值”的问题。EBK-prototypes 算法针对 k-prototypes 算法提出一个新的相似性度量,新的相似性度量针对标称属性基于不同簇中标称属性值的频率提出了权重汉明距离,针对 k-prototypes 算法提出的新相似性度量只对标称属性部分进行了提升,并没有对数值属性部分做相关提升。 
软件工程论文怎么写
软件工程论文怎么写
.............................

第 3 章  基于分类效用函数的混合数据簇数确定算法 ·················· 44
3.1  引言 ·························· 44
3.2  相关工作 ······························· 44
3.3  基于分类效用函数的混合数据划分度量合理性策略 ······················· 45
第 4 章  MDCA-Tool 的设计与实现 ····························· 63
4.1  需求分析 ·································· 63
4.1.1  需求概述 ······························ 63
4.1.2  工具角色分析 ···························· 64
第 5 章  总结与展望 ································· 89
5.1  本文工作总结 ······························· 89
5.2  未来研究展望 ···································· 90

第 4 章  MDCA-Tool 的设计与实现

4.1  需求分析
4.1.1  需求概述
MDCA-Tool 主要功能模块包括:参数设置模块、数据管理模块、算法运行模块、实验记录模块。
参数设置模块主要功能:加载算法的默认参数和描述信息,此外还提供了算法参的修改与重置功能。修改的算法参数不会持久化到硬盘,软件重启后,此前对算法参数的修改失效,将加算法载配置文件中的默认参数。算法参数重置功能,通过加载算法配置文件中的默认参数来覆盖之前对算法参数的修改。 数据管理模块主要功能:该模块管理三类数据集(标称数据、数值数据、混合数据),提供数据集的添加和删除功能,此外,还提供对数据集属性的填充和重置功能。对数据集属性的填充将会持久化到数据集载配置文件中。数据集属性的重置功能,可以回退到上次保存数据集属性后的状态。
算法运行模块主要功能:该模块实现了算法运行和结果展示的功能。提供算法运行前的数据集和算法选择功能,通过设定处理数据类型过滤并展示满足需要的数据集和算法。选定算法和数据集后运行算法,对算法的运行结果进行保存和展示,算法的历史运行结果将全部持久化到硬盘中。
实验记录模块主要功能:该模块对算法运行产生的三类结果进行保存,即算法运行时间信息、算法运行结果信息、算法运行指标信息;此外,提供 NC 确定算法对聚类算法运行结果信息进行二次处理,确定对应数据集的近似最优 NC。 
..........................

第 5 章  总结与展望

5.1  本文工作总结
本文的研究主要是为了提升混合数据聚类的效果。首先,本文介绍了混合数据聚类相关的研究背景及其研究意义。随后,针对当前混合数据簇中心标称属性部分描述不准确的问题,研究提出了滤噪分布质心表示簇中心的标称属性部分,滤噪分布质心能够解决簇中心标称属性部分表示存在信息缺失或纳入噪声信息的问题,同时提出簇内与簇间信息自适应权重调整策略统一量化标称属性和数值属性的权重。紧接着研究混合数据簇数确定的问题,提出基于分类效用函数的混合数据簇数确定算法,解决混合数据簇数设定困难的问题。最后通过多组实验验证所提算法的有效性,并将所有的理论研究成果设计开发形成混合数据聚类分析工具,具体工作内容如下:
1.  滤噪分布质心能够很好的表示簇中心标称属性部分,其准确的量化簇内标称属性信息,自适应权重调整策略迭代统一的量化标称属性和数值属性的权重,据此提出带滤噪分布质心与权重调整的混合数据聚类算法 MCFCAW。该算法针传统分布质心纳入“噪声取值”的问题,提出滤噪分布质心表示簇中心标称属性部分;同时利用离散系数和信息熵量化簇内信息,并利用海林格距离量化簇间信息,结合簇内与簇间信息迭代量化属性的权重。通过实例分析说明以上两个策略的有效性,最后结合这两个策略提出 MCFCAW 算法。在 UCI 数据仓库中的18 个数据集上进行 MCFCAW 算法的对比实验分析,使用 7 种常用的聚类评价指标用于实验结果的评估。滤噪分布质心和自适应权重调整策略的参数分析、MCFCAW 算法聚类性能和收敛速度的对比实验结果表明,相对其他基于划分的经典混合数据聚类算法、基于数据转化的混合数据聚类算法,MCFCAW 算法能获得较好的混合数据聚类性能。
2.  为解决过去大多簇数确定算法只能处理标称数据或数值数据,提出了基于分类效用函数的混合数据簇数确定算法 DNCCUFM。基于信息熵提出标称数据分类效用函数,基于离散系数提出数值数据分类效用函数,通过实例分析说明以上两个分类效用函数的有效性,随后结合以上两个分类效用函数提出混合数据分类效用函数。将混合数据分类效用函数与混合数据聚类算法相结合提出DNCCUFM 算法。最后在 2 个数值数据、2 个标称数据和 2 个混合数据集上的实验结果表明 DNCCUFM 能够有效确定数据集的近似最优簇数,在数值数据上有更好的准确性,在标称数据集和混合数据集上有更高的效率。
参考文献(略)

QQ 1429724474 电话 18964107217