Android平台上个性化推荐引擎开发设计

摘要

　　移动互联网的泛起和普及将我们带入一个数据爆炸的年代，海量数据资源在满足用户的同时，也带来了数据资源超载的问题，即随着网络上数据资源的大幅增长，人们在如此大的资源中查找自己需要的资源变的如大海捞针般困难。目前，针对该问题最有效的解决方法是采用以推荐引擎为代表的信息推送系统，它是根据监听记录用户的行为数据，分析归纳使用者的上网习惯、浏览记录等，匹配出使用者或许想知道的信息、想购买的产品并推荐给使用者。现阶段大多数商用的推荐引擎都是 web 服务器上进行使用者行为数据收集和建模。这不仅占用了 Web 服务器的系统资源，加重了成本开销，使用户行为数据的采集受到限制，还可能会导致用户信息的泄露。基于上述的时代背景，文本对 android 平台上的个性化推荐引擎主要做了一下研究工作：

　　首先，对安卓系统的平台架构和基本组件进行了研究。提出采用 ContentProvider 机制与 SQLite 数据库结合的方式实现对用户手机上的短信息内容和下载到手机本地的英文文本内容的提取。

　　其次，对字符文本存储的 trie（字典树）算法进行研究和改进。研究发现该树结构除根节点外的每个节点都只包含一个字符。本文提出了一种改进办法，在所有有词尾标识的节点上同时存储字符串的末尾字符和整个字符串。这样可以大大节省分析模块对存储数据的检索时间。

　　再次，对应用在分析模块中的字符串匹配相关的 kmp 算法进行研究，并改进优化了 AC 算法。研究发现 AC 算法是 kmp 算法在复杂模式下的扩展，是在 trie 树的基础上为失配节点设计跳转表来减少比较次数，节省匹配时间。由于本设计是基于英文文本的分析，本文为 AC 算法增加了分隔符匹配的功能，来实现单词分割，优化后的算法保障了分析模块结果的准确性。

　　最后，根据以上算法来挖掘描述用户喜好和需求的关键字，完成了分析匹配模块和广告推送模块的设计和实现，并对整个推荐系统进行测试和验证。

　　关键词:个性化推荐，本地资源，AC 算法，Trie 结构，安卓手机

Abstract

　　The emergence and popularity of mobile Internet is thrown us into an era of data explosion. Massive data resources are meet the user's need, at the same timebrings the problem of data resources overload. With the substantial growth of the data on the network, people want to find what they are need as difficult as looking for a needle in a bottle of hay. Thus,the efficiency of the using information has been reduced.At present, one of the solutions for the problem of data resource surplusis the information push system, which is a represented of the recommendation engine. The information push system can matchthe products which users may want to buy and recommend it to the user. Compared with the search system, the recommendation system is generally running in the background to monitoring and recording user’s behavior data, it analysis those data and sum up the rules, so as to solve the problem of search engine which cannot be deep understanding of user personalization information, potential users information, vertical one-way transmission of information.

　　At the present stage, most of the commercial recommendation engine architecture is based on the server.In principle, this type of recommendation engine is a web server for user behavior data collection and modeling. It is not only takes up resources of the web server system which adding the cost of overhead and limitedthe behavior data collection, but also may lead to leakage of user information which brings potential hazards to the user's privacy.

　　This paper is based on the above background to developing a personalized recommendation engine that was applied on the android platform.The AC algorithm and Trie tree data structure are used to optimize this recommendation engine.Mining the key words to describe user's preferences and needs by analyze the short message content on the user's mobile phone and the contents of the English text downloaded to the phone. It is match the mining information and the ad content in the memory to recommend the information to the user which they are interested in or need. In addition, the combination of the personalized recommendation engine and android system are also provides a great space for future business promotion.

　　Keywords: pe rsonalized recomme ndation, Local resources, AC algorithm, Trie structure, Android phone

　　近十年是移动互联网超高速崛起的黄金十年，“移动改变生活”的意识渐渐深入人心，市场上频繁涌现的各款移动智能终端慢慢的渗入到生活中的各个角落,在高端用户数量连续增涨和用户希望在终端上更好的娱乐、学习和办公的需求日益高涨的背景下，与终端厂商联合的应用软件开发如春笋般崛起,各种应用市场规模的扩大,应用软件产品丰富多彩；商业服务、接入模式步入多元化、多样化。根据最新统计数据,2015 上半年智能手机在中国的销售量达到 1.1 亿,增速为 40.0%。智能手机的快速普及,尤其是配置较高的 Android 机的普及,俨然促成了移动科技发展的新载体的诞生。

