基于拉格朗日算法的多媒体云资源分类检索方法*
刘平a, 刘春b
a. 河北科技大学 图书馆, 石家庄 050018
b. 河北科技大学 环境与工程学院, 石家庄 050018

作者简介: 刘 平(1976-),女,河南安阳人,讲师,硕士,主要从事多媒体信息安全及竞争情报等方面的研究.

摘要

针对云计算环境下多媒体资源分类检索准确性差的问题,提出一种新的多媒体资源分类检索方法,通过决策树算法对多媒体资源进行采集及属性划分.引入基于拉格朗日系数的拉格朗日算法对资源进行求解和预处理,以李雅普诺夫定理为基础,获取多媒体资源特征,并通过标注传播算法实现对多媒体资源的分类检索.实验结果表明,采用改进的方法可以有效增加多媒体资源分类检索的准确度和检索效率,具有一定的实用性.

关键词: 云计算; 多媒体; 资源; 分类; 检索方法; 属性划分; 扩展; 效率
中图分类号:TP311 文献标志码:A 文章编号:1000-1646(2017)04-0433-05 doi: 10.7688/j.issn.1000-1646.2017.04.14
Classification retrieval method for multimedia cloud resources based on Lagrange algorithm
LIU Pinga, LIU Chunb
a. Library, Hebei University of Science and Technology, Shijiazhuang 050018, China
b. School of Environment and Engineering, Hebei University of Science and Technology, Shijiazhuang 050018, China
Abstract

Aiming at the problem that the classification retrieval accuracy for multimedia resources is poor in cloud computing environment, a new classification retrieval method for multimedia resources was proposed, and the collection and attribute division for multimedia resources were carried out with the decision tree algorithm. The solving and preprocessing for the resources were performed through introducing Lagrange algorithm based on Lagrange coefficient. Based on the Lyapunov theorem, the characteristics of multimedia resources were acquired, and the classification retrieval for multimedia resources was realized with the label propagation algorithm. The experimental results show that the improved method can effectively enhance the accuracy and retrieval efficiency for the classification retrieval of multimedia resources, and has a certain practicality.

Keyword: cloud computing; multimedia; resource; classification; retrieval method; attribute division; extension; efficiency

随着计算及储存技术的不断发展, 云计算技术被提出, 且近几年云计算应用愈来愈成熟, 越来越多的资源信息中心部署了自己的云空间.为了满足大众用户对于计算能力、储存共建和相关计算服务复杂度的需求, 云计算技术很好地供应了相应解决方案, 并从各个角度解释了其固有的优势[1].多媒体资源检索一直是多媒体使用及信息处理领域的探讨热点, 与多媒体资源的储存、相似度匹配等多方面相关[2].尤其是最近几年, 随着互联网和信息技术的快速发展, 多媒体资源快速增加, 使得多媒体资源检索面临很大的挑战.如何对云计算环境下的多媒体资源进行快速分类检索成为了相关领域亟待解决的问题, 具有实际意义, 受到很多学者的关注, 且提出了很多好的方法[3, 4, 5].

文献[6]提出数据网格环境下的多媒体资源分类检索方法, 其通过设计分层构造的虚拟资源空间管理非构造化的异构资源, 该方法虽然在检索性能及查准率方面都有相应的提高, 但该方法容易受到周围检索环境的干扰, 不适合复杂环境中使用; 文献[7]提出基于Ajax的网络多媒体资源分类检索方法, 通过对各多媒体资源进行组织、融合、管制及划分, 减少分类检索过程中产生的各种干扰, 增加多媒体资源的分类检索准确度, 但是存在使用条件受限的问题; 文献[8]提出基于UPnP的多媒体资源分类检索方法, 采用UPnP方法在降低资源分类检索的同时, 却产生了资源浪费和耗时过长的问题.

针对上述产生的问题, 提出一种新的多媒体资源分类检索方法.首先利用决策树算法对多媒体资源采集及划分, 并使用拉格朗日算法对资源进行预处理, 最后以李雅普诺夫定理为基础获取多媒体资源特征.实验结果表明, 采用本文所提出的方法可以有效增加多媒体资源分类检索的准确度和检索效率, 具有一定的实用借鉴意义.

1 多媒体资源分类算法的提出
1.1 多媒体资源采集

