双层随机游走半监督聚类

半监督聚类旨在根据用户给出的必连和不连约束,把所有数据点划分到不同的簇中,从而获得更准确、更加符合用户要求的聚类结果.目前的半监督聚类算法大多数通过修改已有的聚类算法或者结合度规学习,使聚类结果与点对约束尽可能地保持一致,却很少考虑点对约束对周围无约束数据的显式影响程度.提出一种由在顶点上的低层随机游走和在组件上的高层随机游走两部分构成的双层随机游走半监督聚类算法,其中,低层随机游走主要负责计算选出的约束顶点对其他顶点的影响范围和影响程度,称为组件;高层随机游走则进一步将各个点对约束以自适应的强度在组件上进行约束传播,把它们在每个顶点上的影响综合在一个簇指示矩阵中.UCI数据集和大型真实数据集上的实验结果表明,双层随机游走半监督聚类算法比其他半监督聚类算法更准确,也比较高效.     

数据空间中一种灵活的集合式实体识别框架

数据空间是一个异构、动态的环境,具有随时间演化的特性.针对数据空间中随时间演化的、彼此间具有相互关联关系的大量异构实体,提出一个灵活的、基于演化的集合式实体识别框架TE-CER.TE-CER在实体识别过程中考虑时间信息和演化的影响,提出基于时间的blocking算法T-blocking和基于时间演化的聚类算法TE-Clustering.TE-Clustering聚类算法考虑了演化对实体相似度的影响,在相似度度量中引入属性演化系数和关联关系演化系数;在聚类过程中引入簇的时间约束.并且TE-CER提出基于识别顺序依赖图来确定集合式实体识别的识别顺序的策略,这样一种实体的识别结果可以用来后续另一种相关联实体的识别证据,以提高识别的准确率.在真实数据集上的大量实验结果表明所提出方法的有效性.     

基于领域知识图谱的短文本实体链接

实体链接任务是识别文本中潜在的实体指称,并将其链接到给定知识库中无歧义的实体上。在绝大多数情况下,实体链接可能存在中文短文本缺乏有效上下文信息,导致存在一词多义的歧义现象;同时候选链接过程中,候选实体的不确定相关性也影响候选实体链接精确性。针对上述两个问题,提出深度神经网络与关联图相结合的实体链接模型。模型添加字符特征、上下文、信息深层语义来增强指称和实体表示,并进行相似度匹配。利用Fast-newman算法将图谱知识库聚类划分不同类型实体簇,将相似度计算得分最高候选实体所属实体簇映射到关系平面,构建聚类实体关联图。利用偏向随机游走算法考查候选实体之间语义相关度,计算指称与候选实体的匹配程度,输入链接实体。该模型可以实现短文本到知识图谱目标实体的准确链接。     

面向大规模数据集的近邻传播聚类

近邻传播聚类在计算过程中需构建相似度矩阵,该矩阵的规模随样本数急剧增长,限制了算法在大规模数据集上的直接应用。为此,提出一种改进的近邻传播聚类算法,利用数据点的局部分布,借鉴半监督聚类的思想构造稀疏化的相似度矩阵,并对聚类结果中的簇代表点再次或多次聚类,直至得到合适的簇划分。实验结果表明,该算法在处理能力和运算速度上优于原算法。     

犹豫模糊数据对象集的谱聚类算法

目前适用于犹豫模糊数据对象集的聚类算法研究仍然非常有限,现有的犹豫模糊数据对象集层次聚类算法受异常点影响较大且容易聚成链状.针对上述问题,本文首先提出了一种可扩展的犹豫模糊集的加权相似度计算方法,该方法不仅可以利用不同的函数计算相似度,而且可以根据实际问题构造最优的相似度函数.基于该加权相似度计算方法,结合经典的谱聚类算法提出了犹豫模糊数据对象集的谱聚类算法(SCHF).针对目前国内外还没有可用于犹豫模糊数据对象集聚类的标准数据集的现实情况,本文提出了一种确定性数据的犹豫模糊方法并在仿真实验中应用.仿真实验不仅验证了SCHF算法的有效性,而且表明SCHF算法比两种已知算法有更好的聚类效果.     

基于约束优化传播的改进大规模数据半监督式谱聚类算法