　　目前，移动终端的操作系统种类丰富，功能强大，日趋完善。市场上安卓和 iOS 的市场优势较为明显,拥有较高的市场占有率。2015 年 4 月 Android I/O 大会公布的统计数据显示,Android 操作系统在在全球手机市场中占有率为 64.6%。其中，在中国手机市场的占有率为 74.8%。Android 是 Google 于 2007 年发布，以 Linux 为内核的开源的操作系统。其内部包括移动终端正常操作所必须的全部服务进程,是世界上第一个开源免费且功能完整的系统平台。

　　移动互联网的泛起和普及将我们带入一个数据爆炸的年代，海量数据资源在满足用户的同时，也带来了数据资源超载的问题，即随着网络上数据资源的大幅增长，人们在如此大的资源中查找自己需要的资源变的如大海捞针般困难，如此以来，用户对信息的使用效率反而降低了。现阶段，针对数据资源过剩问题的解决方向之一是以搜索服务为代表信息检索系统，比如国外遥遥领先的谷歌、国内独树一帜的百度，它们在加快用户查询网络资源方面立下了汗马功劳。在用户需求明了时，搜索服务通过输入若干关键字可以方便快捷的找到相匹配的数据信息；但是并不是所有人的需求都可以简单明了的描述出来，用户想通过上述的检索系统来解决自己不明确的需求成为该技术发展的盲点。另外一个解决信息资源过剩的办法是使用个性化推荐服务，它是先分析使用者的上网习惯、浏览记录等，匹配出使用者或许想知道的信息、想购买的产品并推荐给使用者。与搜索系统相比，推荐系统一般是运行在后台监听记录用户行为数据，并从这些行为数据中分析和归纳其中的规律，由此解决搜索引擎无法深刻了解的用户个人化信息问题、用户潜在信息需求的问题、信息的垂直单向传播问题。

　　本课题正是基于上述的时代背景，研发出一种应用在android平台上的个性化推荐引擎。该推荐引擎才用创新优化后的 AC 算法和 Trie 树数据结构，通过分析用户手机上的短信息内容和下载到手机本地的英文文本内容，挖掘描述用户喜好和需求的关键字，与预置在内存中的广告内容进行匹配，由此将其感兴趣或者需要的信息推荐给用户。另外，个性化推荐引擎和 Android 系统的结合，也给以后的商业推广提供了巨大的空间。

　　海外最早的推荐引擎 LIRA 是被 Stanford 大学以 MarkoBalabanovic 为代表的团队研发，并于1995年3月美国举行的人工智能协会上发布。之后，对推荐引擎的研究日益深入和灵活，被广泛应用在搜索引擎、电子商务、汽车导航、智能手机等领域。全球最大的电子商务公司Amazon 之所以成为行业领域里的佼佼者效，并常常被其他公司模仿。就是因为他们在很早地时候就开始应用推荐服务的数据挖掘和分析算法将用户的网购习惯进行归类、分析，并推荐出客户潜在需要的产品。但是 Amazon 偏向于给客户推送一些常用的相似商品，欠缺对单一客户个性化的分析和了解，因此它在个性化推送业务方面做得有些欠缺。 另一个海外的 movie推送网站“What to Rent”似乎发现了性化推送业务的商机和需求，他们尝试用大量的调查问卷来了解客户的习惯，获取客户的信息，分析后给客户进行推送，取得了一定程度的胜利。

　　但是这同时也给用户和开发团队带来了较多完全可以避免的麻烦。

　　在国内，最早的专业推荐系统服务平台是由百分点科技公司研发的。得利于发达互联网，如今的推荐系统服务技术已经趋于成熟，并广泛使用在生活中的各个角落。尤其是电商购物网站的站内推送、搜索结果的智能匹配、相关新闻链接、微博、社区、SNS 等的站内推荐、视频/音乐等。但是这些商业推荐服务的体系结构都是基于服务器的，从原则上讲，这类的推荐引擎都是 web 服务器上进行使用者行为数据收集和建模。这不仅占用了 Web 服务器的系统资源，加重了成本开销，使用户行为数据的采集受到限制，还可能会导致用户信息的泄露，对使用者的隐私构成潜在危险。

　　另外，迄今为止，国内外大量的论文和着作都关注于推荐引擎的推荐算法的研究，推荐算法是整个推荐系统中头脑和心脏，直接决定了推荐服务引擎类型和性能的优劣。现在的推荐算法多种多样，对其分类也没有统一的标准，但是主流常用的推荐算法主要是下面几个：

