当前位置： >>
基于K-均值聚类的小样本集KNN分类算法
第２８卷第５期 ２０１１年５月计算机应用与软件Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ ａｎｄ ＳｏｆｔｗａｒｅＶ０１．２８ Ｎｏ．５ Ｍａｙ ２０１１基于Ｋ－均值聚类的小样本集ＫＮＮ分类算法刘应东 牛惠民（：Ａｔ．州交通大学交通运输学院甘肃兰州７３００７０）
摘要ＫＮＮ及其改进算法进行分类时，如样本集中、样本过少或各类样本的密度差异较大，都将会影响最后的分类精度。提出一种基于聚类技术的小样本集ＫＮＮ分类算法。通过聚类和剪理，形成各类的样本密度接近的新的样本集，并利用该新样本集对类 标号未知数据对象进行类别标识。通过使用标准数据集的测试，发现该算法能够提高ＫＮＮ的分类精度，取得了较满意的结果。 关键词 Ｋ．均值聚类Ｋ最近邻 小样本ＫＮＮ ＣＬＡＳＳＩＦＩＣＡＴＩＯＮＡＬＧＯＲＩＴＨＭ Ｋ．ＭＥＡＮＳＦｏＲＳＭＡＬＬ ＳＡＭＰＬＥＳＥＴＳ ＢＡＳＥＤｏＮＣＬＵＳＴＥＲＤ‘Ｇ（Ｓｃｈｏｏｌ矿嘶ａｎｄＡｂｓｔｒａｃｔ ｂｅｃａｕｓｅ ｏｆ ｅｉｔｈｅｒ ｓｍａｌｌ ｓａｍｐｌｅｓｅｔ ｔｏｏＵｕ ＹｉｎｇｄｏｎｇＮｉｕ Ｈｕｉｍｉｎ Ｕｎｉｖｅｒｓｉｔｙ。Ｌａｎｚｈｏｕ力０Ｄ７Ｄ，ＧｔｔｌＭｕ，Ｃｈｉｎａ）ｔｈｅ ｆｉｎａｌ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｃｃｕｒａｃｙａＴｒａｎｓｐｏｒｔａｔｉｏｎ，Ｌａｎｚｈｏｕ ＪｉａｏｔｏｎｇＷｈｅｎ ＫＮＮ ａｎｄ ｉｔｓ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍｓ ｄｅｎｓｅｏｒａｒｅｐｅｒｆｏｒｍｉｎｇ ｃｌａｓｓｉｆｉｃａｔｉｏｎ，ｉｔ ａｌｗａｙｓ ｉｎｆｌｕｅｎｃｅｓｔｏｏ ｆｅｗ ｔｈｅ ｓａｍｐｌｅｓｏｒｔｏｏ ｌａｒｇｅ ｔｈｅ ｄｅｎｓｉｔｙ ｄｉｆｆｅｒｅｎｃｅｓｏｎａｍｏｎｇｓａｍｐｌｅｔｏｖａｒｉｏｕｓ ｋｉｎｄｓ ｏｆ ｓａｍｐｌｅｓ．Ｔｈｅ ｐａｐｅｒ ｐｒｏｐｏｓｅｓｓｅｔＫＮＮ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍｂａｓｅｄｃｌｕｓｔｅｒｉｎｇ ｔｅｃｈｎｏｌｏｇｙ．Ａｎｅｗｎｅｗｉｓ ｇｅｎｅｒａｔｅｄ ｔｈｒｏｕｇｈ ｃｌｕｓｔｅｒｉｎｇ ａｎｄ ｅｄｉｔｉｎｇｗｈｉｃｈ ｃｏｎｔａｉｎｓ ｖａｒｉｏｕｓ ｋｉｎｄｓ ｏｆ ｓａｍｐｌｅｓ ｗｉｔｈ ｃｌｏｓｅ ｄｅｎｓｉｔｉｅｓ．Ｔｈａｔｓａｍｐｌｅｓｅｔｉｓ ｕｓｅｄｃｌａｓｓｉｆｙ ａｎｄ ｌａｂｅｌ ｄａｔａ ｏｂｊｅｃｔｓ ｗｈｏｓｅ ｃｌａｓｓｉｆｉｃａｔｉｏｎｉｍｐｒｏｖｅ ＫＮＮ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｃｃｕｒａｃｙａｎｄ ｌａｂｅｌ ｎｕｍｂｅｒｓ ａ弛ｕｎｋｎｏｗｎ．Ｔｅｓｔｓ ｂｙ ｓｔａｎｄａｒｄ ｄａｔａｓａｔｉｓｆａｃｔｏｒｙ ｒｅｓｕｌｔｓ．ｓｅｔｓｒｅｖｅａｌ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍｃａｌｌａｎｄ ｏｂｔａｉｎＫｅｙｗｏｒｄｓＫ??ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇＫ－ｎｅａｒｅｓｔ?－ｎｅｉｇｈｂｏｒＳｍａｌｌｓａｍｐｌｅｓｅｔ０引言１ＫＮＮ算法ＫＮＮ分类方法属于传统统计模式识别算法，其最基本的算ＫＮＮ分类算法是一种典型的非参数的惰性学习方法。它 比较简单，并且实现起来比较容易，但是当训练样本集较大时， 计算开销很高。目前主要通过两种途径来减小ＫＮＮ方法的计 算量：一种途径是通过快速搜索算法，在尽量短的时间内找到测 试样本的最近邻ｕ’２１；另一种途径是在原来的训练样本集中选 取一些代表样本作为新的训练样本”’４ Ｊ。为了提高ＫＮＮ算法 的性能，人们还通过改进距离度量ｕＪ、使用加权函数。刮等技术 来提高ＫＮＮ分类的性能。然而如果训练数据集很小，带有类标 签的数据集中的数据本来就不够用来对未标签数据进行分类， 缩小查找范围和最近邻编辑方法，还将更进一步地影响最后的 分类精度。如何充分利用这－ｄ，部分标签数据提高分类精度是 本文研究的内容。本文提出了一种基于聚类技术，在各样本类 具有相近密度条件下的ＫＮＮ算法，通过基于带类标记的指导性 聚类，剔除原样本集中的“噪声数据”，从未标签数据集中选择 一部分数据对其进行类别标号，将其加入训练集中作为标签数 据集，并且使其各样本类的密度接近，然后使用扩展后的训练集 对原来所有的未标签数据进行分类，从而提高ＫＮＮ算法检测的 准确度。法步骤如下： （１）对一个待分类的数据对象ｘ，计算它与训练集尺中的 每个数据对象的距离； （２）找出未标签数据集Ｕ中待分数据集中对象省与训练集 Ｒ中的数据对象距离最近的ｋ个； （３）依次统计出这ｋ个数据对象的所属类别，找出包含最 多个数的类； （４）将待分数据算划分到此类中； （５）重复以上步骤，直到所有待分数据分类结束； （６）输出标识后的数据集。 影响ＫＮＮ算法分类准确度的因素主要有：（１）ｋ值的设定。 如果ｋ值取的过大，那么并的ｋ近邻中必将包括其它类别的数据 对象，甚至某一类的数据对象数目超过了茹真正所属类别的数 据对象数目，从而导致菇的类别标号错误；如果ｋ值取得过小，那 么就有可能受到噪声数据的影响。（２）样本集的密度。在样本集收稿日期：２０１０―１１一１２。甘肃省自然科学研究基金规划项目（１０ ｌＯＲＪＺＡ０６９）。刘应东，讲师，主研领域：计算机在交通运输中的应用。万方数据第５期刘应东等：基于Ｋ－均值聚类的小样本集ＫＮＮ分类算法１ １３中数据分布不均匀，尤其在样本各类之间的密度差异比较大的 情况下，很大可能导致使待分类菇归于密度较大的类中。（３）样 本的数量。当训练样本集太大或数据的维数较高时，计算的代价 会很高。但如果样本数据集尺中的数据对象数目过少，标签数据 不能真正反映整个数据集Ｄ（此处Ｄ表示数据集尺和ｕ并集）中 数据对象的真正分布时，算法执行后的误分率较大。基于以上 原因，本文提出了基于聚类技术的小样本集ＫＮＮ算法。将归于类２。因此，各聚类中排除掉距聚类中心距离比较大的 一些边缘数据（或只保留每类中的距聚类中心某一比例的标记 数据对象）。，三是使样本集中的样本分布趋于均匀。对于任意处于类边 界区域的数据茹，在数据分布不均匀的情况下，尤其在样本各类 的密度差异比较大的情况下，使用ＫＮＮ分类算法，当最近邻阈 值．｜｝选择不当时，很大可能导致使聋归于密度较大的类中。为了 提高分类精度，在扩充样本时，尽量使各类间密度接近，各类中 样本分布均匀。 扩充训练集Ｒ的算法如下： （１）输入数据集Ｄ为数据集Ｒ和￡，并集（此时的ｕ的各数 据已经全部带有标记）。 （２）去掉在原样本集中原来所属类和聚类后所属类不同样 本（噪声数据）的类标记。’２基于Ｋ－均值聚类的ＫＮＮ算法本文提出的改进分类算法主要是将Ｋ．均值和ＫＮＮ两种方 法相结合，采用聚类的方法，剔除原样本中的一些噪声数据，从 未标签数据集￡，中选择适当数量的数据以扩充训练集尺中的每 一类，然后利用扩充Ｒ使用ＫＮＮ算法对剩余的ｕ中数据进行类 别标号。算法包括以下三个步骤： （１）用Ｋ一均值聚类算法聚类尺和部分Ｕ组成的数据集； （２）在各聚类中选择适当数量的数据以扩充训练集冗； （３）使用传统ＫＮＮ算法分类对未标记数据分类。 其中第（３）步采用传统的ＫＮＮ算法，不再赘述。这里主要 研究的是如何对未标记数据如何聚类、选择那些数据对象可以 使每个类的数据分布比较均匀。２．１（３）计算Ｒ的各类中带标记数据对象到样本中心的最大距 离ｄ；＝ｍａｘＩ毛一吒Ｉ，吒为Ｓ。类中所有带标记的数据对象。在各 聚类Ｓ；中去掉距离大于ｄ；的数据对象的标记（或只保留聚聚类 中心较近的某一比例的数据）。 （４）选取尺中的一个类Ｓ；作为样本选取对象。 （５）在类Ｓ。中取任意一数据对象茁，计算ｚ与Ｓ。类中所有有 标签标记数据对象之间的距离。如果所有距离均不小于阈值ｅ， 并且距聚类中心盈距离不大于ｄ；，则给对象聋加类标记，否则把 ｚ从类ｓ。中排除。 （６）返回步骤（５），直到类Ｓ；中所有对象都有类标记。 （７）返回步骤（４），直到Ｒ中所有对象都有类标记。 在算法中，步骤（２）至步骤（５）分别用来实现扩充训练集尺 的三个目的。其中步骤（２）目的是去除噪声数据；步骤（３）的目 的是在各聚类中排除掉距聚类中心距离比较大的一些边缘数 据，选取距聚类中心距离较近的数据作为样本集的候选集；步骤 （４）、步骤（５）目的是对于每一个类，均以同一个阈值ｅ作为基 准，选取的样本间的距离均大于阈值ｅ。经过样本的选择，使得 个样本类样本数据分布趋于均匀，数据对象之间的距离接近 ｅ（ｅ可以根据样本的密度而定，这里的ｅ定义为原样本中最近的 两个样本数据的欧氏距离）；保留了原样本数据，保证了整个少 数类的新样本具有更好的覆盖性和代表性，更加符合原样本空 间的分布。Ｋ－均值聚类作为算法第一步的聚类，其主要目的是为了扩充样本集中的样本数量。首先选定样本集中各类的中心作为初始聚类中 心，然后再用Ｋ?均值算法将其余的点化分到各类别中去。假设 样本集Ｒ＝｛毛，茗２，…，膏。｝含ｍ（ｍ＜Ｉｔ）个类型，即Ｒ＝ＳＩｕ…ｕ Ｓ。。聚类的步骤如下：ｕｓ２（１）输人数据集Ｄ为数据集Ｒ和￡，并集；（２）选取ｍ个初始聚类中心为尺中ｍ个类的中心＝：，：；，…， ：：（右上标为寻找聚类中心的迭代次数Ｐ，即Ｐ＝１）；（３）计算每个数据对象与聚类中心的距离Ｄ（毛，Ｚ），ｉ＝ ｌ，２，…，Ｉｔ，．『＝ｌ，２，…，ｍ，如果满足Ｄ（％，艺）＝ｍｉｎ｛Ｄ（ｘｉ， 彳）Ｊ＝ｌ，２，…，ｎ｝，贝４茹‘Ｅｓ。；（４）计算新的聚类中心才“（其中＿『＝１，２，…，ｍ）；（５）判断：若才＝彳“，其中＿『＝１，２，…，ｍ，转到步骤（６），否则转到步骤（３）。 （６）给￡，中各数据对象置类标记。 这一步骤中选择不同的初始聚类中心，将决定不同的聚类 结果，从而导致聚类结果的不确定性，所以初始聚类中心的选择 就显得尤为重要¨Ｊ。在本算法中，选用原样本集的各类的中心 作为初始聚类中心，保证了聚类结果分布在原样本各类中。通 过聚类，各个簇中均获取到一定数量的新样本，保证了每个类的 样本具有更好的覆盖性和代表性，更加符合原样本空间的分布。３实验结果与分析试验数据是使用标准数据集ＵＣＩ中的ＩＲＩＳ数据集构造的 两组测试数据。第一组是从ＩＲＩＳ中随机选取２０个数据对象样 本集，其余的１３０个数据作为测试数据集；第二组是从ＩＲＩＳ中 随机选取５０个数据对象作为样本集，其余的１００个数据作为测 试数据集。其中第一组样本集中有６个属于ＩＲＩＳ－ｓｅｔｏｓａ、有６个 属于ＩＲＩＳ．ｖｅｒｓｉｃｏｌｏｒ、有８个属于ＩＲＩＳ?ｖｉｒｇ】＂ｎｉｃａ；第二组样本集中 有１４个属于ＩＲＩＳ．ＳｅｔＯＳ８、有１７个属于ＩＲＩＳ?ｖｅｒｓｉｅｏｌｏｒ、有１９个属 于ＩＲＩＳ．ｖｉｒｇｉｎｉｃａ。为了验证基于聚类技术的小样本集ＫＮＮ算 法，使用两组数据对其有效性进行分析。 第一组数据试验结果如图１所示。ＫＮＮ算法最近邻阈值ｋ 的值在Ｉ到４之间相对较好，大于４时分类误差率较大，而本算 法最近邻学习阈值＿｜｝的值在ｌ到７之间均优于ＫＮＮ算法，大于５ 时分类误差率趋于平稳。这是因为在ＫＮＮ算法中，当ｋ的值较大 ｏ（下转第１２５页）２．２选择适当数量的数据以扩充训练集Ｒ第二步选择适当的数据对象，其主要有以下三个目的： 一是去除掉原样本集中的“噪声数据”。在原样本集中，有 些样本距其所属的类中心较远，聚类后它们属于另外的类，正是 这些数据在使用传统的ＫＮＮ算法分类时，会严重影响分类的误 分率。因此，将其从样本集中去除。 二是为了不使扩充的样本过分的影响分类的结果。对于数 据对象茹，如果按照原样本集使用ＫＮＮ算法进行分类，将归于类 ｌ，但是用聚类后的样本集，如果在菇附近类２密度较大时，分类万方数据第５期李李等：一个公开可验证的秘密共享新个体加入协议１２５ｓ；；在协议中增加了计算并公布以＝∥一ｔ‘”ｎ，由于离散对数在ｌ第二组数据试验结果如图２所示。基于聚类技术的ＫＮＮ 算法与传统的ＫＮＮ算法和均在最近邻阈值ｋ的值在ｌ到５之间 相对较好，误分率差距不大；当ｋ值较大时，误分率差优于传统 的ＫＮＮ算法，稳定性明显占优，没有象传统的ＫＮＮ算法一样对 ｋ值那样非常敏感。这是因为样本数据相对于第一组的样本数 据来说，数量较大，优势在于样本数据密度比较均匀，对较大的 最近邻闯值ｋ更稳健。计算上的不可行，从而无法求得８ｉ毗ｎ＋１），由％＋Ｉ＝∑５ｉ毗（ｎ、‘＝ｌ＋１），因此公开参数仉不会泄露旧成员只的秘密份额ｓ；亦不会 泄露新个体Ｐ川的秘密份额ｓ。。本协议使用的是非交互式的 零知识证明协议，协议简单，不需交互，具有较高的性能。４结论本文利用高效的非交互式零知识证明对文献［４］中构造的 协议进行改进，提出了一种公开可验证的秘密共享新个体加入 协议。新协议弥补了原协议中新个体的秘密份额仅能被他自己 验证而不被其他人验证，而出现的新个体与密钥分发者勾结欺 骗的安全性缺陷。经过分析与验证，新协议是正确且安全的。｜ｉ／ 。：蠢嘉答篡志琵贼糊削嘎滩／１ ｌ／―●ｒ－传坑的ＫＮｈＩ髯法＿ ．Ｉ－…?…＾……－?雳～］Ｚ．Ｉ－－＂－０●参考文献［１］ＳｈａｍｉｒＡ．Ｈｏｗｔｏ最近邻闻值ｋ的僵ｓｈａｒｅａｓｅｃｒｅｔ［Ｊ］．Ｃｏｍｍｕｎｉｃａｔｉｏｎ ｏｆ ｔｈｅ ＡＣＭ．图２大样本集下常规ＫＮＮ与基于聚类技术的ＫＮＮ误分率比较１９７９，２２（１１）：６１２―６１３． ［２】Ｂｌａｋｌｅｙ Ｇ Ｒ．Ｓａｆｅｇｕａｒｄｉｎｇ ｅｒｙｐｔｏｇｒａｐｈｉｃ ｋｅｙｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇ ｏｆＡＦＩＰＳ Ｎａｔｉｏｎａｌ Ｃｏｍｐｕｔｅｒ Ｃｏｎｆｅｒｅｎｃｅ．Ｎｅｗ ３１３―３１７．Ｙｏｒｋ：ＡＦＩＰＳ从图１和图２中可以看出。在小样本集情况下应用基于聚 类技术的ＫＮＮ误分率改善效果明显优于在大样本集情况下。 主要原因是在小样本集情况下原来的样本集不能完全代表数据 集的分布特性，且样本的分布不均匀；而基于聚类技术的ＫＮＮ 算法通过扩充样本集，改善样本分布的提高分类的准确率。因 此，本算法主要适用于基于小样本分类的情况。 同时从图中也可以看出，传统ＫＮＮ算法对于最近邻阈值ｋ 比较敏感，而对于本算法，对于最近邻阈值ｋ选择范围较宽，误 分率较为稳定，分类精度较为满意。ＢＰｒｅｓｓ。１９７９：［３］董攀，况晓辉，卢锡城．一种秘密共享新个体加入协议［Ｊ】．软件学 报，２００５，１６（１）：１１６―１２０．［４］许静芳，崔国华，程琦，等．秘密共享新个体加入协议的安全性分析与改进［Ｊ］．通信学报，２００９，３０（１０）：１１８―１２３．［５］王锋，张建中．一个新的可验证的秘密共享新个体加入协议［Ｊ］．计算机工程与应用，２００７，４３（２８）：１２２―１２４，１４９． ［６］Ｙｕ Ｊ，ＫｏｎｇＦ，ＨａｏＲ，ｅｔ ａ１．Ｈｏｗ ｔｏ ｐｕｂｌｉｃｌｙ ｖｅｒｉｆｉａｂｌｙ ｅｘｐａｎｄｉｎａ ｓｅｃｒｅｔｍｅｍｂｅｒｗｉｔｈｏｕｔ ｃｈａｎｇｉｎｇ ｏｌｄ ｓｈａｒｅｓｉｎｇｓｈａｒｉｎｇ ｓｃｈｅｍｅ［Ｃ］／／Ｐｒｅｃｅｅｄ? Ｉｎｆｏｒｍａｔｉｅｓ，２００８：１３８４结束语本文提出了一种基于聚类技术的小样本集ＫＮＮ分类算法。ｏｆ ＬＮＣＳ ５０７５，Ｉｎｔｅｌｌｉｇｅｎｃｅ ａｎｄｓｅｃｕｒｉｔｙ―１４８．［７］ＳｈｏｅｍａｋｅｍＢ．Ａｓｉｍｐｌｅ ｐｕｂｌｉｃｌｙ ｖｅｒｉｆｉａｂｌｅｔｏｓｅｃｒｅｔｓｈａｒｉｎｇ ｓｃｈｅｍｅ ａｎｄｉｎ该算法通过对标签数据集的学习，将部分未标签数据集加入到 标签数据集中用来对数据进行分类，通过在ＵＣＩ数据集中ＩＲＩＳ 上的测试，得到了较为满意的效果。尤其是对于小样本数据集 来说，效果更为明显。ｉｔｓ ａｐｐｌｉｃａｔ?ｉｏｎｅｌｅｃｔｒｉｃｖｏｔｉｎｇ［ｃ］／／Ｐｒｏｃｅｅｄｉｎｇ ０ｆ ＡｄｖａｎｃｅｓＣｒｙｐｔｏｌｏｇｙ―Ｃｒｙｐｔｏ’９９．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，１９９９：１４８―１６４．（上接第１１３页） 时，会使原来基本平衡的样本数据集变成了不平衡数据集，测试 数据集中的数据对象更多的被加入到样本数较多的类中，所以 误差率较高。而对于聚类技术的小样本集ＫＮＮ算法来说，通过 聚类扩展了样本数据，通过样本选择，使样本集始终保持比较平 衡。从整体来看，本算法在针对于小样本进行分类时。明显优于 传统的ＫＮＮ算法。参考文献［１］余小鹏。周德翼．一种自适应ｋ－最近邻算法的研究［Ｊ］．计算机应用研究，２００６，２３（２）：７０―７２．［２】桑应宾，刘琼荪．改进的ｋ－ｎｎ快速分类算法［Ｊ］．计算机工程与应用，２００９，４５（１１）：１４５―１４６．１６１． ［３］熊忠阳，杨营辉。张玉芳．基于密度的ｋＮＮ分类器训练样本裁剪方 法的改进［Ｊ］．计算机应用，２０１０，３０（３）：７９９―８０１，８１７． ［４］Ｇｕａｎ Ｄ，Ｙｕａｎｗ，ｋＹ Ｋ，ｅｔ丑１．Ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｅｄｉｔｉｎｇ ａｉｄｅｄ ｂｙＵＳ－ｌａｂｅｌｅｄ ｄａｔａ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ．２００９，１７９（１３）：２２７３―２２８２． ［５］Ｗａｎｇ Ｊ，Ｎｅｓｋｏｖｉｅ Ｐ，ＣｏｏｐｅｒａＬＮ．Ｉｍｐｒｏｖｉｎｇｎｅａｒｅｓｔｎｅｉｇｈｂｏｒ ｒｕｌｅ ｗｉｔｈｓｉｍｐｌｅ ａｄａｐｔｉｖｅｄｉｓｔａｎｃｅ ｍｅａｓｕｒｅ［Ｊ］．Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ Ｌｅｔｔｅｍ，２００７，２８（２）：２０７―２１３．［６］ＪａｈｒｏｒｍＭｚ，Ｐａｒｖｉｎｎｉａ Ｅ，Ｊｏｈｎ Ｒ．Ａ ｍｅｔｈｏｄ ｏｆ ｌｅａｒｎｉｎｇｔｏｗｅｉｇｈｔｅｄｓｉｍｉ－ｌａｒｉｔｙ ｆｕｎｃｔｉｏｎ 最近邻闲值ｋ ｆｏｒｍａｔｉｏｎｉｍｐｒｏｖｅｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆｎｅａｒｅｓｔｎｅｉｇｈｂｏｒ［Ｊ］．Ｉｎ－Ｓｃｉｅｎｃｅｓ，２００９，１７９（１７）：２９６４―２９７３． ａｌｇｏｒｉｔｈｍ［Ｊ］．ＩＥＥＥ Ｔｒｔｍｓｏｎ［７］Ｋｒｉｓｈｍａ图１ 小样本集下常规ＫＮＮ与基于聚类技术的ＫＮＮ误分率比较Ｋ，Ｍｕｒｔｙ Ｍ Ｎ．Ｇｅｎｅｔｉｃ Ｋ?ｍｅａｎｓＳｙｓｔｅｍ。Ｍａｎ。ａｎｄ Ｃｙｂｏｍｅｔｉｅｓ：Ｐａｒｔ Ｂ，１９９９，５（１）：９６―１００．万方数据基于K-均值聚类的小样本集KNN分类算法作者： 作者单位： 刊名： 英文刊名： 年，卷(期)： 刘应东， 牛惠民， Liu Yingdong， Niu Huimin 兰州交通大学交通运输学院,甘肃,兰州,730070 计算机应用与软件 COMPUTER APPLICATIONS AND SOFTWARE )本文链接：http://d..cn/Periodical_jsjyyyrj.aspx本系列意在长期连载分享，内容上可能也会有所增删改减；
因此如果转载，请务必保留源地址，非常感谢！
知乎专栏：
博客园：（暂时公式显示有问题）
当我们在谈论kmeans：总结
　　通过前面阅读K-means相关论文，大致能梳理出K-means算法发展过程中的一些轨迹。由于本人所阅读的仅仅是一部分，因此还会有更多的方面，欢迎大家补充（补充时请给出具体例子）。
K-means算法的提出
对K-means算法的性质进行分析的文章相继发出
对K-means算法思想进行扩展：
有作者提出“Maximum Entropy”算法，并表示K-means为其一种特殊形式
后又有作者提出“Mean Shift”算法，并表示“Maximum Entropy”也是其特殊形式
针对K-means缺陷，对K-means算法进行修改（一般仅适用于某场景）：
提出online的K-means
提出针对非凸数据集的K-means
提出应用在FPGA中的K-means
提出自动对特征进行加权的K-means
Intelligent K-means算法使用异常检测的思想聚类
对K-means算法进行优化：
KD树加速的K-means
利用SVD分解加速K-means
K-means++的初始化聚类中心算法
将K-means与新提出的思想融合：
结合Ensembling与K-means
K-means存在的问题
K-means由于简单有效被大量的用于数据预处理、数据分析等。在K-means被实际应用的过程中，大家也逐渐发现它本身存在很多的问题。如：
聚类数量K需要提前设定，并影响聚类效果
聚类中心需要人为初始化，并影响聚类效果
异常点的存在，会影响聚类效果
只能收敛到局部最优
其中每个问题都有作者分析，并尝试提出解决办法：
KD树加速K-means
聚类数量K需要提前设定，并影响聚类效果
各种估计K的方法
聚类中心需要人为初始化，并影响聚类效果
K-means++方法
其他初始化聚类中心方法
异常点的存在，会影响聚类效果
数据预处理
只能收敛到局部最优
以下我们对其中两点（“类别数量估计”，“初始化聚类中心”）进行更多的介绍
类别数量估计
估计类别数量，现在还没有很通用的方法。以下介绍常见的估计类别数量的一些方式
数据的先验知识，或者数据进行简单分析能得到
基于变化的算法：即定义一个函数，随着K的改变，认为在正确的K时会产生极值。如Gap Statistic（Estimating the number of clusters in a data set via the gap statistic, Tibshirani, Walther, and Hastie 2001），Jump Statistic （finding the number of clusters in a data set, Sugar and James 2003）
基于结构的算法：即比较类内距离、类间距离以确定K。这个也是最常用的办法，如使用平均轮廓系数，越趋近1聚类效果越好；如计算类内距离/类间距离，值越小越好；等。
基于一致性矩阵的算法：即认为在正确的K时，不同次聚类的结果会更加相似，以此确定K。
基于层次聚类：即基于合并或分裂的思想，在一定情况下停止获得K。
基于采样的算法：即对样本采样，分别做聚类；根据这些结果的相似性确定K。如，将样本分为训练与测试样本；对训练样本训练分类器，用于预测测试样本类别，并与聚类的类别比较。
初始化聚类中心
接下来介绍几个看到的初始化聚类中心的方法。需要强调的是，在任何场景下都合适的方法是不存在的。理想情况应该是针对数据的特点，挑选或设计出适合的方法。
K-means++已经被证明是一种简单、好用的方法
先计算整体样本中心，然后根据样本点到中心的距离，由近至远均匀采样作为初试聚类中心
初步将数据分成K个区域，将每个区域中心作为初始聚类中心
计算出每个点的”密度“，认为”密度“较大的是聚类中心。先把”密度“最大的挑出作为第一个聚类中心，从剩下的点中找出密度最大，且离所有已有聚类中心大于一定距离的点作为下一个聚类中心，直到选择了K个
计算整体均值，作为第一个聚类中心。从剩下的点中顺序寻找，当遇到离所有已有聚类中心大于一定距离的点，则作为下一个聚类中心，直到选择了K个
其他聚类算法总结
聚类算法非常多，这里仅列举在前文中介绍的几个常用聚类算法。更多的聚类算法在以后实践过程中，会继续补充
基于层次聚类的算法
算法：Hierarchical Clustering
优点：适用于任意形状和属性的数据集；灵活控制不同层次的聚类粒度；
缺点：时间复杂度高；
基于平方误差的聚类算法
算法：Fuzzy C-Means
优点：能求出样本属于每一类的概率；
缺点：结果依赖于对初始聚类中心的选择；容易陷入局部最优解；对K值的选择没有准则可依循；对异常数据较为敏感；
基于模型的聚类算法
算法：Mixture of Gaussians
优点：对样本精确建模；参数求解简单；
缺点：要求样本服从某种分布；
基于密度的聚类算法
算法：DBSCAN；Density Peaks
优点：不需要设定类别数量；适用于任意形状的数据集；
缺点：时间复杂度高；密度不均匀时效果较差
阅读(...) 评论()(window.slotbydup=window.slotbydup || []).push({
id: '2014386',
container: s,
size: '234,60',
display: 'inlay-fix'
&&|&&0次下载&&|&&总9页&&|
您的计算机尚未安装Flash，点击安装&
阅读已结束，如需下载到电脑，请使用积分（）
下载：5积分
0人评价11页
5人评价11页
0人评价6页
0人评价2页
0人评价5页
所需积分：（友情提示：大部分文档均可免费预览！下载之前请务必先预览阅读，以免误下载造成积分浪费！）
（多个标签用逗号分隔）
文不对题，内容与标题介绍不符
广告内容或内容过于简单
文档乱码或无法正常显示
文档内容侵权
已存在相同文档
不属于经济管理类文档
源文档损坏或加密
若此文档涉嫌侵害了您的权利，请参照说明。
我要评价：
下载：5积分模式识别考试
3.请详细写出感知器训练算法步骤。设训练样本集X={x1,x2,…,xn}，其中xk属于wi或者wj，且xk的类别是已知的。为了确定加权向量w*，执行下面的训练算法a)给定初始值：置k=0，权向量w(k)为任意值，可选常数0＜c≤1)输入样本xm∈{x1,x2,…,xn}，计算判决函数值g(xm)=wT(k)xmc)按如下规则修改权向量i.若xm∈wi，且g(xm)≤0，则w(k+1)=w(k)+cxmii.若xm∈wj，且g(xm)＞0，则w(k+1)=w(k)-cxmd)令k=k+1，返回第二步，直到w对所有样本稳定不变，结束4.请详细写出Fishe算法实现步骤。o在两类问题中，设分别属于wi与wj的样本数为n1与n2，n=n1+n2o令yk=wTxk(k=1,2,…,n)，由子集X1与X2映射后的两个子集为Y1与Y2。o使Y1与Y2最容易区分开的w方向正好是分类超平面的法线方向。o定义Fishe准则函数。使得JF最大的解w*就是最佳解向量o以上工作是将d维空间的样本映射到了一维样本集，这个一维空间的方向是相对于Fishe准则为最好的。o我们还需要解决分类问题。将d维分类问题转化为一维分类问题后，只需要确定一个阈值点，将投影点与阈值点比较，就可以做出决策。5.什么是两分剪辑近邻法与压缩近邻法。将原始样本随机分为两个集合：预测集T和参考集R，来自预测集和参考集的样本分别完成考试和参考任务，相互独立。对预测集T中的所有样本，利用参考集采用近邻法对其进行分类决策，如果决策结果与实际类别不同，则从预测集中删除该样本，最后得到经过剪辑的考试样本集TE。利用考试样本集TE，采用最近邻法对测试样本进行分类决策。剪辑近邻的结果只是去掉了两类边界附近的样本，而靠近两类中心的样本几乎没有被去掉。在剪辑的基础上，再去掉一部分这样的样本，有助于进一步缩短计算时间和降低存储要求。这类方法叫作压缩近邻法。6.请详细介绍初始聚类中心的选择方法。任取前c个样本点作为初始聚类中心凭经验选择将全部数据随机分为c类，计算其重心，将重心作为聚类中心密度法选择代表点（具有统计特性）从c-1类划分中产生c类划分问题的初始聚类中心7.请描述K均值聚类算法。a)给定允许误差?，令t=1)初始化聚类中心wi(t)，i=1,2,…,cc)修正dij，d)修正聚类中心wi(t+1)
& 果果文库所有资源均来源于互联网，仅供网友学习交流，若侵犯了您的权益，请联系我们予以删除。
10609&&人浏览
1884&&人浏览
10583&&人浏览
7706&&人浏览
4438&&人浏览
4278&&人浏览
15997&&人浏览
15082&&人浏览
9376&&人浏览
7838&&人浏览
8413&&人浏览
11636&&人浏览
8187&&人浏览
1258&&人浏览
3329&&人浏览
本文标题：模式识别考试 链接地址：
copyright@ 2013- Inc. All Rights Reserved 果果文库 版权所有 联系站长: ; 经营许可证编号:浙ICP备号}