针对传统谱聚类算法在聚类过程中所出现的高计算复杂度、噪声敏感,以及聚类簇形态偏斜等问题,结合当前大规模数据聚类的特点与需求,本文建立基于约束优化传播的改进大规模数据半监督式谱聚类模型。该模型首先利用先验成对点约束信息构建微型相似性矩阵,在此基础上采用Gabow算法提取该微型相似性矩阵所对应连通图的各强连通分支,继而提出面向各强连通分支的新型约束优化传播算法以获取整个数据集的点对相似度,最后通过奇异值分解并运用加速k-means算法获得大规模数据的聚类结果。在多个标准测试数据集上的实验表明,相比于该领域其它前期研究成果,本文所提聚类模型具有更高的聚类准确率和更低的计算复杂度,更适合大规模数据的聚类应用。     

基于区间数的多维不确定性数据UID-DBSCAN聚类算法

不确定性数据聚类方法的研究日益受到广泛关注,其中UIDK-means算法与U-PAM算法继承了基于划分算法无法识别任意形状簇和对噪声点敏感的缺陷。FDBSCAN算法事先假定不确定性数据的概率分布函数或概率密度函数是已知的,然而这些信息在实际应用中往往难以获取。针对上述算法的不足,提出一种基于区间数的多维不确定性数据聚类UID-DBSCAN算法。该算法利用区间数结合数据的统计信息合理地表示不确定性数据,采用低计算复杂度的区间数距离函数衡量不确定性数据对象间的相似度,首次提出区间数的密度、密度可达与密度相连等概念,并将其用于扩展簇中,同时结合数据集的统计特征自适应地选取算法的密度参数来实现自动聚类。实验结果表明,UID-DBSCAN算法能够有效识别噪声,处理任意形状簇,具有较高的聚类精度和较低的计算复杂度。     

实例簇驱动的图结构聚类参数计算算法

pSCAN算法的聚类结果受密度约束参数和相似度阈值参数的影响,如果用户提供的聚类参数得到的聚类结果无法满足需求,那么用户可以通过实例簇表达自己的聚类需求。针对实例簇表达聚类查询需求的问题,提出一种实例簇驱动的图结构聚类参数计算算法PART及其改进算法ImPART。首先,分析两个聚类参数对聚类结果的影响,并提取实例簇的相关子图;其次,对相关子图进行分析得到密度约束参数的可行区间,并根据当前密度约束参数和节点之间的结构相似度将实例簇内节点划分为核心节点和非核心节点;最后,依据节点划分结果计算出当前密度约束参数对应的最优相似度阈值参数,并在相关子图上对得到的参数进行验证和优化,直到得到满足实例簇需求的聚类参数。在真实数据集上的实验结果表明,所提算法能够为用户实例簇返回一组有效参数,且所提改进算法ImPART的运行时间比PART缩短了20%以上,能够快速有效地为用户返回满足实例簇要求的最优聚类参数。     

基于区间数的不确定性数据聚类算法:UD-OPTICS

在不确定性数据聚类算法的研究中,普遍需要假设不确定性数据服从某种分布,继而获得表示不确定性数据的概率密度函数或概率分布函数,然而这种假设很难保证与实际应用系统中的不确定性数据分布一致。现有的基于密度的算法对初始参数敏感,在对密度不均匀的不确定性数据聚类时,无法发现任意密度的类簇。鉴于这些不足,提出基于区间数的不确定性数据对象排序识别聚类结构算法(UD-OPTICS)。该算法利用区间数理论,结合不确定性数据的相关统计信息来更加合理地表示不确定性数据,提出了低计算复杂度的区间核心距离与区间可达距离的概念与计算方法,将其用于度量不确定性数据间的相似度,拓展类簇与对象排序识别聚类结构。该算法可很好地发现任意密度的类簇。实验结果表明,UD-OPTICS算法具有较高的聚类精度和较低的复杂度。     

基于改进凝聚层次聚类的协议分类算法

在比特流未知协议识别过程中,针对如何将得到的多协议数据帧分为单协议数据帧这一问题,提出了一种改进的凝聚型层次聚类算法。该算法以传统的凝聚型层次聚类算法思想为基础,结合比特流数据帧的特征,定义了数据帧之间及类簇之间的相似度,采用边聚类边提取符合要求类簇的方式,能快速有效地对数据帧进行聚类;并且该算法能自动地确定聚类的个数,所得的类簇含有相似度评价指标。利用林肯实验室公布的数据集进行测试,说明该算法能以较高的正确率对协议数据帧进行聚类。     

一种基于二部图谱划分的聚类集成方法

