毕业论文-基于移动端游戏数据的人群特征可视化研究.doc

本 科 生 毕 业 论 文题目 基于移动端游戏数据的人群特征可视化研究 姓 名 学 号 指导教师 专 业 数字媒体 学 院 计算机学院 A Dissertation Submitted to Zhejiang University for the Degree of Bachelor of EngineeringTITLE: Visualizing users characteristics based on mobile games data Author: Supervisor: Major: Di College: Computer Science and Technology Submitted Date: 2015.6.3 浙江大学本科生毕业论文（设计）诚信承诺书 1.本人郑重地承诺所呈交的毕业论文（设计），是在指导教师的指导下严格按照学校和学院有关规定完成的。2.本人在毕业论文（设计）中引用他人的观点和参考资料均加以注释和说明。3. 本人承诺在毕业论文（设计）选题和研究内容过程中没有抄袭他人研究成果和伪造相关数据等行为。4. 在毕业论文（设计）中对侵犯任何方面知识产权的行为，由本人承担相应的法律责任。 毕业论文（设计）作者签名： 年 月 日浙江大学计算机科学与技术学院本科毕业论文 摘要摘要随着智能手机等移动设备和高速4G网络的快速发展和普及，移动设备的用户数量日趋庞大，而游戏作为一种休闲娱乐的方式，也逐渐在移动设备上普及，许多大型的游戏公司都成立了对应的移动部门来开发移动端游戏，每天都会有新的游戏APP发布在各个平台上，移动端游戏行业的兴起让这个行业受到了重视，海量的游戏和用户带来了大量的游戏数据，从这些移动端的游戏数据中，我们可以挖掘出很多有效的信息，可以映射出许多用户特征，这刚好是游戏开发者和渠道商最需要的数据。目前对于移动端游戏数据的研究和分析，大多是基于对单一属性的统计结果的分析，例如游戏APP下载量，用户留存率，用户付费率等等，本文将会进一步挖掘移动端游戏数据背后深层的隐含信息，研究用户人群特征，并且用可视化的方法进行清晰的特征描述和概括。关键词移动端，游戏数据，用户特征，可视化I浙江大学计算机科学与技术学院本科毕业论文 AbstractAbstractAs smartphones and other mobile devices and the rapid development and popularization of high-speed 4g network, mobile devices increasingly vast number of users, and the game as a way of leisure entertainment, also gradually spread on mobile devices, many big game companies have set up the corresponding mobile division to develop mobile games, every day there are many new game APP released on the platform, the rise of mobile game industry puts a premium on the industry, a huge number of game and the user has brought a lot of data, from the mobile end game data, we can dig up a lot of effective information, features can be mapped out many users, this is just the game developers and distributors of data are needed most. For mobile game research and analysis of data, are mostly based on the analysis of the statistical results of a single attribute, such as game APP downloads, user retention rates, users pay rate and so on, this article will further the implied information in the deep hidden in mobile game data, studies the user population characteristics, and use the method of visualization for clear character description and generalization.KeywordsMobile, Games Data, Users Characteristics, VisualizationII浙江大学计算机科学与技术学院本科毕业论文 目 录目 录摘要IAbstractII第1章 绪论1 1.1 课题背景1 1.2 国内外研究现状2 1.2.1 主题模型的应用2 1.2.2 数据挖掘3 1.2.3 数据可视化的发展4 1.3 本文研究目标和内容5 1.4 本文结构安排5第2章 文献综述7 2.1 主题模型7 2.1.1 主题模型简介7 2.1.2 主题模型分类7 2.1.3 LDA主题模型8 2.2 聚类分析9 2.2.1 聚类算法简介9 2.2.2 聚类算法分类9 2.2.3 基于划分的聚类算法10 2.2.3.1 K-Means算法10 2.2.3.2 K-Medoids算法11 2.3 可视化分析11 2.3.1 矩形式树状结构图（Treemap）11 2.4 本章小结13第3章 研究方案14 3.1 问题分析14 3.1.1 数据分析14 3.1.2 挖掘隐藏信息14 3.1.3 数据预处理15 3.2 主题模型建立15 3.2.1 建立应用标签的词袋模型16 3.2.2 计算LDA模型17 3.2.3 聚类19 3.3 可视化转换20 3.3.1 Treemap图21 3.4 案例分析23 3.4.1 有效性验证23 3.4.1.1 总体规律23 3.4.1.2 同一人群的用户数据分析25 3.4.1.3 不同人群的用户数据分析26 3.4.2 不同分类标签数据对结果的影响28 3.5 本章小结29第4章 实验结果30 4.1 可视化结果30 4.2 人群特征研究结果31 4.3 本章小结32第5章 分析与讨论33 5.1 案例分析33 5.1.1 有效性验证33 5.1.1.1 总体规律33 5.1.1.2 同一人群的用户数据分析34 5.1.1.3 不同人群的用户数据分析35 5.1.2 不同分类标签数据对结果的影响37 5.2 本章小结38第6章 本文总结40参考文献41致谢42IV浙江大学计算机科学与技术学院本科毕业论文第1章 绪论第1章 绪论1.1 课题背景自从进入二十一世纪以来，信息技术和智能手机产业飞速发展，苹果公司在2007年1月9日发布了第一代iPhone手机，在2010年1月27日发布了第一代平板电脑iPad1，之后，各式各样的智能手机和智能平板电脑如雨后春笋般涌入消费者市场。根据工信部的统计数据显示，中国手机用户数量已经接近13亿人，其中智能手机用户数量已超5亿人。智能手机和平板电脑可以使用户根据自己的需求和爱好，选择安装具有各式各样功能的软件，App，各种类型的娱乐休闲游戏，是智能手机区别于非智能手机，吸引用户的主要特色之一。苹果应用市场App Store商店的应用数量已经超过了120万，安卓应用市场Google Play商店的应用数量甚至超过了150万。据不完全统计，在国内各类应用市场中，小米应用商店中软件的下载次数已经超过了100亿次，而360手机助手，豌豆荚应用市场中应用程序的下载次数则更多。如何从琳琅满目的应用程序的应用市场中，为移动端用户推荐他们真正需要的应用程序；如何将一款正火爆上市的手机游戏推荐给喜欢该类型游戏的用户，如何从游戏版本更替，用户替换，流水走势中权衡游戏开发方向和运营之间的关系，这些问题都是应用商店平台提供商，移动应用程序开发者都希望得到解决的问题。另外，用户在不断下载他们感兴趣的应用的同时，也会卸载他们不再需要的应用，如何留住用户也是一个开发团队需要解决的问题。 对于移动端游戏爱好者来说，从他们手机的游戏数据上，可以映射出许多重要信息，例如从游戏数量和玩游戏时间可以映射出用户是属于多样游戏爱好者还是单一游戏爱好者，用户日常生活中用来娱乐的时间段，从游戏类型中可以映射出用户是属于武侠爱好者还是玄幻爱好者或者是其他，甚至能映射出用户的性别和年龄段。例如一个用户的手机游戏主要是消除类和解谜类，那么用户是女性的可能性就比较大，如果一个用户的手机游戏主要是益智类和卡通类，那么用户年龄偏小的可能性就比较大。如何对这些数据进行分析，得到更准确的用户特征和行为习惯，是本文的核心内容。用户特征和行为习惯对于开发者来说具有非常重要的价值，例如一个用户下载了非常多的移动端游戏，每天花在游戏上的时间非常多，我们暂且称呼他们为游戏痴迷人群，这类用户由于经常玩游戏，对手机性能的要求比较高，可以给他们推荐一些清理和加速的软件。又例如手机游戏的类型全是武侠类型的用户，极有可能是武侠痴迷者，可以给他们推荐一些武侠小说或者经典的武侠电视剧。再例如从一个用户在游戏中消费额，消费额随时间变化等数据中，判断该用户的游戏预期支出，例如一个用户的消费大多是在某月的特定时间，那么很有可能改用户是一名已工作的人，可以给他们推荐一些投资理财的软件。但是通过单一属性的统计结果分析往往存在一定误差，我们希望能够尽可能地使分析结果准确。因此我们希望可以建立一个适合的主题模型，从多属性的统计结果来分析用户特征和行为习惯，还可以结合多维度例如时间，地点等信息，来更加全面的分析用户特征。最后通过合适的可视化方法进行清晰的展现，将结果以直观易懂的方式展示给开发和研究人员还有相关厂商，帮助他们更有效的对用户进行分析，对产品进行改进。1.2 国内外研究现状1.2.1 主题模型的应用主题模型1是一个在自然语言处理，机器学习等领域都有广泛应用的产生式模型（generative model）。 主题模型最初使用于自然语言处理的相关方向，用来在一系列文档中发现抽象的主题。直观来说，如果一篇文档有一个中心思想，那么与该中心思想关联的一些特定的词语在文档中出现的频率就会更高。比如说有一篇文章是介绍“人工智能”的，那么“人工智能”，“图灵”，“机器学习”等词出现的频率就会比较高，如果有一篇文章是介绍“狗”的，那么“狗”和“骨头”等词出现的频率就会比较高。而其他一些没有实际意义的词语如“和”，“或”大概在两篇文章中出现的概率就会大致相近。大多数情况下，一篇文档都会涉及多个主题，而每个主题占的比重各不相同。如果介绍“狗”的文章里有80%和狗有关，20%和猫有关，那么与狗相关的关键词出现的次数大概会是与猫相关的关键词的出现次数的4倍。所谓的主题模型就是试图使用数学框架来体现文档中的这些特点。主题模型通过自动分析每篇文档，统计文档内的词语，根据统计的信息来推测每篇文档包含哪些主题以及每个主题所占的比重。 为了更加清晰直观地展示主题模型得出的结果，可视化越来越多地使用到主题模型中来，主题模型为数据可视化提供模型基础，可视化将主题模型的内容直观的展示并且加入一定的交互元素。斯坦福大学的可视化小组对上面基于LDA主题模型的文档可视化系统进行了改进2。他们提出了一种显著值度量算法，对单词进行筛选，选用更具有信息价值的单词代表主题信息。并且在可视化展现时，在小范围内调整单词的排序，将相关联的单词排列在一起，增强易读性 ，如图 1.1 所示 。图1.1 基于LDA主题模型的文本可视分析系统近几年来，主题模型以及延伸到了各个领域例如气象学，生物学进行应用。而Trinh-Minh-Tri Do等人最早将主题模型应用到手机用户数据的分析中，提取用户特征345。他们通过和诺基亚研究中心合作，对110名诺基亚手机用户进行连续的观察，采集短信，电话，浏览器，相机，相册等应用的使用数据进行分析。来分析用户对手机应用的使用习惯，而现在智能手机盛行，用户在使用手机玩游戏的过程中也会产生一系列可采集的数据，包括游戏类型，每日玩游戏时间，充值数额，游戏数量等等，对这些数据进行采集并且建立主题模型进行分析最后用可视化的方法进行展示，也会是一个比较有意义的研究。1.2.2 数据挖掘在这个大数据时代，数据挖掘引起了信息产业界的极大关注，快速有效的数据挖掘可以大大减少工作量，在大量数据中挖掘有用的信息和知识来广泛应用到商务管理，生产控制，市场分析，工程设计和科学探索等工作上，是数据挖掘的核心工作。 数据挖掘一般是通过算法来搜索隐藏在大量数据中的有用的信息的过程，主要有分类，估计，预测，关联性分组，聚类，复杂数据挖掘等方法。我们非常熟悉的K-means算法就是属于数据挖掘中聚类的一种算法。 数据挖掘成功的案例有很多，例如帮助全球物流行业领先者DHL实现了实时跟踪货箱温度，由于药品在装运的过程中需要保持温度达标，而客户又不愿意提高成本，虽然由记录器方法生成的信息准确无误，但是无法实时传递数据，客户和DHL都无法在发生温度偏差时采取任何预防和纠正措施。因此，DHL的母公司德国邮政世界网（DPWN）通过技术与创新管理（TIM）集团明确拟定了一个计划，准备使用RFID技术在不同时间点全程跟踪装运的温度。通过IBM全球企业咨询服务部绘制决定服务的关键功能参数的流程框架。DHL获得了两方面的收益：对于最终客户来说，能够使医药客户对运送过程中出现的装运问题提前做出响应，并以引人注目的低成本全面切实地增强了运送可靠性。对于DHL来说，提高了客户满意度和忠实度；为保持竞争差异奠定坚实的基础；并成为重要的新的收入增长来源。1.2.3 数据可视化的发展可视化的概念最早是对数据的视觉表现形式方面的研究，主要是借助一些图形手段来表达数据信息，会应用一些美学效果来直观清晰地表达思想概念和关键特征。而现代的可视化概念则更为广泛，在当今的大数据时代，可视化旨在研究大规模信息资源的视觉呈现6，以及利用图形和图像的相关技术方法，来帮助人们理解和分析数据7，其技术设计各个领域，如计算机图形学，计算机视觉，计算机辅助设计等。 十八世纪后期，随着数据图形学的诞生和发展，人们有了用抽象信息的视觉表达手段来揭示数据和文字背后的奥秘的动机，使得数据可视化迈出了发展的第一步。 二十世纪九十年代，随着图形化界面的问世，人们开始能够直接和可视化信息进行交互，带动了二十多年来的可视化研究8。1987年，由Mccormick，DeFanti和Brown所编写的美国国家科学基金会报告Visualization in Scientific Computing，对数据可视化领域产生了大幅度的作用。这份报告强调了新的基于计算机的可视化技术方法的必要性。随着计算机的计算能力不断提升，人们开始建立数据越来越多，规模越来越大，复杂度越来越高的模型，因此需要高级的计算机图形学技术，来分析并可视化这些大规模的数据集，短语“Visualization in Scientific Computing”后来变成了“Scientific Visualization”。二十世纪九十年代初期，人们发起了一个新的，称为“信息可视化的”研究领域，为的是对许多应用领域中关于抽象的异质性数据集的分析工作提供技术支持9，所以可视化也称为一个重要的学科逐渐成长起来。如今，可视化技术已经成为一个揭示数据集中数据之间的关系和背后隐藏的信息的基本工具10，全世界的各所高校都在积极开展数据可视化的研究工作，而可视化相关的职业，也正在逐步兴起，生活中随处都可以看到复杂的数据经过优异的可视化处理之后给人带来震撼的作品，目前世界上有10余个专门的可视化期刊和杂志，并且每年都会邀请可视化领域的专家，举办可视化相关的国际会议。1.3 本文研究目标和内容 本文主要实现了基于移动端游戏数据，关于人群特征的可视化系统。 本文从海量的应用信息，游戏数据信息，通过建立合适的主题模型，挖掘其中能够映射出的有价值的隐藏信息，从而概括出移动用户的人群特征。如图1.2所示，主要工作包括： 1）将LDA主题模型引入到移动端数据的分析中，提取出手机应用分类主题。并将手机用户按照与不同应用主题的相关度进行聚类，形成具有代表性的人群。 2）在具有代表性的人群中，分析各个方面的数据，提取人群特征和行为习惯。 3）对提取出的人群特征和行为习惯进行可视化展现。 4）对分析出特定人群特征的人群进行进一步的优化服务。图1.2 本文主要工作1.4 本文结构安排 本文首先概述了移动端游戏行业的兴起和先状，介绍了基于移动端游戏数据的人群特征研究的大致内容，以及在互联网时代的重要意义及价值。然后介绍了本课题的研究内容和过程，包括数据的分析，人群特征的分析，可视化方法的设计，优化服务，结合时序的可视化，算法实现，案例分析，结果展示等。 本文共分为六章，主要内容描述如下： 第一章：绪论，主要介绍基于移动端游戏数据可挖掘的人群特征和行为习惯信息，以及其重要意义，然后介绍了国内外研究概况。 第二章：文献综述，主要介绍了相关资料对于本文中用到的一些技术的说明和描述。 第三章：研究方案，详细介绍了基于移动端游戏数据的人群特征可视化研究的流程和方法，以及具体的实现步骤。 第四章：实验结果，展示本文主要的实验结果。 第五章：分析与讨论，主要是结合案例，对实验结果的分析和讨论。第六章：本文总结，主要是对本文进行总结。6浙江大学计算机科学与技术学院本科毕业论文第2章文献综述第2章 文献综述2.1 主题模型2.1.1 主题模型简介 主题模型（Topic Model）1是一种层次贝叶斯模型，属于概率产生式模型，它可以以无监督的方式自动组织和理解文档，从而提供了一种新的文档表示方法，在近几年得到了广泛的研究和应用。传统方法来判断两个文档是否相似是通过检查两个文档中共同出现的单词的多少，但是这种方法有一个漏洞，它没有考虑到文字背后关联的语义，比如说有可能两个文档共同出现的单词很少甚至没有，也可能是用同义词代替，但这两个文档是相似的。 在主题模型中，主题是用来表示某一概念或某一方面，表现为一系列相关的单词，是这些单词的条件概率，认为一篇文档的每个单词都是通过以一定的概率选取了某个主题，然后从这个主题中以一定概率选取某个单词生成出来的。通过机器学习的方法，我们就可以得到文档的主题，从而判断两个文档是否相似。2.1.2 主题模型分类 早期文本数据挖掘和信息出来的主要方法是基于向量空间模型（Vector Space Model，VSM）11。在VSM中，一个基本的单词作为向量的元素，向量的值往往选择规范化的TF-IDF（term frequency-inverse document frequency），从而构成单词-文档矩阵，文档被表示成由特征单词的出现概率所组成的多维向量，这种方法优点是可以将查询目标和文档转化为同一个空间下的向量，从而计算余弦相似度，还可以给不同特征单词分量赋予不同的权重。但是，VSM没有对文本进行语义识别，无法处理同义词和一次多义问题。Landauer等人提出的潜在语义分析模型（Latent Semantic Analysis, LSA）减轻了上述问题。LSA的目的是要从文档中挖掘隐含的语义维度，即“主题”。LSA通过线性代数中的奇异值分解（Singular Value Decomposition, SVD）方法来对单词-文档矩阵实现维数约减，从而将单词-文档映射到一个低维的潜在语义空间中。LSA可以在一定程度上识别同义词和近义词，但是LSA缺乏严谨的数理统计基础，而且SVD分解计算非常耗时。Hofmann等人在1999年提出了概率潜在语义分析模型（Probabilistic Latent Semantic Analysis, PLSA）12。PLSA模型基于似然估计原理提出产生式模型，它认为一个文档由多个潜在主题按照特定的比例混合而成，而潜在主题被认为是在单词表上的多项式分布。PLSA模型与LSA相比具有更加坚实的数理统计基础。但PLSA模型在文档层面没有合适的概率模型，PLSA必须在确定文档的情况下才能对其进行随机抽样。PLSA中需要训练的参数会随着文档数量的增加而线性增长，在参数学习过程中存在“过拟合”的问题，计算量较大。2003年Blei等人提出了潜在狄利克雷分配模型(Latent Dirichlet Allocation，LDA)13，可以解决上述问题。LDA模型为PLSA中的模型参数提出了先验假设，即Dirichlet先验，并用一个服从狄利克雷分布的k维随机变量来表示一个文档由不同主题的构成比例。LDA模型是完全的产生式主题模型，参数空间不会随着文档数量的增加而增大，非常适用于对大规模文本数据进行建模。潜在狄利克雷分配模型(Latent Dirichlet Allocation，LDA)是一个对离散数据集合(如文档)进行主题建模的概率产生式模型。它假设一篇文档是由主题集合中的主题按照一定的比例混合而成的，而每一个主题又是由单词表中的单词按照一定的比例混合而成的。LDA模型层次结构清晰，依次分为文档层、主题层和单词层。其中，文档与主题相关联，而主题又与单词相关联。2.1.3 LDA主题模型潜在狄利克雷分配模型（Latent Dirichlet Allocation，LDA）是一个对离散数据集合（如文档）进行主题建模的概率产生式模型。它假设一篇文档是由主题集合中的主题按照一定的比例混合而成的，而每一个主题又是由单词表中的单词按照一定的比例混合而成的。LDA模型层次结构清晰，依次分为文档层，主题层和单词层。其中，文档与主题相关联，而主题又与单词相关联。LDA模型涉及的基本概念13： 1)单词（word）：单词是离散数据的基本单位，语料库中所有单词均来自某个单词表，单词表大小为V。 2)文档（document）：LDA与PLSA一样，是基于词袋模型（bag of words）假设的，即文档由一个一个的单词组成，只考虑单词在文档中的出现次数，而不考虑其在文档中出现的先后顺序及其约束关系。所以一篇文档可以使用单词向量来表示，假设文档中有N个单词，则可以表示为w = (w1, w2, ,wN)。 3)语料库（corpus）：即文档集，由D个文档组成，可以表示成D = (w1, wD)。概率主题模型认为同一个语料库中的文档之间也是可以相交换的。 4)主题（topic）：假设语料库一共有T个隐含主题，主题集可以表示为Z=z1,zT。文档中属于某个主题的单词与该文档中所有单词的比例，即代表此主题在文档中所占的比例。主题数T一般是已知且确定的。 LDA模型的目标就是通过学习文档集中的单词，挖掘出所有隐含的主题信息，并可以用来挖掘文档集以外的其他文档的主题分布。对于语料库中的一篇文档，LDA定义了如下生成过程：1. 对每一篇文档，从主题分布中选取几个主题；2. 从上述选取的主题所对应的单词分布中选取一个单词；3. 重复上述过程直至生成文档中的每一个单词。 该模型有两个参数需要推断，一个是“文档-主题”分布，另外是“主题-单词”分布。推断方法主要有LDA模型作者提出的变分-EM算法，还有现在常用的Gibbs抽样法。通过无监督学习这两个参数，我们最终得到文档集中的所有作者所感兴趣的主题（用单词库中的单词按一定比例混合构成），以及每篇文档所包含的主题比例。2.2 聚类分析2.2.1 聚类算法简介聚类分析（Cluster Analysis），又称为群分析，它是研究（样品或指标）分类问题的一种统计分析方法。聚类分析是指将抽象对象的集合分成相似的簇的过程14。位于同一个簇内的对象之间相似性较高，不同簇之间的数据对象相似性较小。通常，我们利用聚类分析将看似无序的对象进行分组、归类，以达到更好地理解研究对象的目的。2.2.2 聚类算法分类聚类分析计算方法主要分为以下五种，如图2.1所示：图2.1 聚类算法分类 1）基于划分方法(partitioning methods)基于划分的聚类算法对数据集进行分组，对于一个有n个元组或记录的数据集，通过分裂法将数据集划分到k个分组中。对于给定的k，算法首先给出一个初始的分组方法，然后通过不断进行迭代以修改分组，直到确定最终的分组方案。常见的基于划分的聚类算法有K-means 算法和K-medoid 算法。 2）基于层次方法(hierarchical methods)基于层次的聚类算法对对给定的数据集进行层次似的分解，直到满足某种条件为止。具体又可分为“自底向上”和“自顶向下”两种方案。“自底向上”方法初始时将每个数据对象看做一个簇，然后不断合并邻近的簇，直到满足条件时结束。“自顶向下”方法将所有数据对象看做一个簇，然后逐渐进行细分，直到满足条件时结束。 3）基于密度的方法(density-based methods)基于密度的聚类算法与其他聚类方法的根本区别在于，在评价相似性时，采用基于密度的评价标准，而不是基于距离的。一个区域中的点的密度大于某个阀值时，就将其加入相似的聚类中。基于密度的聚类算法不受初始数据分布形状的影响，能够识别数据集中的噪声点，有较好的伸缩性。 4）基于网格的方法(grid-based methods)基于网格的聚类方法，首先将数据空间划分为有限个的单元的网格结构，然后以单个的单元结构为对象进行聚类操作。由于聚类操作是以单元为对象进行,与原始的数据记录个数无关，基于网格的聚类方法处理速度很快。 5）基于模型的方法(model-based methods)基于模型的聚类算法，先假设每一个聚类的模型，然后去寻找比较适合这个模型的数据集。常见的模型有数据点在空间分布中的密度分布函数和基于标准的统计方法等。2.2.3 基于划分的聚类算法 基于划分的聚类方法，又称为分裂法，其具体定义为：假设一个数据集合中包含n个对象或元组，将这n个对象划分成k个分组，那么这k个划分就代表k个类（kn）。其中，数据对象需要满足如下条件：每个类中至少要包含一个对象；每个数据对象只能被划分到一个类中。通过划分聚类，使得在同一个簇中的数据对象具有较高的相似度，而不同簇之间的数据对象具有较低的相似度。基于划分的聚类算法通常需要穷举所有可能的划分来寻找最优的划分，其过程是不断迭代进行的，分为两个步骤：首先划分一个对象到某一个类中，使得此数据对象到其他类的距离大于到这个类的距离；然后修改聚类中心，选择合适的目标函数，当目标函数达到最优时结束，此时不再有数据被重新划分。基于划分的聚类算法主要分为两类：一类是基于质心技术的划分聚类方法，以K-Means算法为代表；一类是基于代表对象技术的划分聚类方法，以K-Medoids算法为代表。2.2.3.1 K-Means算法K-Means 算法将n个数据对象划分到k个簇中，使得同一个簇中的对象相似度较高，不同簇之间的对象相似度较低。首先选择k个对象作为初始的聚类中心，然后计算其它的对象与这k个簇中心点的距离，将其它的对象划分到距离最近的簇中，然后重新计算各个簇的平均值更新簇的中心点，不断迭代这个过程，直到准则函数收敛。聚类准则函数用于判断聚类质量的高低，K-Means 算法采用平方误差准则函数，其定义如下：E=ki=1pci|p-mi|2其中，E是数据集中所有对象的平均方差总和，p表示数据对象。K-Means 算法需要用户给定聚类的簇的数目，并且对于初始聚类中心的指定具有较强的依赖性，K-Means 算法不能处理非凸面形状的簇，对于孤立点数据和“噪声”也比较敏感。2.2.3.2 K-Medoids算法 K-Medoids 算法，首先为每个簇选择一个代表对象，然后将其他对象分配到距离最近的簇中，然后为各个簇重新选择一个对象来代表该簇。通过迭代计算，不断更新簇中的代表对象，并通过代价函数来估算聚类结果的质量。K-Medoids算法和K-Means算法的主要区别在于，K-Medoids算法没有使用簇中对象的平均值作为中心点，而是选择一个实际的对象来代表该簇。因此可以消除K-Means方法中对于孤立点的敏感性。但复杂度与K-Means算法相比较高。2.3 可视化分析数据可视化的主要目的是，将数据直观显示、为用户提供可交互操作等。基于不同的显示需求、交互需求等，可视化的方法也是多种多样的。2.3.1 矩形式树状结构图（Treemap）Treemap（矩形式树状结构绘图法)，是一种在受限空间内展示树状数据结构的可视化方法。在一个固定大小的矩形区域内，将该矩形交替切分为水平和垂直方向的矩形，不断重复下去，用递归来实现层级关系。这种通过将矩形不断进行细分（Slice And Dice）的方法，可以在固定大小区域内展示多层级的数据信息，也可以比较直观地展示同层级数据之间的比较。图2.2 Treemap2.4 本章小结 本章主要介绍了文献中对本文相关技术的相关介绍。首先介绍了主题模型的分类，以及LDA主题模型；然后介绍了聚类算法的分类，以及基于划分的聚类算法；最后介绍了可视化方法，主要是多层结构数据的可视化方法。后面本文也会采用treemap的方法对数据进行可视化展现。13浙江大学计算机科学与技术学院本科毕业论文第3章研究方案第3章 研究方案3.1 问题分析本论文的研究课题是基于移动端游戏数据的人群特征可视化，挖掘游戏数据背后隐藏的数据信息，更加深入的了解手机用户的人群特征。根据这一方向和目标，确立了基本的研究流程，如图3.1，主要分为5个步骤：（1）获取研究所需的移动端游戏数据，包括手机用户安装的游戏数据，游戏类型，游戏频率，游戏消费等等数据文件。（2）对这些数据进行筛选，构造主题模型。（3）通过聚类分析，分析人群特征。（4）构造合适的可视化模型，进行结果展示。（5）根据结果，结合案例和实际进行对比分析，不断调整完善。3.1.1 数据分析随着智能手机的普及，智能手机的功能也越来越强大，手机应用市场也飞速发展，各式各样的手机应用层出不穷。而本课题研究的是移动端游戏数据，挖掘出其所能映射出的用户特征及行为习惯。因此，本章节研究内容所需要的数据主要有两类。一类是采集到的每天的手机用户安装的游戏列表信息，如表3.1；另一类则是各个游戏的分类标签信息，如表3.2。表3.1 手机用户安装的游戏列表信息表3.2 游戏分类标签信息3.1.2 挖掘隐藏信息 之前的关于手机游戏数据的可视化，大多是以简单的二维形式展现统计结果。如“日下载量”，“月流水”，“日活跃用户”，“某用户安装的游戏列表”等。而我们希望可以挖掘出更深层次的，能够反映用户特征的数据进行进一步的可视化。经过对真实用户数据的观察以及用户调研，我们发现手机用户安装的游戏，往往可以进行归类，如“神庙逃亡”，“天天酷跑”，“熊出没”等都属于跑酷类；“梦幻西游”，“神魔”，“仙剑奇侠传”等都属于角色扮演类。喜欢玩跑酷类游戏的用户反应敏捷，喜欢角色扮演类游戏的用户往往沉迷虚拟世界，会花费大量时间在游戏上。每个用户安装的游戏类型并不只有一种，但是我们发现有些用户对某一类型或主题的游戏安装的特别多，我们能够挖掘用户安装的不同类型游戏和数量之间的比例，这是非常有价值的信息。例如说安装武侠游戏类型多的用户往往会比较痴迷于武侠，我们可以推荐一些看武侠剧的应用或者武侠小说的App给用户；再例如说安装游戏数量多，玩游戏时间长的用户对手机性能的要求会比较高，我们可以推荐一些清理加速的应用，及时帮助用户清理内存，来优化体验。3.1.3 数据预处理 因为每天用户都有可能安装新的游戏，卸载旧的游戏，所以我们必须筛选有用的数据信息进行建模分析，主题模型需要做的数据预处理工作主要有以下几点： 1）系统会每天采集多次数据，但是会有很多重复的数据，因为一部手机上一天内的应用程序信息往往是一样的，所以需要去除重复的记录。 2）每天都会有新激活的移动设备，也会有不再使用，销毁的移动设备。对于主题模型而言，由于通过LDA学习出来的主题模型不受总的手机设备的影响，所以我们对于每个月的数据可以固定的只观察一部分确定的手机设备的游戏数据。 3）每天需要获取手机今日新安装的游戏信息，卸载的游戏信息，但不包括该手机当前状态下的所有游戏信息，所以需要额外一张数据表，来存储我们观察的手机设备的历史累积的安装的游戏信息列表，每天根据游戏信息变化数据以及前一天的游戏状态数据计算得到当天的游戏数据信息。预处理后的数据按表3.3中的字段存入数据库：表3.3 预处理后数据字段3.2 主题模型建立LDA主题模型是文档分析中常用的模型。在LDA模型中，一段文档被当做是一个不考虑前后顺序的词袋，通过分析这些词袋，LDA模型可以提取出文档中潜在的主题信息。LDA主题模型通过在文档和单词之间增加一层抽象层，而使得对文档见关系的分析能更加准确全面，如判断两篇文档是否是同一个主题。我们则将LDA主题模型巧妙地引入到手机游戏数据的可视化和分析中来。如图3.4所示，定义手机游戏所包含的多个分类标签对应单词，一部手机则对应一篇文档，采集到的手机用户即为语料库，通过提取出的主题来分析手机用户特征。通过对用户的手机上所安装的游戏标签数据进行分析，我们可以得到该手机用户潜在的主题信息，基于此我们可以判断两名手机用户是否属于同一类型的用户，我们可以将类似的用户聚类成一个人群。在进行聚类之前，LDA模型很好地帮助我们对数据进行了降维，将千差万别的游戏名称，提取为该手机用户与几个主题的相关度。而几个主题按照不同比例组合，就可以代表一个手机用户的特征。解决了直接基于游戏名称聚类，不同用户之间差异性太大而使得无法有效聚类的问题。3.2.1 建立应用标签的词袋模型 首先，我们需要将手机上的游戏数据与LDA模型的输入数据文档中的单词建立对应关系。有两种映射方法： 1）将游戏名称直接作为单词。 2）将游戏名称，和预先维护好的游戏名称-分类标签数据表进行匹配，得到该游戏的几个分类标签，使用分类标签作为单词。 显然，第二种方法更加优秀，原因如下： 1）将游戏名称直接作为单词，会导致整个语料库单词太多，词频太小。而且同一个游戏在不同的应用市场上可能会有不同的名字，会导致不同手机上安装的相同游戏名字却不同，无法有效得到所有手机用户安装游戏的分类和主题，无法有效整理出整个语料库中的文档主题信息。 2）将游戏名称对应为预先维护好的几个分类标签后，可以达到名称的规范统一，保证语料库的单词量适中，词频适中；通过将一个游戏名称转换为几个分类标签后，还可以增加代表该手机用户的标签数量。所以，我们使用游戏的分类标签信息作为单词，建立了每部手机的词袋模型，如表3.4所示：表3.4 游戏应用标签词袋模型另外，为了更好地分析结果，使主题模型更加准确地代表手机用户，我们尝试对采集到的每个手机上安装的游戏数据，增加对应的打分机制。因为手机用户安装一个游戏之后，可能从未玩这个游戏，也可能经常玩这个游戏，可能玩了一两次就卸载了，可能玩了很久很久还保留在手机上。所以我们设计了以下的打分机制，对于手机上安装的每个游戏，如果该游戏当天安装当天就卸载则认为是不得分的，该游戏每在该手机上存留一天对应的分类标签便增加1分，留存10天以上则认为是一直保留在手机上，对应分类标签得10分。手机用户每实际启动该应用程序一次，就为该应用程序对应的分类标签增加一分。增加打分机制后，得分越高的应用标签我们认为该标签类别的游戏在该手机上使用的越多，和该手机用户的特征关系越大。和LDA模型中的词频相对应，一篇文档中出现次数越多的单词越能代表该篇文档。当然和LDA处理文档时会剔除如“and”这种在每篇文档中都会出现很多次的无意义单词一样，我们也会剔除“免费游戏”，“付费游戏”这种会属于很多游戏的，没有实际统计意义的标签。通过这样对分类标签增加打分机制后，我们得到了能够更加准确代表手机用户游戏数据的词袋模型。3.2.2 计算LDA模型 将一部手机看做一篇文档，该手机的所有应用程序对应的分类标签作为单词，根据LDA主题模型，我们可以得到以下关系式： P（标签|手机）=P（标签|主题）P（主题|手机）更具体一些，语料库中的每一篇文档与T（通过反复试验等方法事先确定）个主题的一个多项分布相对应，将该多项分布记为变量。每个主题又与单词表中V个单词的一个多项分布相对应，将这个多项分布记为变量。上述单词表是由语料库中所有文档中的所有互异单词组成，但实际建模的时候要剔除一些停用词，还要进行一些词干化处理等。和分别有一个带有超参数和的狄利克雷先验分布。对于一篇文档d中的每一个单词，我们从该文档所对应的多项分布中选取一个主题z，然后我们再从主题z所对应的多项分布中选取一个单词w。将这个过程重复Nd次，就产生了文档d，其中Nd是文档中的总单词数。这个生成过程可以用如下图3.5的盘子表示法（plate notation）表示：图3.1 LDA模型盘子表示法盘子表示法图中的阴影圆圈表示可观测变量（observedvariable），非阴影圆圈表示潜在变量（latentvariable），箭头表示两变量间的条件依赖性（conditional dependency），方框表示重复抽样，重复次数在方框的右下角。LDA模型中涉及两个非常重要的概率分布:狄利克雷分布（Dirichlet Distribution）和多项式分布（Multinomial Distribution），狄利克雷分布是多项是分布的共轭先验，狄利克雷分布的定义如下：Dir(;)=(1/Beta()Ti=1ii-1LDA的建模流程是：先假设产生文档集的一个过程，然后根据观察到的实际文档集，来估算过程中的各项具体参数。因此可以说LDA模型训练阶段的主要任务就是找到“最有可能产生当前观察到的文档集”参数。对于一篇给定的文档，如何推断其隐含变量和，是LDA模型的关键。通过可以观察到的文档集中的单词来推断模型中的隐含变量。实现了隐含变量的推断，就可以通过参数估计算法来估算模型的全局参数和。参数确定后，主题模型也随之确定下来。LDA模型有两个参数需要推断：一个是“文档-主题”分布，另外是T个主题“主题-单词”分布。在LDA模型中，超参数表示了文档和主题之间的关系，因此在T维向量中，即使主题数非常多T非常大，也不会造成大量的参数而产生PLSA模型中的过拟合问题。表示每个主题中各个单词的生成概率，我们可以通过一个主题中单词的构成比例来确定该主题所表达的语义。对模型求解参数和，主要有LDA模型作者David M.Blei教授提出的变分推算算法，最大期望算法，还有现在常用的基于Gibbs抽样的算法。成果求解出和后，得到了表示手机在主题上的分布和主题在标签上的分布。我们经过多次实验，认为提取5个主题，更具有代表性和实际意义。我们最终得到的是5个主题，每个主题由若干个分类标签构成，我们按照分类标签和该主题的相关度大小排序选取前面的标签用于代表该主题的意义。3.2.3 聚类通过上面LDA模型的学习，我们同时得到了每个手机游戏用户与5个主题分别的相关度大小。此时用5个主题的相关度就可以代表该手机游戏用户的特征。如某个手机游戏用户和“跑酷”，“消除”，“塔防”，“射击”，“卡牌”5个主题的相关度大小依次为0.8,0.3,0.3,0.3,0.1我们可以看出该手机游戏用户属于比较典型的休闲类游戏玩家，很有可能是一名学生在课间或者空余时间通过这些休闲游戏来放松自己。再例如某个手机游戏用户和“角色扮演”，“武侠”，“仙侠”，“魔幻”，“格斗”5个主题的相关度大小依次为0.7,0.4,0.3，0.2,0.1我们可以