聚类算法叙述

1、基于划分聚类算法（partition clustering)k-means：是一种典型的划分聚类算法，它用一个聚类的中心来代表一个簇，即在迭代过程中选择的聚点不一定是聚类中的一个点，该算法只能处理数值型数据k-modes：K-Means算法的扩展，采用简单匹配方法来度量分类型数据的相似度k-prototypes：结合了K-Means和K-Modes两种算法，能够处理混合型数据k-medoids：在迭代过程中选择簇中的某点作为聚点，PAM是典型的k-medoids算法CLARA：CLARA算法在PAM的基础上采用了抽样技术，能够处理大规模数据CLARANS：CLARANS算法融合了PAM和CLA

2、RA两者的优点，是第一个用于空间数据库的聚类算法Focused CLARAN：采用了空间索引技术提高了CLARANS算法的效率PCM：模糊集合理论引入聚类分析中并提出了PCM模糊聚类算法基于层次聚类算法：CURE：采用抽样技术先对数据集D随机抽取样本，再采用分区技术对样本进行分区，然后对每个分区局部聚类，最后对局部聚类进行全局聚类ROCK：也采用了随机抽样技术，该算法在计算两个对象的相似度时，同时考虑了周围对象的影响CHEMALOEN（变色龙算法）：首先由数据集构造成一个K-最近邻图Gk ,再通过一个图的划分算法将图Gk 划分成大量的子图,每个子图代表一个初始子簇,最后用一个凝聚的层次聚类算法

3、反复合并子簇，找到真正的结果簇SBAC：SBAC算法则在计算对象间相似度时，考虑了属性特征对于体现对象本质的重要程度，对于更能体现对象本质的属性赋予较高的权值BIRCH：BIRCH算法利用树结构对数据集进行处理，叶结点存储一个聚类，用中心和半径表示，顺序处理每一个对象，并把它划分到距离最近的结点，该算法也可以作为其他聚类算法的预处理过程BUBBLE：BUBBLE算法则把BIRCH算法的中心和半径概念推广到普通的距离空间BUBBLE-FM：BUBBLE-FM算法通过减少距离的计算次数，提高了BUBBLE算法的效率基于密度聚类算法：DBSCAN：DBSCAN算法是一种典型的基于密度的聚类算法，该算

4、法采用空间索引技术来搜索对象的邻域，引入了“核心对象”和“密度可达”等概念，从核心对象出发，把所有密度可达的对象组成一个簇GDBSCAN：算法通过泛化DBSCAN算法中邻域的概念，以适应空间对象的特点DBLASD：OPTICS：OPTICS算法结合了聚类的自动性和交互性，先生成聚类的次序，可以对不同的聚类设置不同的参数，来得到用户满意的结果FDC：FDC算法通过构造k-d tree把整个数据空间划分成若干个矩形空间，当空间维数较少时可以大大提高DBSCAN的效率基于网格的聚类算法：STING：利用网格单元保存数据统计信息，从而实现多分辨率的聚类WaveCluster：在聚类分析中引入了小波变换

5、的原理，主要应用于信号处理领域。（备注：小波算法在信号处理，图形图像，加密解密等领域有重要应用，是一种比较高深和牛逼的东西）CLIQUE：是一种结合了网格和密度的聚类算法OPTIGRID：基于神经网络的聚类算法：自组织神经网络SOM：该方法的基本思想是-由外界输入不同的样本到人工的自组织映射网络中，一开始时，输入样本引起输出兴奋细胞的位置各不相同，但自组织后会形成一些细胞群，它们分别代表了输入样本，反映了输入样本的特征基于统计学的聚类算法：COBWeb：COBWeb是一个通用的概念聚类方法，它用分类树的形式表现层次聚类CLASSIT：AutoClass：是以概率混合模型为基础，利用属性的概率分

6、布来描述聚类，该方法能够处理混合型的数据，但要求各属性相互独立-几种常用的聚类算法从可伸缩性、适合的数据类型、高维性（处理高维数据的能力）、异常数据的抗干扰度、聚类形状和算法效率6个方面进行了综合性能评价，评价结果如表1所示：算法名称可伸缩性适合的数据类型高维性异常数据的抗干扰性聚类形状算法效率WaveCluster很高数值型很高较高任意形状很高ROCK很高混合型很高很高任意形状一般BIRCH较高数值型较低较低球形很高CURE较高数值型一般很高任意形状较高K-Prototypes一般混合型较低较低任意形状一般DENCLUE较低数值型较高一般任意形状较高OptiGrid一般数值型较高一般任意形状