将二部图模型引入聚类集成问题中,使用二部图模型同时建模对象集和超边集,充分挖掘潜藏在对象之间的相似度信息和超边提供的属性信息.设计正则化谱聚类算法解决二部图划分问题,在低维嵌入空间运行K-means++算法划分对象集,获得最终的聚类结果.在多组基准数据集上进行实验,实验结果表明所提出方法不仅能获得优越的结果,而且具有较高的运行效率.     

复杂高维数据的密度峰值快速搜索聚类算法

机器学习的无监督聚类算法已被广泛应用于各种目标识别任务。基于密度峰值的快速搜索聚类算法(DPC)能快速有效地确定聚类中心点和类个数,但在处理复杂分布形状的数据和高维图像数据时仍存在聚类中心点不容易确定、类数偏少等问题。为了提高其处理复杂高维数据的鲁棒性,文中提出了一种基于学习特征表示的密度峰值快速搜索聚类算法(AE-MDPC)。该算法采用无监督的自动编码器(AutoEncoder)学出数据的最优特征表示,结合能刻画数据全局一致性的流形相似性,提高了同类数据间的紧致性和不同类数据间的分离性,促使潜在类中心点的密度值成为局部最大。在4个人工数据集和4个真实图像数据集上将AE-MDPC与经典的K-means,DBSCAN,DPC算法以及结合了PCA的DPC算法进行比较。实验结果表明,在外部评价指标聚类精度、内部评价指标调整互信息和调整兰德指数上,AE-MDPC的聚类性能优于对比算法,而且提供了更好的可视化性能。总之,基于特征表示学习且结合流形距离的AE-MDPC算法能有效地处理复杂流形数据和高维图像数据。     

一种基于核心顶点的无参图聚类算法

针对许多经典的图聚类算法存在输入参数难以确定、时间复杂度过高、聚类精度较低等缺点,本文提出了一种无需输入参数的基于核心顶点的图聚类算法（NGCC）。该算法将相似的顶点分配到同一个簇后,再利用PageRank算法发现核心顶点以形成初始簇。然后,将剩余的未标记顶点进行分配,形成最终簇结构。实验结果证明,NGCC算法在无需任何参数的条件下,在不同规模的数据集上的聚类质量与对比的经典图聚类算法相当或更优,而且适用范围更广。     

基于GraphX的分布式幂迭代聚类

为解决幂迭代聚类算法并行实现中存在的编程繁琐、效率低下等问题,基于Spark大规模数据通用计算引擎及其GraphX组件,提出了一种在分布式环境下实现幂迭代聚类的方法。首先,利用某种相似性度量方法,将原始数据转换成一个可以视为图的亲和矩阵;然后,通过顶点切割,把行归一化后的亲和矩阵切分成若干个小图,分别存储在不同的机器上;最后,利用Spark基于内存计算的特点,对存储在集群中的图进行多次迭代计算,得到这个图的一个切割,图的每一个划分子图对应一个类簇。在不同规模的数据集和不同executor个数下进行的实验结果表明,基于GraphX的分布式幂迭代聚类算法具有良好的可扩展性,算法运行时间与executor个数呈负相关的线性关系,在6个executor下,与单个executor相比,算法的加速比达到了2.09到3.77。同时,通过与基于Hadoop的幂迭代聚类进行对比,在新闻数量为40000篇时,运行时间降低了61%。     

基于图聚类的汉越双语新闻话题发现

跨语言新闻话题发现是将互联网上报道相同事件的不同语言新闻进行自动归类,由于不同语言文本很难表示在同一特征空间下,对其共同话题的挖掘就比较困难。然而类似的新闻事件在不同语言文本表达上具有相同的新闻要素,这些要素之间关联能够体现出新闻事件的关联性,因此,针对汉越新闻话题发现问题,提出基于文档图聚类的汉越双语新闻话题发现方法。首先提取汉越新闻文本新闻要素,借助文本中要素相似度计算汉越文本相关度,构建汉越双语文本图模型,获得新闻文本相似度矩阵;然后,借助图模型中文本间的传播特点,采用随机游走算法对相似度矩阵进行调整,最后利用信息传递算法进行聚类。实验结果表明提出的方法取得了很好的效果。     

基于消息传递的谱聚类算法

谱聚类将数据聚类问题转化成图划分问题,通过寻找最优的子图,对数据点进行聚类。谱聚类的关键是构造合适的相似矩阵,将数据集的内在结构真实地描述出来。针对传统的谱聚类算法采用高斯核函数来构造相似矩阵时对尺度参数的选择很敏感,而且在聚类阶段需要随机确定初始的聚类中心,聚类性能也不稳定等问题,本文提出了基于消息传递的谱聚类算法。该算法采用密度自适应的相似性度量方法,可以更好地描述数据点之间的关系,然后利用近邻传播（Affinity propagation,AP）聚类中“消息传递”机制获得高质量的聚类中心,提高了谱聚类算法的性能。实验表明,新算法可以有效地处理多尺度数据集的聚类问题,其聚类性能非常稳定,聚类质量也优于传统的谱聚类算法和k-means算法。     

