基于改进的自组织竞争神经网络的聚类分析.docx

南昌航空大学硕士学位论文开题报告基于改进的SOFM聚类方法研究学 号：100081002005姓 名：肖鹏导 师：余达祥 学 院：信息工程学院专 业：信号与信息处理研究方向：人工神经网络日 期：2011年10月南昌航空大学研究生学院制目录一、选题依据3二、本课题国内外研究状况及发展趋势3国内外研究状况3聚类的要求7聚类算法的发展趋势7三、人工神经网络的发展7四、竞争性网络在聚类分析中存在的问题8五、论文预期成果的理论意义和应用价值9六、课题研究的主要内容9研究目标9研究内容9创新点9实验大致流程10七、研究计划进度与安排10八、传统的SOFM神经网络结构和学习算法10SOFM神经网络结构10传统的SOFM神经网络算法具体描述11九、改进的SOFM算法11孤立点的检测12SOFM神经网络算法具体描述12kmeans算法和sofm算法性能之间的比较15参考文献17一、选题依据在人类从工业社会向信息社会演进的今天，计算机越来越普及，人们获取的数据和信息也越来越多。过去的数十年中，存储数据的爆炸式增长业已激起对新技术和自动信息处理工具的需求，以便将海量的数据和信息转化为有用的知识。人们希望由计算机驱动的机器或者设备能代替或扩展人类的部分脑力劳动，让机器也具有认知学习思考的能力，要做到这些，首先计算机要对数据进行挖掘，对信息进行提取，聚类分析算法是数据分析与挖掘的一个必备工具。二、本课题国内外研究状况及发展趋势国内外研究状况现有的典型聚类分析算法有：（1） 划分式聚类算法：最典型的划分式聚类算法是k-means算法和k-medoids算法。K-means算法的基本流程如下：首先选取k个对象作为初始的k个簇心，然后将剩余的每个对象根据其与各个簇心的距离分配到最近的簇心中，重新计算每个簇的簇心，直到准则函数收敛为止。平方误差准则函数：式中表示每个类的中心点，这个点可以是质心，也可以是该类的代表点。k-means算法对类球形且大小差别不大的类簇有很好的表现，实现非常简单，运算效率也很高，适合对大型数据进行聚类处理。缺点是聚类结果跟初始点的选择有很大的关系，不同的初始点选择对结果的影响很大，而且不能用于非凸集的数据，容易受噪声数据的影响。对k-means算法的改进方法也很多，2008年国内的雷小锋1等给出了K-MeansSCAN的算法，算法采用k-means对数据进行多次预聚类，对预聚类结果构造子簇的加权连通图，并根据连通性合并子簇。2009年，Xiong H2等分析了数据集本身的分布与k-means算法的聚类结果之间的关系。2007年，钟国亮3等给出了一种基于对称距离测度的k-means算法。2005年，Huang Joshua Zhexu4给出了一种在迭代划分过程中自动变换变量权值的k-means算法。2008年，Wu F.X5等采用遗传加权k-means算法来分析基因表达数据。同年，Bagirov Adil M6提出了一种新的全局k-means算法，算法能够克服k-means算法对初始点选择敏感的问题。2003年，Hamerly G7等讨论了如何从聚类过程中学习k值的方法。2008年，Du8等将粒子群优化方法和k-means算法结合用于分析基因表达数据。k-medoids算法是直接选取一个对象作为一类的代表，这个代表为最靠近中心的一个对象。这种算法由于采用了实际的对象来代替中心店，因此可以消除孤立点带来的不利影响。（2） 层次化聚类算法这种算法的基本思路是首先将所有的对象看成是单独的个体类，通过计算类间的距离来选择最小距离的两个类合并成一个新类，再重新计算新类和其它类之间的距离，同样选择最小距离的两个类合并，依次迭代合并直到没有合并为止。层次聚类算法的两个主要缺陷：（1）聚类结果的类个数难以确定；（2）聚类过程中对象的合并是不可逆过程，影响了聚类的结果。当然对层次聚类算法，前人也做了很多的改进工作。2008年，Goldberger Jaco9等人提出了一种基于匈牙利方法的层次聚类方法，使用匈牙利方法来构建基本的聚类块划分。同年，Loewenstein Yani10等改进了非加权组平均法（UPGMA）方法，用于大规模的蛋白质序列聚类分析，算法可以在内存受限的环境下进行大数据量的聚类分析。2007年，Wang H.11等采用改进的层次聚类算法分析基因表达序列数据。2006年，Arifin Agus Zainal12 等采用层次聚类算法对图像进行分割。由于层次聚类算法适用于大量数据的处理，因此被广泛应用于分析蛋白质数据上。（3） 基于密度和网格的聚类算法基于密度的聚类算法采用局部数据的密度作为标准来划分数据。此算法的主要思想是将空间中的数据按照聚集密度的高低来划分，密度相近的划分成一个类。相对于k-means算法，此种算法能够发现任意形状的数据分布。如何定义数据分布的密度是基于密度的聚类算法研究的关键，通常情况下基于密度的聚类算法计算数据所处空间的密度，如果密度高于某个阀值就认为是高密度区，反之为低密度区；最后将得到高密区的部分与低密度区分离。具有代表性的基于密度的聚类算法有：DBSCAN13，GDBSCAN14，OPTICS15，DENCLUE16，CLIQUE17等。基于网格的聚类算法从输入对象中构建一个网格结构，围绕模式组织由矩形块划分的值空间，每个对象分类到一个单元或网格。（4） 模糊聚类算法1969 年,Ruspini 首次将模糊集理论应用到聚类分析中,提出了模糊聚类算法(fuzzy c-means,简称 FCM).模糊聚类算法最开始先初始化构建一个初步的划分，将数据划分为K个模糊组，构建一个隶属矩阵U，通过隶属矩阵求解每个模糊组的中心点，根据计算出的中心点来获得当前划分的目标函数值，将当前获得的目标函数值与上一次获得的目标函数值进行比较，如果满足截止条件则终止算法，否则更新隶属矩阵U，重复以上步骤。具体步骤如下：初始化：给定聚类类别数C，2，N是数据个数，设定模糊系数m和迭代停止阈值，随机初始化隶属度矩阵，初始化聚类原型模式，设置迭代计数器b=0。步骤1 计算隶属度矩阵元素，对于任意的i,j，如果，为第i个聚类中心与第j个数据点间的欧几里得距离，为模糊组i的聚类中心，则隶属度矩阵元素为，如果存在i，r，使得，则有。步骤2 更新聚类原型模式矩阵；其中为b+1次迭代后的聚类中心。步骤3 如果，则算法停止并输出隶属度矩阵U和聚类原型V，否则令b=b+1，转向步骤1。其中为某种合适的矩阵范数。针对模糊聚类算法，也有许多的改进。2006年，国内的王丽娟18博士等提出了一种给每个特征属性加权的模糊聚类算法，简称CF-WFCM算法。属性权重学习算法从数据自身的相似性出发，通过梯度递减算法极小化属性评价函数C Fuzziness(w) ，为每个属性赋予一个权重。将属性权重应用于Fuzzy C Mean聚类算法，得到CF-WFCM算法的聚类算法2006年，Hathaway Richard J. 19等给出了一个扩展快速 FCM 算法，geFFCM。同样为了加速 FCM 算法的运行效率，Kolen JF等将原始的FCM中的交替更新隶属矩阵中耗费内存空间的过程移除，将两步更新合并为一步更新，显著的加快了聚类运行效率。2008年，Laskaris Nikolaos A.20等给出了一种Beyond FCM的算法，该算法增加了一个图的后处理阶段，解决了FCM过度划分集的弊端。2003年，采用 FCM 对 DNA 微阵列数据进行聚类分析21。.2005年，Pal NR等给出了一个中概率模糊 C 均值算法22。2008年，用于对象数据聚类的算法 ECM23，模糊子空间聚类24，活跃半监督模糊聚类算法25。2010年，迭代贝叶斯模糊聚类26。2010年，国内的周红芳27教授给出了一种改进的模糊聚类算法，该算法将粒度分析原理应用在FCM算法中，提出了基于粒度原理确定聚类类别数的方法，并采用密度函数法初始化聚类中心。改进后的聚类算法能够得到合理有效的聚类数目，并且与随机初始化相比，迭代次数明显减少，收敛速度明显加快。（5） 基因表达数据分析聚类算法随着人类基因组计划的实施,目前已经产生了大量的 DNA 和蛋白质序列如何在这些海量的生物信息中提取有用的信息是目前生物信息学研究的重要问题。基因表达数据能够在基因组的水平上检测基因转录mRNA 的丰度(Abundance)，目前基因表达数据主要通过 cDNA 微阵列、基因芯片等高通量技术。常用于基因分类的算法有：支持向量机（SVM），贝叶斯算法（Nave Bayes），KNN算法。支持向量机的基本思想可以概括为：首先将输入空间变换到一个新的空间，然后在这个新空间里求取最优线性分类面。其优点是所获得分类器的复杂度可以支持向量的个数，而不是变换空间的维数来刻画。因此，SVM往往不像一些别的方法一样容易产生过拟合的现象。（6） 蛋白质序列分析聚类算法聚类分析通过测量蛋白质序列之间的相似性对蛋白质序列进行有效的划分，为确定蛋白质序列的家族信息和预测蛋白质序列的功能及对蛋白质序列进行同源检测提供了有力的依据。（7） 其他一些热点的聚类算法基于核的聚类算法，谱聚类算法，基于神经网络的聚类算法神经网络方法包括Rumelhart等人提出的竞争学习神经网络和Kohonen提出的自组织特征映射(简称SOM)神经网络。竞争学习采用了若干个单元的层次结构，它们以一种“胜者全取”的方式对系统当前处理的对象进行竞争。在一个簇中获胜的单元成为活跃的，而其他单元是不活跃的。各层之间的连接是激发式的，即在某个给定层次中的单元可以接收来自低一层次所有单元的输入。在一层中活动单元的布局代表了高一层的输入模式。在某个给定层次中，一个簇中的单元彼此竞争，对低一层的输出模式做出反应。一个层次内的联系式抑制式的，以便在任何簇中只有一个单元是活跃的。获胜的单元修正它与簇中其他单元连接上的权重，以便未来它能够对与当前对象相似或一样的对象做出较强的反应。如果我们将权重看作定义的一个标本，那么新的对象被分配给具有最近标本的簇。结果簇的数目和每个簇中单元的数目是输入参数。在聚类过程结束时，每个簇可以被看作一个新的“特征”，它检测对象的某些规律性。这样产生的结果簇可以被看作一个底层特征向高层特征的映射。 在SOM算法中，聚类也是通过若干个单元竞争当前对象来进行的。权重向量最接近当前对象的单元成为获胜的和活跃的单元。为了更接近输入对象，对获胜单元及其最近的邻居的权重进行调整。SOM算法假设在输入对象中存在一些拓扑结构和顺序，单元将最终在空间中呈现这种结构。单元的组织形成一个特征映射。SOM算法被认为类似于大脑的处理过程，对在二维或三维空间中可视化高维数据是有用的。聚类的要求（1）聚类分析算法的可扩展性;（2） 具有处理不同类型属性的能力; （3）能发现任意形状的聚类;（4）具有处理噪声数据的能力;（5）对数据的输入顺序不敏感;（6）用于决定输入的参数最少; （7）能够处理空间中的聚类; （8）聚类的结果的可解释性和可用性。聚类算法的发展趋势（1）聚类算法之间的相互结合；大部分无监督聚类都需要由用户来决定聚类的数目，但对许多基因表达数据，我们往往无法确定数据所应划分出的聚类数目，而更希望这个数目能够自动产生。（2）聚类算法与其他算法的结合。（3）聚类算法的可视化表示。用各种聚类方法对基因表达数据进行聚类之后，使用可视化工具以图、树、方体和链的形式展现，能够方便模式理解、知识发现和数据交互。（4）聚类算法与计算智能的结合。将聚类算法与计算智能中的人工神经网络、遗传算法和模糊逻辑等进行有机的结合，在蛋白质序列分析的建模和结果优化方面都会成为强有力的工具。（5）加强聚类算法在分布式环境下的应用。大型数据库的产生，会占用大量的数据处理资源，需要分布式系统来解决这一问题。 在这种趋势下，神经网络技术就有其特有的优势, 以其并行分布、自组织、自适应、自学习和容错性等优良性能，可以较好应用于聚类分析上。而竞争型神经网络的神经元通过输入信息能够识别成组的相似输入向量，可以自动学习对输入向量模式的分类。三、人工神经网络的发展1943年，心理学家W.S.Mcculloch和数理逻辑学家W.Pitts提出了M-P模型，M-P模型的提出具有开创意义，为以后的研究工作提供了重要依据；1949年，心理学家D.O.Hebb提出突触联系可变的假设。由这一假设得出的学习规则Hebb学习规则，为神经网络的学习算法奠定了基础；1957年， 计算机科学家Rosenblatt提出了著名的感知机（Perception）模型，是第一个完整的人工神经网络，并且第一次把神经网络研究付诸工程实现， 从而奠定了从系统的角度研究 人工神经网络的基础；1960年B.Windrow和M.E.Hoff提出了自适应线性单元网络，可用于自适应滤波、预测和模型识别；1982年和1984年美国加州理工学院生物物理学家J.J.Hopfield发表的两篇文章，提出了新的神经网络模型Hopfield网络模型和实现此网络模型的电子电路， 为神经网络的工程实现指明了方向，有力地推动了神经网络的研究，引起了神经网络研究的又一次热潮；1984年，Hinton等人将模拟退火算法引入神经网络中， 提出了Boltzmann机网络模型；1986年，D.E.Rumelhart和J.LMcclelland提出了误差反向传播算法 ， 成为至今影响很大的一种网络学习方法；90年代初，诺贝尔奖获得者Edelman提出了Darwinism模型，建立了神经网络系统理论；几乎同时，Aihara等人给出了一个混沌神经元模型，该模型已成为一种经典的混沌神经网络模型；1995年，Mitra把人工神经网络与模糊逻辑理论 、 生物细胞学说以及概率论相结合提出了模糊神经网络， 使得神经网络的研究取得了突破性进展。人工神经网络提供了一种揭示智能和了解人脑工作方式的合理途径，但是人类对神经系统的了解非常有限，还没有揭开大脑运作的真正的机制，尽管如此，近年来人工神经网络正向模拟人类认知上更加深入地发展。当然，人工神经网络的各种硬件实现也在逐步地发展。许多专家认为，第六代电子计算机是模仿人脑判断能力和适应能力，并具有可并行处理多种数据功能的神经网络计算机。与基于逻辑处理为主的第五代计算机不同，神经计算机可以判断对象的性质和状态，并能采取相应的行动，而且它可以同时并行处理实时变化的大量数据，并得出结论。以往的信息处理系统只能处理条理清晰、界限分明的数据。而人脑却具有处理支离破碎、含糊不清信息的灵活性。第六代电子计算机将具有类似人脑的智慧和灵活性。神经计算机的信息不是存储于存储器中，而是存储在神经细胞之间的联络网中，若有节点断裂，仍有重建资料的能力。它还具有联想记忆、视觉和声音识别能力。日本科学家已开发出神经电子计算机的大规模集成电路芯片，在1.5cm2的硅片上可设置400个神经元和40000个神经键，这种芯片能实现每秒2亿次的运算速度。1990年，日本理光公司宣布研制出一种具有学习功能的大规模集成电路“神经LST”。这是依照人脑的神经细胞研制成功的一种芯片。它利用生物的神经信息传送方式，在一块芯片上载有一个神经元，然后把所有芯片连接起来，形成神经网络。其处理信息的速度为每秒90亿次。富士通研究所开发的神经计算机，每秒更新数据速度近千亿次。日本电气公司推出一种神经网络声音识别系统，能够识别出任何人的声音，正确率达99.8%。美国研究出由左脑和右脑两个神经块连接而成的神经电子计算机：右脑为经验功能部分，有1万多个神经元，适于图像识别；左脑为识别功能部分，含有100万个神经元，用于存储单词和语法规则。我国在1995年也研制成功了小型神经计算机，可以直观地模拟人的脑神经细胞活动的计算方式。四、SOFM的研究现状2007年，国内的黄丽娟，甘筱青对传统的SOFM算法进行了以下三方面的改进：一则，为获取较快的网络收敛速度，采用了对Euclid距离公式取对数函数的方法获取广义的；二则，为避免邻域的中断和无效映射，采用了球面的神经元拓扑结构而非传统的平面神经元拓扑结构；三则,为获得比较精确的聚类效果，将样本数据的PAM聚类重心作为权值的初始值，而没有采用传统的随机取值方法29。2011年，陈善学，王佳果等人通过搜索获胜神经元，引入频率敏感因子对基本的SOFM进行改进，提高了SOFM网络的性能30。2011年，罗辛，潘乔等人提出一种基于自组织特征映射网络的高速图像检索算法，在保留高维空间距离的前提下将图像特征映射到一维空间，在低维空间的限定范围内完成检索工作31。2011年，王焱，王磊明等针对在杂草图像分割方面存在使用阈值分割需要选择分割阈值、图像分割精度不高等不足，结合超绿特征分割算法和SOFM网络，构造出一种杂草图像识别模型G-SOFM空间聚类模型32。2009年，朱丽娟，徐小明等尝试在SOFM神经网络中引入最近插入法形成混合算法，很好地解决了SOFM神经网络在TSP问题上的部分节点无法分离的情况33。2009年，李鑫环，陈立潮等人针对MRI脑图像分割算法在图像分割速度和精度上不理想的问题，提出了一种将平衡多小波分析与SOFM相结合的BMSOFM算法。实验结果表明，BMSOFM不但加快了分割速度，而且提高了聚类精确度，分割效果得到明显改善34。2009年，刘慧，冯乃勤，南书坡等结合粗糙集理论和自组织特征映射提出了一种算法，该算法利用粗糙集理论的属性约简去掉样本的冗余属性，并将处理过的数据作为SOFM神经网络的训练样本，从而减少了SOFM网络的规模，提高了样本的聚类效率35。2009年，武淑红，张刚，张雪英从以下两个方面对SOFM进行了改进：1、对输入训练矢量以及连接权矢量进行；2、采用快速的网络学习决定获胜的神经元并对网络权值分阶段进行自适应调整。实验表明，与传统LBG算法比较，采用SOFM神经网络训练的码书其合成语音的主、客观质量均有大量提高36。2008年，Teuvo Kohonen在其发表的一文中介绍了一种新的发现，即输入向量能更准确地被一些线性组合表征37。 五、竞争性网络在聚类分析中存在的问题 竞争型神经网络在聚类分析前需要确定聚类数目，但是在很多的情况下，聚类数目在初始时很难确定。 而且，竞争型神经网络的聚类结果对初始权值的依赖性比较大，如果初始权值选的不好，就有可能导致属于某一类别的样本数为0，或者将某两类样本划分为一类，或者将某一类样本划分为两类。 聚类的数据不可避免地会产生少量的孤立点，即少量数据点远离数据密集区的情况, 由于随机的选取初始聚类中心, 可能会将孤立点选为初始聚类中心, 这样会使聚类结果产生很大的偏差。另外, 在进行聚类计算时,是将聚类均值点(类中所有数据的平均值)作为新的聚类中心进行新一轮的聚类计算, 在这种情况下, 新的聚类中心可能偏离真正的数据密集区, 从而导致聚类结果出现偏差。由此可见, 孤立点对于 K - M eans算法有很大的影响。所以改进算法首先运行孤立点查找算法, 排除孤立点, 然后进行聚类。孤立点在聚类算法之后单独聚类。六、论文预期成果的理论意义和应用价值本课题的理论意义表现在：（1）探索聚类分析的好方法，丰富和完善聚类分析算法；（2）将改进的自组织竞争型神经网络应用于聚类分析，得到更具优势的算法。本课题的研究应用价值体现在：聚类分析是一个极富挑战性的研究领域，是近年来迅速发展起来的一种新兴的数据处理技术，它在气象分析、图像处理、模糊控制、计算机视觉、天气预报、模式识别、生物医学、化学、食品检验、生物种群划分、市场细分、业绩评估等诸多领域有着广泛的应用，并在这些领域中取得了长足的发展。七、课题研究的主要内容研究目标优化自组织竞争神经网络，将其应用于聚类分析，使得结果更加合理，算法性能更加优越。研究内容 研究聚类问题，讨论主要的聚类算法，对算法的优缺点进行分析和总结，并通过仿真实验对部分算法进行验证和讨论。 分析讨论自组织特征映射网络，通过仿真实验对网络优缺点进行验证和总结。 对自组织映射神经网络进行改进，主要对孤立点的检测，初始权值，学习率进行改进。 对研究工作及获得的研究成果进行了总结，并提出了后续的研究方向，为进一步的研究工作开拓了思路。 创新点引入孤立点检测算法，排除孤立点对整个算法的影响。 利用kmeans算法对算法进行初始权值的设置。 实验大致流程 第一步：对孤立点进行检测，将其独立出来。 第二步：运用K-means算法设定初始权值的大小。 第三步：建立自组织竞争型神经网络，对孤立点以外的点进行分类 第四步：判断是否达到迭代次数，如果达到，转第五步，否则，转第二步。 第五步：得到聚类结果，求出每一类的均值。 第六步：将孤立点分配给最近的一类，依据是与每一类均值的欧式距离。八、研究计划进度与安排（1）2011年10月2011年11月 检索文献、查阅课题相关资料并研究开题报告的撰写 （2） 2011年11月2011年12月 测试传统的聚类算法的性能并分析总结其优劣 （3） 2011年12月2012年04月 测试传统的SOFM算法的性能并总结其优劣 （4） 2012年05月2012年08月 测试引入kmeans算法的SOFM算法的性能 （5） 2012年 10月2012年11月 总结并分析实验结果 （6） 2012年11月2012年12月 着手毕业论文的撰写 九、传统的SOFM神经网络结构和学习算法SOFM神经网络结构 自组织特征映射网络SOM是基于无监督学习方法的神经网络的一种重要类型。自组织映射网络理论最早是由芬兰赫尔辛基理工大学的Teuvo Kohonen于1981年提出的，这种模型模拟了大脑神经系统的自组织特征映射功能。它通过学习可以提取一组数据中的重要特征或者某种内在规律，按离散时间方式进行分类。网络可以把任意高维的输入映射到低维空间，并且使得输入数据内部的某些相似性质表现为几何上的特征映射。这样，就在输出层映射成一维或二维离散图形，并保持其拓扑结构不变。这种分类反映了样本集的本质区别，大大减弱了一致性准则中的人为因素。 SOM的网络结构如下图所示，由输入层和输出层两层构成，输入层为一维矩阵，输出层则是二维节点矩阵，该矩阵由神经元按一定的方式排列成一个平面。输入层的神经元与输出层的神经元通过权值相互联结在一起。输出层各神经元之间实行侧抑制连接，当SOM网络接收到外部的输入信号以后，输出层的某个神经元就会表现为兴奋状态。.X1Xn输出层输入层传统的SOFM神经网络算法具体描述 设训练矢量数为，训练矢量集表示为，网络有个输入节点，竞争层有个神经元，由输入层到竞争层的连接权值为，其算法如下：(1) 网络状态的初始化。将初始化连接权值赋予随机值并进行归一化处理，得到；确定初始学习速率，；确定邻域的初始值，同时确定总的学习次数。(2) 从训练集合中选择训练矢量，并进行归一化处理，用并行的方式输入到竞争层的每一个神经元。(3) 计算与各神经元(即)间的距离，选择具有最小距离的神经元及的拓扑邻域内，按式(2)调整神经元及的拓扑邻域内的神经元的权值，其他的神经元权值保持不变，即： (1) (2)其中，为获胜神经元的拓扑邻域，为当前迭代次数。为学习速率因子，一般选为： 其中，为总的迭代次数，取。(4) 对所有训练输入模式，重复步骤(2)、(3)，直到算法收敛或达到初始设定的最大迭代次数。十、改进的SOFM算法 通过上面对传统的SOFM算法的具体描述，发现该算法还存在一些缺陷，如随机赋予初始连接权值，可能会将孤立点作为聚类中心，这样会使结果产生很大的偏差。由此可见，孤立点对于SOFM算法有很大的影响，所以改进算法首先运行孤立点查找算法，排除孤立点，然后进行聚类，孤立点在聚类算法之后单独聚类。另一方面，随机赋予初始连接权值会影响算法的收敛性，无法尽快找到一个合适的全局最优解。再者，为了提高效率，SOFM网络权值的调整通过调整学习率来控制。孤立点的检测常见的基于距离的孤立点定义可以总结如下28：（1） 在数据集S中，如果有P（p1）的对象到点O的距离大于r，那么点o是一个孤立点。如果点o在半径为r的超球范围内有不多于M个邻居，则点o是一个孤立点。这里M=N（1-P），N为S中数据点的个数。（2） 孤立点是指数据集S中的n个点，这n个点到其第k个最近邻点的距离是所有点中最大的，其中n是孤立点个数的估计值。（3） 孤立点是数据集S中的n个点，这n个点到其k个最近邻点的距离之和是所有点中最大的。改进距离的定义如下：式中：和分别表示和到其个最近邻点的欧式距离的平均值。孤立点的检测算法的步骤如下：(1) 对每个样本点，由欧氏距离的定义，计算出距离它最近的k个近邻点。(2) 由改进距离的定义，计算所有样本点两两之间的改进距离。 (3)对每个样本点，根据步骤(2)计算出的改进距离找出距离它最近的k个近邻点，并计算到其k个近邻点的改进距离之和sumi，使sumi最大的n个点即为孤立点。SOFM神经网络算法具体描述第一步：运行孤立点检测算法，将样本中的孤立点逐一找出。第二步：运行kmeans算法，寻找出聚类中心，将聚类中心的值赋给初始权值。第三步：网络状态的初始化。初始化学习率，领域半径，并设定最大训练次数。第四步：输入训练样本并归一化，记为 train_samp le。第五步：计算经过归一化处理后的训练样本和权值向量之间的欧氏距离 ，即式中：为输入神经元个数，为竞争层神经元个数。第六步：选择获胜的神经元，依据为欧氏距离最小的神经元，标记为。第七步：调整权值向量，由于竞争层之间的侧向抑制作用，每次只调整邻域内的神经元权值，邻域外的神经元不作调整，调整函数为式中：为以获胜神经元为中心，以为半径的邻域函数 第八步：将调整之后的权值向量进行归一化处理。 第九步：选取另一个学习模式提供给网络的输入层，返回第五步。直到全部输入模式提供给网络。第十步：调整学习率和邻域半径，调整公式为第十一步：训练次数，如果，返回到第二步继续训练，否则，保存训练好的全职向量，训练结束。拟改进算法的流程图如下：孤立点检测算法，检测出孤立点Kmeans算法，求取初始权值向量初始化SOFM网络，初始邻域，初始学习率并进行归一化处理输入样本归一化从样本模式中选取一个输入模式计算输入样本与权值向量之间的欧式距离，选择获胜神经元并标记调整获胜神经元及其邻域的权值向量，并选取另一个学习模式提供给网络的输入层更新后的权值重新进行归一化处理输入是否全部提供给网络YNYN调整学习率和邻域半径 算法结束 训练次数t=t+1t=Tkmeans算法和sofm算法性能之间的比较（1）衡量算法性能的指标 准则函数 相似度 （2）数据比较K-means算法改进的kmeans算法SOFM改进的SOFM准则函数相似度准则函数相似度准则函数相似度准则函数相似度1.04130.44950.97760.23501.03360.21891.01310.24291.10620.46550.88950.23101.03780.22111.02530.20931.03150.41070.86870.21861.01540.20131.01540.20131.02610.42480.96290.21361.06250.22460.99540.22660.98770.38661.03480.27151.01170.20091.07360.24620.93770.41900.93320.22301.03780.22111.09620.25090.95960.40010.98840.27831.03780.22111.00320.20181.01940.47660.94870.22751.03780.22111.01800.22721.01670.43450.85610.19091.03780.22111.01580.19870.98170.35890.86700.20841.03780.22111.04180.22811.01080.42260.93270.22981.03500.21721.02970.22330.04730.03600.06040.02690.01390.00860.03210.0196（2）图形比较改进的kmeans算法：SOFM算法：去除孤立点的SOFM算法：参考文献1 雷小锋,谢昆青,林帆, 等.一种基于 K-Means 局部最优性的高效聚类算法.软件学报, 2008, 19(7): 1683-16922 Xiong H., J. Wu, J. Chen. K-means clustering versus validation measures: a data-distribution perspective. IEEE Trans Syst Man Cybern B Cybern, 2009, 39(2): 318-3313 Chung Kuo-Liang, Jhin-Sian Lin. Faster and more robust point symmetry-based K-means algorithm. Pattern Recognition, 2007, 40(2): 410-4224 Huang Joshua Zhexue, Michael K. Ng, Hongqiang Rong, et al. Automated variable weighting in k-means type clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(5): 657-6685 Wu F. X. Genetic weighted k-means algorithm for clustering large-scale gene expression data. BMC Bioinformatics, 2008, 9(Suppl 6): S126 Bagirov Adil M. Modified global k-means algorithm for minimum sum-of-squares clustering problems. Pattern Recognition, 2008, 41(10): 3192-31997 Hamerly G., C. Elkan. Learning the k in k-means. Advances in Neural Information Processing Systems 16. MIT Press, 2003, 281-2898 Du Z., Y. Wang, Z. Ji. PK-means: A new algorithm for gene clustering. Comput Biol Chem, 2008, 32(4): 243-249 Goldberger Jacob, Tamir Tassa. A hierarchical clustering algorithm based on the Hungarian method. Pattern Recognition Letters, 2008, 29(11): 1632-163810 Loewenstein Yaniv, Elon Portugaly, Menachem Fromer,et al. Efficient algorithms for accurate hierarchical clustering of huge datasets: tackling the entire protein space. Bioinformatics, 2008, 24(13): i41-i4911 Wang H., H. Zheng, F. Azuaje. Poisson-based self-organizing feature maps and hierarchical clustering for serial analysis of gene expression data. IEEE/ACM Trans Comput Biol Bioinform, 2007, 4(2): 163-17512 Arifin Agus Zainal, Akira Asano. Image segmentation by histogram thresholding using hierarchical cluster analysis. Pattern Recognition Letters, 2006, 27(13): 1515-152113 Ester M, H P Kriegel, J Sander. A density-based algorithm for discovering clusters in large spatial databases. Knowledge Discovery and Data Mining(KDD96). AAAI Press, 1996, 226-23114 Sander J, M Ester, HP Kriegel, et al. Density-based clustering in spatial databases: The algorithm gdbscan and its applications. Data mining and knowledge discovery, 1998, 2(2): 169-19415 Ankerst Mihael,Markus M. Breunig, Hans-Peter Kriegel,et al. OPTICS: ordering points to identify the clustering structure. Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM Press, 1999, 49-6016 Hinneburg A, DA Keim. An efficient approach to clustering in large multimedia databases with noise. Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining KDD98. AAAI Press, 1998, 58-6517 Agrawal R, JE Gehrke, D Gunopulos, et al. Automatic subspace clustering of high dimensional data for data mining applications. Proceedings of the ACM-SIGMOD98 Int. Conf. Management of Data. ACM Press, 1998, 94-10518王丽娟，关守义，王晓龙，王熙熙. 基于属性权重的Fuzzy C Mean算法.计算机学报，2006，29(10)：1178-180319 Hathaway Richard J., James C. Bezdek. Extending fuzzy and probabilistic clustering to very large data sets. Computational Statist