海量数据聚类文献

名目

聚类算法讨论..............................................................2

面对中文自然语言文档的自动学问抽取方法...................................8

学问抽取技术综述*........................................................10

当前学问抽取的主要技术方法解析*..........................................11

基于本体的专利摘要学问抽取*..............................................13

一种基于网格的改进的K-Means聚类算法.....................................15

基于初始点选取的K-Means聚类近似常数算法.................................17

一种半监督K均值多关系数据聚类算法.......................................19

基于单元区域的高维数据聚类算法...........................................21

一种层次化的检索结果聚类方法.............................................23

面对信息检索的快速聚类算法...............................................25

基于MapReduce的分布式近邻传播聚类算法..................................27

一种基于层次距离计算的聚类算法...........................................30

聚类算法讨论

题目：孙吉贵，刘杰，赵连宇等.聚类算法讨论[J].软件学

JU,2022,19（1）:48-61.DOI:10.3724/SPJ.1001.2022.00048.

基本学问储备与理解：

01、聚类过程与定义：

1）数据预备：包括特征标准化和降维。

2）特征选择：从最初的特征中选择最有效的特征，并将其存储于向量中。

3）特征提取：通过对所选择的特征进行转换形成新的突出特征。

4）聚类（或分组）：首先选择合适特征类型的某种距离函数（或构造新的距离函数）进行

接近程度的度量；而后执行聚类或分组。

5）聚类结果评估：是指对聚类结果进行评估.评估主要有3种：外部有效性评估、内部

有效性评估和相关性测试评估。

聚类的定义：一个类簇内的实体是相像的，不同类簇的实体是不相像的；一个类簇是测

试空间中点会聚，同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离。

所谓聚类，就是把大量的d维数据对象（N个）聚集成K个类（K<N）,使同一个类内对象

的相像性尽可能最大，而不同类内的对象的相像性尽量达到最小，也就是说，形成类之

后，同一个类内对象具有很高的相像性，而且与不属于该类的对象有迥然的差异。

划分的方法：k均值，k中心点灯；

层次的方法：分散法和分裂法，BIRCH,CURE,变色龙法；

基于密度的方法：DBSCAN,OPTICS,DENCLUE（基于对象的聚类只能发觉球状的簇，基于

密度可以发觉任意的簇）

基于网格的方法：将一个网格内的数据当成一个对象来处理，STING、WaveCluster.

CLIQUE

基于模型的方法：统计学方法（COBWEB）和神经网络方法（竞争学习、自组织特征映射），

数据是依据潜在的概率分布生成的。

02、层次聚合算法：

又叫做树聚类算法，使用数据的联接规章，透过一种层次架构方式，反复将数据进行分

裂和聚合，以形成一个层次序列的聚类问题解。

层次聚类算法：类似于树形结构，自底向上逐层聚合，直至全部样本都属于同一个类。

Binary-Positive方法（正二进制法）：该方法把待分类数据以正的二进制形式存储于

一个二维矩阵中，其中，行表示纪录（对象），列表示其属性的可能取值。纪录对应的取

值为1或者0,分别表示此纪录有对应的属性值或者不存在对应属性值。因此，相像性距

离计算只在被比较的二进制向量中的正比特位上进行，即只在取值为1的纪录（对象）之

间进行。将原始数据转换成正二进制会改善聚类结果的正确性和聚类的鲁棒性，对于层

次聚类算法尤其适用。

连续数据的粗聚类算法（roughclusteringofsequentialdata,简称RCOSD）：关键思

想是查找能捕获数据序列的连续信息及内容信息的一个特征集，并把这些特征集映射到

一个上近似空间，应用约束相像性上近似技术获得粗类簇的上近似，其中一个元素可以

属于多个类簇.该算法引入S3M作为Web数据的相像性度量方法，S3M既考虑了项的消失次

序又考虑了集合内容。该算法每一次迭代可以合并两个或多个类，所以加快了层次聚类

速度。该算法能够有效挖掘连续数据，并刻画类簇的主要特性，关心呢b挖掘者描述潜

在的新的Web用户组的特性。

03、划分式聚类算法：需要预先指定聚类数据或者聚类中心，通过反复迭代运算，逐步

降低目标函数的误差值，当目标函数收敛时，得到最终的聚类结果。

K均值聚类：

第一步：选择K个点作为初始的质心；

其次步：repeat

