论文关键词：数据挖掘；聚类算法；聚类分析论文摘要：该文详细阐述了数据挖掘领域的常用聚类算法及改进算法，并比较分析了其优缺点，提出了数据挖掘对聚类的典型要求，指出各自的特点，以便于人们更快、更容易地选择一种聚类算法解决特定问题和对聚类算法作进一步的研究。并给出了相应的算法评价标准、改进建议和聚类分析研究的热点、难点。上述工作将为聚类分析和数据挖掘等研究提供有益的参考。 1 引言随着经济社会和科学技术的高速发展，各行各业积累的数据量急剧增长，如何从海量的数据中提取有用的信息成为当务之急。聚类是将数据划分成群组的过程，即把数据对象分成多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。它对未知数据的划分和分析起着非常有效的作用。通过聚类，能够识别密集和稀疏的区域，发现全局的分布模式，以及数据属性之间的相互关系等。为了找到效率高、通用性强的聚类方法人们从不同角度提出了许多种聚类算法，一般可分为基于层次的，基于划分的，基于密度的，基于网格的和基于模型的五大类。 2 数据挖掘对聚类算法的要求(1)可兼容性：要求聚类算法能够适应并处理属性不同类型的数据。(2)可伸缩性：要求聚类算法对大型数据集和小数据集都适用。(3)对用户专业知识要求最小化。(4)对数据类别簇的包容性：即聚类算法不仅能在用基本几何形式表达的数据上运行得很好，还要在以其他更高维度形式表现的数据上同样也能实现。(5)能有效识别并处理数据库的大量数据中普遍包含的异常值，空缺值或错误的不符合现实的数据。(6)聚类结果既要满足特定约束条件，又要具有良好聚类特性，且不丢失数据的真实信息。(7)可读性和可视性：能利用各种属性如颜色等以直观形式向用户显示数据挖掘的结果。(8)处理噪声数据的能力。(9)算法能否与输入顺序无关。 3 各种聚类算法介绍随着人们对数据挖掘的深入研究和了解，各种聚类算法的改进算法也相继提出，很多新算法在前人提出的算法中做了某些方面的提高和改进，且很多算法是有针对性地为特定的领域而设计。某些算法可能对某类数据在可行性、效率、精度或简单性上具有一定的优越性，但对其它类型的数据或在其他领域应用中则不一定还有优势。所以，我们必须清楚地了解各种算法的优缺点和应用范围，根据实际问题选择合适的算法。 3.1 基于层次的聚类算法基于层次的聚类算法对给定数据对象进行层次上的分解，可分为凝聚算法和分裂算法。 (1)自底向上的凝聚聚类方法。这种策略是以数据对象作为原子类，然后将这些原子类进行聚合。逐步聚合成越来越大的类，直到满足终止条件。凝聚算法的过程为：在初始时，每一个成员都组成一个单独的簇，在以后的迭代过程中，再把那些相互邻近的簇合并成一个簇，直到所有的成员组成一个簇为止。其时间和空间复杂性均为O(n2)。通过凝聚式的方法将两簇合并后，无法再将其分离到之前的状态。在凝聚聚类时，选择合适的类的个数和画出原始数据的图像很重要。 [!--empirenews.page--] (2)自顶向下分裂聚类方法。与凝聚法相反，该法先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件。其主要思想是将那些成员之间不是非常紧密的簇进行分裂。跟凝聚式方法的方向相反，从一个簇出发，一步一步细化。它的优点在于研究者可以把注意力集中在数据的结构上面。一般情况下不使用分裂型方法，因为在较高的层很难进行正确的拆分。 3.2 基于密度的聚类算法很多算法都使用距离来描述数据之间的相似性，但对于非凸数据集，只用距离来描述是不够的。此时可用密度来取代距离描述相似性，即基于密度的聚类算法。它不是基于各种各样的距离，所以能克服基于距离的算法只能发现“类圆形”的聚类的缺点。其指导思想是：只要一个区域中的点的密度（对象或数据点的数目）大过某个阈值，就把它加到与之相近的聚类中去。该法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可发现任意形状的簇，并可用来过滤“噪声”数据。常见算法有DBSCAN，DENCLUE 等。[1][2][3]下一页 3.3 基于划分的聚类算法给定一个N个对象的元组或数据库，根据给定要创建的划分的数目k，将数据划分为k个组，每个组表示一个簇类（<=N）时满足如下两点：(1)每个组至少包含一个对象；(2)每个对
聚类分析算法解析 一、不相似矩阵计算 1.加载数据 data(iris) str(iris) 分类分析是无指导的分类，所以删除数据中的原分类变量。 iris$Species<-NULL 2. 不相似矩阵计算 不相似矩阵计算，也就是距离矩阵计算，在R中采用dist()函数，或者cluster包中的daisy()函数。dist()函数的基本形式是 dist(x, method = "euclidean", diag = FALSE, upper = FALSE, p = 2) 其中x是数据框（数据集），而方法可以指定为欧式距离"euclidean", 最大距离"maximum", 绝对值距离"manhattan", "canberra", 二进制距离非对称"binary" 和明氏距离"minkowski"。默认是计算欧式距离，所有的属性必须是相同的类型。比如都是连续类型，或者都是二值类型。 dd<-dist(iris) str(dd) 距离矩阵可以使用as.matrix()函数转化了矩阵的形式，方便显示。Iris数据共150例样本间距离矩阵为150行列的方阵。下面显示了1~5号样本间的欧式距离。 dd<-as.matrix(dd)
二、用hclust()进行谱系聚类法（层次聚类） 1.聚类函数 R中自带的聚类函数是hclust()，为谱系聚类法。基本的函数指令是 结果对象 <- hclust（距离对象, method=方法） hclust()可以使用的类间距离计算方法包含离差法"ward"，最短距离法"single"，最大距离法"complete"，平均距离法"average"，"mcquitty"，中位数法 "median" 和重心法"centroid"。下面采用平均距离法聚类。 hc <- hclust(dist(iris), method="ave") 2.聚类函数的结果 聚类结果对象包含很多聚类分析的结果，可以使用数据分量的方法列出相应的计算结果。 str(hc) 下面列出了聚类结果对象hc包含的merge和height结果值的前6个。其行编号表示聚类过程的步骤，X1，X2表示在该步合并的两类，该编号为负代表原始的样本序号，编号为正代表新合成的类；变量height表示合并时两类类间距离。比如第1步，合并的是样本102和143，其样本间距离是0.0，合并后的类则使用该步的步数编号代表，即样本-102和-143合并为1类。再如第6行表示样本11和49合并，该两个样本的类间距离是0.1，合并后的类称为6类。 head (hc$merge,hc$height)
计算机工程与应用2006.16 引言 聚类分析是数据挖掘领域中的一个重要分支[1],是人们认 和探索事物之间内在联系的有效手段,它既可以用作独立的 据挖掘工具,来发现数据库中数据分布的一些深入信息,也 以作为其他数据挖掘算法的预处理步骤。所谓聚类(clus- ring)就是将数据对象分组成为多个类或簇(cluster),在同一 簇中的对象之间具有较高的相似度,而不同簇中的对象差别大。传统的聚类算法主要分为四类[2,3]:划分方法,层次方法, 于密度方法和基于网格方法。 受生物进化机理的启发,科学家提出许多用以解决复杂优 问题的新方法,如遗传算法、进化策略等。1991年意大利学A.Dorigo等提出蚁群算法,它是一种新型的优化方法[4]。该算不依赖于具体问题的数学描述,具有全局优化能力。随后他 其他学者[5～7]提出一系列有关蚁群的算法并应用于复杂的组优化问题的求解中,如旅行商问题(TSP)、调度问题等,取得 著的成效。后来其他科学家根据自然界真实蚂蚁群堆积尸体分工行为,提出基于蚂蚁的聚类算法[8,9],利用简单的智能体 仿蚂蚁在给定的环境中随意移动。这些算法的基本原理简单懂[10],已经应用到电路设计、文本挖掘等领域。本文详细地讨现有蚁群聚类算法的基本原理与性能,在归纳总结的基础上 出需要完善的地方,以推动蚁群聚类算法在更广阔的领域内 到应用。 2聚类概念及蚁群聚类算法 一个簇是一组数据对象的集合,在同一个簇中的对象彼此 类似,而不同簇中的对象彼此相异。将一组物理或抽象对象分组为类似对象组成的多个簇的过程被称为聚类。它根据数据的内在特性将数据对象划分到不同组(或簇)中。聚类的质量是基于对象相异度来评估的,相异度是根据描述对象的属性值来计算的,距离是经常采用的度量方式。聚类可用数学形式化描述为:设给定数据集X={x 1 ,x 2 ,…,x n },!i∈{1,2,…,n},x i ={x i1 ,x i2 , …,x
聚类分析K-means算法综述 摘要：介绍K-means聚类算法的概念，初步了解算法的基本步骤，通过对算法缺点的分析，对算法已有的优化方法进行简单分析，以及对算法的应用领域、算法未来的研究方向及应用发展趋势作恰当的介绍。 关键词：K-means聚类算法基本步骤优化方法应用领域研究方向应用发展趋势 算法概述 K-means聚类算法是一种基于质心的划分方法，输入聚类个数k，以及包含n个数据对象的数据库，输出满足方差最小标准的k个聚类。 评定标准：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算。 解释：基于质心的划分方法就是将簇中的所有对象的平均值看做簇的质心，然后根据一个数据对象与簇质心的距离，再将该对象赋予最近的簇。 k-means 算法基本步骤 （1）从n个数据对象任意选择k 个对象作为初始聚类中心 （2）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分 （3）重新计算每个（有变化）聚类的均值（中心对象） （4）计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤（2） 形式化描述 输入：数据集D，划分簇的个数k 输出：k个簇的集合 （1）从数据集D中任意选择k个对象作为初始簇的中心； （2）Repeat （3）For数据集D中每个对象P do （4）计算对象P到k个簇中心的距离 （5）将对象P指派到与其最近（距离最短）的簇；
（6）End For （7）计算每个簇中对象的均值，作为新的簇的中心； （8）Until k个簇的簇中心不再发生变化 对算法已有优化方法的分析 (1)K-means算法中聚类个数K需要预先给定 这个K值的选定是非常难以估计的，很多时候,我们事先并不知道给定的数据集应该分成多少个类别才最合适，这也是K一means算法的一个不足"有的算法是通过类的自动合并和分裂得到较为合理的类型数目k，例如Is0DAIA算法"关于K一means算法中聚类数目K 值的确定，在文献中，根据了方差分析理论，应用混合F统计量来确定最佳分类数，并应用了模糊划分嫡来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵RPCL算法，并逐步删除那些只包含少量训练数据的类。文献中针对“聚类的有效性问题”提出武汉理工大学硕士学位论文了一种新的有效性指标：V(k km) = Intra(k) + Inter(k) / Inter(k max)，其中k max是可聚类的最大数目,目的是选择最佳聚类个数使得有效性指标达到最小。文献中使用的是一种称为次胜者受罚的竞争学习规则来自动决定类的适当数目"它的思想是：对每个输入而言不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法使之远离输入值。 (2)算法对初始值的选取依赖性极大以及算法常陷入局部极小解 不同的初始值，结果往往不同。K-means算法首先随机地选取k个点作为初始聚类种子，再利用迭代的重定位技术直到算法收敛。因此，初值的不同可能导致算法聚类效果的不稳定，并且，K-means算法常采用误差平方和准则函数作为聚类准则函数(目标函数)。目标函数往往存在很多个局部极小值，只有一个属于全局最小，由于算法每次开始选取的初始聚类中心落入非凸函数曲面的“位置”往往偏离全局最优解的搜索范围，因此通过迭代运算，目标函数常常达到局部最小，得不到全局最小。对于这个问题的解决，许多算法采用遗传算法(GA)，例如文献中采用遗传算法GA进行初始化，以内部聚类准则作为评价指标。 (3)从K-means算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时,算法的时间开销是非常大 所以需要对算法的时间复杂度进行分析，改进提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的候选集，而在文献中，使用的K-meanS算法是对样本数据进行聚类。无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。
比较专家系统、模糊方法、遗传算法、神经网络、蚁群算法的特点及其适合解决的实际问题 一、专家系统(Expert System) 1，什么是专家系统？ 在日常生活中大家所认知的“专家”一般都拥有某一特定领域的大量专业知识，以及丰富的实际经验。在解决问题时，专家们通常拥有一套独特的思维方式，能较圆满地解决一类困难问题，或向用户提出一些建设性的建议等。 专家系统一般定义为一个具有智能特点的计算机程序。 它的智能化主要表现为能够在特定的领域内模仿人类专家思维来求解复杂问题。因此，专家系统必须包含领域专家的大量知识，拥有类似人类专家思维的推理能力，并能用这些知识来解决实际问题。 专家系统的基本结构如图1所示，其中箭头方向为数据流动的方向。 图1 专家系统的基本组成 专家系统通常由知识库和推理机两个主要组成要素。 知识库存放着作为专家经验的判断性知识,例如表达建议、 推断、 命令、 策略的产生式规则等, 用于某种结论的推理、 问题的求解,以及对于推理、 求解知识的各种控制知识。 知识库中还包括另一类叙述性知识, 也称作数据,用于说明问题的状态,有关的事实和概念,当前的条件以及常识等。
专家系统的问题求解过程是通过知识库中的知识来模拟专家的思维方式的，因此，知识库是专家系统质量是否优越的关键所在，即知识库中知识的质量和数量决定着专家系统的质量水平。一般来说，专家系统中的知识库与专家系统程序是相互独立的，用户可以通过改变、完善知识库中的知识内容来提高专家系统的性能。 推理机实际上是一个运用知识库中提供的两类知识,基于木某种通用的问题求解模型,进行自动推理、 求解问题的计算机软件系统。 它包括一个解释程序, 用于决定如何使用判断性知识推导新的知识, 还包括一个调度程序, 用于决定判断性知识的使用次序。 推理机的具体构造取决于问题领域的特点,及专家系统中知识表示和组织的方法。 推理机针对当前问题的条件或已知信息，反复匹配知识库中的规则，获得新的结论，以得到问题求解结果。在这里，推理方式可以有正向和反向推理两种。正向推理是从前件匹配到结论，反向推理则先假设一个结论成立，看它的条件有没有得到满足。由此可见，推理机就如同专家解决问题的思维方式，知识库就是通过推理机来实现其价值的。 人机界面是系统与用户进行交流时的界面。通过该界面，用户输入基本信息、回答系统提出的相关问题，并输出推理结果及相关的解释等。 综合数据库专门用于存储推理过程中所需的原始数据、中间结果和最终结论，往往是作为暂时的存储区。解释器能够根据用户的提问，对结论、求解过程做出说明，因而使专家系统更具有人情味。 知识获取是专家系统知识库是否优越的关键，也是专家系统设计的“瓶颈”问题，通过知识获取，可以扩充和修改知识库中的内容，也可以实现自动学习功能。 2，专家系统的特点 在功能上, 专家系统是一种知识信息处理系统, 而不是数值信息计算系统。在结构上, 专家系统的两个主要组成部分 – 知识库和推理机是独立构造、分离组织, 但又相互作用的。在性能上, 专家系统具有启发性, 它能够运用专家的经验知识对不确定的或不精确的问题进行启发式推理, 运用排除多余步骤或减少不必要计算的思维捷径和策略；专家系统具有透明性, 它能够向用户显示为得出某一结论而形成的推理链, 运用有关推理的知识(元知识)检查导出结论的精度、一致性和合理性, 甚至提出一些证据来解释或证明它的推理；专家系统具有灵活性, 它能够通过知识库的扩充和更新提高求解专门问题的水平或适应环境对象的某些变化,通过与系统用户的交互使自身的性能得到评价和监护。 3，专家系统适合解决的实际问题 专家系统是人工智能的一个应用，但由于其重要性及相关应用系统之迅速发展，它已是信息系统的一种特定类型。专家系统一词系由以知识为基础的专家系统(knowledge-based expert system)而来，此种系统应用计算机中储存的人类知识，解决一般需要用到专家才能处理的问题，它能模仿人类专家解决特定问题时的推理过程，因而可供非专家们用来增进问题解决的能力，同时专家们也可把它视为具备专业知识的助理。由于在人类社会中，专家资源确实相当稀少，有了专家系统，则可使此珍贵的专家知识获得普遍的应用。 专家系统技术广泛应用在工程、科学、医药、军事、商业等方面，而且成果相当丰硕，甚至在某些应用领域，还超过人类专家的智能与判断。其功能应用领
社会性动物的群集活动往往能产生惊人的自组织行为，如个体行为显得盲目的蚂蚁在组成蚁群后能够发现从蚁巢到食物源的最短路径。生物学家经过仔细研究发现蚂蚁之间通过一种称之为“外激素”的物质进行间接通讯、相互协作来发现最短路径。受其启发，1991年由意大利学者 M. Dorigo，V. Maniezzo 和 A. Colorni 通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法——蚁群优化。本文阐述了算法的基本原理及特性以及一些优化的蚁群算法，阐述了蚁群算法在数据挖掘中的应用,最后总结了蚁群算法在数据挖掘应用中尚待解决的问题。 关键词: 蚁群算法; 蚁群优化; 数据挖掘 正文文字大小：大中小 1 蚁群算法原理 自1991年由意大利学者 M. Dorigo，V. Maniezzo 和 A. Colorni 通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法——蚁群优化。该算法的出现引起了学者们的极大关注，蚁群算法的特点： ①其原理是一种正反馈机制或称增强型学习系统; 它通过【最优路径上蚂蚁数量的增加→信息素强度增加→后来蚂蚁选择概率增大→最优路径上蚂蚁数量更大增加】达到最终收敛于最优路径上L ②它是一种通用型随机优化方法, 它吸收了蚂蚁的行为特(内在搜索机制) , 它是使用人工蚂蚁仿真(也称蚂蚁系统) 来求解问题L但人工蚂蚁决不是对实际蚂蚁的一种简单模拟, 它融进了人类的智能L人工蚂蚁有一定的记忆; 人工蚂蚁不完全是瞎的; 人工蚂蚁生活的时空是离散的L ③它是一种分布式的优化方法, 不仅适合目前的串行计算机, 而且适合未来的并行计算机L ④它是一种全局优化的方法, 不仅可用于求解单目标优化问题, 而且可用于求解多目标优化问题L ⑤它是一种启发式算法, 计算复杂性为o (Nc*n2*m) , 其中Nc 是迭代次数, m 是蚂蚁数目, n 是目的节点数目L 蚁群发现最短路径的原理和机制[1] 下面用图 1解释蚁群发现最短路径的原理和机制。 如图 1(a)所示，在蚁巢和食物源之间有两条道路 Nest-A-B-D-Food 和Nest-A-C-D-Food，其长度分别为 4 和 6。单位时间内蚂蚁可移动一个单位长度的距离。开始时所有路径上都没有外激素。 如图 1(b)，在 t=0 时刻，20 只蚂蚁从蚁巢出发移动到 A。由于路径上没有外激素，它们以
7.1 蚁群优化算法概述 ?7.1.1 起源 ?7.1.2 应用领域 ?7.1.3 研究背景 ?7.1.4 研究现状 ?7.1.5 应用现状
7.1.1 蚁群优化算法起源 20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。
20世纪90年代意大利学者M．Dorigo，V．Maniezzo，A．Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法——蚁群算法，是群智能理论研究领域的一种主要算法。
背景：人工生命 ?“人工生命”是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容。 ?研究如何利用计算技术研究生物现象。?研究如何利用生物技术研究计算问题。
?现在关注的是第二部分的内容，现在已经有很多源于生物现象的计算技巧。例如，人工神经网络是简化的大脑模型，遗传算法是模拟基因进化过程的。 ?现在我们讨论另一种生物系统－社会系统。更确切的是，在由简单个体组成的群落与环境以及个体之间的互动行为，也可称做“群智能”(swarm intelligence)。这些模拟系统利用局部信息从而可能产生不可预测的群体行为（如鱼群和鸟群的运动规律），主要用于计算机视觉和计算机辅助设计。
?在计算智能(computational intelligence)领域有两种基于群智能的算法。蚁群算法(ant colony optimization)和粒子群算法(particle swarm optimization)。前者是对蚂蚁群落食物采集过程的模拟，已经成功运用在很多离散优化问题上。
嵌入式方向工程设计实验报告 学院班级：130712 学生学号：13071219 学生姓名：杨阳 同作者：无 实验日期：2010年12月
聚类算法分析研究 1 实验环境以及所用到的主要软件 Windows Vista NetBeans6.5.1 Weka3.6 MATLAB R2009a 2 实验内容描述 聚类是对数据对象进行划分的一种过程，与分类不同的是，它所划分的类是未知的，故此，这是一个“无指导的学习” 过程，它倾向于数据的自然划分。其中聚类算法常见的有基于层次方法、基于划分方法、基于密度以及网格等方法。本文中对近年来聚类算法的研究现状与新进展进行归纳总结。一方面对近年来提出的较有代表性的聚类算法，从算法思想。关键技术和优缺点等方面进行分析概括；另一方面选择一些典型的聚类算法和一些知名的数据集，主要从正确率和运行效率两个方面进行模拟实验，并分别就同一种聚类算法、不同的数据集以及同一个数据集、不同的聚类算法的聚类情况进行对比分析。最后通过综合上述两方面信息给出聚类分析的研究热点、难点、不足和有待解决的一些问题等。 实验中主要选择了K 均值聚类算法、FCM 模糊聚类算法并以UCI Machine Learning Repository 网站下载的IRIS 和WINE 数据集为基础通过MATLAB 实现对上述算法的实验测试。然后以WINE 数据集在学习了解Weka 软件接口方面的基础后作聚类分析，使用最常见的K 均值（即K-means ）聚类算法和FCM 模糊聚类算法。下面简单描述一下K 均值聚类的步骤。 K 均值算法首先随机的指定K 个类中心。然后： （1）将每个实例分配到距它最近的类中心，得到K 个类； （2）计分别计算各类中所有实例的均值，把它们作为各类新的类中心。 重复（1）和（2），直到K 个类中心的位置都固定，类的分配也固定。 在实验过程中通过利用Weka 软件中提供的simpleKmeans （也就是K 均值聚类算法对WINE 数据集进行聚类分析，更深刻的理解k 均值算法，并通过对实验结果进行观察分析，找出实验中所存在的问题。然后再在学习了解Weka 软件接口方面的基础上对Weka 软件进行一定的扩展以加入新的聚类算法来实现基于Weka 平台的聚类分析。 3 实验过程 3.1 K 均值聚类算法 3.1.1 K 均值聚类算法理论 K 均值算法是一种硬划分方法，简单流行但其也存在一些问题诸如其划分结果并不一定完全可信。K 均值算法的划分理论基础是 2 1 min i c k i k A i x v ∈=-∑∑ （1） 其中c 是划分的聚类数，i A 是已经属于第i 类的数据集i v 是相应的点到第i 类的平均距离，即
蚁群算法聚类分析 摘要： 蚁群算法是今年来才提出的一种基于种群寻优的启发式搜索算法，由意大利学者M.Dorigo等于1991年首先提出。该算法受到自然界中真实蚁群集体行为的启发，利用真实蚁群通过个体间的信息传递、搜索从蚁穴到食物间的最短路径的集体寻优特征，来解决一些离散系统中优化的困难问题。本文就蚁群算法的基本原理、模型特征、聚类分析展开论述。 关键字： 蚁群算法原理模型聚类分析
引言 蚁群算法是最近几年才提出的一种新型的模拟进化算法。蚂蚁是大家司空见惯的一种昆虫，而他们的群体合作的精神令人钦佩。他们的寻食、御敌、筑巢(蚂蚁的筑窝、蜜蜂建巢)之精巧令人惊叹。蚂蚁是自然界中常见的一种生物，人们对蚂蚁的关注大都是因为“蚂蚁搬家，天要下雨”之类的民谚。然而随着近代仿生学的发展，这种似乎微不足道的小东西越来越多地受到学者们的关注。1991年M．DIorigo，V.MaIliezzo等人首先提出了蚁群算法 (Ant Colony Algorithms)，人们开始了对蚁群的研究：相对弱小，功能并不强大的个体是如何完成复杂的工作的(如寻找到食物的最佳路径并返回等)。在此基础上一种很好的优化算法逐渐发展起来。 基本蚁群算法的机制原理 模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算智能模式引入的，该算法基于如下基本假设： (1)蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境做出反应，也只对其周围的局部环境产生影响； (2)蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行为实际上是其基因的适应性表现，即蚂蚁是反应型适应性主体； (3)在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为； 由上述假设和分析可见，基本蚁群算法的寻优机制包含两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，信息量越大，则该路径越容易被选择；时间越长，信息量会越小；在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解，类似于学习自动机的学习机制。 蚁群算法实际上是一类智能多主体系统，其自组织机制使得蚁群算法不需要对所求问题的每一方面都有详尽的认识。自组织本质上是蚁群算法机制在没有外界作用下使系统熵增加的动态过程，体现了从无序到有序的动态演化，其逻辑结构如图1所示。
聚类分析法 先用一个例子引出聚类分析 一、聚类分析法的概念 聚类分析又叫群分析、点群分析或者簇分析，是研究多要素事物分类问题的数量，并根据研究对象特征对研究对象进行分类的多元分析技术，它将样本或变量按照亲疏的程度，把性质相近的归为一类，使得同一类中的个体都具有高度的同质性，不同类之间的个体都具有高度的异质性。 聚类分析的基本原理是根据样本自身的属性，用数学方法按照某种相似性或差异性指标，定量地确定样本之间的亲疏关系，并按这种亲疏关系程度对样本进行聚类。 描述亲属程度通常有两种方法：一种是把样本或变量看出那个p维向量，样本点看成P 维空间的一个点，定义点与点之间的距离；另一种是用样本间的相似系数来描述其亲疏程度。有了距离和相似系数就可定量地对样本进行分组，根据分类函数将差异最小的归为一组，组与组之间再按分类函数进一步归类，直到所有样本归为一类为止。 聚类分析根据分类对象的不同分为Q型和R型两类，Q--型聚类是对样本进行分类处理，R--型聚类是对变量进行分类处理。 聚类分析的基本思想是，对于位置类别的样本或变量，依据相应的定义把它们分为若干类，分类过程是一个逐步减少类别的过程，在每一个聚类层次，必须满足“类内差异小，类间差异大”原则，直至归为一类。评价聚类效果的指标一般是方差，距离小的样品所组成的类方差较小。 常见的聚类分析方法有系统聚类法、动态聚类法（逐步聚类法）、有序样本聚类法、图论聚类法和模糊聚类法等。 二、对聚类分析法的评价 聚类分析也是一种分类技术。与多元分析的其他方法相比，该方法较为粗糙，理论上还不完善，但应用方面取得了很大成功。与回归分析、判别分析一起被称为多元分析的三大方法。 聚类的目的：根据已知数据，计算各观察个体或变量之间亲疏关系的统计量（距离或相关系数）。根据某种准则（最短距离法、最长距离法、中间距离法、重心法），使同一类内的
编程实现聚类分析算法 调用函数： min1.m——求矩阵最小值，返回最小值所在行和列以及值的大小 min2.m——比较两数大小，返回较小值 std1.m——用极差标准化法标准化矩阵 ds1.m——用绝对值距离法求距离矩阵 cluster.m——应用最短距离聚类法进行聚类分析 print1.m——调用各子函数，显示聚类结果 聚类分析算法 假设距离矩阵为vector，a阶，矩阵中最大值为max，令矩阵上三角元素等于max 聚类次数=a-1,以下步骤作a-1次循环: (1)求改变后矩阵的阶数,计作c (2)求矩阵最小值，返回最小值所在行e和列f以及值的大小g (3)for l=1:c,为vector(c+1,l)赋值，产生新类 (4)令第c+1列元素，第e行和第f行所有元素为max，第e列和第f列所有元素 为max 5.1源程序 %std1.m,用极差标准化法标准化矩阵 function std=std1(vector) max=max(vector); %对列求最大值 min=min(vector); [a,b]=size(vector); %矩阵大小,a为行数,b为列数 for i=1:a for j=1:b std(i,j)= (vector(i,j)-min(j))/(max(j)-min(j)); end end %ds1.m,用绝对值法求距离 function d=ds1(vector); [a,b]=size(vector); d=zeros(a); for i=1:a for j=1:a for k=1:b d(i,j)=d(i,j)+abs(vector(i,k)-vector(j,k)); end end
－5009－ 0引言 俗话说“物以类聚，人以群分”，人们在不知不觉中进行着 聚类活动，它是人们认识和探索事物之间内在联系的有效手段。聚类在数据挖掘中有着重要的地位，它既可以用作独立的数据挖掘工具，来发现数据库中数据分布的一些深入信息，也可以作为其它数据挖掘算法的预处理步骤。因此，聚类算法的研究具有很重要的现实意义。 蚁群算法不依赖于具体问题，具有全局优化能力，因此受 到了广大学者的注意。此后蚁群算法不断被改进并应用于不同领域。在聚类分析方面，Deneubourg等人受蚂蚁堆积尸体和分类它们的幼体启发，最早将蚁群算法用于聚类分析，从此开始了蚁群聚类算法的研究。 本文详细地讨论了现有的蚁群聚类算法的基本原理与性 能，在归纳总结的基础上提出需要完善的地方，以推动蚁群聚类算法的进一步研究及在更广阔的领域内得到应用。 1聚类概念及数学模型 聚类就是把一组个体按照相似性归为若干类或簇，使得 属于同一类或簇的个体之间的差别尽可能的小，而不同类或簇的个体间的差别尽可能大。聚类质量是用对象的相异度来评估，而不同类型变量的相异度的计算方法是不同的，常用的度量方法是区间标度变量中的欧几里得距离。 聚类的数学描述：设样本集={,=1,2,…,}，其中为 维模式向量，其聚类问题就是找到一个划分={ 1 , 2 ,…, }，满足= =1 ，≠，=，,=1,2,…,，≠，且使 得总的类内离散度和= =1 ,最小，其中为的 聚类中心，=1,2,…,；,为样本到其聚类中心的距 离，即,=‖‖。聚类目标函数为各样本到对应 聚类中心的距离总和，聚类中心=1 ，||为的样 本数目。 2蚁群聚类算法分类及应用 由于现实的蚁群运动过程接近于实际的聚类问题，所以 近年来涌现出大量的蚁群聚类算法。这些算法不仅思想、原理不同，而且算法的特性也根据解决问题的不同而不同，如初始参数及待聚类数据的要求、聚类形状等。
聚类分析及算法研究 公允价值计量属性的应用 ——以我国金融行业为例 赵婷 （重庆理工大学会计学院，重庆400054） 公允价值对金融行业的影响不容忽视。以我国金融行业A股上市公司2015年年报披露的信息为基础，分析了当前公允价值计量的应用意义；同时，阐述了金融行业运用公允价值计量的现状。结果表明，公允价值计量属性对金融行业资产的计量极其重要，可以帮助提高行业信息的相关性，有助于投资者了解金融市场动态。 标签：公允价值；金融行业；会计信息质量 1引言 随着经济的发展，国家在不断地修订会计准则，会计政策也随之产生巨大的变化，而会计政策的每一次变动，都对处于该经济背景下的企业产生了深远的影响。有学者认为，经济环境的变化将持续不断地影响着会计政策的选取，而如何在历次的变化中觉察会计政策变化的轨迹与特征，并利用其具有的特征和轨迹做出有利于企业经营管理的决策，应是我们重点关注的领域，而公允价值计量属性是会计政策的内容之一。 2公允价值计量属性的应用意义 公允价值计量属性对我国金融资产的计量影响深远。美国历史上著名的“储蓄与贷款危机”表明：企业若以公允价值对储蓄和贷款款项进行计量，能够及时的向大众传达企业已经资不抵债的现状，有助于减少投资者的损失，反之，企业若自欺欺人的认为自身资金实力雄厚，偿债能力较强，会误导外部投资者与政府监管部门而使企业和社会蒙受了巨大的损失。随着市场经济的发展，企业经营业务不断的扩张，越来越多的公司开展股票、债券等金融产品的交易，市场活跃程度加强，历史成本计量属性已不符合广大投资者的需求，急需“公允价值”入驻进行恰当的补充。 3金融行业公允价值计量属性应用现状 表12015年金融业A股上市公司年报披露公允价值变动损失最大的前十家公司及原因
聚类分析算法解析 一、不相似矩阵计算 1. 加载数据 data(iris) str(iris) > data (iris) > str(iris) 1 data .fizame ：": 150 oba.. of 5 var iato les : $ Sepal. Length: num 5,. 1 电?9 屯?=4.6 5 5.4 4, E S 4?4 4?9 ■■甲 S Sepal. Width : num 3<5 3 3*2 3.1 3.6 3*9 3.4 3.1 2 ,9 3*1 $ Petal .Length: nuio 1?4 1?4 1?3 1.5 1?4 1,4 1 ■理 1?5??? $ Petal. Width. : num 0..2 0). 2 0.2 0.2 0.2 0.4 0?3 0.2 0.2 0.1 ■… $ Species : Factor w/ 3 levels ^setosa^-j -?verslcolor **, ■八 1 1 分类分析是无指导的分类，所以删除数据中的原分类变量。 iris$Species<-NULL 2. 不相似矩阵计算 不相似矩阵计算，也就是距离矩阵计算，在 R 中采用dist()函数，或者cluster 包中 的daisy()函数。dist()函数的基本形式是 dist(x, method = "euclidean", diag = FALSE, upper = FALSE, p = 2) 其中x 是数据框(数据集)，而方法可以指定为欧式距离 "euclidean", 最大距离 "maximum",绝对值距离"manhattan", "canberra", 二进制距离非对称 "binary" 和明氏距 离"mi nkowski"。默认是计算欧式距离，所有的属性必须是相同的类型。 比如都是连续类型， 或者都是二值类型。 dd<-dist(iris) str(dd) > str(dd) Class 'disf atomic [1: 11175] CL 539 Cl ?￡l 0.6^18 D ? 1^11 0.616 **? ??—attr (*z *r Size F,J = lnt 150 .attr= logi FALSE .atvr ^Vpper**) = logi FALSE ■ +— attr ( *, fr methcd r,) = chr fF euclidean F, ?* 一 attr ( *t *r calldist (x = ir is) 距离矩阵可以使用 as.matrix() 函数转化了矩阵的形式，方便显示。 例样本间距离矩阵为 150行列的方阵。下面显示了 1~5号样本间的欧式距离。 dd<-as.matrix(dd) > str(dd) -attr (*y ^diimnames"] =List of 2 ..$ : chr [1:150] H l ,f ”旷 ”3” "4” : chr [1:150] n l rr "2n Iris 数据共150 0.51 0.648 0?141 num [1:150, 0 0.539
例： 为了更深入了解我国环境的污染程度状况，现利用2009 年数据对全国31个省、自治区、直辖市进行聚类分析。 解：现在要分析我国各个地区的环境污染程度，案例中选择了各地区“工业废气排放总量”、“工业废水排放总量”和“二氧化硫排放总量”三个指标来反映不同污染程度的环境状况，同时选择了北京等省市的数据加以研究。这个问题属于典型的多元分析问题，需要利用多个指标来分析各省市之间环境污染程度的差异。因此，可以考虑利用快速聚类分析来研究各省市之间的差异性，具体操作步骤如下。 1)打随书光盘中的数据文件9-2.sav，选择菜单栏中的【A nalyze（分析）】→【Classify（分 类）】→【K-Means Cluster（K均值聚类）】命令，弹出【K-Means Cluster Analysis（K均值聚类分析）】对话框。 2)在左侧的候选变量列表框中将X1、X2和X3变量设定为聚类分析变量，将其添加至 【Variables（变量）】列表框中；同时选择Y作为标识变量，将其移入【Label Cases by （个案标记依据）】列表框中。 3)在【Number of Clusters（聚类数）】文本框中输入数值“3”，表示将样品利用聚类分析 分为三类，如下图所示。 4)单击【Save（保存）】按钮，弹出【K-Means Cluster Analysis：Save（K均值聚类分析： 保存）】对话框；勾选【Cluster membership（聚类新成员）】和【Distanc e from cluster center （与聚类中心的距离）】复选框，表示输出样品的聚类类别及距离，其他选项保持系统默认设置，如下图所示，单击【Continue（继续）】按钮返回主对话框。
1、什么是聚类分析 聚类分析也称群分析或点群分析，它是研究多要素事物分类问题的数量方法，是一种新兴的多元统计方法，是当代分类学与多元分析的结合。其基本原理是，根据样本自身的属性，用数学方法按照某种相似性或差异性指标，定量地确定样本之间的亲疏关系，并按这种亲疏关系程度对样本进行聚类。 聚类分析是将分类对象置于一个多维空问中，按照它们空问关系的亲疏程度进行分类。 通俗的讲，聚类分析就是根据事物彼此不同的属性进行辨认，将具有相似属性的事物聚为一类，使得同一类的事物具有高度的相似性。 聚类分析方法，是定量地研究地理事物分类问题和地理分区问题的重要方法，常见的聚类分析方法有系统聚类法、动态聚类法和模糊聚类法等。 2、聚类分析方法的特征 （1）、聚类分析简单、直观。 （2）、聚类分析主要应用于探索性的研究，其分析的结果可以提供多个可能的解，选择最终的解需要研究者的主观判断和后续的分析。 （3）、不管实际数据中是否真正存在不同的类别，利用聚类分析都能得到分成若干类别的解。 （4）、聚类分析的解完全依赖于研究者所选择的聚类变量，增加或删除一些变量对最终的解都可能产生实质性的影响。 （5）、研究者在使用聚类分析时应特别注意可能影响结果的各个因素。 （6）、异常值和特殊的变量对聚类有较大影响，当分类变量的测量尺度不一致时，需要事先做标准化处理。 3、聚类分析的发展历程 在过去的几年中聚类分析发展方向有两个：加强现有的聚类算法和发明新的聚类算法。现在已经有一些加强的算法用来处理大型数据库和高维度数据，例如小波变换使用多分辨率算法，网格从粗糙到密集从而提高聚类簇的质量。 然而，对于数据量大、维度高并且包含许多噪声的集合，要找到一个“全能”的聚类算法是非常困难的。某些算法只能解决其中的两个问题，同时能很好解决三个问题的算法还没有，现在最大的困难是高维度(同时包含大量噪声)数据的处理。 算法的可伸缩性是一个重要的指标，通过采用各种技术，一些算法具有很好的伸缩
基于聚类分析的K-means算法研究及应用 摘要：通过对聚类分析及其算法的论述，从多个方面对这些算法性能进行比较，同时以儿童生长发育时期的数据为例通过聚类分析的软件和改进的K－means算法来进一步阐述聚类分析在数据挖掘中的实践应用。 关键词：数据挖掘；聚类分析；数据库；聚类算法 随着计算机硬件和软件技术的飞速发展，尤其是数据库技术的普及，人们面临着日益扩张的数据海洋，原来的数据分析工具已无法有效地为决策者提供决策支持所需要的相关知识，从而形成一种独特的现象“丰富的数据，贫乏的知识”。数据挖掘[1]又称为数据库中知识发现（Knowledge Discovery from Database，KDD），它是一个从大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的复杂过程。目的是在大量的数据中发现人们感兴趣的知识。 常用的数据挖掘技术包括关联分析、异类分析、分类与预测、聚类分析以及演化分析等。由于数据库中收集了大量的数据，聚类分析已经成为数据挖掘领域的重要技术之一。 1问题的提出 随着社会的发展和人们生活水平的提高，优育观念[2，3]逐渐渗透到每个家庭，小儿的生长发育越来越引起家长们的重视。中国每隔几年都要进行全国儿童营养调查，然而用手工计算的方法在大量的数据中分析出其中的特点和规律，显然是不现实的，也是不可行的。为了有效地解决这个问题，数据挖掘技术——聚类分析发挥了巨大的作用。 在数据挖掘领域，聚类算法经常遇到一些问题如聚类初始点的选择[4]、模糊因子的确定[5]等，大部分均已得到解决。现在的研究工作主要集中在为大型的数据库有效聚类分析寻找适当的方法、聚类算法对复杂分布数据和类别性数据聚类的有效性以及高维数据聚类技术等方面。本文通过对聚类分析算法的分析并重点从聚类分析的软件工具和改进的K－means算法两个方面来论证聚类分析在儿童生长发育时期中的应用。 2聚类算法分析 聚类[6]分析是直接比较各事物之间的性质，将性质相近的归为一类，将性质差别较大的归入不同的类。在医学实践中也经常需要做分类工作，如根据病人的一系列症状、体征和生化检查的结果，判断病人所患疾病的类型；或对一