【作者】 崔昊旻；

【导师】 朱明；

【作者基本信息】 中国科学技术大学 ， 模式识别与智能系统， 2014， 博士

【摘要】 随着计算机网络和数字多媒体技术的发展,互联网应用日益普及,网络多媒体数据量急剧膨胀使得人们难以获取有用的信息和服务。面对海量媒体数据,如何有效的处理、检索和推荐,逐渐成为多媒体视频应用和信息管理系统领域中亟待解决的问题。本文研究问题集中于以下三个方面：1)多媒体检索的研究逐渐从关键词检索方式转向对象检索方式,即以视频片段为输入,从海量视频库从找出相似视频。以视觉单词为基础的常规检索方法,忽视视频帧时间序列上的关联,在检索效果上仍有提升空间。如何考虑视频帧序列关系,并保持可接受的检索速度,值得进一步研究。2)基于协同过滤的方法是推荐系统领域的一类热门方法,广泛用于在线电子商务中。然而,传统协同过滤方法面临多种问题。近年的研究表明,对象选择存在“长尾效应”,大量对象因缺少用户关联信息而被传统协同过滤推荐算法所忽视。同样是缺少足够的用户-对象关联信息,对象“冷启动”问题也一直成为协同过滤推荐系统研究难点。如何利用对象自身特点找出相似关联性,克服协同推荐中关联信息缺失问题,值得进一步研究。3)实际应用场景下,单纯基于显式反馈(如评分等直接评价信息)的推荐算法,需要用户主动配合反馈信息采集,一定程度上影响用户体验,致使该类推荐系统常面临反馈信息不足问题。而大量隐式反馈信息,如浏览网页的时间,观看视频多久后切换,以及对象选择的先后顺序等,在不影响用户正常浏览的同时,也为推荐系统提供丰富的信息。如何有效利用用户隐式反馈信息,弥补显式反馈信息的不足,值得进一步研究。针对上述三个问题,本文的主要工作和创新包括以下三点：1)支持复制检测的相似视频检索性能优化方法研究：为了提高相似视频检索的性能,本文提出一种支持复制检测的相似视频检索方法。该方法首先对视频片段进行系统采样,提取视频帧的全局特征向量,并对特征向量哈希得到特征点,将视频表示为特征点的时序序列。检索过程将特征点视为视觉单词,利用倒排索引,快速计算两个视频的相同特征点种类和离散度,对无关候选对象进行过滤。序列距离采用基于Jaccard距离的动态时间规整(Dynamic Time Waring, DTW)度量方法,利用距离下界的快速估计,对相似序列搜索过程进行优化。实验表明,采用多级评价准则的检索方法在同样检索效果下,所耗时间仅为原DTW算法的1/3。与MUSCLE VCD2007数据集公开实验结果对比,本方法的检索得分/时间比值高于其他算法结果。2)基于语义本体表示的视频推荐方法研究：针对推荐系统中的对象信息稀疏问题,本文提出一种语义本体表示的视频推荐方法,用于对用户评分矩阵中缺失的评分信息进行预估,提升对长尾对象和冷启动对象的推荐效果。以电影数据为例,该方法首先根据电影本体属性间的相似度,确定相似电影的候选集。利用用户对候选集电影的评分,预测该用户对电影的评分值,并对评分矩阵进行填充。最后采用PureSVD算法对填充后的矩阵进行分析,将Top-N电影推荐结果返回用户。实验采用Hetrec’11电影评分数据集测试,并用推荐结果的Top-N召回率进行评估。结果表明,相比于目前多种的推荐算法(TopPop,近邻推荐,PureSVD),本文方法对于一般对象的推荐召回率提升240%～30%,对于长尾对象的推荐召回率提升2-5倍,并能有效处理对象冷启动问题。3)结合隐式反馈的对象推荐方法研究：针对实际应用场景下显式反馈信息不足问题,本文提出了一种结合隐式反馈的对象推荐方法。该方法将用户的隐式反馈信息转化为0-1用户-对象评分矩阵,并放入有向关联图结构中。采用时间窗口技术,对图中隐式反馈的影响范围进行限定。利用HITS算法迭代计算出关联图中对象的auth权重和hub权重,作为对象的隐式反馈推荐评判依据,并与显式反馈推荐值融合,获得最终推荐列表。基于MovieLens公开数据集的实验结果表明,隐式反馈信息可以作为显式反馈的有效补充,相比PureSVD协同推荐算法和ItemRank等基于显式反馈的图类推荐算法,本文方法获得的推荐列表序列正确度得到进一步提升,平均序列正确度达到90%以上。本文研究是国家科技支撑计划课题“增强型搜索系统架构、关键技术及测试规范的研究”(2011BAH11B01)以及国家科技支撑计划课题“电视商务综合体新业态应用示范”(2012BAH73F02)的一部分。更多还原

