摘要:

摘要:现有一些典型的半监督聚类方法一方面难以有效地解决成对约束的违反问题,另一方面未能同时处理高维数据.通过提出一种基于成对约束的判别型半监督聚类分析方法来同时解决上述问题.该方法有效地利用了监督信息集成数据降维和聚类,即在投影空间中使用基于成对约束的K均值算法对数据聚类,再利用聚类结果选择投影空间.同时,该算法降低了基于约束的半监督聚类算法的计算复杂度,并解决了聚类过程中成对约束的违反问题.在一组真实数据集上的实验结果表明,与现有相关半监督聚类算法相比,新方法不仅能够处理高维数据,还有效地提高了聚类性能.

摘要:提出了一种基于近邻传播(affinity propagation,简称AP)算法的半监督聚类方法.AP是在数据点的相似度矩阵的基础上进行聚类.对于规模很大的数据集,AP算法是一种快速、有效的聚类方法,这是其他传统的聚类算法所不能及的,比如:K中心聚类算法.但是,对于一些聚类结构比较复杂的数据集,AP算法往往不能得到很好的聚类结果.使用已知的标签数据或者成对点约束对数据形成的相似度矩阵进行调整,进而达到提高AP算法的聚类性能.实验结果表明,该方法不仅提高了AP对复杂数据的聚类结果,而且在约束对数量较多时,该方法要优于相关比对算法.

摘要:提出了一种半监督K均值多关系数据聚类算法.该算法在K均值聚类算法的基础上扩展了其初始类簇的选择方法和对象相似性度量方法,以用于多关系数据的半监督学习.为了获取高性能,该算法在聚类过程中充分利用了标记数据、对象属性及各种关系信息.多关系数据库Movie上的实验结果验证了该算法的有效性.

摘要:在典型相关分析算法(canonical correlation analysis,简称CCA)的基础上,通过引入以成对约束形式给出的监督信息,提出了一种半监督的典型相关分析算法(Semi-CCA).在此算法中,除了考虑大量的无标号样本以外,还考虑成对约束信息,即已知两样本属于同一类(正约束)或不属于同一类(负约束),同时验证了两者的相对重要性.在人工数据集、多特征手写体数据集和人脸数据集(Yale 和AR)上的实验结果表明,Semi-CCA能够有效地利用少量的监督信息来提高分类性能.

摘要:在很多机器学习和数据挖掘任务中,仅仅利用边信息(side-information)并不能得到最好的半监督学习(semi-supervised learning)效果,因此,提出一种基于局部与全局保持的半监督维数约减(local and global preserving based semi-supervised dimensionality reduction,简称LGSSDR)方法.该算法不仅能够保持正、负约束信息而且能够保持数据集所在低维流形的全局以及局部信息.另外,该算法能够计算出变换矩阵并较容易地处理未见样本.实验结果验证了该算法的有效性.

摘要:提出利用基于图的半监督学习算法,即标注传递算法,指导计算机从非结构化的文本中自动识别出实体之间的关系.该方法首先利用图策略来建立关系抽取的模型.在这个图模型中,各个有标签和未标签的样本被表示成图上的各个节点,而样本间的距离则作为图上各边的权重.然后,关系抽取的任务就转化成在这个图上估计出一个满足全局一致性假设的标注函数.通过对ACE(automatic content extraction)语料库的评测,结果显示,当只有少量的标签样本时,采用该标注传递的方法可以获得比基于SVM(support vector machine)的有监督关系抽取更好的性能,同时也明显优于基于Bootstrapping的半监督关系抽取的方法.

摘要:提出了一种基于高阶张量表示的视频语义分析与理解框架.在此框架中,视频镜头首先被表示成由视频中所包含的文本、视觉和听觉等多模态数据构成的三阶张量;其次,基于此三阶张量表达及视频的时序关联共生特性设计了一种子空间嵌入降维方法,称为张量镜头;由于直推式学习从已知样本出发能对特定的未知样本进行学习和识别,最后在这个框架中提出了一种基于张量镜头的直推式支持张量机算法,它不仅保持了张量镜头所在的流形空间的本征结构,而且能够将训练集合外数据直接映射到流形子空间,同时充分利用未标记样本改善分类器的学习性能.实验结果表明,该方法能够有效地进行视频镜头的语义概念检测.

