《聚类分析中的若干问题研究及应用》由会员分享，可在线阅读，更多相关《聚类分析中的若干问题研究及应用（43页珍藏版）》请在金锄头文库上搜索。
1、应用数学专业毕业论文应用数学专业毕业论文 精品论文精品论文 聚类分析中的若干问题研究聚类分析中的若干问题研究及应用及应用关键词：聚类分析关键词：聚类分析 统计模型统计模型 数值试验数值试验摘要：聚类分析是知识发现、机器学习和数据挖掘等领域的一个非常重要的基 本工具。与传统的分类方法不同，聚类是在没有任何先验知识的前提下，仅根 据数据间的相似性将没有标号数据集划分成不同的类(或簇)，使得同一个类中 的元素尽可能相似，而不同类中的元素差别尽可能大，因此聚类分析又是一个 非监督学习过程。 模糊聚类和 Gauss 混合模型是目前应用最为广泛的两种聚 类分析方法，本文主要针对这两类方法中存在的一些基本问
2、题，做了以下几个 方面的研究工作： 在第一章，我们对文献中存在的主要聚类分析方法做了一 个全面的综述，主要分析了划分聚类方法、层次聚类方法、基于密度的聚类方 法、基于网格的聚类方法以及基于模型的聚类方法中的多种算法的优缺点。 第二章主要就模糊聚类方法中的 FCM 和 PCM 及其优缺点展开讨论。 首先对 FCM 和 PCM 做了较为详尽的综述报告，并从理论和数值试验两个角度分析了 FCM 和 PCM 算法的不足之处。 然后研究了由 J S Zhang 等人提出的将 FCM 和 PCM 相结合的模糊聚类算法，数值试验表明，该算法能有效地发挥 FCM 和 PCM 的优 点，克服它们各自的缺点，其聚
3、类效果比单一的 FCM 和 PCM 都更为理想。在第 二章的最后部分，我们以数值试验说明了模糊球壳聚类算法 FCSS 不能对加有噪 声的同心球壳状数据进行有效聚类，并从理论上分析了产生这一现象的原因， 那就是 FCSS 采用的基于梯度法和交替寻优策略容易陷入局部极值点，从而影响 聚类效果。 因此，我们提出用遗传算法搜索 FCSS 目标函数的最优解，并且， 为了加速遗传算法的收敛速度，我们还将原 FCSS 算法与遗传算法进行巧妙地结 合起来，产生出所谓的基于遗传算法与 FCSS 相结合的模糊球壳聚类算法 GA- FCSS。 大量的数值试验表明，我们提出的 GA-FCSS 算法是有效的，它能将各
4、种含有噪声的球壳(包括同心球壳)状数据进行很好地分离，得到的球壳中心和 半径与真实值较为接近，对数据点的分类结果也几乎完全正确。 第三章就基 于统计模型的聚类算法展开讨论，主要选择了目前较为实用的 Gauss 混合模型， 它是一种半参数的聚类方法。 首先，我们将 Gauss 混合模型与聚类问题进行 了类比。 然后推导了求解 Gauss 混合模型相关参数的极大似然估计的 EM 算 法，并以数值试验实例说明了 EM 算法对实心椭球状数据进行聚类是有效的。 最后，我们以 Gauss 混合模型为基础，研究了聚类的有效性问题，即待聚类的 数据中有多少个类别的问题，这在 Gauss 混合模型中表现为有多少
5、个正态分支。 我们主要研究了基于极小信息长度准则的 MML-EM 算法，该算法可以同时处理 Gauss 混合模型的模型选择(估计类别数)与参数估计两个问题。 数值试验表 明，当以接近真实值的整数初始化聚类的类别数时，MML-EM 算法能以较高的正 确率选择出最优类别数，但对聚类原型的估计可能出现较大偏差；当以远离真 实值的整数初始化类别数时，MML-EM 算法选择最优类别数的正确率迅速降低， 并且有过高估计最优类别数的趋势。 针对这一情况，我们从理论上重新分析 了 MML 准则，找出了出现这样结果的原因，并提出了一种改进算法(IMML-EM)。 数值试验表明，我们改进的 IMML-EM 算法极
6、大地克服了原 MML-EM 算法的上述缺 点，特别是它选择最优类别数的正确率会随着初始类别数的增加而迅速递增，这比原 MML-EM 算法具有更广泛的实用性，因为人们在实际的聚类问题中常常没 有关于类别数的信息，只能在较大的范围内搜索最优类别数。 所以，我们的 IMML-EM 具有更大的实用价值。正文内容正文内容聚类分析是知识发现、机器学习和数据挖掘等领域的一个非常重要的基本 工具。与传统的分类方法不同，聚类是在没有任何先验知识的前提下，仅根据 数据间的相似性将没有标号数据集划分成不同的类(或簇)，使得同一个类中的 元素尽可能相似，而不同类中的元素差别尽可能大，因此聚类分析又是一个非 监督学习过
7、程。 模糊聚类和 Gauss 混合模型是目前应用最为广泛的两种聚类 分析方法，本文主要针对这两类方法中存在的一些基本问题，做了以下几个方 面的研究工作： 在第一章，我们对文献中存在的主要聚类分析方法做了一个 全面的综述，主要分析了划分聚类方法、层次聚类方法、基于密度的聚类方法、 基于网格的聚类方法以及基于模型的聚类方法中的多种算法的优缺点。 第二 章主要就模糊聚类方法中的 FCM 和 PCM 及其优缺点展开讨论。 首先对 FCM 和 PCM 做了较为详尽的综述报告，并从理论和数值试验两个角度分析了 FCM 和 PCM 算法的不足之处。 然后研究了由 J S Zhang 等人提出的将 FCM 和
8、 PCM 相 结合的模糊聚类算法，数值试验表明，该算法能有效地发挥 FCM 和 PCM 的优点， 克服它们各自的缺点，其聚类效果比单一的 FCM 和 PCM 都更为理想。在第二章 的最后部分，我们以数值试验说明了模糊球壳聚类算法 FCSS 不能对加有噪声的 同心球壳状数据进行有效聚类，并从理论上分析了产生这一现象的原因，那就 是 FCSS 采用的基于梯度法和交替寻优策略容易陷入局部极值点，从而影响聚类 效果。 因此，我们提出用遗传算法搜索 FCSS 目标函数的最优解，并且，为 了加速遗传算法的收敛速度，我们还将原 FCSS 算法与遗传算法进行巧妙地结合 起来，产生出所谓的基于遗传算法与 FCS
9、S 相结合的模糊球壳聚类算法 GA- FCSS。 大量的数值试验表明，我们提出的 GA-FCSS 算法是有效的，它能将各 种含有噪声的球壳(包括同心球壳)状数据进行很好地分离，得到的球壳中心和 半径与真实值较为接近，对数据点的分类结果也几乎完全正确。 第三章就基 于统计模型的聚类算法展开讨论，主要选择了目前较为实用的 Gauss 混合模型， 它是一种半参数的聚类方法。 首先，我们将 Gauss 混合模型与聚类问题进行 了类比。 然后推导了求解 Gauss 混合模型相关参数的极大似然估计的 EM 算 法，并以数值试验实例说明了 EM 算法对实心椭球状数据进行聚类是有效的。 最后，我们以 Gaus
10、s 混合模型为基础，研究了聚类的有效性问题，即待聚类的 数据中有多少个类别的问题，这在 Gauss 混合模型中表现为有多少个正态分支。 我们主要研究了基于极小信息长度准则的 MML-EM 算法，该算法可以同时处理 Gauss 混合模型的模型选择(估计类别数)与参数估计两个问题。 数值试验表 明，当以接近真实值的整数初始化聚类的类别数时，MML-EM 算法能以较高的正 确率选择出最优类别数，但对聚类原型的估计可能出现较大偏差；当以远离真 实值的整数初始化类别数时，MML-EM 算法选择最优类别数的正确率迅速降低， 并且有过高估计最优类别数的趋势。 针对这一情况，我们从理论上重新分析 了 MML
11、准则，找出了出现这样结果的原因，并提出了一种改进算法(IMML-EM)。 数值试验表明，我们改进的 IMML-EM 算法极大地克服了原 MML-EM 算法的上述缺 点，特别是它选择最优类别数的正确率会随着初始类别数的增加而迅速递增， 这比原 MML-EM 算法具有更广泛的实用性，因为人们在实际的聚类问题中常常没 有关于类别数的信息，只能在较大的范围内搜索最优类别数。 所以，我们的 IMML-EM 具有更大的实用价值。 聚类分析是知识发现、机器学习和数据挖掘等领域的一个非常重要的基本工具。与传统的分类方法不同，聚类是在没有任何先验知识的前提下，仅根据数据间 的相似性将没有标号数据集划分成不同的类
12、(或簇)，使得同一个类中的元素尽 可能相似，而不同类中的元素差别尽可能大，因此聚类分析又是一个非监督学 习过程。 模糊聚类和 Gauss 混合模型是目前应用最为广泛的两种聚类分析方 法，本文主要针对这两类方法中存在的一些基本问题，做了以下几个方面的研 究工作： 在第一章，我们对文献中存在的主要聚类分析方法做了一个全面的 综述，主要分析了划分聚类方法、层次聚类方法、基于密度的聚类方法、基于 网格的聚类方法以及基于模型的聚类方法中的多种算法的优缺点。 第二章主 要就模糊聚类方法中的 FCM 和 PCM 及其优缺点展开讨论。 首先对 FCM 和 PCM 做了较为详尽的综述报告，并从理论和数值试验两个
13、角度分析了 FCM 和 PCM 算 法的不足之处。 然后研究了由 J S Zhang 等人提出的将 FCM 和 PCM 相结合的 模糊聚类算法，数值试验表明，该算法能有效地发挥 FCM 和 PCM 的优点，克服 它们各自的缺点，其聚类效果比单一的 FCM 和 PCM 都更为理想。在第二章的最 后部分，我们以数值试验说明了模糊球壳聚类算法 FCSS 不能对加有噪声的同心 球壳状数据进行有效聚类，并从理论上分析了产生这一现象的原因，那就是 FCSS 采用的基于梯度法和交替寻优策略容易陷入局部极值点，从而影响聚类效 果。 因此，我们提出用遗传算法搜索 FCSS 目标函数的最优解，并且，为了 加速遗传
14、算法的收敛速度，我们还将原 FCSS 算法与遗传算法进行巧妙地结合起 来，产生出所谓的基于遗传算法与 FCSS 相结合的模糊球壳聚类算法 GA-FCSS。 大量的数值试验表明，我们提出的 GA-FCSS 算法是有效的，它能将各种含有噪 声的球壳(包括同心球壳)状数据进行很好地分离，得到的球壳中心和半径与真 实值较为接近，对数据点的分类结果也几乎完全正确。 第三章就基于统计模 型的聚类算法展开讨论，主要选择了目前较为实用的 Gauss 混合模型，它是一 种半参数的聚类方法。 首先，我们将 Gauss 混合模型与聚类问题进行了类比。然后推导了求解 Gauss 混合模型相关参数的极大似然估计的 EM
15、 算法，并以 数值试验实例说明了 EM 算法对实心椭球状数据进行聚类是有效的。 最后， 我们以 Gauss 混合模型为基础，研究了聚类的有效性问题，即待聚类的数据中 有多少个类别的问题，这在 Gauss 混合模型中表现为有多少个正态分支。我们 主要研究了基于极小信息长度准则的 MML-EM 算法，该算法可以同时处理 Gauss 混合模型的模型选择(估计类别数)与参数估计两个问题。 数值试验表明，当 以接近真实值的整数初始化聚类的类别数时，MML-EM 算法能以较高的正确率选 择出最优类别数，但对聚类原型的估计可能出现较大偏差；当以远离真实值的 整数初始化类别数时，MML-EM 算法选择最优类别
16、数的正确率迅速降低，并且有 过高估计最优类别数的趋势。 针对这一情况，我们从理论上重新分析了 MML 准则，找出了出现这样结果的原因，并提出了一种改进算法(IMML-EM)。 数 值试验表明，我们改进的 IMML-EM 算法极大地克服了原 MML-EM 算法的上述缺点， 特别是它选择最优类别数的正确率会随着初始类别数的增加而迅速递增，这比 原 MML-EM 算法具有更广泛的实用性，因为人们在实际的聚类问题中常常没有关 于类别数的信息，只能在较大的范围内搜索最优类别数。 所以，我们的 IMML-EM 具有更大的实用价值。 聚类分析是知识发现、机器学习和数据挖掘等领域的一个非常重要的基本工具。 与传统的分类方法不同，聚类是在没有任何先验知识的前提下，仅根据数据间 的相似性将没有标号数据集划分成不同的类(或簇)，使得同一个类中的元素尽 可能相似，而不同类中的元素差别尽可能大，因此
