适应性聚类算法及其应用的研究

1、项目负责人: 戴靖 项目成员： 郑萍 祝文斌 陈永宏23研究意义：问题一：如何从这些众多的文件中找到代表某些主题的文件；问题二：如何根据这具有代表性的文件再找到与它相关的文件。透过聚类算法可以找出一个具有代表性的特征的文件，亦即聚类中心，再根据聚类后得到的结果就可以找到与这篇代表性文件相关的其它文件。文件数量众多，浏览文件费事长。4研究意义：u 目前大部分的聚类算法，对于某些少量但是又重要的文件却无法正确的分别出来，反而可能被归类到毫不相干的类别去，甚至会被当成噪声(Noise) 而不予以处理。u 本项目中也尝试改进适应性聚类算法使其应用在文件聚类的问题上，希望能够解决以上的问题。56国内外同

2、类研究工作现状：u 聚类(clustering)是应用于数据分析的技术之一。主要功能是将一群在多维度空间(multi-dimensional space) 中的数据，依照数据的属性或特征来聚类。u 聚类的方法区分为阶层式聚类法(hierarchical clustering) 与切割式聚类法(partitional clustering) 这两大类。7国内外同类研究工作现状：u 阶层式聚类法：将数据层次分裂或合并，聚类的阶层通常都会被视为一个树状结构。u 切割式聚类法：是指在一个N 度空间中，将数据切割成K 个群集。切割式聚类法中，常用的方法是K-Means 算法，它是利用不断迭代的方式，将一

3、群在多维度空间中的数据分为K 群。以随机选取K 个中心代表点，利用欧基里德距离(Euclidean Distance) ，找出最接近每一群数据的中心点。8国内外同类研究工作现状：遗传算法(Genetic Algorithms; GAs) 是一种仿真自然界演化过程的最佳化搜寻机制。实际问题参数集编码群体t计算适值运算：复制、交叉、变异群体t+1满足要求？群体t+1群体tNY解码改善式解决实际问题9国内外同类研究工作现状：适应性遗传算法： 为了使遗传算法的演化过程更符合自然界的演化过程，尝试改善传统遗传算法，加入适应性的观念有其必要。适应性遗传算法之目的：u 维持族群中染色体的差异性；u 改善遗传

4、算法过早收敛的情况；u 避免因交配运作而导致schemata 遭到破坏。 10 目前聚类算法是被大量的应用在计算机视觉和图形识上，但是对于文件聚类问题以目前较常用的的聚类算法并无法得到令人满意的结果，并且受到噪声的影响而导致聚类准确度不高。国内外同类研究工作现状：1112主要研究内容及拟解决的问题：u 改进算法，搭配使用阶层式聚类算法和分割式聚类算法并应用在文件聚类上。u 消除噪声干扰，应用改进的模糊聚类PAC算法对噪声数据进行处理以提高聚类的准确性。u 程序实现，具体收集某类文件（比如新闻，某公司的表单）并用生成的程序将其聚类。13主要研究内容及拟解决的问题： 将适应性的观念结合遗传算法，尝

5、试将固定数值的交配机率跟突变机率修改成适应性机率，并且将其理论应用于解决K-Means 在聚类时所产生误判的问题以及针对数据量大的聚类时可以加快演化速度。 运用传统遗传算法在求得近似最佳解时，可能会陷入局部最佳解的范围。14主要研究内容及拟解决的问题：染色体编码与族群初始化 切割式聚类是将一群在多维度空间(multi-dimensional space)中的数据，依照数据的属性或特征来聚类，并将数据切割成K 群。 将K 个群集的中心点所形成的向量编码成染色体，每一条染色体就是代表一个可能聚类的结果。 染色体的长度定为：l 代表染色体长度，d 代表数据属性维度或是空间维度，K 则表示聚类的数目。

6、 染色体的编码方式采用实数编码。kdl15主要研究内容及拟解决的问题： 函数 适应值的计算方面，是利用染色体所配置的中心点，以类似K-Means 算法将数据聚类，同时以聚类后所求得新的中心点更新染色体内原有的中心点。我们将适应函数定为： xj 表示为Ci ,i=1,. , K的数据点， zi 则为第Ci 群中心点。ijC Xijn,1,=jk,1,=i ,z-xF16主要研究内容及拟解决的问题：演化流程:选择方式竞争法交配方式单点交配交配机率适应性机率突变方式渐进式突变突变机率适应性机率17项目目标： 改进聚类算法，使两种聚类算法能够优缺互补，并在文件聚类上应用能得到令人满意的结果。努力发表论文一篇，并争取得到程序实现。本PPT模版来自PowerB