　　基于内容的推荐算法、协同过滤推荐算法、基于知识的推荐算法、基于网络结构的推荐算法、组合推荐算法。这些算法都是以获取用户上网数据为前提的，但随着用户隐私保护意识的增强，个人信息的获取变得越来越难。信息泄露是推荐服务系统存在很久的难题，既能容易的获取用户数据资源来提升推荐服务质量，又能高效的保护用户数据必然成为新一代推荐引擎的一个研究方向。

　　基于上面介绍的推荐服务系统的研究现状，本文将提出一种安装在客户端的推荐引擎，该引擎的用户信息主要是基于本地英文文本资源和短信息数据，同时创新性的应用了 Trie 树数据结构和 AC 算法，并进行了优化和改进。本文的主要工作如下：

　　第一章绪论部分，主要介绍国内外个性化推荐服务技术的发展现状，分析推荐引擎目前研究困境，智能本文的研究方向，为后续研究做准备。

　　第二章介绍了在安卓平台上开发推荐引擎所涉及的基本理论和相关技术，如安卓平台的架构、组件；安卓后端 service 与前端的消息处理机制；Java 开发使用的多线程机制等，为下文的研究和设计提供了理论基础。

　　第三章主要是对本推荐引擎采用的算法的研究和改进。首先是通过在每个分支的尾节点中存储本分支表示的字符串来改进 Trie 树算法，接着又研究了 AC 算法和 KMP 算法,并对 AC算法做了一些优化设计：增加分隔符的匹配功能，增加单词的分割识别。

　　第四章主要是对本推荐引擎的整体设计与实现。包括推荐 service 与安卓前台应用的通信；本地短息数据的提取和分析；广告模块与分析模块的信息匹配与推送。实现了基于用户行为的个性化推送服务设计，并在本章的最后分别测试了该设计的数据分析模块和广告推送模块。

Android平台上个性化推荐引擎开发设计：

推送的广告图片

短信发送界面

消息推送界面

广告推送图片图

推送图片的链接网站

Demo 输入测试界面图

Demo 消息询问界面

无匹配结果弹框提示图

目录

　　第一章 绪论
　　　　1.1 课题背景及研究意义
　　　　1.2 国内外研究现状
　　　　1.3 本文的主要工作
　　　　1.4 本章小结
　　第二章 技术介绍背景
　　　　2.1 Android 操作系统介绍
　　　　　　2.1.1 Android 系统的平台架构
　　　　　　2.1.2 Android 应用的基本组件
　　　　　　2.1.3 Android 开发的环境配置
　　　　2.2 Android 消息的处理机制介绍
　　　　2.3 Java 多线程编程
　　　　　　2.3.1 多线程定义
　　　　　　2.3.2 Java 多线程的实现
　　　　　　2.3.3 线程的四种状态
　　　　　　2.3.4 线程的同步及阻塞
　　　　2.4 本章小结
　　第三章 相关算法的研究和改进
　　　　3.1 Trie 的研究与改进
　　　　　　3.1.1 Trie 算法的研究
　　　　　　3.1.2 Trie 算法的改进
　　　　3.2 KMP 算法研究
　　　　3.3 AC 算法研究
　　　　3.4 匹配规则的设计和实现
　　　　　　3.4.1 匹配规则文件设计
　　　　　　3.4.2 AC 算法中失败节点的创建
　　　　　　3.4.3 AC 算法匹配改进和优化
　　　　3.5 本章小结
　　第四章 推荐引擎的设计与实现
　　　　4.1 概要设计
　　　　4.2 手机本地数据资源的提取
　　　　　　4.2.1 手机短信数据的提取
　　　　　　4.2.2 手机 SD 卡文本数据的提取
　　　　　　4.2.3 Android 数据共享之 contentprovider
　　　　4.3 分析模块的设计和实现
　　　　4.4 广告推送模块的设计与实现
　　　　4.5 推荐引擎 Demo 的设计与实现
　　　　　　4.5.1 Demo 界面的设计与实现
　　　　　　4.5.2 推荐引擎与 Demo 通信的实现
　　　　4.6 本章小结
　　第五章 软件的测试
　　　　5.1 短信内容提取和消息推送的功能测试
　　　　5.2 推荐引擎的分析功能模块测试
　　　　5.3 本章小结
　　第六章 总结与展望
　　　　6.1 论文总结
　　　　6.2 展望
　　参考文献
　　致谢

（如您需要查看本篇毕业设计全文，请您联系客服索取）