基于二部图的联合谱嵌入多视图聚类算法

多视图聚类在图像处理、数据挖掘和机器学习等领域引起了越来越多的关注.现有的多视图聚类算法存在两个不足,一是在图构造过程中只考虑每个视图数据之间的成对关系生成亲和矩阵,而缺乏邻域关系的刻画;二是现有的方法将多视图信息融合和聚类的过程相分离,从而降低了算法的聚类性能.为此,提出一种更为准确和鲁棒的基于二部图的联合谱嵌入多视图聚类算法.首先,基于多视图子空间聚类的思想构造二部图进而产生相似图,接着利用相似图的谱嵌入矩阵进行图融合,其次,在融合过程中考虑每个视图的重要性进行权重约束,进而引入聚类指示矩阵得到最终的聚类结果.提出的模型将二部图、嵌入矩阵与聚类指示矩阵约束在一个框架下进行优化.此外,提供一种求解该模型的快速优化策略,该策略将优化问题分解成小规模子问题,并通过迭代步骤高效解决.提出算法和已有的多视图聚类算法在真实数据集上进行实验分析.实验结果表明,相比已有方法,提出算法在处理多视图聚类问题上是更加有效和鲁棒的.

二部图性质的谱刻画

为了刻画二部图的性质,研究了图的邻接矩阵、邻接特征多项式、线图、关联矩阵、拉普拉斯矩阵、无符号拉普拉斯矩阵等。用图的谱性质刻画了二部图的特征,并得到了以下结论:二部图G的奇数阶谱矩为0,邻接谱在实数轴上关于原点对称,–2是线图l(G)的重数为m−n+1的特征值,拉普拉斯矩阵和无符号拉普拉斯矩阵有相同的谱,最小无符号拉普拉斯特征值等于0,最大拉普拉斯特征值等于最大无符号拉普拉斯特征值。

基于汉字拆分嵌入和二部图的残损碑文识别

古籍碑刻承载着丰富的历史文化信息,但是由于自然风化浸蚀和人为破坏使得碑石上的文字信息残缺不全。古碑文语义信息多样化且样例不足,使得学习行文语义补全识别残损文字变得十分困难。该文试图从字形空间语义建模解决补全残损汉字进行识别理解这一挑战性任务。该文在层级拆分嵌入(HDE)编码方法的基础上使用动态图修补嵌入(DynamicGrape),对待识别汉字的图像进行特征映射并判别是否残损。如未残损直接转化为层级拆分编码,输入二部图推理字节点到部件节点的边权重,比对字库编码识别理解;如残损需要在字库里检索可能字和部件,对汉字编码的特征维度进行选择,输入二部图推理预测可能的汉字结果。在自建的数据集以及中文自然文本(CTW)数据集中进行验证,结果表明二部图网络可以有效迁移和推理出残损文字字形信息,该文方法可以有效对残损汉字进行识别理解,为残损结构信息处理开拓出了新的思路和途径。

完全二部图上的筹码分发博弈

本文主要研究完全二部图上的筹码分发博弈(chip-firing games)次数的有限性。我们根据顶点的筹码数,定义两个函数并进行分类;结合完全二部图的性质,给出了博弈次数有限的充要条件。

团-二部图的距离矩阵的行列式和逆

一个连通图G被称为团-二部图,如果它的块是一些团或者完全二部图.设D(G)是其距离矩阵,利用Graham等作者的一个定理,该文证明了det(D(G))≠0当且仅当K 2,2不是G的一个块,并且给出了D(G)的行列式和逆的公式.

完全二部图K_(4,n)的点被多重集可区别的E-全染色

利用反证法、色集合事先分配法及构造具体染色等方法,讨论完全二部图K_(4,n)的点被多重集可区别的E-全染色,并确定K_(4,n)的点被多重集可区别的E-全色数.

基于用户画像与二部图的大学生就业岗位推荐算法

针对现有就业岗位推荐算法仅基于单一的信息源或简单的用户分类,无法充分捕捉大学生的多维特征和个性化需求,从而导致推荐效果不佳的问题,提出基于用户画像与二部图的大学生就业岗位推荐算法。在融合长短期记忆神经网络的条件随机场模型辅助下,从高校图书馆的档案管理系统中抽取出用户基础信息,基于此生成大学生用户画像。计算不同用户画像特征之间的距离,并采用k均值聚类算法完成用户画像聚类。运用二部图网络搭建基础的大学生就业岗位推荐结构,基于能量分配情况设计初步推荐方案。最后,以加权随机森林模型为基础,考虑用户对项目特征的偏好实现大学生就业岗位的分类,修正初步给出推荐列表的评分,获取精准的大学生就业岗位推荐结果。实验结果表明,应用该方法,给出长度为120的大学生就业岗位推荐列表,其推荐结果的命中率达到了0.94。由此说明,该方法可以精准得出大学生就业岗位推荐结果,从而提高就业匹配度和人力资源利用效率。