摘要:主要以提高求解马尔可夫决策问题的实时动态规划(real-time dynamic programming,简称RTDP)算法的效率为目的.对几类典型的实时动态规划算法所使用的收敛判据进行了对比分析,并利用值函数上界、下界给出了称为最优行动判据的收敛判据,以及一个更适合实时算法的分支选择策略.最优行动判据可以更早地标定当前状态满足精度要求的最优行动供立即执行,而新的分支选择策略可以加快这一判据的满足.据此设计了一种有界增量实时动态规划(bounded incremental RTDP,简称BI-RTDP)算法.在两种典型仿真实时环境的实验中,BI-RTDP均显示出优于现有相关算法的实时性能.

摘要:P₂-Packing问题是一个典型的NP难问题.目前这个问题的最好结果是时间复杂度为O^*(2^5.301k)的参数算法,其核的大小为15k.通过对P₂-packing问题的结构作进一步分析,提出了改进的核心化算法,得到大小为7k的核,并在此基础上提出了一种时间复杂度为O^*(2^4.142k)的参数算法,大幅度改进了目前文献中的最好结果.

摘要:针对信息过滤反馈中充斥噪声的缺陷,提出一种基于二元近似关系分布(distribution of two-dimension similarity,简称DTS)的过滤策略.DTS根据噪声和用户模型的相悖关系,为信息流建立二元近似关系模型.同时,根据信息在二维近似关系空间中的分布,采用基于LMS(least mean square)分类器的AdaBoost算法建立噪声和相关信息的分类曲线,从而辅助信息过滤系统识别和屏蔽反馈中的噪声.通过实验验证,该算法显著提高了过滤系统屏蔽噪声的能力.

摘要:为了提高交叉熵算法求解最大团问题(maximum clique problem,MCP)的性能,提出一种领导者-跟随者协作求解的并行策略来实现交叉熵算法,从而达到减少计算时间和保障解的质量这两方面的平衡.算法中领导者活跃在并行处理器之间采集数据,并根据当前获得信息对跟随者作出决策;受控的跟随者则主要根据领导者的决策信息自适应地调整搜索空间,完成各自的集团产生任务.采用了OpenMPI在MIMD平台上实现了该算法,并应用到MCP基准测试问题上.加速比和效率分析结果表明,算法具有很好的加速比和效率.而与其它几种当前最好的启发式算法相比,结果表明算法相对于基于种群的启发式算法有一定的性能改善.

摘要:近年来出现了多种新型的非线性降维方法,且在一些应用中体现出良好的效果.然而,当面对球体、柱体等环状流形产生的非线性流形数据时,这些方法往往会失效.针对这一问题,提出了针对环状流形数据的环结构检测算法与非线性降维方法.理论上,基于目前极受关注的Isomap降维方法的运行原理,给出了一个判断环状流形的充要条件;算法上利用所得的判断定理,制订了基于数据的环状流形检测算法;最后基于所找到的环结构,利用极坐标展开的思想设计了针对环状流形数据的非线性降维策略.针对一系列典型环状流形数据集的仿真实验结果表明,与其他流形学习降维方法相比,该方法对环状流形数据进行降维具有显著优势.

摘要:根据支持向量机(support vector machine,简称SVM)理论,对基于边界的分类算法(geometric approach)而言,类别边界附近的样本通常比其他样本包含有更多的分类信息.基于这一基本思路,以人脸检测问题为例,探讨了对给定训练样本集进行边界增强的问题,并为此而提出了一种基于支持向量机和改进的非线性精简集算法IRS(improved reduced set)的训练集边界样本增强算法,用以扩大训练集并改善其样本分布.其中,所谓IRS算法是指在精简集(reduced set)算法的核函数中嵌入一种新的距离度量——图像欧式距离——来改善其迭代近似性能,IRS可以有效地生成新的、位于类别边界附近的虚拟样本以增强给定训练集.为了验证算法的有效性,采用增强的样本集训练基于AdaBoost的人脸检测器,并在MIT+CMU正面人脸测试库上进行了测试.实验结果表明,通过这种方法能够有效地提高最终分类器的人脸检测性能.

摘要:提出了一种基于局部方向分布的角点检测与定位算法.该算法主要由两步组成,首先利用绝对角点能量和相对角点能量进行角点检测,然后使用最小二乘技术拟合支撑像素方向线的交点得到角点的亚像素位置.实验结果表明,相对于常见的角点检测算法,基于局部方向分布的算法不仅具有更高的定位精度,同时对噪音也有较强的鲁棒性.