第三步：将每个点指派到最近的质心，形成k个簇；

第四步：重新计算每个簇的质心；

第五步；until质心不再发生变化。

优点：能对大型数据集进行高效分类，其计算简单性为O（tKmn）,其中，t为迭代次数，

K为聚类数，加为特征属性数，n为待分类的对象数，通常，K,m,t«n.在对大型数据

集聚类时,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、AC0DF聚类算法：不需要求任何硬子问题，但能给出近似最优解的聚类算法。

第一步：应用蚁群算法，规定每个蚂蚁只需要访问全部城市数量的特别之一，并且访问

城市数目渐渐削减；循环几次，两点之间的相对较短的路径的信息素浓度会增大，两点

之间相对长的路径的信息素会削减。因此，蚂蚁会选择访问近距离的节点，并用自己的

信息加强次路径，最终形成具有较高浓度的路径，聚类完毕。

其次步：应用模拟退火策略来解决局部最优解的问题。

ns(t+l)=ns(t)XT其中ns是蚁群在T。函数期间访问的节点数,ns(t+l)表示当前蚁群

的访问的节点数,ns(t)表示上一次循环蚁群访问的节点数，r是一个常数(T=0.95)。

nf(t+l)=2ns(t)/3-ins(t)/(run*3)其中,nf是蚁群在Ti函数期间访问的节点数,

nf(t+1)表示蚁群当前访问的节点数，nf(t)表示上一次循环蚁群访问的节点数，run=2,

ie{1,2}。

第三步：使用锦标赛选择策略，即从N条路径中随机选择K条路径，再从K条路径中选择

最短路径。

算法类型算法名称算法描述算法优缺点

针对大型数据库的高效的聚类算优点：对孤立点的处理更加健壮，能够

法，采纳固定数目有代表性的点代识别外形简单，大小不一的聚类。

CURE算法

表一个簇，处理大数据量时采纳随缺点：代表点是来自一组随机抽取的样

机取样。本集，它的最初数目需要人为确定。

优点：简洁聚类，并适用于类别属性的

对CURE算法的改进，采纳基于元组

数据。

分散层次聚类ROCK算法之间的连接数目来计算相像形。

缺点：该算法的相像度函式sim是基于

算法

领域专家的直觉。

在层次聚类中采用了动态建模技优点：在发觉高质量的任意外形簇方面

术，通过图划分算法将数据对象划有更强的力量。

CHAMELEON

分为相对较小的子集，然后用一个缺点：聚类结果的精确性和

算法

分散的层次聚类算法通过反复合并有效性有待提高，时间效率需进•步优

子类来找到结果簇。化。

采纳自顶向下的策略，先将全部对

优点：适用于任意外形和任意属性的数

象置于一个簇中，然后渐渐细分为

据集，敏捷掌握不同层次的聚类粒度，

越来越小的簇，直到每个对象自成

DIANA算法聚类力量强。

分裂层次聚类一簇，或者达到了某个终结条件。

缺点：大大延长了算法的执行时间，不

算法其主要思想是将那些成员之间不是

能回溯处理。

特别紧密的簇进行分裂。

基于密度的空间聚类算法，它将簇优点：在处理空间数据时能快速、有效

定义为密度相连的点的最大集合，和发觉任意外形聚类。

DBSCAN算法能够把具有足够高密度的区域划分缺点：对用户定义的参数是敏感的，参数

为簇，并可在空间数据库中发觉任难以确定，全局密度参数不能刻画内在

意外形的聚类。的聚类结构。

优点：有良好的聚类特征，算法速度快，

可以有效揭示数据分布的内在层次，可

基于密度的分基于一组密度分布函数的算法，依

以发觉任意外形的聚类，对噪声数据不

割聚类算法DENCLU算法据数据点在属性空间中的密度进行

敏感。

聚类，得到的是全局最优化分。

缺点：聚类结果严峻依靠于用户参数的

合理选取。

通过对象排序识别聚类结果，为聚优点：具有良好的聚类想能，具有较高

类分析生成一个增广的簇排序，这的敏捷性。

OPTICS算法

个排序代表了各样本点基于密度的缺点：需要额外的存储空间，处理稀疏

聚类结构。点具有局限性。

基于网格的多辨别率聚类技术，将优点:不依靠于查询，有利于并行处理和

空间划分为矩阵单元，形成一个层增量更新，效率高。

STING算法

