海量数据聚类文献整理

1目录聚类算法研究...........................................................................................................................2面向中文自然语言文档的自动知识抽取方法.......................................................................8知识抽取技术综述*...............................................................................................................10当前知识抽取的主要技术方法解析*...................................................................................11基于本体的专利摘要知识抽取*...........................................................................................13一种基于网格的改进的K-Means聚类算法.........................................................................15基于初始点选取的K-Means聚类近似常数算法.................................................................17一种半监督K均值多关系数据聚类算法.............................................................................19基于单元区域的高维数据聚类算法.....................................................................................21一种层次化的检索结果聚类方法.........................................................................................23面向信息检索的快速聚类算法.............................................................................................25基于MapReduce的分布式近邻传播聚类算法....................................................................27一种基于层次距离计算的聚类算法.....................................................................................302聚类算法研究题目：孙吉贵,刘杰,赵连宇等.聚类算法研究[J].软件学报,2008,19(1):48-61.DOI:10.3724/SP.J.1001.2008.00048.基本知识储备与理解：01、聚类过程与定义：1)数据准备：包括特征标准化和降维。2)特征选择：从最初的特征中选择最有效的特征，并将其存储于向量中。3)特征提取：通过对所选择的特征进行转换形成新的突出特征。4)聚类(或分组)：首先选择合适特征类型的某种距离函数(或构造新的距离函数)进行接近程度的度量；而后执行聚类或分组。5)聚类结果评估：是指对聚类结果进行评估．评估主要有3种：外部有效性评估、内部有效性评估和相关性测试评估。聚类的定义：一个类簇内的实体是相似的，不同类簇的实体是不相似的；一个类簇是测试空间中点会聚，同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离。所谓聚类，就是把大量的d维数据对象（N个）聚集成K个类（KN），使同一个类内对象的相似性尽可能最大，而不同类内的对象的相似性尽量达到最小，也就是说，形成类之后，同一个类内对象具有很高的相似性，而且与不属于该类的对象有迥然的差异。划分的方法：k均值，k中心点灯；层次的方法：凝聚法和分裂法，BIRCH，CURE,变色龙法；基于密度的方法：DBSCAN,OPTICS,DENCLUE（基于对象的聚类只能发现球状的簇，基于密度可以发现任意的簇)基于网格的方法：将一个网格内的数据当成一个对象来处理，STING、WaveCluster、CLIQUE基于模型的方法：统计学方法（COBWEB）和神经网络方法（竞争学习、自组织特征映射），数据是根据潜在的概率分布生成的。02、层次聚合算法：又叫做树聚类算法，使用数据的联接规则，透过一种层次架构方式，反复将数据进行分裂和聚合，以形成一个层次序列的聚类问题解。层次聚类算法：类似于树形结构，自底向上逐层聚合，直至所有样本都属于同一个类。Binary—Positive方法（正二进制法）：该方法把待分类数据以正的二进制形式存储于一个二维矩阵中，其中，行表示记录(对象)，列表示其属性的可能取值。记录对应的取值为1或者O，分别表示此记录有对应的属性值或者不存在对应属性值。因此，相似性距离计算只在被比较的二进制向量中的正比特位上进行，即只在取值为1的记录(对象)之间进行。将原始数据转换成正二进制会改善聚类结果的正确性和聚类的鲁棒性，对于层次聚类算法尤其适用。连续数据的粗聚类算法(roughclusteringofsequentialdata，简称RCOSD)：关键思想是寻找能捕捉数据序列的连续信息及内容信息的一个特征集，并把这些特征集映射到3一个上近似空间，应用约束相似性上近似技术获得粗类簇的上近似，其中一个元素可以属于多个类簇．该算法引入S3M作为Web数据的相似性度量方法，S3M既考虑了项的出现次序又考虑了集合内容。该算法每一次迭代可以合并两个或多个类，所以加快了层次聚类速度。该算法能够有效挖掘连续数据，并刻画类簇的主要特性，帮助Web挖掘者描述潜在的新的Web用户组的特性。03、划分式聚类算法：需要预先指定聚类数据或者聚类中心，通过反复迭代运算，逐步降低目标函数的误差值，当目标函数收敛时，得到最终的聚类结果。K均值聚类：第一步：选择K个点作为初始的质心；第二步：repeat第三步：将每个点指派到最近的质心，形成k个簇；第四步：重新计算每个簇的质心；第五步；until质心不再发生变化。优点：能对大型数据集进行高效分类，其计算复杂性为O(tKmn)，其中，t为迭代次数，K为聚类数，m为特征属性数，n为待分类的对象数，通常，K,m，tn．在对大型数据集聚类时,K-means算法比层次聚类算法快得多。不足：通常会在获得一个局部最优值时终止；仅适合对数值型数据聚类；只适用于聚类结果为凸形(即类簇为凸形)的数据集。K-modes算法：该算法对K-means进行了3点扩展：引入了处理分类对象的新的相异性度量方法(简单的相异性度量匹配模式)，使用modes代替means，并在聚类过程中使用基于频度的方法修正modes，以使聚类代价函数值最小化。K-modes算法的另一个优点是modes能给出类的特性描述。缺点是会产生局部最优解，依赖于初始化modes的选择和数据集中数据对象的次序。初始化modes的选择策略尚需进一步研究。迭代初始点集求精K-modes算法，由于k-modes算法需要通过预先决定或者随机选择类的初始modes才能够聚类分类数据，并且初始modes的差异常常会导致截然不同的聚类结果，可通过迭代初始点求精算法予以解决。一致性保留k均值算法：对于一个类中的任意数据点，要求它的K最近邻和K互最近邻都必须在该类中。模糊聚类算法（FCM）：主要适用于图像分割，成功之处在于为解决每个图像像素的隶属需要引入了模糊性，可以保留更多的图像的信息。缺点是没有考虑图像上下文中的任何空间信息，对于噪声比较敏感。图论算法：构造一颗最小生成树（MST），通过删除最小生成树的最长边来形成类。04、基于网格和密度聚类：基于密度，通过数据密度来发现任意形状的类簇；基于网格，使用一个网格结构，围绕模式组织由矩阵块划分的值空间，基于块的分布信息实现模式聚类。DBSCAN算法：第一步：将所有点标记为核心点、边界点、噪声点第二步：删除噪声点；第三步：为距离在Eps(半径)之内的所有核心点之间赋予一条边；第四步：每组连通的核心点形成一个簇；第五步：将每个边界点指派到一个与之关联的核心点的簇中。09、ACODF聚类算法：不需要求任何硬子问题，但能给出近似最优解的聚类算法。4第一步：应用蚁群算法，规定每个蚂蚁只需要访问全部城市数量的十分之一，并且访问城市数目逐渐减少；循环几次，两点之间的相对较短的路径的信息素浓度会增大，两点之间相对长的路径的信息素会减少。因此，蚂蚁会选择访问近距离的节点，并用自己的信息加强次路径，最后形成具有较高浓度的路径，聚类完毕。第二步：应用模拟退火策略来解决局部最优解的问题。ns(t+1)=ns(t)×T其中ns是蚁群在T0函数期间访问的节点数，ns(t+1)表示当前蚁群的访问的节点数,ns(t)表示上一次循环蚁群访问的节点数，r是一个常数(T=0.95)。nf(t+1)=2ns(t)/3-ins(t)／(run*3)其中，nf是蚁群在T1函数期间访问的节点数，nf(t+1)表示蚁群当前访问的节点数，nf(t)表示上一次循环蚁群访问的节点数，run=2，i∈{l，2}。第三步：使用锦标赛选择策略，即从N条路径中随机选择K条路径，再从K条路径中选择最短路径。5算法类型算法名称算法描述算法优缺点凝聚层次聚类算法CURE算法针对大型数据库的高效的聚类算法，采用固定数目有代表性的点代表一个簇，处理大数据量时采用随机取样。优点：对孤立点的处理更加健壮，能够识别形状复杂，大小不一的聚类。缺点：代表点是来自一组随机抽取的样本集，它的最初数目需要人为确定。ROCK算法对CURE算法的改进，采用基于元组之间的连接数目来计算相似形。优点：容易聚类，并适用于类别属性的数据。缺点：该算法的相似度函式sim是基于领域专家的直觉。CHAMELEON算法在层次聚类中利用了动态建模技术，通过图划分算法将数据对象划分为相对较小的子集，然后用一个凝聚的层次聚类算法通过反复合并子类来找到结果簇。优点：在发现高质量的任意形状簇方面有更强的能力。缺点：聚类结果的准确性和有效性有待提高，时间效率需进一步优化。分裂层次聚类算法DIANA算法采用自顶向下的策略，先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件。其主要思想是将那些成员之间不是非常紧密的簇进行分裂。优点：适用于任意形状和任意属性的数据集，灵活控制不同层次的聚类粒度，聚类能力强。缺点：大大延长了算法的执行时间，不能回溯处理。基于密度的分割聚类算法DBSCAN算法基于密度的空间聚类算法，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在空间数据库中发现任意形状的聚类。优点：在处理空间数据时能快速、有效和发现任意形状聚类。缺点：对用户定义的参数是敏感的,参数难以确定，全局密度参数不能刻画内在的聚类结构。DENCLU算法基于一组密度分布函数的算法，根据数据点在属性空间中的密度进行聚类，得到的是全局最优化分。优点：有良好的聚类特征，算法速度快，可以有效揭示数据分布的内在层次，可以发现任意形状的聚类，对噪声数据不敏感。缺点：聚类结果严重依赖于用户参数的合理选取。OPTICS算法通过对象排序识别聚类结果，为聚类分析生成一个增广的簇排序，这个排序代表了各样本点基于密度的聚类结构。优点：具有良好的聚类想能，具有较高的灵活性。缺点：需要额外的存储空间，处理稀疏