在进行多媒体资源分类检索时, 首先需要对其资源进行采集.本文采用决策树算法对资源属性进行划分, 利用资源属性信息的增益率来构建决策树, 其中具备最高信息增益率的属性可作为决策树的支点, 依据不同取值对样本资源属性进行划分.待划分的多媒体样本资源通过决策树算法进行资源数据采集, 假设S=(S1, S2, …, Sn)是训练样本集合, 其中样本Si由属性集合A=(A1, A2, …, Am)表示.样本集合S由类别属性取值划分为k个子集C1, C2, …, Ck, 样本资源的信息增益率表达式为

H(S)=-p=1k[P(Cp)log2P(Cp)](1)

式中, P(Cp)= Cp/ S, 1≤ pk.设非类别属性A0存在t0个不一样的取值aq(1≤ qt), 则C1, C2, …, Ck也能被A0进一步划分为kt个子集, 每个子集Cpq表示在A0=aq的条件下属于第p类的样本集合.采用决策树算法进行属性划分, 得到样本集合S的平均信息量表达式为

H(SA0)=-q=1tP(Cq)[-p=1k(P(Cpq)log2P(Cpq))](2)

式中: P(Cq)=p=1kCpq/S; P(Cpq)=Cpq/S.

利用A0S进行划分的资源信息增益量表达式为

fG(S, A0)=H(S)-H(S/A0) (3)

A0S进行划分的信息增益率fGR(S/A0)等于资源信息增益量与分割信息量之比, 即

fGR(S A0)= fG(S, A0)fsp(S, A0)(4)

fsp(S, A0)具体表达式推导可参见文献[9].综上所述, 通过决策树算法对多媒体资源属性进行分类, 可实现多媒体资源的属性划分与采集.

1.2 多媒体资源预处理

在对多媒体资源进行采集后, 需对资源进行预处理, 降低资源自身影响因素对特征获取时带来的干扰.将资源数据矩阵和样本转换成为具备n个样本和p个变量的数据矩阵X, 同时把多媒体资源数据矩阵X进行标准化处理[10].在此基础上, 构建一个具备多个资源数据对象变异信息且基于X线性组合的综合变量f0, 即将f0=Xa0的方差取到最大值, 其中, a0为线性变换矩阵.将多媒体资源数据进行标准化处理之后, 令V= 1nXTX为其协方差矩阵, 则f0的方差获取表达式为

将求解方差最大值问题转换为求解n最大值问题, 并引入基于拉格朗日系数的拉格朗日算法进行特征求解和预处理.令L= aT0Va0-( aT0a0-1), 对L分别取关于a0λ 的偏导使其为零, 即

La0=2Va0-2λa0=0Lλ=-(aT0a0-1)=0(6)

由式(6)可知, Va0=λ a0, 且a0V的一个标准化特征变量, 其所对应的特征值为λ , 根据特征值进行多媒体资源求解.若var(f0)= aT0Va0, 则a0为多媒体资源数据矩阵V的最大特征值λ 的标准化特征变量, 即为最优的多媒体资源; 反之, var(f0)≠ λ , 则需要重新进行预处理, 直到获取最优的多媒体资源为止.

1.3 多媒体资源特征获取

在得到最优的多媒体资源数据后, 利用李雅普诺夫定理对其进行资源特征提取.假设随机多媒体资源变量X1, X2, …, Xn相互独立且具有相似的数学期望和方差, E(Xk), D(Xk)2> 0, k=1, 2, …, n, 则对任意多媒体资源均有

limnPk=1nXk-σn< x=-x12πex22dx=Φ(x)(7)

Xk 随机分布, 只要n充分大, 则 k=1nXk-σn就越近似服从标准正态分布N(0, 1), 提取多媒体资源特征表达式为

Zn=k=1nXk-E(k=1nXk)(8)

2 多媒体资源分类检索方法的实现

在提取多媒体资源特征的基础上, 采用标注传播算法对多媒体资源特征分布情况进行标注, 即

fij=Yij, 1≤ il, 1≤ jc (9)

f= fLfU, 根据已标注(L)和未标注(U)将多媒体资源p分成4个子矩阵, 即

p= pLLpLUpULpUU(10)

未标注的多媒体资源可表示为

fU=pUUfU+pULYL (11)

则其最终的分类结果表示为

f'U=limn(pUU)nfU+(i=1n(pUU)i-1)pULYL(12)

(pUU)n越趋于0, 分类结果越接近期望的分类结果, 准确度越高.将多媒体资源向量记作Q=((q1, l1), (q2, l2), …, (qn, ln)), 其中, qn为多媒体资源数量, ln为对应的多媒体资源特征.Q中的每个资源qi均可进行扩展, 扩展之后均有一个特征量(qi1, qi2, …, qik)与之对应, 每个扩展资源qij在扩展后都可得到与qi之间的检索相似度sij, 此时得到的多媒体资源扩展向量可记作

