摘 要

随着互联网技术的迅速发展，各行各业积累的图像数据都呈现出爆炸式增长趋势。虽然急剧增长的图像数据在人们的日常生活中起着越来越重要的作用，但是在浩如烟海的图像数据中高效、快速地查找感兴趣的图像却变得越发困难。因此如何在海量多媒体图像数据库中快速、准确地检索到用户需求的图像己成为一个非常有意义且具有挑战性的研究课题。

本文针对大规模图像数据索引技术存在的问题，先研究了监督式SCM哈希方法，包括正交学习语义最大化SCM_Orth哈希和顺序学习语义最大化SCM_Seq哈希，并将这两种哈希方法与典型相关分析CCA方法进行比较。监督式SCM哈希方法充分利用了数据语义标签信息，通过语义标签向量之间的余弦相似来定义两个实体图像之间的相似性，从而建立优化模型，优化目标为最小化平方误差。本文主要目标就是通过语义标签数据学习到投影矩阵，进而学习到哈希码。

监督式SCM哈希方法法需要大量的标签数据，而获取大量标签数据费时费力，不切实际。因此，对监督式SCM方法进行改进，提出半监督SCM哈希学习方法，并将半监督学习方法引入到随机森林算法中，利用少量标签数据训练分类器，再用分类器对未标签数据进行分类预测，最后再用监督学习SCM哈希方法进行图像检索。

在数据集wiki上分别进行监督学习、半监督学习实验，监督学习实验结果表明：在准确性和训练时间方面，两种SCM哈希方法均优于CCA方法，由于存在量化误差，导致SCM_orth哈希方法准确度远远低于SCM_seq哈希方法。半监督实验结果：两种半监督SCM哈希学习方法准确度均优于半监督典型相关分析CCA方法，半监督SCM_orth哈希方法准确度高于半监督SCM_seq哈希方法，且两种半监督SCM哈希方法准确度都远远高于监督SCM哈希方法。综上所述，半监督顺序学习语义最大化SCM_Seq哈希方法在海量图像数据快速索引方面最优，且更适用于实际应用中标签数据较少的情况。

关键字: 哈希函数 随机森林 余弦相似 语义相关最大化 平均准确率

Abstract

With the rapid development of Internet technology, the image data from all walks of life are showing explosive growth trend. Although the rapid growth of the image data in the people's daily life plays a more and more important role, but in the vast image data, fast search images are of interest has become more difficult. Therefore, how to quickly and accurately retrieve the image of user needs in the mass multimedia image database has become a very meaningful and challenging research topic.

The in view of the problems existing in the large-scale image data indexing technology, first of supervised SCM hash method, including orthogonal learning semantic maximizing SCM_Orth hash and order learning semantic maximizing SCM_Seq hash, and comparing the two hash method with canonical correlation analysis CCA. Supervised SCM hash method makes full use of the data label semantic information, through between the semantic label vector cosine similar to define the similarity between two entities image, so as to establish the optimization model, optimization objective is to minimize the square error. The main goal of this paper is to learn the projection matrix through semantic label data, and then learn the hash code.

Supervised SCM hash method requires a large number of tag data, and access to a large number of labeled data is time-consuming and laborious. Therefore, the supervised SCM method was improved, SCM hash, a semi supervised learning method, and semi supervised learning method is introduced to the random forest algorithm, using a small amount of labeled data to train the classifier, and then the classifier on the unlabeled data classification and prediction, then supervised learning SCM hashing method for image retrieval is proposed.

The data set on the wiki were supervised learning, semi supervised learning experiments, supervised learning experiments results show that: in terms of accuracy and training time, two SCM hash method were better than that of CCA method, due to the presence of quantization error, resulting in SCM_Orth hash method accuracy is much lower than that of the SCM_Seq hash method. Semi supervised experimental results: two semi supervised SCM hash learning method accuracy were better than semi supervised canonical correlation analysis CCA, semi supervised SCM_Orth hash method accuracy is higher than that of the semi supervised SCM_Seq hash method, and two kinds of semi supervised SCM hash method accuracy is much higher than SCM hash methods for supervision. To sum up, the semi supervised sequential learning algorithm for maximizing the SCM_Seq hash algorithm is optimal in the fast indexing of massive image data, and is more suitable for practical applications.

Key words: hash function; random forest;cosine similarity; semantic correlation maximization; average accuracy

目录

摘要 I

Abstract II

第一章 绪论 2

1.1研究背景和意义 2

1.1.1研究背景 2

1.1.2研究意义 2

1.2研究现状 2

1.2.1 基于哈希的检索方法 2

1.2.2半监督学习 3

1.3 监督多模式哈希 4

1.4 研究内容 5

第二章 语义相关最大化SCM哈希 7

2.1 符号说明与问题定义 7

2.1.1符号说明 7

2.1.2问题定义 7

2.2模型建立 8

2.3正交学习SCM 9

2.4顺序学习SCM 10

2.4.1 SCM顺序学习算法 11

2.5实验 12

2.5.1数据集 12

2.5.2平均准确率的均值MAP 12

2.5.3评估方案 12

第三章 半监督随机森林算法 19

3.1半监督SCM哈希学习 19

3.2半监督哈希过程 19

