海量数据聚类文献整理.doc

《海量数据聚类文献整理.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、目录聚类算法研究2面向中文自然语言文档的自动知识抽取方法8知识抽取技术综述*10当前知识抽取的主要技术方法解析*11基于本体的专利摘要知识抽取*13一种基于网格的改进的K-Means聚类算法15基于初始点选取的K-Means聚类近似常数算法17一种半监督K均值多关系数据聚类算法19基于单元区域的高维数据聚类算法21一种层次化的检索结果聚类方法23面向信息检索的快速聚类算法25基于MapReduce的分布式近邻传播聚类算法26一种基于层次距离计算的聚类算法27聚类算法研究题目：孙吉贵,刘杰,赵连宇等.聚类算法研究[J].软

2、件学报,2008,19(1):48-61.DOI:10.3724/SP.J.1001.2008.00048.基本知识储备与理解：01、聚类过程与定义：1)数据准备：包括特征标准化和降维。2)特征选择：从最初的特征中选择最有效的特征，并将其存储于向量中。3)特征提取：通过对所选择的特征进行转换形成新的突出特征。4)聚类(或分组)：首先选择合适特征类型的某种距离函数(或构造新的距离函数)进行接近程度的度量；而后执行聚类或分组。5)聚类结果评估：是指对聚类结果进行评估．评估主要有3种：外部有效性评估、内部有效性评估和相关性测试

3、评估。聚类的定义：一个类簇内的实体是相似的，不同类簇的实体是不相似的；一个类簇是测试空间中点会聚，同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离。所谓聚类，就是把大量的d维数据对象（N个）聚集成K个类（K

4、DENCLUE（基于对象的聚类只能发现球状的簇，基于密度可以发现任意的簇)基于网格的方法：将一个网格内的数据当成一个对象来处理，STING、WaveCluster、CLIQUE基于模型的方法：统计学方法（COBWEB）和神经网络方法（竞争学习、自组织特征映射），数据是根据潜在的概率分布生成的。02、层次聚合算法：又叫做树聚类算法，使用数据的联接规则，透过一种层次架构方式，反复将数据进行分裂和聚合，以形成一个层次序列的聚类问题解。层次聚类算法：类似于树形结构，自底向上逐层聚合，直至所有样本都属于同一个类。Binary—Po

5、sitive方法（正二进制法）：该方法把待分类数据以正的二进制形式存储于一个二维矩阵中，其中，行表示记录(对象)，列表示其属性的可能取值。记录对应的取值为1或者O，分别表示此记录有对应的属性值或者不存在对应属性值。因此，相似性距离计算只在被比较的二进制向量中的正比特位上进行，即只在取值为1的记录(对象)之间进行。将原始数据转换成正二进制会改善聚类结果的正确性和聚类的鲁棒性，对于层次聚类算法尤其适用。连续数据的粗聚类算法(roughclusteringofsequentialdata，简称RCOSD)：关键思想是寻找能捕捉

6、数据序列的连续信息及内容信息的一个特征集，并把这些特征集映射到一个上近似空间，应用约束相似性上近似技术获得粗类簇的上近似，其中一个元素可以属于多个类簇．该算法引入S3M作为Web数据的相似性度量方法，S3M既考虑了项的出现次序又考虑了集合内容。该算法每一次迭代可以合并两个或多个类，所以加快了层次聚类速度。该算法能够有效挖掘连续数据，并刻画类簇的主要特性，帮助Web挖掘者描述潜在的新的Web用户组的特性。03、划分式聚类算法：需要预先指定聚类数据或者聚类中心，通过反复迭代运算，逐步降低目标函数的误差值，当目标函数收敛时，得

7、到最终的聚类结果。K均值聚类：第一步：选择K个点作为初始的质心；第二步：repeat第三步：将每个点指派到最近的质心，形成k个簇；第四步：重新计算每个簇的质心；第五步；until质心不再发生变化。优点：能对大型数据集进行高效分类，其计算复杂性为O(tKmn)，其中，t为迭代次数，K为聚类数，m为特征属性数，n为待分类的对象数，通常，K,m，t<

8、K-modes算法：该算法对K-means进行了3点扩展：引入了处理分类对象的新的相异性度量方法(简单的相异性度量匹配模式)，使用modes代替means，并在聚类过程中使用基于频度的方法修正modes，以使聚类代价函数值最小化。K-modes算法的另一个优点是modes能给出类的特性描述。缺点是会产生局部最优解，依