H= (q11, l1, s11)(q12, l1, s12)(q1k, l1, s1k)(q21, l2, s21)(q22, l2, s22)(q2k, l2, s2k)(qn1, ln, sn1)(qn2, ln, sn2)(qnk, ln, snk)(13)

检索引擎接收到多媒体资源扩展向量H后, 得到相应的检索结果R, 即

R= (R11, l1, s11)(R12, l1, s12)(R1k, l1, s1k)(R21, l2, s21)(R22, l2, s22)(R2k, l2, s2k)(Rn1, ln, sn1)(Rn2, ln, sn2)(Rnk, ln, snk)(14)

因为H中每个资源qij都索引了一组相关的资源特征Rij(rij1, rij2, …, rijh), rijh表示索引到的第h个资源, 故多媒体资源分类检索结果可进一步优化, 即

R'= (R11(r111, r112, , r11h), l1, s11)(R12(r121, r122, , r12h), l1, s12)(R1k(r1k1, r1k2, , r1kh), l1, s1k)(R21(r211, r212, , r21h), l2, s21)(R22(r221, r222, , r22h), l2, s22)(R2k(r2k1, r2k2, , r2kh), l2, s2k)(Rn1(rn11, rn12, , rn1h), ln, sn1)(Rn2(rn21, rn22, , rn2h), ln, sn2)(Rnk(rnk1, rnk2, , rnkh), ln, snk)(15)

利用李雅普诺夫定理获取多媒体资源特征, 并通过标注传播算法可以准确地对多媒体资源进行分类, 使得检索运算速度更快, 结果更加准确.

3 实验结果分析

为了验证本文提出的多媒体资源分类检索方法的有效性, 本文进行了实验分析.实验利用多媒体搜集器大范围搜集各种类型的多媒体网页, 对网页中多媒体资源进行下载并对多媒体资源的特征进行提取, 最终下载图像6210幅, 视频4329个, 动画2738个.从下载的多媒体资源中选取500个作为测试样本, 将Upnp分类检索方法、Ajax分类检索方法、数据网格检索方法与本文所提出的改进方法进行了对比分析, 各种分类检索时间对比结果如图1所示.

图1 不同算法的分类检索时间对比Fig.1 Comparison in classification retrieval time needed for different algorithms

由图1可知, 在样本个数相同的情况下, 采用改进算法进行分类检索平均所需时间约为4.5s, 虽然在350~450之间出现了波动, 但是并未增加分类检索时间; 采用Ajax分类检索方法时, 其平均检索时间约为6.34s, 且检索时间随着样本数量的增加而下降; 采用Upnp分类检索方法时, 其平均所需时间约为7.83s, 由于该算法资源利用率较低, 是四种算法中耗时最长的; 采用数据网络方法平均的分类检索时间约为7.14s, 由于算法构建了分层管理结构, 故未出现特别大的波动, 但其检索时间一直处于改进算法之上.

在检索样本数量相同的情况下, 将Upnp分类检索方法、Ajax分类检索方法、数据网格检索方法与改进方法进行图像、视频、动画资源分类检索准确率方面的测试, 对比结果如图2~4所示.

图2 不同算法下分类检索图像资源的准确率Fig.2 Accuracy in classification retrieval of image resource with different algorithms

图3 不同算法下分类检索视频资源的准确率Fig.3 Accuracy in classification retrieval of video resource with different algorithms

图4 不同算法下分类检索动画资源的准确率Fig.4 Accuracy in classification retrieval of animation resource with different algorithms

由图2~4分析可知, 采用改进方法相比其他检索方法分类检索准确率更高, 且图像的检索准确率要稍高于其他两种媒体形式.这主要是因为图像在网页中嵌入的方式较为单一, 建构及形式较为稳定, 且图像一般都有相应的文字描述, 使得图像类的分类检索准确率较高.而视频和动画类多媒体资源具有一定的相似性, 这两类多媒体资源嵌入网页的构造复杂, 且大部分都使用了隐藏代码的技术, 在客户端很难分析并提取相关的资源特征, 导致这两类多媒体资源分类检索效果不如图像类多媒体资源.

4 结 论

针对云计算环境下多媒体资源分类检索一直存在检索不准确的问题, 本文提出一种新的多媒体资源分类检索方法.实验结果表明, 采用改进的方法可以有效增加多媒体资源分类检索的准确度和检索效率, 具有一定的借鉴价值.但是, 改进方法在检索中也存在一定的问题, 例如在图像相似资源较多的冗余环境下, 改进方法的效率会受到一定的影响, 另外, 在多媒体资源的检索过程中, 方法的稳定性不够好, 出现波动, 这都是今后需要进一步解决的问题.