【Abstract】 With the improvement of network and digital multimedia technology, it makes people increasingly difficult to get useful information from the explosive growth of digital products and obtain services from the rapid development of Internet application. Therefore, how to effectively discover, retrieve and process with massive data becomes a problem worthy of study.This dissertation focuses on the researches in the following three issues:1) The multimedia retrieval methods are shifted from key-words based ones to example-based ones. The video clip is employed as an input for finding similar video clips in huge datasets. Based on bag of video words, the traditional retrieval method for video ignored ordinal association among video frames. There’s still room for enhancing the system performance. How to measure the similarity of the time series for video frames and maintain acceptable retrieval speed is worthy of future study.2) Collaborative filtering is widely used in the online e-commerce and proved to be one of popular methods in the recommender system. However, the effect of collaborative filtering is limited by several problems. Due to the lack of user selection information, recent researches show that items in the long tail turn to be ignored by traditional collaborative filtering algorithm. By the same token, the cold-start of the recommender system also becomes a difficult problem for collaborative filtering method. It is particularly important to find similarity which is based on the inherent relationship between items, to overcome problems with missing information.3) In some actual scenes, the recommended algorithm may be based on explicit feedback(rating scores etc.). However, the rating collection process needs some help from the user to collect information. This will impact the user’s experience, and lead to insufficient information problem in recommender system. Implicit feedback such as the time spent on website, how soon the user skipped the song, and the ordinal association of selected items have proved to be useful in recommender systems. How to make use of implicit information to revise the result of the recommendation is worthy of further investigation.For these problems, the main research work and innovations in this dissertation are concentrated on three main parts:1. To improve the search efficiency for large-scale video database, we describe an approach to video retrieval for copy detection. Firstly, an ordered list of global frame features with systematic sampling is extracted from the video clip. The global features then are hashed into time series, which is represented for the video clip. In the retrieval process, the elements of time series are used as video words. The category and dispersion rate of common feature can be calculated by inverted index, which is used to filter unrelated candidates. The distance of time series can be calculated by dynamic time warping with Jaccard distance. Cheap-to-compute low bound is also used to prune off unpromising candidates in the DTW computing processes. The experimental results indicate that the proposed approach achieves the same performance with1/3time consumption compared with original DTW algorithm, and a better ratio of score and time compared with the result of other methods in MUSCLE VCD2007dataset.2. To solve the data sparsity problem in recommender system, we introduce an approach using ontology-based similarity to estimate missing values in the user rating matrix, and improve the effect of recommendation for items in the long tail and the cold start problem. With movie domain, for example, the method find similar candidates by the similarity of features in movie ontology. The missing rating score is predicted by the rating score for ontology similar candidates set. With the filling rating matrix, the PureSVD method could get better performance in recall metric. Experiments using Hetrec’11dataset were carried out to evaluate the proposed methods with Top-N recall metrics. Compared with state-of-the-art approaches(TopPop, Neighborhood recommendation and PureSVD), the proposed method achieves24%～30%better recall rate for average, and2to5times better recall rate when applied to the long-tail situation. It could also well deal with the new item cold start problem.3. To solve the problem of insufficient information based on explicit feedback, we proposed a recommendation algorithm considering implicit feedback to produce a better recommended list. The implicit feedback of users is used as a0-1user-item rating matrix and put into the directed correlation graph. Time window is also used to limit the impact range of implicit feedback in graph. The authority and hub values can be calculated by HITS iteration algorithm, which are used as results for recommendation from implicit feedback. The final recommended list is the result of both explicit feedback and implicit feedback. Experimental results on MovieLens datasets show that the implicit feedback can effectively compensate for the shortcomings of explicit feedback. In the proposed algorithm, the macro-average degree of agreement (DoA) could achieve90%, which is more accurate than the PureSVD and ItemRank based on explicit feedback.Part of research results mentioned above has been applied into projects as follows:the National Key Technologies R&D Program of China "The Architecture, Key Technologies and Test Specifications of Enhanced Search System"(No.2011BAH11B01), the Key Programs of the Chinese Academy of Sciences "A New TV Commerce Complex Format Application Demonstration"(2012BAH73F02).更多还原