次结构，关于每个网格单元属性的缺点:全部聚类边界都是水平或者平衡

统计信息被预先计算和存储，这些的，没有对角的边界，可能降低簇的质

基于网格的分信息用于回答查询。量和精确性。

割聚类算法

优点：自动的发觉最高维的子空间，对

结合网格和密度聚类的思想，区分于输入挨次不敏感，无须假设任何法律

空间中的稀疏和拥挤的单元，以发规范的数据分布，与输入数据的大小呈

CLIQUE算法觉数据集合的全局分布模式，假如线性关系，当数据维数增加时具有良好

一个单元中包含的数据超过了某个的扩展性。

输入模型参数，则该单元是密集的缺点：随着方法的简化，精度可能大大

降低。

采纳小波变换聚类，是一种多辨别优点：能有效地处理大数据集合，发觉

WaveCluster率的聚类算法，通过在数据空间上任意外形的簇集，胜利处理孤立点，对噪

算法加一个多维网格结构来汇总数据，声和输入数据的挨次不敏感。

然后采纳小波变化找到密集区域。缺点：对数学和建模的学问要求较高。

优点：具有较强的发觉任意外形和任意

通过在合并两类时用更高的标准来大小簇的力量，可以得到较好的聚类质

CHAMELEON

提高聚类质量的聚类算法既考虑r量。

算法

交互性，又考虑了近似度。缺点：不适合大型数据库中的数据聚

类。

基于图论的分

点集自动聚类的算法，使用特别的

割聚类算法优点：能够发觉任意外形的类簇，需要

图结构来描述对象的空间近邻，然

AUTOCLUST很少的输入参数，聚类精度高。

后删除不全都的边来形成一组子

算法缺点：算法不行靠，计算量较大，不考

图，该算法基于Delaunay三角网进

虑空间对象的属性。

行计算

优点：期望最大化、能够处理异构数据、

逐步对聚类结果进行优化、不断将

概率聚类算能够处理具有简单结构的纪录、能够连

目标数据集向各个聚类中心进行重

法续处理成批的数据、具有在线处理力

新安排。

量、产生的聚类结果易于解释。

最近邻聚类

优点：在处理大小不同、外形不同以及

算法一一共

密度不同的数据集上具有很好的聚类

享最近邻算结合基于密度方法和ROCK思想，保

效果。

基于划分的聚法SNN留K最近邻简化相像矩阵和个数。

缺点：时间简单度提高，不适合处理大

类算法

规模数据集。

选择k个对象，每个对象代表一个聚

类，把其余的对象分别安排给最相

K-Medioids算优点：能处理任意类型的属性，对特别

像的聚类，然后尝试把每个中心分

法数据不敏感。

别用其他非中心来代替，检查聚类

缺点：执行代价高。

的质量是否有所提高，若是，则保

留替换，直到不再发生变化。

选择k个对象，每个对象代表一个聚优点：应用最为广泛，收敛速度快，能

K-Means算法

类的质心，对于其余的每一个对象，扩展以用于大规模的数据集，具有很好

依据该对象与各聚类质心之间的距的收缩性。

高，把它安排到与之最相像的聚类缺点：要多次扫描数据库，只能找出球

中，计算每个聚类的新质心，通常形的类，初始质心的选择对聚类结果有

采纳的准则函数是平方误差准则函较大的影响，对噪声很敏感。

数。

过滤不行能包含任何爱好度子空间优点：含有大量的局部信息，算法的效

中的属性，计算得到由非冗余属性率高。

用于高维数据ENCLUS算法的相关度函数值所组成的关系矩缺点：不行避开地带来了原始数据信息

的聚类算法阵，将属性聚类，产生子空间聚类。的损失和聚类精确性的降

低。

自组织映射，向量化方法，递增逐优点：采用相应的启发式算法获得较高

神经网络聚i处理，映射至二维平面，实现可质量的聚类结果。

类方法视化缺点：计算简单度较高，结果依靠于对

某些阅历参数的选择。

基于模型的方输入对象用分类属性-值来描述，以优点：不需要用户输入参数来确定类的

法一个分类树的形式创建层次聚类，个数，可以自动修正划分中类的个数。

COBWEB算法分类树的每个节点对应一个概念，缺点：分类树对于偏斜的输入数据是不

包含该概念下的一个概率描述，概平衡的，可能导致时间空间简单性的猛

述被分在该节点下的对象.烈变化。