3.2.1半监督哈希算法 20

3.3随机森林 21

3.3.1随机森林提出背景 21

3.3.2决策树 21

3.3.3随机森林的构建 22

3.3实验 23

第四章 结论 25

参考文献 26

致 谢 28

第一章 绪论

1.1研究背景和意义

1.1.1研究背景

随着互联网、云计算、物联网、社交网络等技术的兴起和普及，全球数据的增长快于任何一个时期，可以称作是爆炸性增长，而数据的存储单位也不断扩大。例如, 据新浪微博官方统计报告，2013年新浪微博用户已经超过4.8亿，平均每天产生的微博数量已经达到800GB。据统计2014年腾讯QQ用户数量已经超过8.3亿，平均每天处理的数据量已经达到300TB，远远超过其它社交软件，毫无疑问腾讯QQ已经成为最受欢迎、最广泛的社交媒体之一。阿里巴巴作为全球最大的网络交易集团之一，2014年每天处理的数据量已经超过120PB^[1]。国家统计局有关数据研究表明，过去三年人类的信息数据总量比以往4万年的数据量还要多^[2]。因此可以说，我们已经进入大数据时代，大数据在各行各业都有广泛的应用价值，对大数据进行挖掘分析也已经成为学术界和工业界高度关注热点之一。但是用常规的软件工具挖掘大数据隐藏的信息需要耗费大量的时间，不太现实，而数据规模越大，对其挖掘可能得到的价值更大，因此学习大数据显得尤为重要。而要有效挖掘大数据隐藏的信息, 大数据机器学习技术必不可少^[3]。

1.1.2研究意义

随着社会的不断发展，大数据在人们生活中扮演着越来越重要的角色，数据规模越大，对其进行数据挖掘获得的价值往往越大。用传统的数据挖掘方法来大规模数据进行分析挖掘行不通，因此，为了有效地挖掘海量数据隐藏的信息，我们必须学习大数据机器学习技术。机器学习技术的快速崛起使得文本、语音、图像、视频中抽象概念的特征提取获得了前所未有的发展。然而,这类数据特征往往具有数据量大、高维、稠密等特性,使得传统的图像检索技术难以对其进行高效索引。而基于哈希学习检索技术对维度不敏感,能够较好地索引此类特征。另一方面,哈希学习技术在计算机视觉、数据挖掘、信息检索、模式识别等领域的诸多应用中都起到了核心作用。在人脸识别技术^[4]中,人们对输入图片中的人脸进行定位、校正,并抽取特征,然后使用哈希学习技术来识别输入图片中的人脸，这在警察搜索犯罪份子、寻找丢失儿童过程中取着决定性作用。信息检索领域最为核心的技术之一也是哈希学习检索技术。可见,这些例子都充分反映了哈希检索技术的重要性,尤其是目前针对海量、高维、稠密数据，哈希学习检索技术必将成为大数据时代的核心、技术之一。

1.2研究现状

数据的海量性将造成存储开销大、检索速度慢等一系列问题，而数据的高维性将造成维度灾难问题，这使得很多传统机器学习算法失效。例如，对于用户给点的任意一幅图像，如何在海量图像数据库中高效、快速、准确地搜索到与给定图像相似的图像。针对这个问题，目前国内外很多学者进行了相关研究，大部分研究者的思路是对图像数据库所有图像提取特征，然后定义特征相似性度量并对相似度进行排序，最后对数据库进行线性搜索，从而得到搜索结果。然而，这样的思路存在两个重要的问题：①图像特征向量数据往往维度较高，而存储高维数据需要大量的内存空间；②对大规模图像数据进行线性搜索时间复杂度较高，需要很长时间。因此，如何对浩如烟海图像数据库进行高效索引成为一个亟需解决的问题。最近几年有很多研究者在这方面进行了相关研究，但研究才刚刚开始, 问题本质和模型建立有待于进一步深入思考。

目前，针对海量多媒体数据的检索主要有两个方法：基于树状结构的检索方法与基于哈希的检索方法。但树状结构的检索方法有其明显的缺点，当数据维度较大时，如大于20，其查询时间大大增加且查询效率低。而基于哈希的图像检索方法对数据维度不敏感，可以有效地解决维度问题，因此本文使用哈希图像检索方法。

1.2.1 基于哈希的检索方法

哈希算法是最近几年被提出来用以解决大规模数据检索问题的方法，其基本思想^[10]是通过哈希函数将原始数据映射到汉明空间，在汉明空间进行检索，即用一系列的二进制编码代替原始数据。其最主要的性质是保持相似性,即在原始特征空间中相近的两个原始数据在映射到汉明空间后汉明距离也比较近,反之，原始特征空间中不相近的两个特征在映射到汉明空间后汉明距离较远。图 1.1 是基于哈希的图像检索的流程图，第一步，对图像数据库所有图像提取特征，得到高维向量，选取最佳哈希函数系列将高维向量映射成二进制哈希码，即将原始图像数据库映射成二进制码库；第二步，通过选择的一系列哈希函数将待查询图像映射成二进制码。第三步，比较待查询图像的二进制码与图像数据库每一幅图像二进制的汉明距离，并将这些汉明距离排序，选择距离最小的图像作为待查询图像的查询结果。