数字电影发行相似案例快速检索方法

数字电影发行相似案例快速检索方法 6382011,Vo1.32,No.2计算机工程与设计 ComputerEngineeringandDesign 数字电影发行相似案例快速检索方法 ,刘翼光 宋双,吴宏涛,高强 (1.北京航空航天大学电子信息工程学院,北京100191;2.国家广电总局电影数字节目管理中心,北京100088) 摘要:为解决传统相似案例检索方法在数字电影大型案例库中检索效率-fAT的问题,针对数字电影大型案例库进行了研 究分析,从提高案例检索速度和参考价值的角度出发,提出了一种聚类,优选和匹配相结合的相似案例检索方法.通过聚类 缩小案例的检索范围,通过优选在相应的检索范围内形成参考价值较高的候选案例集,通过匹配算法在候选案例集中寻找 最相似案例,并通过数字电影发行实施实例表明了其可行性.实验结果表明,该方法提高了案例的检索速度和参考价值 关键词:案例检索;聚类;神经网络;匹配;数字电影 中图法分类号:TP18文献标识码:A文章编号:1000—7024(2Ol1)02—0638—04 Fastsimilarcaseretrievalmethodfordigitalfilmdistribution SONGShuang,WUHong—tao.,GAOQiang,LIUYi—guang (1.ElectronicsandInformationEngineering,BeijingUniversityofAeronauticsandAstronautics,Beijing100191,China; 2.AdministrationCentreofDigitalFilmContent,StateofAdministrationofRadioFilmandTelevision,Beijing100088,China) Abstract:Thetraditionalcaseretrievalmethodinefficienttosearchacaseinthelargedigitalfilmcasedatabase,toimprovecaseretrieval speedandthereferencevalue,athree—stepcaseretrievalmethodisproposedf orthelargedigitalfilmcasedatabase.Thismethodincludes clustering,optimizationandmatching.Throughtheclusteringalgorithmtonarrowthescopeofcaseretrieval,andbyoptimizingto formcandidateofcaseswithhigherreferencevalue,finallyinthecandidatebymatchingalgorithmfocusonfindingthemostsimilar case.Theimplementationofdigitalfilmdistributiondemonstratesitsfeasibility.Experimentsshowthatthismethodimprovesthecase retrievalspeedandreferencevalue. Keywords:casesearch;clustering;neuralnetwork;matching;digitalfilm 0引言 针对数字电影发行数据成指数逐年增长的情况,国家电 影数字节目管理中心已建立了数字电影发行的案例库,用于 指导数字电影的制作,订购和发行管理.对于新发行的数字 电影,若能从案例库中找到具有相似属性的成功案例指导发 行,则能大量节约影片发行成本. 传统的基于比较模型的相似案例检索方法,算法简单,但 需要与案例库中的所有案例依次比较,随案例库中案例数的 增大,其检索时间也越来越长.在大型案例检索库中,要提高 检索速度,最常见的方法就是缩小检索范围.文献[1】提出了 一 种基于ART-2神经网络的案例检索方法,为大型案例库建 立了案例分类及检索模型,但其需要根据先验知识预先建立 分类的子案例库.但数字电影发行中缺乏对案例进行分类的 先验知识,若通过案例的某一个或几个属性对其进行硬性划 分,主观影响较大,不一定符合数据的潜在特征.文献[2]提出 了一种基于网格聚类的相似案例检索策略,通过建立案例库 样本 保单样本pdf木马病毒样本下载上虞风机样本下载直线导轨样本下载电脑病毒样本下载 集合,将案例库的维护转换成对规模较小的样本集合的 维护,当样本集合密度大于阈值时,就不能添加新的案例.其 忽略了案例本身的参考价值,即在样本集合中检索出来的案 例未必都有较高的参考价值. 本文综合考虑了相似案例的检索速度和参考价值,引入 了聚类算法和人工神经网络算法,针对数字电影大型案例库, 提出一种聚类,优选和匹配相结合的相似案例检索方法.该 方法通过聚类算法缩小了检索范围,提高了案例检索的速度, 同时由于在相应的检索范围内神经网络优选出的候选案例均 为成功案例,故通过匹配算法从候选案例集中检索出的相似 案例的参考价值也较高,能够满足数字电影发行大型案例库 的案例检索性能要求. 1相似案例检索方法 聚类,优选和匹配相结合的检索方法是基于案例的属性 实施的.数字电影发行案例的属性主要包括两部分:特征属 性和发行属性.特征属性是案例本身的属性,发行属性是案 收稿日期:2010—02.22;修订日期:2010—04—29. 作者简介:宋双(1986--),女,江苏盱眙人,硕士,研究方向为数据挖掘,信息与通信系统;吴宏涛(1981一),男,江西人,硕士,工程师, 研究方向为信息与通信系统;高强(1971一),男,四川人,博士,副教授,研究方向为信息与通信系统;刘翼光(1974--),男,江西人,博 士,高级工程师,研究方向为图像处理,信息安全.E—mail:songsh_zone@yahoo.tom.cn 宋双,吴宏涛,高强,等:数字电影发行相似案例快速检索方法2011,Vo1.32,No.2639 例发行结束后才有的属性.在聚类,优选和匹配相结合的检 索方法中:聚类是在案例发行前对案例进行分类,故聚类考查 案例的特征属性;优选是在发行结束后对案例发行的成功与 否进行评判,既需要考查案例的特征属性也需考查案例的发 行属性;匹配是新案例与历史案例间的比较,由于新案例无发 行属性,故主要考查案例的特征属性.属性的内容描述如表 1所示. 表1数字电影案例属性内容 属性种类属性内容应用范围 影片类型,公益性,语言类型,主演等级,聚类,优选, 特征属性导演等级 , 发行年份匹配 发行属性总收益,发行成本比例,发行规模优选 聚类,优选和匹le,l结合的相似案例检索方法具体描 述如下. 1.1聚类 聚类算法通过案例间的距离对所有案例进行分类,而案 例间的距离由案例中各属性变量间的距离决定.数字电影案 例f可表示为X=,…,…),表示案例i中第k个属性变量, p为案例中属性变量的个数.案例{与案Nj间距离的计算公式 定义如下 式中:——案例f与案例在第七个属性变量上的距离.根据 属性变量类型的不同,属性变量间距离的计算方法也不同. 1.1.1属性变量间距离定义 数字电影案例的特征属性变量可分为3种类型:间隔尺 度变量,有序尺度变量和名义尺度变量,具体内容如表2所示. 表2数字电影案例特征属性内容 特征属性变量类型取值编码 f故事片,科教片,动画片,记录片,其影片类型名义尺度变量 它}:{1,2,3,4,5} 公益性名义尺度变量{公益片,商业片)={l,2) {汉语,藏语,维语,哈语,蒙语,粤语,语言类型名义尺度变量 其它)={1,2,3,4,5,6,7) 主演等级有序尺度变量{高,中,低}={1,2,3) 导演等级有序尺度变量{高,中,低)={1,2,3) 发行年份间隔尺度变量[1999.2009] 传统的聚类算法只适合处理间隔尺度变量,为计算案例 间距离和案例到类的距离我们定义了上述3种类型的属性变 量间的距离. (1)计算案例间距离时,根据变量类型的不同,的计算方 法定义如下: 对于问隔尺度变量,=f一f,其中,为第k个变量的 幅值,即见=max(x~=),min),其中m=1,2,…,,为案例总数. 对于有序尺度变量,假设相邻有序尺度变量间的间距相 等,则相邻间隔为l/一】),其中g为有序尺度变量的取值个数, 则有序尺度变量间的距离为::I一l×了. 对于名义尺度变量,=,对I={薹薹.若案例f和案例 ,若在变量上的取值相等则距离为0,若取值不等则距离为1. r——一 (2)计算案例到类的距离时,D/?()表示案例内类 V=1 ,的距离,表示案例和在第个属性变量上的距离.根据 变量类型的不同,D的计算方法定义如下: 对于间隔尺度变量,:l一mean(C~)l/R,其中mean(C~) 表示类,中第k个变量的均值. ?l一1. 对于有序尺度变量,=兰_『,其中吩为类,中的 案例个数,Xs为类,中的案例,即等于案例i与的平均等级 差乘以相邻等级间距. 对于名义尺度变量,:?(蔓塑,其中,??柏, ?【1,瑚表示中在第k个变量上取值不等于的案例个数. 1.1.2聚类算法描述 由上述属性变量间距离的定义,可计算出案例间距离和 案例到类的距离.根据这两距离,按下述方法对所有的案例 进行分类: (】)分别计算两两案例的距离,并以每个案例作为球心,以 距离d为半径做球形,落在球内的案例数称为该点的密度,选 择密度大于的案例,并按密度大小排序: (2)选密度最大案例作为第一个代表点,即第一个聚类中心; (3)再考虑第二大密度点,若第二大密度点距第一代表点 的距离大于d~(dl=2d)则把第二大密度点作为第二代表点,否 则不能作为代表点,这样按密度大小考察下去,所选代表点间 的距离都大于dl; (4)代表点选择完毕后,在剩余案例中,根据第一个案例到 各代表点的距离,把其归于距离最近的那个代表点内,这样就 形成了新的分类; (5)再计算第二个案例到新的分类的距离,以及到其它代 表点的距离,将其归于距离最小的分类中或代表点内; (6)重复第(5)步计算,直到所有案例都分配完毕. 1.2优选 经过聚类,历史案例被分成了若干类,但每个类别中的案 例对新案例的参考价值不同,部分不成功案例的参考价值较 小,故需找出一种方法以正确评估各案例的成功系数.案例 的成功系数由案例的特征属性和发行属性共同决定,这些属 性的影响是非线性的.BP神经网络理论上能逼近任何的非 线性函数,同时还有较强的泛化能力和容错能力,故我们利 用BP神经网络来逼近一个非线性函数,以评判每个案例的成 功系数,实现数字电影发行案例的优选. 1’2.1神经网络的构建 一 个BP神经网络由一个输入层,多个隐含层和多个输出 层组成.研究表明,一个三层人工神经网络模型就可解决一 般非线性函数的拟合,逼近问题,故本文采用三层BP神经网 络结构. 神经网络的输入是数字电影发行案例的特征属性和发行 属性,根据表1可知,输入节点个数是9;隐含层的节点个数为 6(经验值,约为输入节点个数的3/4);输出节点个数为1,输出 案例的成功系数y?[O,1].隐含层的激活函数采用S型双曲 宋双,吴宏涛,高强,等:数字电影发行相似案例快速检索方法2011,Vo1.32,No.2641 故选案例1和案例2分别为代表点. 3)分别对剩余的案例3,案例4和案例5进行分类.?对 案例3归类:根据矩阵,案例3到案例1的距离=O.866小于 案例3到案例2的距离:=1.631.故案例3和案例1形成类 1.?对案例4进行归类:根据矩阵,案例4到案例2的距离 :1.871.再计算案例4到类1的距离:/9,=1.43l<d4.所以 案例4归到类1中,即类1={案例1,案例3,案例4}.?对案 例5归类:根据矩阵,案例5到案例2的距离z=1.000.同上, 计算案例5到类1的距离,可得Ds.=1.773>~:,所以案例5与 案例2归于一类,形成类2. 至此,所有的案例归类完毕,5个历史案例共分成了两类: 类1={案例1,案例3,案例4};类2={案例2,案例5}. (2)优选每个分类的候选案例集 通过上文中训练好的BP神经网络选出每个分类的候选 案例集.设定闽值=0.5,历史案例的成功系数如表5所示. 表5历史案例优选结果 分类案例神经网络输出是否归入成功案例集 案例1o.967711 类l案例30.0273lO 案例40.820781 案例2O.O1252O类 2 案例50.87739l 最终得到类1和类2的候选案例集分别是{案例l,案例 4}和{案例5}. (3)新案例的匹配 可计算出,案例6到类1的距离D,=0.779,到类2的距离 z=1.913.由于/)6<062,故案例6归于类1.类1的候选案例 集为{案例1,案例4}.采用最近相邻法分别计算案例6与案 例1和案例4的相似度,并选择相似度最大的案例作为参考 案例.由公式(2)可得:&-=5,&=3.1.由于&.>,所以案例 l可做案例6的参考案例. 从直观上看,案例6与案例1只有一个属性不同,由于本 文中各属性的权重是一样的,故案例1作为新案例6的参考 案例是符合实际认知的. 3性能分析 传统基于比较模型的最近相邻检索法,需要与所有历史 案例比较,从而选出相似度最大的案例.本文提出的聚类,优 选和匹配相结合的检索方法与最近相邻检索法相比,有以下 两点优势: (1)提高了检索的速度:假设所有历史案例聚成了Q类,每 个类中有m,(f=1,2,…,Q)个案例,使用传统的检索模型,需要计 旦 算约欣.而本文提出的聚类,优选和匹配相结合的检索 =1 方法,在假设每个类别中成功案例约占50%的情况下,只需计 算,1,2,…,Q次.最近相邻检索法与聚类,优选和匹配 相结合的检索方法在Matlab仿真环境下检索不同数量级案例 时所消耗的时间如图2所示. 墅 蕾 耀 霆 案例数 —一 最近相邻检索法;—一聚类,优选和匹配相结合检索方法 图2案例检索方法消耗时间对比 (2)综合考虑案例的参考价值与相似度:传统检索方法, 将新案例与所有的历史案例进行比较,从而检索出相似度最 大的案例,但实际上,相似度最大的案例不一定有参考价值. 例如,文中的实施实例中,新案例6与案例3的相似度最大, 但案例3是非成功案例,参考价值很小.而聚类,优选和匹配 相结合的检索方法,检索出来的案例的参考价值较高. 4结束语 数字电影发行相似案例检索能够利用过去的经验来处理 现在的问题,减少了重复劳动,节约了发行成本.本文针对数 字电影大型案例库,采用了聚类,优选和匹配相结合的相似案 例检索方法,提高了案例的检索速度和参考价值,解决了传统 相似案例检索方法在处理数字电影大型案例库时效率低下的 问题,在数字电影发行相似案例的检索中得到了良好的应用. 参考文献: [1]孟妍妮.一种基于ART-2神经网络的案例检索方法【J].情报学 报,2006,25(4):428—432. [2】贾世杰.基于网格聚类的案例检索策略[J].计算机工程,2009,35 (1O):170.172. [3】王建军.多元多项式函数的三层前向神经网络逼近方法[J].计 算机,2009,32(12):2482.2488. [4]何同祥等.带动量批处理梯度下降法对模型的动态辨识[J].计 算机仿真,2006,23(7):76.83. 【5】NiloofarArshadiIgorJurisica.Dataminingforcase—basedreaso— ninginhigh—dimensionalbiologicaldomains[J].IEEETransac. tionsonKnowledgeandDataEngineering,2005,17(8):1127— 1l37. 【6】MaciejAMazurowski.Trainingneuralnetworkclassifiersfor medicaldecisionmaking[J].NeuralNetworks,2008,21:427.436. [7】BouguessaM,WangS,SunH.Anobjectiveapproachtocluster validation[J].ProceedingsoftheNationalAcademyofSciences oftheUnitedStatesofAmerica,2007,104(36):14312.14317. [8]高慧颖,颜志军.基于CBR的信息系统案例检索多Agent模型 研究【J]_计算机工程与设计,2008,29(5):1226.1228.