基于子模函数构建优化商空间链

通过商空间链,可得到特定目标求解的逼近方法,由此可完成处理复杂信息,发现隐含知识,揭示事物和事件的内在规律的任务.但随着数据环境的变化,商逼近近似求解开始遇到挑战,由此引发的关键问题就是怎样构建满足求解精度的商空间链,逼近过程中误差界是多少.结合子模函数优化理论来构建商空间链,并对商逼近过程的逼近精度问题展开研究,证明了商空间可保持目标函数的子模性,可利用简单的贪心策略构建最优商空间链,逼近过程中最大误差界≤[1-(1-1/e)-1].

模糊子模函数与模糊秩函数

讨论模糊集合的一些性质;再以一般子模函数为蓝本,定义模糊子模函数,研究模糊子模函数和模糊秩函数的性质;然后利用这些性质推广通过模糊秩函数确定模糊拟阵的一个重要定理。

拟阵约束下最大化子模函数的模型及其算法的一种熵聚类方法

本文提出了一个新的带有信息熵的聚类目标函数,它是由基于图论的随机路径的熵率和平衡项两部分组成。熵率有利于形成紧凑和均匀的聚类,平衡函数鼓励相似度比较高的对象才能聚类,并惩罚那些相似度比较低的对象。首先构造了与数据关联的赋权无向图,并发现这种构造诱导出一个拟阵,它是一个组合在向量空间中推广线性独立概念的结构。接着得到了拟阵约束下最大化子模函数的模型。最后根据目标函数的单调性、递增性和下模性,开发了一个高效的贪婪算法并讨论了它的性能保证。最后根据数值实验,与已有的算法做了比较,说明了该算法的有效性。

基于优化的子模函数最大化的超像素图像分割

在研究熵率超像素图像分割的基础上,提出基于拟阵的子模函数最大化算法来解决目标函数的优化问题。采用图拓扑方法进行图像分割,在拟阵约束下最大化目标函数,利用目标函数的子模性和单调性,设计了一种基于堆结构的高效率贪婪算法。通过在Berkeley分割数据集和基准测试中的大量实验,以及对真实自然环境下多幅叶片图像的分割实验,从欠分割误差率、边界回溯率、可达分割精度以及运行时间等方面与现有分割算法进行了对比。实验结果显示,子模函数最大化优化算法的所有标准评估指标均优于现有技术,对于100个超像素,分割精度可达到95%,运行速度提高50%,对图像的分割具有一定的现实意义。

基于最大化子模和RRWM的视频协同分割

成对视频共同运动模式的协同分割指的是同时检测出两个相关视频中共有的行为模式,是计算机视觉研究的一个热点.本文提出了一种新的成对视频协同分割方法.首先,利用稠密轨迹方法对视频运动部分进行检测,并对运动轨迹进行特征表示;然后,引入子模优化方法对单视频内的运动轨迹进行聚类分析;接着采用基于重加权随机游走的图匹配方法对成对视频运动轨迹进行匹配,该方法对出格点、变形和噪声都具有很强的鲁棒性;同时根据图匹配结果实现运动轨迹的共显著性度量;最后,将所有轨迹分类成共同运动轨迹和异常运动轨迹的问题转化为基于图割的马尔科夫随机场的二值化标签问题.通过典型运动视频数据集的比较实验,其结果验证了本文方法的有效性.

分配格上函数差的共轭函数的一般公式

对于分配格上的任意函数 f∶ D→ R和子模函数 g∶ D→ R,利用 f和 g的共轭函数 ,我们给出了 ( f - g)的共轭函数的一个公式 ,作为它的应用 ,我们得到了Fujishije的对偶定理 .

基于子模优化的边界域处理社团发现算法

使用聚类粒化方法求取非重叠社团结构时,经常会出现重叠区域。三支决策模型将两个存在重叠的社团的左边社团中非重叠部分定义为正域,右边社团中非重叠部分定义为负域,而两个社团的重叠部分定义为边界域。为了获得更好的社团性能,须将边界域中的节点进行二次划分。子模优化在机器学习中有广泛的应用,如果目标函数具有子模性,则存在一个简单的贪心算法能在多项式时间内以常数因子逼近问题的最优解。将子模优化思想引入社团重叠区域节点的处理,提出一种基于子模优化的边界域处理社团发现算法(SO-CDA)。定义设备选址函数进行子模优化,重叠节点的划分可以转化为子模函数最大化问题,在7个真实网络上的实验结果表明,SO-CDA能够有效地进行社团划分,性能更加稳定。

基于CVaR子模效益模型的传感器布局优化