7、一般CLIQUE较高数值型较高较高任意形状较低DBSCAN一般数值型较低较高任意形状一般CLARANS较低数值型较低较高球形较低-目前聚类分析研究的主要内容：对聚类进行研究是数据挖掘中的一个热门方向，由于以上所介绍的聚类方法都存在着某些缺点，因此近些年对于聚类分析的研究很多都专注于改进现有的聚类方法或者是提出一种新的聚类方法。以下将对传统聚类方法中存在的问题以及人们在这些问题上所做的努力做一个简单的总结：1 从以上对传统的聚类分析方法所做的总结来看，不管是k-means方法，还是CURE方法，在进行聚类之前都需要用户事先确定要得到的聚类的数目。然而在现实数据中，聚类的数目是未知的，通常要经过不

8、断的实验来获得合适的聚类数目，得到较好的聚类结果。2 传统的聚类方法一般都是适合于某种情况的聚类，没有一种方法能够满足各种情况下的聚类，比如BIRCH方法对于球状簇有很好的聚类性能，但是对于不规则的聚类，则不能很好的工作；K-medoids方法不太受孤立点的影响，但是其计算代价又很大。因此如何解决这个问题成为当前的一个研究热点，有学者提出将不同的聚类思想进行融合以形成新的聚类算法，从而综合利用不同聚类算法的优点，在一次聚类过程中综合利用多种聚类方法，能够有效的缓解这个问题。3 随着信息时代的到来，对大量的数据进行分析处理是一个很庞大的工作，这就关系到一个计算效率的问题。有文献提出了一种基于最小

9、生成树的聚类算法，该算法通过逐渐丢弃最长的边来实现聚类结果，当某条边的长度超过了某个阈值，那么更长边就不需要计算而直接丢弃，这样就极大地提高了计算效率，降低了计算成本。4 处理大规模数据和高维数据的能力有待于提高。目前许多聚类方法处理小规模数据和低维数据时性能比较好，但是当数据规模增大，维度升高时，性能就会急剧下降，比如k-medoids方法处理小规模数据时性能很好，但是随着数据量增多，效率就逐渐下降，而现实生活中的数据大部分又都属于规模比较大、维度比较高的数据集。有文献提出了一种在高维空间挖掘映射聚类的方法PCKA（Projected Clustering based on the K-Me

10、ans Algorithm），它从多个维度中选择属性相关的维度，去除不相关的维度，沿着相关维度进行聚类，以此对高维数据进行聚类。5 目前的许多算法都只是理论上的，经常处于某种假设之下，比如聚类能很好的被分离，没有突出的孤立点等，但是现实数据通常是很复杂的，噪声很大，因此如何有效的消除噪声的影响，提高处理现实数据的能力还有待进一步的提高。经典算法研究系列：七、深入浅出遗传算法分类：01.Algorithms（研究）2011-01-12 20:5749922人阅读评论(68)收藏举报算法优化生物图像处理数据挖掘经典算法研究系列：七、深入浅出遗传算法作者:July二零一一年一月十二日。本文参考：维基

11、百科华南理工大学电子讲义互联网-一、初探遗传算法Ok，先看维基百科对遗传算法所给的解释：遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突

12、变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。光看定义，可能思路并不清晰，咱们来几个清晰的图解、步骤、公式：基本遗传算法的框图：所以，遗传算法基本步骤是：1）初始化t0进化代数计数器；T是最大进化代数；随机生成M个个体作为初始群体P（t）；2）个体评价计算P（t）中各个个体的适应度值；3）选择运算将选择算子作用于群体；4）交叉运算将交叉算子作用于群体；5）变异运算将变异算子作用于群体，并通过以上运算得到下一代群体P（t+1）;6）终止条件判断tT：tt+1转到步骤2；tT：终止输出解。好的，看下遗传算法的伪代码实现：ProceduresGA：伪代码begininitializeP

13、(0);t=0;/t是进化的代数，一代、二代、三代.while(t=T)dofori=1toMdo /M是初始种群的个体数EvaluatefitnessofP(t);/计算P（t）中各个个体的适应度endforfori=1toMdoSelectoperationtoP(t);/将选择算子作用于群体endforfori=1toM/2doCrossoveroperationtoP(t);/将交叉算子作用于群体endforfori=1toMdoMutationoperationtoP(t);/将变异算子作用于群体endforfori=1toMdoP(t+1)=P(t);/得到下一代群体P（t+1）e

14、ndfort=t+1;/终止条件判断tT：tt+1转到步骤2endwhileend二、深入遗传算法1、智能优化算法概述智能优化算法又称现代启发式算法，是一种具有全局优化性能、通用性强且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。遗传算法属于智能优化算法之一。常用的智能优化算法有：遗传算法、模拟退火算法、禁忌搜索算法、粒子群算法、蚁群算法。（本经典算法研究系列，日后将陆续阐述模拟退火算法、粒子群算法、蚁群算法。）2、遗传算法概述遗传算法是由美国的J.Holland教授于1975年在他的专著自然界和人工系统的适应性中

15、首先提出的。借鉴生物界自然选择和自然遗传机制的随机化搜索算法。模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象。在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。基本遗传算法（SimpleGeneticAlgorithms，GA)又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。3、基本遗传算法的组成（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选