摘要:针对现有的约束处理技术的一些不足之处,提出一种用于求解约束优化问题的算法——免疫克隆多目标优化算法(immune clonal multi-objective optimization algorithm,简称ICMOA).算法的主要特点是通过将约束条件转化为一个目标,从而将问题转化为两个目标的多目标优化问题.引入多目标优化中的Pareto-支配的概念,每一个个体根据其被支配的程度进行克隆、变异及选择等操作.克隆操作实现了全局择优,有利于得到高质量的解;变异操作提高算法的局部搜索能力,有利于所得解的多样性;选择操作有利于算法向着最优搜索,而且加快了收敛速度.基于抗体群的随机状态转移过程,证明该算法具有全局收敛性.通过对13个标准测试问题的测试,并与已有算法进行比较,结果表明,该算法在收敛速度和求解精度上均具有一定的优势.

摘要:对于冲突博弈,研究了一种理性保守的行为选择方法,即最小化最坏情况下Agent的后悔值.在该方法下,Agent当前的行为策略在未来可能造成的损失最小,并且在没有任何其他Agent信息的条件下,能够得到Nash均衡混合策略.基于后悔值提出了多Agent复杂环境下冲突博弈的强化学习模型以及算法实现.该模型中通过引入交叉熵距离建立信念更新过程,进一步优化了冲突博弈时的行为选择策略.基于Markov重复博弈模型验证了算法的收敛性,分析了信念与最优策略的关系.此外,与MMDP(multi-agent markov decision process)下Q学习扩展算法相比,该算法在很大程度上减少了冲突发生的次数,增强了Agent行为的协调性,并且提高了系统的性能,有利于维持系统的稳定.

摘要:针对缺乏多类型偏好共存的偏好逻辑系统的现状,MPL(logic of many kinds of preference)被构造为一种能够表示和推理四类型偏好的偏好逻辑,但是MPL的语义基于全前序偏好结构,因而不能表示不完全偏好.为此,提出了偏好逻辑GMPL(a generalized edition of MPL).此外,通过常见逻辑偏好的GMPL重写表明GMPL较强的表达能力和实际应用前景,并提出一种将GMPL的SAT问题归结为命题逻辑的SAT问题的方法.

摘要:提出了一种时间窗口机制,能够基于路由抖动抑制中路由惩罚值的变化改善BGP(border gateway protocol)路由收敛.这种新机制把来自不同邻居的路由变化情况结合起来,利用BGP路由传播过程形成的路由相关性判断路由在网络中的稳定情况.时间窗口机制使BGP路由器能够更早地发现不稳定路由,优先将稳定路由选择为最优路由,终止路径搜索过程.模拟实验的结果表明,通过选择适当的参数,时间窗口机制能够大大缩短BGP路由收敛延时,减小收敛过程中的通信开销.而且,这种方法不需要在BGP的路由消息中增加额外的信息,因此容易在实际网络中逐步部署.

摘要:针对不同级别的旁路信息泄露,提出一种通用的旁路信息泄露容忍防御模型,并结合信息熵理论给出该模型的形式化描述.该模型采用(t,n)门限机制,使得部分旁路信息泄露不会影响系统的安全性.在该防御模型的基础上,结合高级加密标准AES-128算法的安全实现,设计了一种两阶段掩码的旁路攻击防御方法.与已有的防御方法相比,该方法能够同时防御高阶旁路攻击与模板攻击.通过理论分析与仿真实验验证了该方法的有效性.

摘要:全面介绍了当前群组移动模型的研究进展,分析了不同群组移动模型的特点和应用范围,针对现有移动模型不能有效反映群组节点运动过程中行为特性的不足,提出了基于Gibbs分布模拟退火的群组移动(Gibbs sampler based simulated annealing group mobility,简称GGM)模型,并与目前广泛采用的参考点群组移动(reference point group mobility,简称RPGM)模型进行仿真比较,分析了两种群组移动模型对网络协议性能评价与网络拓扑的影响.仿真结果表明,通过选择不同的Gibbs势函数,GGM模型能够有效描述群体运动过程中的聚集行为、分散行为和列队行为;模型比较的结果也表明,不同的移动模型对Ad Hoc网络协议性能具有不同的影响.