针对在不确定情况下如何保证传感器布局取得最优效果问题,本文在初始部署节点时考虑节点存在的不确定性,采用基于CVaR的子模效益模型来最小化这种不确定性对传感器网络布局效果的影响,为了快速有效获得该模型下的最优传感器布局,对传统贪婪算法进行改进,根据模型中存在的参数τ对全局最优解进行有序搜索,同时引入lazy evuluation减少算法的时间复杂度.仿真实验表明,在不确定情况下对传感器进行布局时,CVaR模型可以有效提高网络布局的鲁棒性,与改进的贪婪算法相结合,可以快速获得保证较高信息增益下的布局点集.

基于图割与泛形信息的对象分割方法

针对交互式图像对象分割对用户交互性、分割速度和精度的需求,提出一种融合用户交互中泛化形状(简称泛形)信息的方法.该方法通过能量函数将用户交互中包含的泛形信息(包括区域、边界泛形)与对象、背景外观颜色以及图像梯度信息有机地融合,建立了从全局优化到局部优化的分割框架,并利用高效的图割优化方法进行求解.在全局优化过程中,利用超像素代替像素作为处理的基本单元,在保留原图像空间结构特征的同时大幅降低了全局优化计算的复杂度,并通过区域泛形保证全局整体分割的质量.局部优化过程对全局分割结果边界处的错误进行修正,仅处理某段边界局部范围内的像素,保证了分割速度;同时,边界泛形约束进一步确保了最终分割结果在边界处的准确性.实验结果证明了文中方法在用户交互性、分割速度和精度方面的良好性能.

一种移动流媒体分层协同缓存系统

随着移动互联网的发展和用户数量的增加,网络中的音视频服务普遍采用动态缓存机制来减轻回程主干网的带宽压力和提高用户的观影体验。如何根据网络和用户需求,调整不同节点的缓存内容,以减少主干网的带宽压力,是当前缓存部署迫切需要解决的问题。基于子模函数理论,本文提出主动和被动资源分配调整方案及其算法。主动方案根据资源的流行度把视频文件部署到缓存节点上,以达到用户访问代价的最小化;被动方案根据音视频流行度的变化对节点上缓存的内容进行实时调整,以提高缓存资源的利用率和用户体验,降低主干网的带宽消耗。最小访问代价算法的复杂度与缓存空间容量大小相关,在缓存空间紧张时能快速迭代出资源的分配方案。数值仿真表明,主动和被动分配资源分配方案能有效降低远程服务器的带宽压力和提高用户体验。

非均匀划分拟阵约束下的多样性推荐方法

多样性推荐方法旨在提供既满足相关性又具有多样性的top-k推荐结果。大多数现有的多样性方法没有同时考虑多样性和准确度,而且这些方法假设每个推荐项的重要程度是相同的。受此启发,针对个性化推荐系统,提出一种新的基于用户偏好的多样性推荐模型。该模型对用户的整体类别偏好程度、同一类别内部的偏好程度和相关度进行建模;将多样性和相关性同时融合到子模函数中,同时在模型上施加了非均匀划分拟阵约束(即不同用户对不同类别的偏好程度以及同一类别内部的偏好程度不同,每个推荐项的重要程度也不同);证明了最大化提出的目标函数是NP-hard问题,并通过类别簇内局部贪心求解子模函数获得(1-1/e)的近似保证率,同时降低了算法复杂度。最后,引入一个惩罚因子自动调节同一类别中的推荐项加入推荐列表的困难程度。不同数据集上的实验结果表明:提出的方法不仅能够在准确度和多样性之间取得有效的折中,而且具有高效性。

一种基于通联数据的信息扩散路径推测算法

信息的传播和扩散对于研究市场营销、病毒木马的传播等具有重要意义。但是,在许多场景下仅能获取网络中用户的通联数据,难以获取用户间通信的内容。针对该问题,文中提出了一个基于概率的信息传播模型来对网络中的通联数据进行建模,以此估计网络中用户通信内容的相关性,进而推测网络中信息的扩散路径。文中证明了求解该模型的复杂度为NP-hard,并提出了PathMine算法来获取模型的一个近似最优解。实验表明,所提PathMine算法能够高效地挖掘网络中信息的传播模式,优于已知的其他方法。

无线可充电传感器网络中一般随机事件捕获调度

当随机事件服从任意概率分布时,如何调度可充电传感器以使得事件捕获的总体监控质量(Qo M)最大化.首先验证了这一问题是NP完全问题,其次证明了优化问题的目标函数是单调子模.通过将这个问题表述为求解一个拟阵约束下子模函数最大值的问题,设计了一种近似算法,得到了系数为1/2的近似解,并通过了仿真验证.

基于通联行为的信息传播模式挖掘方法

针对通信内容未知且无关通联占比高情况下信息传播模式的挖掘问题,提出了一个生成模型,对通联行为发生的时间建模,预测网络中用户通信内容的相关性,进而获取网络中信息的传播模式.证明了求解所提模型的复杂度为NP-hard,并提出用Net Mine算法来估计模型的一个近似最优解.实验结果表明,所提Net Mine算法能够高效地挖掘网络中信息的传播模式,并优于已知的其他方法.