Cluster center initialization algorithm for K-modes clustering

Partitional clustering of categorical data is normally performed by using K-modes clustering algorithm, which works well for large datasets. Even though the design and implementation of K-modes algorithm is simple and efficient, it has the pitfall of randomly choosing the initial cluster centers for invoking every new execution that may lead to non-repeatable clustering results. This paper addresses the randomized center initialization problem of K-modes algorithm by proposing a cluster center initialization algorithm. The proposed algorithm performs multiple clustering of the data based on attribute values in different attributes and yields deterministic modes that are to be used as initial cluster centers. In the paper, we propose a new method for selecting the most relevant attributes, namely Prominent attributes, compare it with another existing method to find Significant attributes for unsupervised learning, and perform multiple clustering of data to find initial cluster centers. The proposed algorithm ensures fixed initial cluster centers and thus repeatable clustering results. The worst-case time complexity of the proposed algorithm is log-linear to the number of data objects. We evaluate the proposed algorithm on several categorical datasets and compared it against random initialization and two other initialization methods, and show that the proposed method performs better in terms of accuracy and time complexity. The initial cluster centers computed by the proposed approach are close to the actual cluster centers of the different data we tested, which leads to faster convergence of K-modes clustering algorithm in conjunction to better clustering results.     

基于密度的聚类中心自动确定的混合属性数据聚类算法研究

面对广泛存在的混合属性数据,现有大部分混合属性聚类算法普遍存在聚类 质量低、聚类算法参数依赖性大、聚类类别个数和聚类中心无法准确自动确定等问题,针对 这些问题本文提出了一种基于密度的聚类中心自动确定的混合属性数据 聚类算法.该算法通过分析混合属性数据特征,将混合属性数据分为数 值占优、分类占优和均衡型混合属性数据三类,分析不同情况的特征选取 相应的距离度量方式.在计算数据集各个点的密度和距离分布图基础 上,深入分析获得规律: 高密度且与比它更高密度的数据点有较大距离的数 据点最可能成为聚类中心,通过线性回归模型和残差分析确定奇异 点,理论论证这些奇异点即为聚类中心,从而实现了自动确定聚类中心.采 用粒子群算法(Particle swarm optimization, PSO)寻找最优dc值,通过参数dc能够计算得到 任意数据对象的密度和到比它密度更高的点的最小距离,根据聚类 中心自动确定方法确定每个簇中心,并将其他点按到最近邻的更高 密度对象的最小距离划分到相应的簇中,从而实现聚类.最终将本文 提出算法与其他现有的多种混合属性聚类算法在多个数据集上进行 算法性能比较,验证本文提出算法具有较高的聚类质量.     

基于密度自适应邻域相似图的半监督谱聚类

谱聚类是基于谱图划分理论的一种聚类算法,传统的谱聚类算法属于无监督学习算法,只能利用单一数据来进行聚类。针对这种情况,提出一种基于密度自适应邻域相似图的半监督谱聚类（DAN-SSC）算法。DAN-SSC算法在传统谱聚类算法的基础上结合了半监督学习的思想,很好地解决了传统谱聚类算法无法充分利用所有数据,不得不对一些有标签数据进行舍弃的问题;将少量的成对约束先验信息扩散至整个空间,使其能更好地对聚类过程进行指导。实验结果表明,DAN-SSC算法具有可行性和有效性。     

基于局部密度和测地距离的谱聚类

传统根据[K]-近邻图计算测地距离的方法,虽然能够发现流形分布数据间的相似关系,但是当不同类的点存在粘连关系时,依此计算相似度时不能体现样本间的真实关系,从而无法有效聚类。针对传统测地距离计算相似度的方法不能有效处理粘连数据集的问题,提出了基于局部密度和测地距离的谱聚类方法。计算样本的局部密度,寻找每个样本点的最近高密度点,并选择边缘点和非边缘点;在边缘点和其最近高密度点之间构造边、非边缘点之间的[K]个近邻点构造边,依此计算测地距离和相似度并进行聚类。在人工数据集和UCI数据集上的实验表明,该算法在处理粘连数据集时有效提高了聚类准确率。