完全二部图K5,n(n ≥ 7114)的点被多重集可区别的E-全染色

利用反证法、色集合事先分配法以及构造具体染色等方法,探讨了完全二部图K5,n(n ≥ 7114)的点被多重集可区别的E-全染色,确定了这一类图的点被多重集可区别的E-全色数。

完全正则三部图与二部图的笛卡尔积的亏格

设Km,m,m(m≥1)是一个完全正则三部图,G是一个围长大于4的二部图.当G的最大度不大于2m时,本文得到完全正则三部图Km,m,m与G的笛卡尔积的亏格.我们的结果推广了Bonnington和Pisanski关于Km,m,m与偶圈的笛卡尔积的亏格.此外,我们还得到了Km,m,m与一些非二部图的笛卡尔积的不可定向亏格.

半正则二部图的补图生成树计数的一种新方法

一个二部图G = (U, V, E)是半正则当且仅当同一部顶点集的两个顶点的度相等。 进一步,设G = (V1, V2, E)是一个二部划分为(V1, V2)的连通二部图,即V1 ∪ V2 = V (G) 且V1 ∩ V2 = ∅。 若G满足|V1| = s, |V2| = t,且∀ui ∈ V1, dG(ui) = x (i = 1, . . . , s), ∀vj ∈ V2, dG(vj ) = y (j = 1, . . . , t),则称G是一个半正则二部图,记作G = (s, t;x, y)。 利用Kirchhoff矩阵-树定理和矩阵的Schur补,本文得到一种半正则二部图的补图的生成树计数一般公式,并得到一些特殊半正则二部图补图的生成树数目计数公式。

基于二部图匹配算法的新高考专业历史数据追踪研究

新高考要求按专业填报志愿,精准志愿填报需根据专业历史数据准确预测当年该专业可能的录取分数。针对新高考海量专业录取分数预测过程中,专业名称变化导致的自动历史数据追踪难的问题,设计了一种基于二部图最优匹配的专业历史数据追踪算法。该算法基于编辑距离构建了专业名称相似度测度,使用二部图最优匹配解决了最大相似度匹配导致的多对一匹配问题,强制专业名称前两个汉字相同的匹配规则可避免因字符串包含导致的匹配错误。

4限制边连通二部图的充分条件

设G是一个4限制边连通图,主要研究含有(4,4)-距离点集对的4限制边连通二部图的最优性.

基于二部图网络的电商平台智能化推送算法研究

在电商平台领域,大多数推荐算法都是基于用户–物品二部图网络(BGN)。但是这种推荐算法在准确性和多样性上严重不足。本文提出了一种基于BGN链接预测的电子商务推荐算法。首先,将所有用户项数据导入距离公式,计算属性之间的相似度;然后,将BGN投影到单模网络(SMN)中,提高了从BGN中提取潜在链路的效率。在此基础上,根据相似性对潜在链接进行预测。通过在真实电子商务数据集上的实验,证明了我们的算法比典型的推荐算法具有更高的准确率和覆盖率。

基于加权二部图及贪婪策略的蜂窝网络D2D通信资源分配

D2D(Device-to-Device)通信是解决频谱资源稀缺问题的关键技术之一。该文研究蜂窝网络中“many-tomany”的复杂场景,即单个RB(Resource Block)可以分配给多对D2D用户重用,并且允许单个D2D用户对使用多个RB,其中D2D用户对数量远多于蜂窝用户设备(Cellular User Equipment,CUE)数量和RB数量。考虑CUE对资源使用具有更高优先级,将此优化问题分解为蜂窝用户资源分配和D2D用户资源重用两个阶段。在第1阶段,提出基于公平性的循环二部图匹配(Fairness-based Circular Bipartite Graph Matching,FCBGM)算法,将现有的RB分配给所有CUE,以最大化蜂窝用户和速率。在第2阶段,分别提出基于二部图的资源重用(Bipartite Graph-based Resource Reuse,BGRR)算法和基于贪婪策略的资源重用(Greedy-based Resource Reuse,GRR)算法,目标是将已经分配给CUE的RB再次分配给D2D用户重用,以最大化系统和速率,同时确保CUE的基本速率需求。仿真结果表明,在D2D用户对数量远大于CUE数量和RB数量的情况下,与现有典型算法相比,所提算法能够有效提高系统和速率,增加D2D接入率,同时兼顾用户公平性和服务质量需求。