面对中文自然语言文档的自动学问抽取方

法

题目：车海燕，冯铁，张家晨等.面对中文自然语言文档的自动学问抽取方法[J].

计算机讨论与进展,2022,50(4):834-842.

作者思路：提出了基于语义web理论和中文自然语言处理(NPL)技术的自动学问抽取新方

法AKE,并用相应试验赐予证明。

基本定义：

01,聚集体学问概念(AKC),是领域本体中的一类概念，它将N元关系所对应的结构化信息

聚集而成一个独立的资源，并用自身的属性刻画N元关系的各个元。

02、外部聚集体学问概念(Outer-AKC),是聚集体学问结构中最外层的AKG,只能作为非AKG

实例的属性值。

03、内部聚集体学问概念(Inner-AKC),只能作为Outer-AKC和Inner-AKC的实例的属性值，刻

画该属性值的聚集体学问结构。

04、有效性，在一个三元组集合中，一个RDF节点是有效的，假如它是RDF文字或命名实体

类型概念的实例或者它是AKC类概念的实例并且在三元组集合中该实例满意领域本体对其

所属概念定义的全部属性约束。

05、完整性：在三元组集合中，一个RDF节点是完整的，假如它是RDF文字或命名实体类型

概念的实例或者它是有效的AKC类概念的实例并且该实例在三元组集合中的全部属性嗾使

有效的。

核心思想：

01、学问三元组的构造：〈主体s,谓词p,客体o>

1)按序原则：构建三元组是以属性为核心为其选择合适的主体和客体，显示属性优先

于隐式属性；选择主体和客体是，依据实例被识别的挨次狗仔三元组。

2)局部最新优先原则：为三元组选择主体或客体时优先从局部概念实例集合中选择，

假如没有，再从全局概念实例集合中选择，并且优先选择最新被识别或被创建的。

02、学问清洗：

对从一篇文档中抽取出的事实学问三元组集合进行有效性和完整性检查,删除无效节点

以及相关的三元组和有效节点的不完整部分。

基本学问储备与理解：

01、学问抽取讨论如何依据本体识别并抽取无语义标注的信息中与本体匹配的事实学问。

学问抽取的讨论意义在于：1、抽取出的事实学问可以用来构建各种基于学问的服务，

如基于语义的智能学问搜寻；2、识别出的语义信息可以为现有的web数据进行语义标

注，从而促进语义web远景的真正实现。

02、目前自动学问抽取中存在的问题：1、依靠于大规模的通用语言学问库或同义词表，例

如目前存在的中文的通用语言学问库“知网”，但是通用语言学问库无法为特定领域的

词汇供应精确的解释；2、没有对常见的N元关系简单学问给出系统化的处

理方法。文章中就是对于这两点进行了讨论。

03、学问抽取处理的对象依据其结构化的程度可以分为结构化、半结构化和自然语言文档。

04、定义领域本体时要为本体概念指定必要的属性约束：对于Outer-AKC要确定关键属性集

合并为该集合中的属性定义基数为1的基数约束，其他非关键属性则依据具体学问特点

指定必要的属性约束；对于其他类型的本体概念也要依据具体学问特点指定必要的属

性约束。

学问抽取技术综述*

基本学问储备与理解：

01、学问抽取讨论如何依据本体识别并抽取无语义标注的信息中与本体匹配的事实学问。

02、本体(Ontology)是共享概念模型的明确形式化的法律规范说明。概念模型是指抽象客

观世界中的一些现象的相关概念而得到的模型，即概念系统所蕴含的语义结构，是对

某一种事实结构的一组非正式的约束规章，可以理解和表达为一组概念(包括实体、属

性和过程)、定义和关系；明确(explicit)是指所使用的概念及使用这些概念的约束都有明

确的定义；形式化(formal)是指本体是计算机可读的；共享(share)是指本体中体现的是

共同认可的学问，反映的是相关领域中公认的概念集，即本体针对的是社会范畴而非

个体之间的共识。

03、W3C提出的用于描述Web资源的资源描述框架语言(resourcesdescriptionframework,

RDF)o不仅是Web数据集成的元数据解决方案，而且是一个能对结构化的元数据进行

编码、交换和重用的体系框架。RDF使用统一资源标志符(universalresourceidentifier,

URI)作为标志机制的基础，采用URI引用(URIreferences)描述任何事物及事物之间的关

