基于属性—链接的聚类算法综述

首先总结了链接挖掘中基于属性—链接聚类算法的研究现状;然后把它大体分为三类,对每一类中具有代表性的算法进行了详细介绍、分析和评价;最后指出了该领域进一步的研究方向。     

基于层次聚类的差异化属性约简算法

属性约简是粗糙集用于数据分析的一个重要概念,提出了一个计算差异化属性约简的算法。利用自底向上的聚合层次聚类方法对决策表的条件属性集进行聚类,得到条件属性集的k个划分,然后对这k个属性子集进行后处理操作而得到k个有较大差异的约简属性集。实验结果表明了算法的有效性。     

一种基于层次聚类的属性全局离散化算法

本文摒弃了以往利用断点集来进行离散化的算法思想,提出了一种新的基于粗糙集和分裂的层次聚类的全局离散化算法.本算法在层次聚类的基础上考虑不同连续属性离散化结果间的互补性和相关性,在不改变原信息系统不可分辨关系的前提下通过增类减类进行全局离散化.实验表明该算法具备了删除不必要属性的能力,提高了离散化的精度,更便于属性约简.     

基于树编辑距离的层次聚类算法

为了识别犯罪嫌疑人伪造和篡改的虚假身份,利用树编辑距离计算个体属性相似性,证明了树编辑距离的相关数学性质,对属性应用层次编码方法,提出了一种新的基于树编辑距离的层次聚类算法HCTED(Hi-erarchical Clustering Algorithm Based on Tree Edit Distance)。新算法通过树编辑操作使用最少的代价计算属性相似性,克服了传统聚类算法标称型计算的缺陷,提高了聚类精度,通过设定阈值对给定样本聚类。实验证明了新方法在身份识别上的准确性和有效性,讨论了不同参数对实验结果的影响,对比传统聚类算法,HCTED算法性能明显提高。新算法已经应用到警用流动人口分析中,取得了良好效果。     

基于属性区分能力和AP聚类的属性粒化方法

提出了一种基于属性区分能力和AP聚类的属性粒化方法(Attribute Granulation based on attribute discernibility and AP algorithm,AGAP)。该方法首先依据属性依赖度计算属性的区分能力;然后将所有属性作为潜在的聚类中心,使用AP算法聚类,得到若干个属性簇类;最后采取选用代表属性的方法得到较粗的属性粒子,从而达到属性粗粒化的要求。对高维数据的特征降维,这种算法比传统的属性约简算法大大提高了运算效率,在属性粒化精度要求不是很严格的情况下,所提算法优势明显。     

基于区分矩阵的启发式属性约简算法

由于大量等价类元素的存在,同一等价类中的记录与其他非该等价类中的记录相比较将会产生大量空元素及重复元素,使得构造区分矩阵需要耗费大量的时间与空间。因此以信息向量为工具处理等价类,改进了区分矩阵的构造过程,有效地提高了构造区分矩阵的时空间效率;其次,利用属性频度为启发信息,给出了一种基于区分矩阵的启发式属性约简算法;最后,利用恒星天体光谱数据集,实验验证了算法的有效性。     

基于混合属性的产品优化聚类算法

针对分类研究中采用单一类型数据造成的结果失真, 提出了综合考虑产品属性和销售时间序列的两阶段优化聚类算法。分别采用基于属性的相似性排序及时间序列的分层优化聚类实现产品单独聚类, 然后基于初始聚类结果及参数化的动态相对权重提出考虑噪声数据处理的分层聚类方法实现产品综合优化分类。企业实例应用研究表明综合聚类模型及两阶段算法在聚类精度及时间复杂度上具有明显的优势, 相对权重的动态参数化设置有效解决了不同产品间个性化特征的差异表示。通用数据集的仿真进一步验证了算法在解决混合属性产品聚类问题时的优越性及广泛适用性。     

基于维度属性距离的混合属性近邻传播聚类算法