基于二部图表示的属性网络社区发现算法

属性网络社区发现是网络数据分析中的一项重要研究内容。为了提高社区发现的准确性,现有算法大多通过融合拓扑信息和属性信息对属性网络进行低维表示,然后基于低维特征进行社区发现。然而,这类算法通常基于深度模型进行表示学习,缺乏一定的可解释性。因此,文中提出了一种基于二部图表示的属性网络社区发现算法,以提高社区发现结果的准确性和可解释性。首先,分别基于属性网络的拓扑信息和属性信息计算网络中各个节点作为代表点的概率,通过两类信息融合选出一定比例的节点作为代表点;其次,基于拓扑结构和节点属性计算各个节点到代表点的距离,构建二部图;最后,基于二部图利用谱聚类算法进行社区发现,得到最终结果。在人造属性网络和真实属性网络上与已有的属性网络社区发现算法进行实验比较分析。实验结果表明,所提算法在标准化互信息、调整兰德指数等评价指标上均优于已有算法。

基于加权二部图的课程教师推荐方法

为给高校课程推荐合适的授课教师以提高课程教学质量,本研究提出一种基于加权二部图的课程授课教师推荐方法。首先,采用TSTI量表和TPACK测量工具,以及所构建的教学质量、课程难度等量表,收集某学科专业中的教师和课程特征数据,并构建教师-课程-教学质量稀疏实验矩阵。接着,将课程难度和教学质量特征混入二部图,构建加权二部图模型,并采用改进的PersonalRank算法科学地预测出教师在未授课程上的教学质量。最后,创建一种融合教师的教学风格和TPACK特征的TOP-N推荐模型,实现课程的授课教师的精确推荐。对比实验结果显示,该方法在课程授课教师推荐准确性和性能上优于传统的协同过滤(CF)推荐算法,并且该方法具有可解释性。

信道分配与二部图的非正常边染色

确定二部图的边染色数和极小边染色是计算机领域的一个经典算法问题.该问题在信道分配和计算机科学的众多方面有广泛应用,并且是NP完全的.本文首先从二部图结构入手,利用非正常边染色定义,采用构造方法得到亏格为1和2时部分完全二部图的非正常边染色数,给出相应算法和复杂性分析,然后将其转化为网络中的信道数量.

赋权二部图最大匹配的灵敏分析

本文主要从理论上讨论赋权二部图的权的变化对最优解的影响 。

全Bregman散度和二部图相结合的高光谱图像稳健聚类算法

针对传统基于图的谱聚类算法底层计算复杂度高、聚类精度低,难以应用于大规模数据聚类,本文利用锚点与数据点之间的相似性度量,提出了一种基于图的聚类算法来处理高光谱图像分类问题,称为全Bregman散度和二部图相结合的高光谱图像稳健聚类算法(RTBBG)。首先,在构造二部图的过程中添加了高光谱图像的空间信息,使得高光谱图像丰富的空间信息得以充分利用;然后,利用全Bregman散度来优化传统的欧氏距离作为数据点与锚点之间新的相似性度量,使得构建的二部图更加稳定,增强了算法稳健性;最后,利用K-means算法直接进行光谱聚类得到最终聚类结果。通过在3个大规模高光谱数据集上进行测试,验证了本文算法的有效性。

一般图与二部图中完美匹配关于距离无符号拉普拉斯谱半径的存在性

令D(G)=(D_(i,j))为连通图G的距离矩阵,其中D_(i,j)等于顶点v_(i)和v_(j)之间的距离.令η1(G)为图G的距离无符号拉普拉斯谱半径,即距离无符号拉普拉斯矩阵Q(G)=Diag(Tr)+D(G)的最大特征值,其中Diag(Tr)为对角矩阵,Diag(Tr)_(ii)=Σ_(vivj∈E)(G)D_(i,j).在本文中,我们研究图中完美匹配的存在性与距离无符号拉普拉斯谱半径之间的关系,并分别给出关于距离无符号拉普拉斯谱半径的一般图和二部图存在完美匹配的充分条件.