The authors have declared that no competing interests exist.

参考文献
[1] 李成海, 黄必清. 基于属性描述匹配的云制造服务资源搜索方法[J]. 计算机集成制造系统, 2014, 20(6): 1499-1507.
(LI Cheng-hai, HUANG Bi-qing. Cloud manufacturing service resources based on attribute description matching[J]. Computer Integrated Manufacturing Systems, 2014, 20(6): 1499-1507. ) [本文引用:1]
[2] 林丽姝, 吴明珠, 林珍. 基于免疫克隆选择和语义计算的自适应资源检索算法[J]. 电脑与信息技术, 2015, 23(3): 18-20.
(LIN Li-shu, WU Ming-zhu, LIN Zhen. A resource retrieval algorithm with self-adaptive feature based immune clone selection and semantic computing[J]. Computer and Information Technology, 2015, 23(3): 18-20. ) [本文引用:1]
[3] 徐守晶, 韩立新, 曾晓勤. 基于改进型SDA的自然图像分类与检索[J]. 模式识别与人工智能, 2014, 27(8): 750-757.
(XU Shou-jing, HAN Li-xin, ZENG Xiao-qin. Natural images classification and retrieval based on improved SDA[J]. Pattern Recognition and Artificial Intelligence, 2014, 27(8): 750-757. ) [本文引用:1]
[4] 谭伟, 刘璇, 徐钦桂. 服务环境下多粒度制造资源自适应组织与发现[J]. 计算机集成制造系统, 2014, 20(9): 2283-2296.
(TAN Wei, LIU Xuan, XU Qin-gui. Adaptive organization and discovery of multi-granularity manufacturing resource in service environment[J]. Computer Integrated Manufacturing Systems, 2014, 20(9): 2283-2296. ) [本文引用:1]
[5] 沈爱华, 唐启义, 程家安. 基于二叉分类检索表正、反向推理的研究及应用[J]. 浙江大学学报(农业与生命科学版), 2006, 32(5): 541-545.
(SHEN Ai-hua, TANG Qi-yi, CHENG Jia-an. Re-search and application of forward and backward reasoning based on binary taxanomic key[J]. Journal of Zhejiang University (Agriculture & Life Sciences), 2006, 32(5): 541-545. ) [本文引用:1]
[6] 李旭东. 用于网络多媒体资源版权保护的数字水印方法[J]. 情报杂志, 2014(10): 171-174.
(LI Xu-dong. Digital watermarking technology for copyright protection of network multimedia rresources[J]. Journal of Intelligence, 2014(10): 171-174. ) [本文引用:1]
[7] 周燕, 曾凡智, 张志飞, . 面向制造过程的海量数字图像高效检索算法研究[J]. 湘潭大学学报(自然科学版), 2014, 36(3): 105-110.
(ZHOU Yan, ZENG Fan-zhi, ZHANG Zhi-fei, et al. Research for efficient retrieval algorithm oriented to massive digital images in manufacturing process[J]. Journal of Xiangtan University (Natural Science), 2014, 36(3): 105-110. ) [本文引用:1]
[8] 孙元, 陈贺新, 陈绵书, . 多媒体高层语义框架及检索算法[J]. 吉林大学学报(工学版), 2011, 41(1): 244-248.
(SUN Yuan, CHEN He-xin, CHEN Mian-shu, et al. Multimedia high-level semantic framework and retrieval algorithm[J]. Journal of Jilin University(Engineering and Technology Edition), 2011, 41(1): 244-248. ) [本文引用:1]
[9] 宋宇, 孟祥增. 基于改进Fish-search算法的多媒体检索[J]. 计算机工程, 2008, 34(11): 189-191.
(SONG Yu, MENG Xiang-zeng. Multimedia retrieval based on improved Fish-search algorithm[J]. Computer Engineering, 2008, 34(11): 189-191. ) [本文引用:1]
[10] 张宇, 袁野, 王国仁. 一个基于概率潜语义分析的多模态多媒体检索模型[J]. 小型微型计算机系统, 2015, 36(8): 1665-1670.
(ZHANG Yu, YUAN Ye, WANG Guo-ren. Multimodal multimedia retrieval model based on probabilistic latent semantic analysis[J]. Journal of Chinese Computer Systems, 2015, 36(8): 1665-1670. ) [本文引用:1]