系。RDF基本数据模型包含资源(resource)、属性(property)和陈述(statement)三种对象模

型。

04、面对中文的学问抽取技术：

对结构化和半结构化文档的学问抽取：iASA语义标注方法(包括规章学习模块、标注

模块和解释模块)、OMKast框架描述语言-NKI本体语言，表示领域本体和猎取到的目标

学问。

05、面对自由文档的学问抽取：

对于中文自然语言文档进行有效学问抽取需要结合多方面的工作，包括中文分词、中

文命名实体识别和中文实体关系抽取等，同时还要依靠于对中文内容部分元素的语义

识别。

06、基于主题的本体属性识别方法不再试图将自然语言句子中的词语与本体中的概念和属

性进行直接匹配，而是先依据已经识别出的信息，包括概念实例和属性，判定当前句

子的描述主题，然后采用本体中定义的与该主题相关的本体属性查找文字中可能蕴含

的属性。

07、iOkra框架借助本体和NLP技术首先对输入文本执行语形分析，分词是通过将文中词汇

与本体中元素进行对应为该词供应语法和语义信息；然后进行浅层的句法分析，对分

词结果执行短语合并操作，并采用基于信息的全部格文法识别文中词汇的主题角色(即

通用本体中定义的关系)；最终进行语义分析，采用通用语言本体和领域本体对ICG的

标记结果进行消歧并构造RDF语句，同时采用语言的局部依靠性特性识别那些没有被

ICG识别出的角色。

当前学问抽取的主要技术方法解析*

题目：张智雄,吴振新,刘建华等.当前学问抽取的主要技术方法解析[J].现代图

书情报技术,2022,(8):2-11.D01:10.3969/j.issn.1003-3513.2022.08.002.

基本学问储备与理解：

01、狭义的学问抽取基本上属于文本挖掘的范畴，其处理的对象是自由文本，目标是分

析文本内容，通过识别出文本中的学问片段，促进对文本内容的理解。

02、学问抽取系统中目前分为两种思路，机器学习和自然语言处理，两种技术思路目前

正在相互融合、相互借鉴，各自都得到了较大的进展。基于机器学习的学问抽取系统,

提出了自适应的信息抽取(AdaptiveIE)、开放信息抽取(OpenIE)等新的技术思路，并向着

自动本体学习(OntologyLearning)的方向进展；而基于自然语言分析的学问抽取系统，则

提出了基于模式标注(Pattern-BasedAnnotation)、语义标注(SemanticAnnotation)等新的

技术思路，并且都在向着基于Ontology的信息抽取(OBIE)的方向进展。

03、自适应的信息抽取需要借助肯定数量的手工标注语料，以适应新的应用领域。

04、开放信息抽取的目的在于促进领域无关的学问抽取应用，它能从文本中抽取出大量

关系对，并可被应用到各种类型和规模的web信息抽取任务中。

05、本体学习就是自动或半自动地从各类数据资源中猎取期望本体的方法和技术集合，

类似概念还有本体生成、本体挖掘、本体抽取等。

06、基于模式标注的学问抽取更加注意采用自然语言分析技术。基于模式标注的学问抽

取可分为两种类型：一种通过模式的自动发觉，进而实现对相关内容的标注：另--种通

过人工定义的模式实现内容标注。

07、语义标注除采用自然语言的语法模式和规章外，更重要的是对语义内容的挖掘。基

于Ontology的信息抽取(OBIE)方法可以认为是当前语义标注讨论的一种主流方法，也被

称作基于本体的标注和基于本体的语义标注。OBIE是语义标注的进一步进展，它不但

要将抽取出的内容纳入到学问库中，还要求在抽取过程中始终得到Ontology的支持。

OBIE通过Ontology定义的类、属性、层次结构抽取非结构化或半结构化文本中对应的

实例，进行歧义消解，进而识别文本中的实体及关系，将结果存储于对应的Ontology

中。

08、于受控语言的信息抽取(CLIE)方法是一种很特别的技术方法，它以某些受掌握语言撰

写的文本为处理对象，从这些受控语言的文本中构建Ontology。它可以降低Ontology构建

的门槛，提高Ontology构建效率。

09、学问抽取的5个特点：

1、学问抽取强调语义的抽取。抽取出的内容是有肯定意义的、能被其它上下文所解释

的语义学问片段(如概念及概念间的关系等)。2、学问抽取普遍将机器学习技术和自然语

