数学建模之模糊学(老师推荐).doc

三种典型聚类算法在职员评定中的应用 摘要：通过利用三种典型算法：Q－型模糊聚类算法、K-Means算法及K-medians算法，对公司职员的年终评定进行应用分析，得到了不同的聚类结果，通过对结果的分析比较、探讨，得出针对不同问题，应结合实际，有针对性地用不同算法更适合。并在此基础上，对聚类算法的聚类过程、本文后续工作进行了探讨总结。 关键词：数据挖掘，聚类分析，Q-型模糊聚类，K-means算法，K-medians算法 中图分类号：O235 文献标识码：A 1前言 随着信息化进程的发展，如何借助计算机的强大处理功能，从海量的繁杂数据中发现对我们有意义的信息并指导我们对研究工作做出更为准确、有效的预测和决策，这正是数据挖掘技术需要解决的问题。其中，聚类分析就是依据数据对象之间的关系及特点，使得同一组内的对象具有较大的相似性，不同组中的对象具有较高的相异性『1』，解决大量数据间的某种分类关系问题的一种重要方法。 2三种典型聚类算法 聚类算法有多种，本文选取三种主要的分类算法，从中探讨它们的异同，得出相关主要结论。 2.1 Q-型模糊聚类算法 聚类分析根据分类对象的不同分为R型和Q型两大类，R型是对变量指标进行分类处理，Q型是对样品进行分类处理，以下简单对Q型聚类进行阐述。 2.1.1 建立模糊关系 中的元素与的接近程度，称为相似系数(其中)。相似系数构成的模糊矩阵是上的模糊关系。其中确定相似系数的方法很多。 在实际的聚类问题中，先通过数据标准化后，通过建立上的模糊关系或模糊相似关系，以模糊相似矩阵为基础来讨论分类问题，然后用最大树法进行分类，根据阀值即可得出聚类结果。 2.1.2 结果评价准则 为了评价聚类结果的好坏，需要定义准则函数，聚类问题转化为使准则函数取极值 的优化问题。一般的聚类分析要解决两个问题，一个是如何确定类的个数，即把n个样本聚成多少类才合适，另一个是在给定类的个数c的情况下，如何把n个样本聚成c个类。 针对第一种问题，在模糊聚类分析中，对于不同的，可以得到不同的分类，从而形成动态模糊聚类图。但许多实际问题中如何根据的值来确定样本的具体分类。常用的两种方法有[2]： (1) 按照实际需要，由专家结合专业知识来确定值，得出在水平上的等价分类。 (2) 用F－统计量确定最佳值。 设论域为样本空间（样本总数为n），而每个样本由m个特征（即由试验或观察得到的m个数据）：。得到原始数据矩阵，其中称为总体样本的中心向量。 设对应于值的分类数为r，第j类的样本数为,第j类的样本记为：第j类的聚类中心为向量，其中为第k个特征的平均值： 作F－统计量 F＝ ， (1) 其中为类内样本间的距离。(1)式遵从自由度为（r－1，n－r）的F－分布。因此，F值越大，说明类与类之间的距离越大，表明类与类之间的差异越大，分类就越好。 如果F＞，则根据数理统计分析理论知道类与类之间差异是显著的，说明分类比较合理，如果满足不等式F＞的F值不止一个，则可以进一步考查差（F-Fa）的大小，从较大者中找一个满意的F 值就行了，即就圆满的解决了存在的第一个问题。 2.2 k-means聚类算法 K-means即K均值聚类算法。该算法根据聚类中心的均值进行分类划分，其处理过程如下:首先，随机选择k个对象，初始代表一个类的中心值。其次，对剩余的每个对象，根据其与类中心的距离，将它赋予最近的类，然后重新计算每个类的平均值。这个过程不断重复，直到准则函数收敛。通常，采用平方误差准则，其定义如下: ＝ 其中，E 表示所有聚类对象的平方误差的和，p是聚类对象，mi是类Ci的各聚类对象的平均值，表示类Ci的聚类对象的数目。 由于该方法对初值敏感，不同的初值、种子点、聚类个数K、初始划分等都可能会导致不同的聚类结果，此外，均值体现的是数据集的整体特征，而掩盖了数据本身的特性，由于目标函数局部极小值点的存在，该算法可能会陷入局部最优,无法达到全局最优，因此应用范围有一定的局限性。 2.3 K-medians聚类算法 K-medians方法的基本策略是通过避免孤立点，而选择类中最中心的对象作为参照点，然后计算其它点与这些参照点的距离，再按照距离重新聚类，分配给最近的一个簇，直到数据点不再改变所属的类为止,以此改进聚类的质量。聚类结果的质量用一个代价函数来估算,该函数可以度量对象与其参照对象之间的平均相似度。与Ｋ均值方法比较,这种划分方法,不采用簇中对象