针对近邻传播聚类算法不能处理混合属性数据集的问题,提出了一种新的距离度量测度,并将其应用到近邻传播聚类算法中,提出了一种基于维度属性距离的混合属性近邻传播聚类算法。与传统聚类算法不同的是,该算法不需要计算虚拟的中心点,同时考虑了数据集整体分布对聚类结果的影响。将算法在UCI数据库的2个混合属性数据集上进行验证,同时对比了经典的K-Prototypes算法以及K-Modes算法。实验结果表明,改进后的算法具有更好的聚类质量以及执行效率,算法的优越性得到了验证。     

基于属性加权的改进K-Means算法

经典的K-Means算法认为被分析样本的各个属性对聚类结果的贡献均匀,没有考虑不同属性特征对聚类结果可能造成的不同影响。文章提出了一种基于样本属性加权的K-Means算法。该算法利用变异系数赋权法对属性进行加权处理,通过权值反映各个属性对聚类结果的贡献的大小。实验表明,该算法在不改变时间、空间复杂度的情况下能取得更好的聚类结果。     

基于最短路径的加权属性图聚类算法研究

图在计算机领域是一种重要的数据结构,可以用来描述事物之间的复杂关系。图的节点和边具备一个或者多个不同的属性。如何结合属性对图进行聚类是目前所面临的一个新的挑战。目前的属性图聚类算法,多存在聚类效果差,消耗资源多,效率低等缺点。针对以上问题,提出一种基于最短距离的加权属性图聚类算法WASP(weighted attribute graph clustering algorithm based on shortest path),建立加权属性无向图模型,在此模型上基于最短路径算法度量节点间的关联度,以此为原则选取新的聚类中心对图进行聚类。实验表明,新的聚类算法具有更高效的聚类效果。     

基于分步聚类的人名消歧算法

针对知识库中存在单条实体定义特征稀疏和人工设置相似度阈值适用性不强的问题,本文提出了一种基于分步聚类的人名消歧算法。首先,将知识库中人名实体定义的人物属性特征作为查询特征,利用文本检索的方式实现基于知识库的初次聚类,弥补了知识库中单条实体定义中特征稀疏的问题;然后,利用初次聚类的结果,采用基于自适应阈值的凝聚层次聚类算法实现知识库人名消歧;最后,采用条件随机场进行Other类识别,利用基于自适应阈值的凝聚层次聚类完成S类聚类,从而实现非知识库人名消歧。在CLP2012的中文人名消歧评测语料上进行实验,结果表明本文的算法能够有效地对人名进行消歧。     

一种基于改进的K-means算法的人名消歧系统的设计与实现

人名歧义是一种身份不确定的现象,指的是文本中具有相同姓名的字符串指向现实世界中的不同实体人物。人名消歧很长时间一直是一个具有挑战性的问题,关注网页里的人名消歧的问题。因为经典的K-means算法如果选择了一个差的随机初始聚类中心,算法会遇到局部收敛的问题,所以文章提出一种基于最大最小原则的改进的K-means算法来进行人名消歧。同时使用了WePS的训练数据作为实验的语料。实验结果表明,改进的方法比层次聚类方法有着更好的性能。     

基于组合特征的Web人名消歧方法

重名问题在Web人物搜索过程中是很普遍的现象.研究了Web人名消歧相关问题,提取与待消歧人名相关的不同特征集,运用向量空间模型构造人物实体的组合特征,最后通过层次聚类算法将相似度高的文档优先聚类,由此实现人名消歧.在WePS数据集上的实验结果表明,提出的方法具有良好的消歧效果.     

基于网页文本依存特征的人名消歧

研究互联网中的人名消歧问题.抽取与网页文本中人名关键字实体相关的依存特征及命名实体等辅助特征,利用二层聚类算法,根据依存特征将可信度高的文档聚类,使用辅助特征将剩余文档加到现有聚类结果中,由此实现人名消歧.实验结果证明,该方法消歧效果优于其他人名消歧方法.     