16、择、交叉、变异）（4）运行参数接下来，咱们分门别类，分别阐述着基本遗传算法的五个组成部分：1、编码遗传算法（GA）通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。基本遗传算法（SGA）使用二进制串进行编码。初始种群：基本遗传算法（SGA）采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。2、适应度函数遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。3

17、.1、选择算子遗传算法使用选择运算对个体进行优胜劣汰操作。适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是从父代群体中选取一些个体，遗传到下一代群体。基本遗传算法（SGA）中选择算子采用轮盘赌选择方法。Ok，下面就来看下这个轮盘赌的例子，这个例子通俗易懂，对理解选择算子帮助很大。轮盘赌选择方法轮盘赌选择又称比例选择算子，其基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为N，个体xi 的适应度为 f(xi)，则个体xi的选择概率为：轮盘赌选择法可用如下过程模拟来实现：(1)在0, 1内产生一个均匀分布的随机数r。

18、(2)若rq1,则染色体x1被选中。(3)若qk-1rqk(2kN), 则染色体xk被选中。其中的qi称为染色体xi (i=1, 2, , n)的积累概率, 其计算公式为：积累概率实例：轮盘赌选择方法的实现步骤:（1）计算群体中所有个体的适应度值；（2）计算每个个体的选择概率；（3）计算积累概率；（4）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。例如，有染色体s1= 13 (01101)s2= 24 (11000)s3= 8 (01000)s4= 19 (10011)假定适应度为f(s)=s2 ，则f (s1) =

19、f(13) = 132 = 169f (s2) = f(24) = 242 = 576f (s3) = f(8) = 82 = 64f (s4) = f(19) = 192 = 361染色体的选择概率为：染色体的累计概率为：根据上面的式子，可得到：例如设从区间0,1中产生4个随机数:r1=0.450126,r2=0.110347r3=0.572496,r4=0.985033.2、交叉算子交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。基本

20、遗传算法（SGA）中交叉算子采用单点交叉算子。单点交叉运算3.3、变异算子变异运算，是指改变个体编码串中的某些基因值，从而形成新的个体。变异运算是产生新个体的辅助方法，决定遗传算法的局部搜索能力，保持种群多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。基本遗传算法（SGA）中变异算子采用基本位变异算子。基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则将其变为1；反之，若原有基因值为1，则将其变为0 。基本位变异算子的执行过程：4、运行参数（1）M ：种群规模

21、（2）T ： 遗传运算的终止进化代数（3）Pc ：交叉概率（4）Pm ：变异概率三、浅出遗传算法遗传算法的本质遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。遗传算法的主要有以下八方面的应用：（1）组合优化 （2）函数优化 （3）自动控制 （4）生产调度（5）图像处理 （6）机器学习 （7）人工生命 （8）数据挖掘四、遗传算法的应用遗传算法的应用举例、透析本质（这个例子简明、但很重要）已知x为整数，利用遗传算法求解区间0,

22、31上的二次函数y=x2的最大值。分析原问题可转化为在区间0, 31中搜索能使 y 取最大值的点 a 的问题。个体：0, 31 中的任意点x适应度：函数值f(x)=x2解空间：区间0, 31这样, 只要能给出个体x的适当染色体编码, 该问题就可以用遗传算法来解决。解(1)设定种群规模,编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1s1= 13 (01101), s2= 24 (11000)s3= 8 (01000), s4= 19 (10011）(2) 定义适应度函数, 取适应度函数f (x)=x2(3) 计算各代种群中的各个体的适应度, 并

23、对其染色体进行遗传操作,直到适应度最高的个体，即31（11111）出现为止。首先计算种群S1中各个体：s1= 13(01101), s2= 24(11000)s3= 8(01000), s4= 19(10011)的适应度f (si), 容易求得：f (s1) = f(13) = 132 = 169f (s2) = f(24) = 242 = 576f (s3) = f(8) = 82 = 64f (s4) = f(19) = 192 = 361再计算种群S1中各个体的选择概率：由此可求得P(s1) = P(13) = 0.14P(s2) = P(24) = 0.49P(s3) = P(8) =

24、 0.06P(s4) = P(19) = 0.31再计算种群S1中各个体的积累概率：选择-复制设从区间0, 1中产生4个随机数如下:r1 = 0.450126, r2 = 0.110347r3 = 0.572496, r4 = 0.98503于是，经复制得群体：s1 =11000（24）, s2 =01101（13）s3 =11000（24）（24被选中俩次）, s4 =10011（19）交叉设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1与s2配对，s3与s4配对。s1 =11000（24）, s2 =01101（13）s3 =11000（24）, s4 =10011（19）分别交换后两位基因，得新染色体：s1=11001（25）, s2=01100（12）s3=11011（27）, s4=10000（16）变异设变异率pm=0.001。这样，