摘要:提出了抽象多重服务范例来解决服务组合问题.同时,为了提高可适应性,给出一种用来选择适合调整的服务范例的可适应性的相似度测量方法,并提出了基于调整运算子的服务范例适应性调整方法.在这些工作的基础上实现服务组合.实验表明,该方法是可行和有效的.

摘要:基于用户行为分析的思路,提出了一种自动进行搜索引擎性能评价的方法.此方法能够基于对用户的查询和点击行为的分析自动生成导航类查询测试集合,并对查询对应的标准答案实现自动标注.基于中文商业搜索引擎日志的实验结果表明,此方法能够与人工标注的评价取得基本一致的评价效果,同时大大减少了评价所需的人力资源,并加快了评价反馈周期.

摘要:针对移动无线传感器网络中周期性信标交换引起的通信暂盲现象,提出一种自适应信标交换算法.在该算法中,工作节点根据相对于上游节点的特征量动态地计算下一次信标交换周期,空闲节点根据相对于所有邻居节点的特征量动态地计算下一次信标交换周期,或者采用周期性信标交换.该算法可以根据网络通信性能要求调整门限概率值来得到合适的信标交换周期;并通过信标反馈等待超时的方法删除被选择为下一跳但已移出的节点.仿真实验结果表明,该算法在工作节点稀疏型网络中不但提高了数据包传送成功率,而且降低了控制开销,可适用于大规模移动无线传感器网络.

摘要:协作缓存在移动自组织网络中得到了充分的应用和部署.提出了一种基于簇的一致性维护策略CCS(cluster-based consistency scheme).在CCS中,相邻的节点组成一个簇.每个簇中挑选一个能量较高、较稳定的节点作为簇头,而簇中的其他节点与簇头节点最多相距两跳.簇头节点利用基于DHT(distributed Hash table,分布式哈希表)的Chord协议作为组管理协议,即簇头节点组成一个Chord环.通过动态地在Chord环上建立更新树传播更新内容.这样,更新数据在不同的簇之间是通过更新树传播的,而在簇内是通过MAC层的广播传播的.仿真实验结果表明,与基于流言传播的缓存一致性维护策略相比,CCS具有开销小、成功率高和传播快的特点.

摘要:对给定的一个直线段集合S,研究求与S中所有直线段都相交的直线的问题.设S中的线段满足一定的不交性假设,算法可回答是否存在与S中所有线段均相交的直线的问题.如果该直线存在,则求出这样的直线的最大存在范围——位于该范围内的每条直线都与S中的所有直线段相交.该算法的时间复杂性为O(n*log n),应用背景是模式匹配等领域.

摘要:提出了Polycube参数化的自动构造技术.该算法首先对网格进行特征分解,然后用立方体组成的一些基本形体逼近分解得到的各部分网格区域,确定基本Polycube的顶点和边在区域上的对应顶点和路径,将各区域进一步分解为面片,从而在构造Polycube的同时完成对曲面的分片,最后再分片参数化并进行面片间的平滑,高效地实现了Polycube的自动参数化.该方法在很大程度上减少了Polycube构造过程中的人工干涉,使其能够在纹理映射等方面得到应用.

摘要:综述了海量层次信息可视化与Focus+Context技术的相关工作,针对海量层次信息可视化的交互问题,在嵌套圆可视化技术的基础上提出了基于上下文感知的Focus+Context交互式可视化技术.首先,基于外切圆排列方法提出对圆心进行三角网格剖分的方法,为变形计算建立上下文;然后,针对变形计算前后上下文一致性问题,在三角网格邻居跟踪方法的基础上,提出了用于同层兄弟节点上下文感知的外切圆变形排列方法,以及用于父子节点上下文感知的嵌套圆迭代排列方法.实验结果表明,上述方法在实现焦点突出的鱼眼视图的同时,能够有效地解决Focus+Context交互式可视化的上下文感知问题.上述方法应用于文件系统海量层次信息的交互式可视化问题,提供了交互式可视化 工具.

摘要:提出了一种从真实物体中提取纹理的方法.利用具有复杂纹理的参考球体作为被采样物体,计算其组成材质的BRDF(bidirectional reflectance distribution function)模型参数以及各点由不同材质构成的比例,形成一幅材质权重图.该图作为纹理映射到3D物体上后,配合BRDF模型参数进行渲染,形成一种适用于重光照(relighting)的纹理.被渲染物体可根据自身方位以及光源亮度/方位呈现出自然的光影变化,达到较为逼真的外观效果.