第 1 章 绪论
1.1 课题来源与选题背景
本课题为导师指导下自选题目，主要研究内容是：分析聚类算法和与智能算法混合聚类的研究现状，提出基于改进PSO和优化的KHM[1]的混合聚类算法，达到了更好的聚类效果。随着数据时代的到来，面临日益喷涌的“碎片化”信息，人们希望将这些信息潜在的价值利用起来。数据财富的宝贵性愈发的让国家、企业重视，大型的互联网企业争相投入人力、资金，通过挖掘数据中的潜在信息，了解客户的潜在需求，从而能够提出更加人性化的产品。然而人们很难使用传统的统计方法对这些数据进行处理提炼，进而获取有用的知识。面对这样的困境和需求，数据挖掘应运而生。数据挖掘是一门跨领域的技术学科，涉及到如统计学、机器学习、智能算法等领域在内的诸多设计、理论运用和评价标准。数据挖掘能够有效的处理来源广泛、结构各异的海量复杂数据信息。在生产控制、商务管理、市场分析、医疗诊断，工程设计和科学探索得到广泛的应用。聚类分析是一种重要的数据挖掘技术，主要的目的是将数据分为不同的子集，每个子集内的数据具有相同的性质，不同子集之间的数据性质不同。由于待处理的数据特性未知，聚类算法通常都需要有较高的伸缩性、鲁棒性、自动化能力和能够发现任意形状的簇。聚类算法的主要技术包括相似度度量和聚类评价标准，前者规定数据怎样分类，后者用于评价分类结果优良程度。聚类分析除了被运用在数据的分类上，还可以运用在图像的分割处理。智能算法是对宏观世界的生物行为的抽象概括，是现今人工智能领域的研究热点。该技术被广泛与其它领域的技术交叉使用。智能算法相对于传统算法的优势就是具有启发性、全局性，能够自动的在全局范围内搜索最优解。为了使传统算法更加“智能”，许多学者提出智能算法和传统算法的混合算法。聚类算法与智能算法的混合就取得了较好的效果。在与聚类算法混合的智能算法中，最常被使用的就是遗传算法和粒子群优化算法，它们都具有简单易用，鲁棒性强的优点。其中粒子群算法在收敛速度上有很大优势而遗传算法收敛时仍然具有潜在的跳出局最优值的优点。为此许多学者通过结合 PSO 和 GA 的优点以达到进一步优化混合算法的效率。
..........
1.2 国内外研究现状
国内研究在聚类分析的理论部分：Xu R 对聚类分析技术做了综述性的介绍[2]。针对传统的 K-MEANS 算法 Huang Z 提出一种模糊 K-MEANS 算法，该方法同过使用非相似性度量模式实现了多簇心数据的有效分类[3]。Huang J Z 提出一种可变权重的 K-MEANS 算法，在在一定程度上改善了 K-MEANS 算法的有效性[4]。陈改霞等提出基于候选聚类的 K-MEANS 算法，并论证在其高维度数据集上的可靠性[5]。Zhang B 在 2000 年提出了基于 boosting 方法的 K-调和均值聚类（KHM），该算法克服了 K-MEANS 算法对初始点敏感的缺点[1]。赵恒等使用模糊概念对 KHM 算法进行进一步扩展[6]。Zhang L 对软聚类算法 KHM 的推导过程进行详细描述并对算法性能评价，实验证明 KHM 对初始点不敏感的优点，并且能够有效处理高维数据[7]。Wu X 引用模糊 C-MEANS 算法概念提出混合模糊的 KHM 算法（HFKHM）解决了噪声敏感问题[8]。范桂明针对 KHM 算法在距离度量中权重分配不足的问题，使用加权的欧氏距离代替传统的欧氏距离，能够有效抑制 KHM 陷入局部最优[9]。Yeh W C 提出一种基于快速集中策略（RCS）来增加收敛速度和最小移动策略（MMS）来提高搜索效能的 RMSSOKHM 方法，使用该方法和聚类算法（KHM、K-MEANS）混合提高了聚类算法的性能和效率[10]。在聚类算法的运用上 Li Q 提出基于空间内核的 KHM（SKKHM）处理算法图像分割问题，证明具有良好的鲁棒性[11]。国内在智能算法和聚类算法的混合研究上，其中遗传算法（GA）和粒子群优化算法（PSO）是被探讨研究最多的算法，在 GA 方面文献[12]和文献[13]研究了基于并行优化的 GA 混合聚类。由于相对与 GA，PSO 在收敛速度上有更优秀的性能表现，更多的研究人员使用 PSO 算法及其改进形式与聚类算法进行混合[14-25]。如文献[14]最先提出 PSO 算法和 K-MEANS 的混合。Yang F 使用 PSO和 KHM 进行混合聚类，实现了 KHM 算法跳出局部最优的能力，也提高了 PSO的收敛速度[15]。Zhang J 使用 PSO 和基于阴影集的 C-MEANS（SP-FCM）算法混合，解决了聚类之间重合的问题[18]。WANG Yong-gui 采用双粒子群，每个粒子群使用不同的惯性权值策略和 K-MEANS 混合[19]。Ling H L 开发一种基于粒子群的局部不可微分的聚类方法优化，该方法能够自动估计聚类中心 K 的数量[21]。Hu Q 提出了一种基于 PSO 和改进的模糊 C-MEANS 的混合算法，该算法使用 PSO 来确定初始聚类中心，同时新定义距离度量方式，优化算法的迭代次数和聚类效果[23]。Wang X 选用 MinMax K-MEANS 算法和 PSO 混合，可以自动达到最低的聚类误差[24]。Pei S 基于高斯核函数 PSO 和 K-MEANS 算法混合，实现了快速收敛全局最优的效果[25]。GA 相对于 PSO 具有变异功能，因此增加了跳出局部最优值的可能性，为此许多学者对 PSO 加入粒子的变异概念[26-28]，如陶新民等使用概率随机变异的 PSO 与 K-MEANS 算法混合[26]。或者两者算法一起使用，如贾旋等通过串行使用 GA 和 PSO，增加种群的多样性，同时采用粒子数周期递增来扩大算法的搜索空间[28]。还有许多其它智能算法与传统聚类算法的混合研究[29-31]。
............
第 2 章 相关理论和技术
2.1 聚类分析
聚类分析是一种基本、通用的人类认知活动，早有中国的谚语：“物以类聚，人以群分”来描述该概念。在现代数据的处理技术中，聚类分析也具备重要的作用，并广泛应用于工程设计和科学分析领域，如医学、心理学、生物学、社会学、模式识别和图像处理。聚类分析是一种寻找潜在统计规律的方法，通过聚类过程自动将相似性大的数据进行聚集，最终分成多个子集（簇），同时能够不断自我更新，达到同簇的对象相似度最大，且从全局的角度上观察得到总体分类程度最优。
2.1.1 概念及定义
聚类不同于分类，聚类与分类的区别体现在：分类是映射概念，是面向监督的方法，根据一定的映射规则，将未知数据进行已知的分类；聚类是一种无指导的学习过程，是面向无监督的方法，在分簇的信息未知的情况下，数据根据一定的相似度度量标准来自动聚集为各个簇，同时簇会动态的更新直到满足一定的终止条件。聚类仍然没有在学术界形成统一的定义。Everitt 定义为：同簇的个体相似度大，不同簇的个体相似度小。以多维数据聚类为例，数据聚类在多维空间上表现为数据点密度的分布，簇就是数据在数据空间上的自然分组，通过使用距离的计算对数据进行相似度判断，一般而言簇内的点与所属簇心的距离小于该点与任意其它簇心的距离，簇内的数据之间的距离也小于其与不同簇数据点的距离。
..........
2.2 遗传算法
遗传算法（GeneticAlgorithm, GA）是 Michigan 大学 Holland 教授在 60 年代根据自然界物竞天择，优胜劣汰的生物进化规律抽象而出的算法模型。GA 是一种启发式的面向全局的随机搜索算法，同时具有较强的鲁棒性和潜在的并行性。由于算法原理适用性广且易与其它算法结合，通过计算机程序能广泛用于优化问题、搜索识别问题。GA 是对自然界生物进化过程的抽象，自然界中承担表现单个生物总体特征的就是染色体（chromosome），染色体是由一组基因（gene）构成，每个基因表示一种特性。自然界通过基因的突变、交叉生成新的基因和染色体，在此过程中自然环境对基因进行了一定的筛选：适应环境的大概率保存下来（染色体的交叉生成新一代个体），不适应的个体小概率幸存，同时对所有的个体而言，染色体上的基因存在一定概率的变异。通过一代又一代的更新达到最适应当前自然环境的个体和种群。GA 对进化过程提炼，并抽象为如下名词和其对应功能：编码：把一个现实问题的解从其解空间抽象转换到 GA 可以处理的搜索空间的转换方法。解码（译码）：遗传算法处理的解空间向现实问题空间的转换。基因：染色体构成的基本单位，解的最小独立单位，基因用于表示整体的部分特征，代表解的子集。染色体：由编码过的一个或者多个基因组成，染色体代表个体的全部特性也是一个完整的问题解。种群：每代包含的染色体个数的上限。适应度函数：用来评价个体适应环境的程度，GA 中也叫评价函数，通过具体的数值表示个体的优劣，选择：对上一代种群的染色体通过一定概率来确定重组或交叉得个体，以及被选个体将产生子代个体的个数。交叉：染色体间基因段之间的交换。变异：GA 中通常的以最小的编码单位转化为它值，使得染色体的解发生改变。
..............
第 3 章 IPSO 和 KHM 的混合聚类....20
3.1 概述 ....20
3.2 K-harmonic means 的优化..........20
3.2.1 算法简介 ......20
3.2.2 算法特性 ......21
3.2.3 参数p值的优化..........23
3.2.4 距离标准优化 ............27
3.3 改进的粒子群优化算法（IPSO） ......30
3.3.1 均匀设计（uniform design）..........30
3.3.2 PSO 的优化........31
3.4 IPSO 和 KHM 算法的混合（IPSO-KHM） ............34
3.4.1 混合方式 ......34
3.4.2 IPSO-KHM 算法流程..........35
3.5 本章小结 ..........36
第 4 章 实证分析............38
4.1 实验设置 ..........38
4.2 IPSO 性能验证 ............39
4.3 IPSO-KHM 性能验证 ..........40
4.4 本章小结 ..........41
第 5 章 总结与展望..........43
5.1 总结 ....43
5.2 展望 ....44
第 4 章 实证分析
4.1 实验设置
为了验证聚类算法的效果，通常可以使用机器学习的标准数据集（UCI 数据集），这些数据集聚类结果已知，可以通过与标准的聚类结果对比，验证算法的评价准则如 SSE 和算法的分类误差。本文数据集选用用 iris、glass、wine，其特性如表 4.1 所示：本节验证 IPSO 相较于基本 PSO 的优势。实验以公式（3.4）的 KHM(Z,C )为适应度函数，分别对其中粒子解向量维度较大的 glass 和 wine 两个数据集记录粒子群每代适应度值，粒子群迭代次数为 1000 代，设置相同的初始粒子群，记录适应度值与代数的关系如图 4.1 所示。由图 4.2 可见，三种算法都在 100 代内趋于局部最优，超过 30 代后 SSE 变化范围变小，均达到稳定（两代 SSE 相差小于 1）。（1）收敛速度。IPSO-KHM 算法在三种数据集上的迭代次数最少，收敛速度最快；K-MEANS 算法在 iris 数据集和 glass 数据集上收敛速度比 KHM 快，在 wine 数据集上收敛速度比 KHM 慢。（2）聚类效果 SSE。IPSO-KHM 和 KHM 的 SSE 值相似，效果好于K-MEANS。结合具体的数值,IPSO-KHM 三种数据集的 SSE 分别为：96.92，213.47，1152.57；而 KHM 则是：97.01，214.45，1153.03。得知 IPSO-KHM 在三种数据集上得到的最优 SSE 最小，效果最好，K-MEANS 算法得到的 SSE 效果最差。
.........
总结
聚类分析是数据挖掘的重要技术，在对数据监督/无监督处理上有着广泛的应用，传统聚类算法和智能算法的混合聚类是当下的热点。在传统的聚类算法中，基于划分的硬聚类算法 K-MEANS 具有简单易用、适用性广的优点和对初始点敏感、全局搜索能力不足的缺点，为了解决对初始点敏感问题，文献[1]在K-MEANS 算法的研究基础上提出了 KHM 算法并验证了其对任意初始点的有效性，然而缺少算法中参数和距离度量对高维数据聚类影响的描述。另一方面为了提高聚类算法的启发性和全局性，多数学者通过使用智能算法和传统聚类算法混合来处理聚类问题，最常使用的就是 PSO 算法，然而 PSO 算法易收敛于局部最优。针对以上问题，本文通过进行理论研究和实证分析，提出基于改进 PSO 和参数优化的 KHM 的混合聚类算法 IPSO-KHM，实验证明该算法在聚类的评价准则 SSE、收敛的速度、分类的准确率上都要更加优秀。本文主要工作和创新点如下：
（1）优化 KHM 算法：分析聚类算法 KHM，对参数 p 和距离的度量方式进行试验对比。实验证明在参数 p 的取值与文献[1]给出的建议值（ p 应该取值大于 2，数据维度越高 p 值应该越大）不同，余弦距离在高维数据上效果不佳，Minkowski 距离中 q 2时（即欧式距离）在本文中取得的算法性能最好，随着 q值的增加 Minkowski 距离的影响趋于相同。该部分的工作提高了 KHM 算法在高维数据上的有效性。
（2）改进 PSO 算法（提出算法 IPSO）：首先对粒子陷入局部最优的分布模型做探讨（高斯分布），引用空间密度判断方法对粒子是否陷入局部最优提供判断，得知粒子在收敛局部最优时离最优值的相对距离与粒子的搜索效率相关，再对粒子群使用 GA 中的变异概念，提出基于粒子分布情况的变异策略。通过实验证明 IPSO 具有跳出局部最优的能力，使得 IPSO 有更好的全局搜索性能。
（3）提出 IPSO-KHM 混合聚类：在对比分析文献[12-31]混合过程提出新的混合方式，使用聚类算法 KHM 的聚类迭代过程与 PSO 的位置更新过程组合，进一步提高粒子的收敛速度。实验证明，IPSO-KHM 相对于传统聚类算法和文献中的混合算法有更加优良的聚类效果。
..........
参考文献（略）
提供海量毕业论文，论文格式，论文格式范文，留学生论文，商务报告相关资料检索服务。