言分析技术相结合。与传统的基于学习或规章的信息抽取不同，由于面对更为简单的任

务，许多学问抽取的系统都采纳机器学习技术和自然语言分析技术相结合的方法。3、

学问抽取需要0ntology的支持。Ontology^学问抽取不行或缺的组件。在学问抽取前，

Ontology定义需要抽取的学问类型：命名实体识别过程中，Ontology除了能够起到词表

和辞典的帮助标识作用外，还可为学问抽取供应推理机制；在语义标注中，Ontology可

以对抽取结果进行语义识别和消退歧义；处理抽取结果，抽取结果被关联到Ontology中，

形成学问库。4、学问抽取关注实体间关系的识别和抽取。学问抽取除了要识别出命名

实体的类型外，还需要识别出这一命名实体与其它命名实体之间的各种关系，通过关系

将识别出来的新实体纳入到相应的学问库之中。5、学问抽取的结果为学问库建设供应

了内容。依据预先定义的Ontology框架，学问抽取系统从一系列文献中抽取出相应实体

和关系，并将这些文献和抽取出的实体和关系组织到学问库中，实现本体填充(Ontology

Population),,所建设的学问库是进一步实现数据挖掘、学问发觉的基础。

基于本体的专利摘要学问抽取*

题目：姜彩红，乔晓东，朱礼军等.基于本体的专利摘要学问抽取［J］.现代图书情

报技术,2022,（2）:23-28.D0I:10.3969/j.issn.1003-3513.2022.02.004.

基本学问储备与理解：

01、专利摘要的内容可以分为如下5个部分：对专利的全局推断（包括所属技术领域的

推断、用途或目的等）、专利采纳或舍弃的方法或技术、专利的工作原理（包括链接接

触。驱动掌握或自动工作等）、专利的组成结构以及专利人对专利的评价（包括正面性

能的增加，负面性能的削减或优秀性能的保持等）。

02、抽取流程：数据转换模块、中文分词模块、本体构建模块、学问抽取模块。

本体

构

|中文分闻模块］建

模

块

中文专利摘

要文档集

知

|数据转换模块］识

抽

取

模

块

中文专利

专利知识库KB

数据库

03、数据转换模块的主要功能是用于对于语料的收集。

04、中文分词模块应用中科院分词软件ICTCLAS,对其进行了二次开发，实现对整个文

档集进行批量分词的功能。

05、本体构建模块的任务是将专利摘要中的五项内容抽取出来，并且以肯定的语义关系

组织起来存放入学问库中。

在专利这个大类下面创建两个子类，专利外部信息和专利内部信息。在文本中，专

利外部信息指的是专利数据库中的专利名称，申请日，申请专利人，申请人地址，公开

号公开日等信息，在构建专利学问库的时候，这些信息都可以从专利数据库中直接猎取;

将专利摘要内容判别原则中的5项内容归为专利内部信息的五个子类，在构建专利学问

库时，这些信息需要先从文本中抽取出来，并通过本体进行组织后存入学问库中

06、学问抽取工具GATE,词表的收集步骤如下所示：

1）全局推断部分。这部分内容基本上由以下三种动词引导表达:表示专利所属领域的动

词（如:属于、属、所属、涉及等）、表示专采用途或目的的动词（如:用于、周作、作为、

适用于、有助于等）以及对专利进行解释说明的动词（如:在于、具有、称为、兼有等）；

2）取舍替代部分。这部分内容基本上由以下三种动词引导表达:引出专利选取对象的

动词（如:选择、选取、采纳、任选等）、专利舍弃对象的动词（如:省去、省摔、取消、撤

销等）以及引出专利代替对象的动词（如:转换、变换、切换、替代等）；

3）评价内容部分。这部分内容基本上由以下三种动词引导表达:表示专利正面性能增

加的动询（如:提高、增高、增大、延长等）、表示专利负面性能削减的动词（如:降低、

削减、缩短、简化、节约等）以及表示专利良好性能保持的动祠（如:保持、维持、保留

等）。

4）组成结构和作用原理部分。二者往往嵌套消失，因此放在一起处理。不但要收集

相关的动坷，还需妥收集其中的名词。名词部分主要有如下几个方面:新能源汽车

名称术语、汽车材料、燃料、动力设施、设施工艺以及动力传递方式等;动饲部分

主要可以分为如下几种:引导组成结构的动词（如:组成、构成、包含、包括等）、表示