一种用于基因名字规范化的多层歧义消解框架

灵活的基因名字命名方式使基因名字具有严重的歧义, 这已成为对生物医学文献进行深层自动文本挖掘的主要障碍之一. 基因名字规范化是解决这一问题的有效途径. 本文提出了一种多层歧义消解框架来完成基因名字规范化任务. 基因名字规范化过程中不同阶段有不同的歧义情形, 在本文提出的框架中, 针对这些情形采用了有针对性的解决策略, 包括: 基于词典的基因名字检测, 基于机器学习方法的候选选择以及基于语义的歧义消解. 试验表明, 我们的方法能够在BioCreAtIvE2006的基因名字规范化测试集上取得0.746的F度量.     

基于社会网络的跨文本同名消歧

跨文本人名消歧是判断出现在不同文本的相同人名是否指称现实中相同实体的过程。跨文本人名消歧是准确获取感兴趣人物相关信息的基础,对多文本摘要、信息融合等具体应用也有重要的作用。该文运用社会网络分析法消歧中文不同文本同名歧义问题,思想是先使用谱聚类对社会网络中的人名聚类,然后根据不同社会网络边权值和不同图划分准则对人名消歧效果的影响,引入了模块度阈值作为社会网络划分的停止条件。在CLP 2010的中文人名消歧数据上进行测试,显示了社会网络分析对人名消歧的有效性。     

面向人名消歧任务的人名识别系统

CLP2010(CIPS-SIGHAN Joint Conference on Chinese Language Processing)的人名消歧评测的任务是个 聚类问题:对给定的一组文档,按照文档中出现的指定查询词所指向的人进行聚类.由于是用"字"串匹配的方法从新华社的语料库中抽出所有含有该查询词的文档.所以对于这个...     

基于多步聚类的汉语命名实体识别和歧义消解

命名实体识别和歧义消解是自然语言理解的重要研究内容。针对提供实体知识库情况下的命名实体识别和歧义消解任务,该文提出了一种基于多步聚类的方法。首先通过两轮聚类将命名实体与知识库实体定义链接,然后通过层次聚合式聚类对知识库中未出现的实体进行聚类,最后进行普通词的识别和基于K-Means聚类的结果调整。在CLP-2012的汉语命名实体识别和歧义消解评测数据上的实验表明,该文的方法表现出良好的性能,在测试集上的F值高出评测参赛队伍最好水平6.46%,达到86.68%。     

基于网络搜索的英汉人名翻译

该文利用搜索引擎从网络中挖掘英语人名的中文翻译。该方法综合利用翻译辅助词、英中人名共现规则、音译相似度和翻译概率。首先,利用搜索引擎从互联网上搜索英文人名的中文翻译候选。把汉语人名标注结果、翻译辅助词、英中人名共现规则和英文人名的发音音节长度结合起来提取翻译候选词。翻译辅助词有助于搜索与英文人名更相关的信息,英中人名共现规则和发音音节长度进一步缩小英文人名的翻译范围,使得英文人名的翻译搜索符合人名共现规律和发音规律。然后,根据音译相似度和翻译概率对候选词进行排序。人名翻译的绝大部分是根据发音翻译过来的,音译相似度是帮助判断两个词在发音上的相似性。翻译概率从统计上判断两个词互为翻译的可能性。实验结果表明,翻译辅助词、规则、音译相似度和翻译概率都有助于提高人名翻译的正确率。     

基于层次与划分方法的聚类算法研究

针对在层次聚类算法中,一个分裂或合并被执行,就不能修正,其聚类质量受到限制的缺陷,提出了利用簇间相异度及基于信息熵或整体相似度的聚类质量评价标准,在簇分裂过程中动态的进行簇的合并与分裂的算法。仿真实验结果证明,该算法具有使结果簇更紧凑和独立的效果,具有更好的聚类质量。