连接作用的动词（如：连接、邻接、连接、结合、接触等）、表示驱动掌握的动词（如：掌

握、驱动、产生、传输、启动等）以及表示自动反应的动词（如:旋转、运转、伸缩、

分流、滑动等）。

规章撰写：Java标注模式引擎（JavaAnnotationPatternsEngine,JAPE）供应了基于

正则表达式的标注有限状态转换，是CPSL（CommonPatternSpecificationLanguage）的一

个版本。通过JAPE语言可以编写GATE能够识别的规章，采用这些规章来对文档进行

抽取。

抽取的结构存储在xml文件中，然后通过对GATEAPI的调用对文档进行批量抽取。

最终通过从xml文件中提取相关字段，并依据本体中抽象出的语义标注集，自动生成学

问库。

一种基于网格的改进的K-Means聚类算法

题目：任家东，孟丽丽，张冬梅等.一种基于网格的改进的K-Means聚类算法［J］.

计算机讨论与进展,2022,46(z2):828-833.

基本定义：

01、单元密度聚合度(U)：一个网格单元c中所包含的全部数据点x与c的几何中心点

mean(c)之间的距离之和再除以网格单元c的密度Density©与网格单元长度d的乘积。

02、对于密集单元c,-•般U=<0.5的网格单元作为密集中心网格单元，其中U<=0.25的

密集中心网格单元为紧密集中心网格单元；0.25<U<-0.5的密集中心网格单元为松密集中

心网格单元。U>0.5的网格单元称为非密集中心网格单元。

03、偏单元网格：密度大于阈值的非密集中心网格。

核心算法：

输入：数据点数n,网格单元宽度d,网格密度阈值s;

输出：聚类结果

Stepl:对输入空间进行预处理。依据d划分单元格，并且统计每个单元格的密度，获得全部

非空单元格的信息，依据非空单元格对象的密度大小依次排序并保存在向量队列Desc(m)中；

Step2:选取初始聚类网格。在向量队列选取初始聚类网格.从向量队列Desc(m)中依次取密度

最大的单元格，若是偏网格，则给该单元格作一个待定处理的标识，等全部聚类基本完成后

再打算其的归属：假如它是松密集中心网格，并且若它的邻居单元是一棵聚类树的节点，则

将其作为这个邻居单元的子节点加入该类；假如其四周没有聚类，则将它作为一个类的根节

点建立聚类树；假如它是紧密集中心网格，则将其作为一个独立的类，并且是最终类，以后

不参与聚类过程。这样从向量队列Desc(m)中最多取［Vn］或［2lnn］个单元格作为聚类树的根

节点。

Step3:构建网格聚类树，依据上步确定的根节点，将没有处理过的邻近单元格并且是松密集

中心网格作为它的子节点，假如邻近单元格是非密集中心网格则等全部聚类基本完成后再打

算其的归属，递归循环至没有邻近网格的加入。

Step4:依据上步的结果，一棵树即为一个类，假如两棵树在聚类过程中有公共的叶子单元

格并且这个单元格是松密集中心网格或偏单元格，则将这两棵树合并在一起作为一个类，并

更新类的标示。

Step5:对于待处理的非密集中心网络，检测与其相邻的网格是否属于同一个类，假如是同一

个类，则将该单元格中的数据并入该类；假如不是，则依据上述对偏单元格的处理方法并入

所属类。

Step6:检测零散类，对于没有标示过和没有处理过的单元格，为其建立聚类树，假如树的层

次在三层以上，则将这些零散节点作为一个类，赐予一个类标示，否则将其视为离群节点删

除。设置此步骤的目的是为了避开遗漏密度较小的聚类。

算法简单度：

该算法只需扫描一遍数据集，假设具有以个数据的空间域经过网格化预处理后，存在非

夺数据单元格数目为Cne。密集中心网格单元数为Cden，偏单元格数为Cdep，则IKMG算法的总

体时间简单度为O(n)+8O(Cden)+3X4O(Cdep)。

试验结果展现:

m耕费就

TestDBl5002

TestDB210002

TestDB350002

KddCupl100002

KddCup2500002

KddCupS1000002

算法理解：

IKMG采用网格连通性原理，借助树形结构，将多个密集网格单元作为初始根节点，四

周网格作为它的子节点，为此类推。试验结果也表明白IKMG在数据集较大时对比K-Means

大大缩短了处理时间，作者还认为IKMG有效消退了聚类结果对初始聚类中心的敏感性，而

且无需认为指定K值，能找出不同大小，不同外形的聚类。我的理解是IKMG在肯定程度上优

化了k均值算法，但是在算法的输入中又引入了网格边长以及网格密度阈值这两个凭借阅历

值设定的量，增加的了算法的不稳定性；对于聚类数量的选取并没有给出合理的数值，仅仅

是用根号下数据集数量或者是2倍的In数据集数量；此外，试验也仅仅是验证了维数为2的时

候的聚类状况，并没有验证多维数据下的IKMG算法的聚类效果。

基于初始点选取的K-Means聚类近似常数

算法

题目：王守强，朱大铭，韩爱丽等.基于初始点选取的k-means聚类近似常数算法

[J].计算机讨论与进展,2007,44(z2):69-74.

问题描述：

在原始的k-means算法中，选取k个点作为聚类中心，依据这K个点进行聚类，而在划分过

程中没有考察这K个中心点的有效性，即这k个点的代表性。当这K个点恰好是分别属于k

个不同最优聚类簇时，该算法能够很快收敛；假如这k个点中存在属于同一簇的状况，则很

简洁将本属于同一簇的数据硬性的划分到其他簇中，从而陷入局部微小，即它依靠于初始化

分。现在的问题就是如何找出这K个点。

核心算法：

初始点猎取算法：

输入：点击P

输出：初始K个点

Stepl：从集合P中随机匀称地选择一个点c,将其当如集合C中。

Step2:从集合P中选择下一个点cl,依据相应的概率选择某一点作为第i个初始点，使得

点ci距离它最近的中心点的距离最小。

Step3:重复step2,直到选择K个点为止。

假如从集合P中随机取k个点，要求这k个点分别属于不同的最优聚类中的点，可采纳上述算

法，该算法假如运行1/(1—09)户次，则以较高概率取得这K个点，使其分别属于不同的最

优聚类簇PI,P2,...PK中的一个点。

局部搜寻算法：

Stepl:从集合P中任选k个点集合作为初始中心点进行K-means聚类划分，设划分后的K-means

聚类的解值为t；

Step2:对于一个确定的整数p,从集合P中选择p，个点与中心点C中p，个点进行替换，新求得中

心点集合为C:设新的K-means聚类的划分值为匕假如t，＜t,则置C=C"t=f;

Step3:重复step2,直至t的值不再变化。

K-means聚类局部搜寻算法：

输入：k个初始中心点

输出：最小聚类解及相应的K-means聚类划分

Stepl：设k个初始点为C-以这k个点作为中心点求得一个初始解值t；

对于每一个初始划分测试全部中的执行一个点交换，求得一个新划分，设对

SteP2：P,Px,

应的解值为匕假如t小于上次运算的解值t,则1=匕C=C\

Step3：重复上述步骤，直到t的值不再变化。

试验结果分析与算法理解:

表与传统聚类相结合实验结果

表2时然版新崩H轴版3hmeans

局部搜索结合

实嬲麻K色近微短数歌K值最优值近做It

m辘献Mmeans结果

Iris2152.347157.6299901.034677348Iris2152,347152.3687291.000142628

378,851483.9600141.064787867378.851478,9408341.001134209

457.228460.4399951.056118903457.228457.3550301.002212713

546.446150.9699861.097400772546,446146,7820931.007234041

639.039943,9199941.125002728639.039939,177475L003523959

734.298238,6899991.128047507734.298234.3880001.002618213

Rusplni289337.8097298.00001.089102261Rusplni289337.8089337.8203131.000000227

351063.4$3390.00001.045562967351063.451155.3906251.001801498

410126.713169.00001.300423633410126.712281.0527341.212739859

58575.4010575.0000,1.23317862758575.4010149.270508L183533189

67126.198945.00001.25522895167126.198597.9560551.206529163

76149.637599.00i.23568409876149.637249.8549801.178909134

85)81.656540.0000001.26214622885181.656272.0698241.210438726

SpathPostal2602546000000703093145600.001.166870489SpathPostal2602546000000649245622272,001.077503829

ZoneData3294506000000294506463232.001.000001573

ZoneData3294506000000318W9024.001.081076409

4104474000000104474689536.001.0000066

4104474000000128375177216.001.22877632

55976150000059761520640.001.000000345