智慧城市大数据方案关键技术课件

1、智慧城市大数据方案关键技术一、大数据、物联网、智慧城市智慧城市大数据（云计算）物联网智慧 交通智慧 医疗智能电网数据采集数据处理智慧 旅游智慧城市：运用先进的信 息技术，实现城市智慧管 理与运行，为城市中的人 创造更美好的生活。物联网：通过RFID、 GPS、传感器等传感 设备与互联网连接起 来，进行信息交换和 通讯，实现智能化识 别、定位、监控与管 理。大数据：大小超 出传统数据处理 工具存储、处理 分析、能力的数据集。（麦肯锡）二、大数据数据质量、处理框架及测评概述1数据质量及评估2分布式数据处理框架及测评3大数据的基准测试4概述 大数据环境下，传统的数据处理技术无法满足对大数据量 分析和

2、处理的要求，大数据治理、大数据处理技术应运而 生。 数据来源的不同、数据形式的多元化，使得数据质量存在 较大的差异，不正确或者不一致的数据可能严重影响数据 分析效果。Hadoop、Spark为代表的各种大数据框架不断涌现，这些数 据处理框架方便了大数据应用的编写，但是由于其分布性 和封装性，给应用程序的测试带来巨大挑战。大数据处理流程使用相关工具对分布广泛的非结构化的数据源进 行抽取/采集，并进行数据传输采用合适的模式/标准对数据进行统一存储利用智能算法，对数据进行分析处理数据分析处理的结果，通过可视化的方法，提供 给大数据应用（预测、分析报表、）数据源数据集成关系数据库数据集成实体 数据质量

3、聚类和关联模式数据质量应用可视化目录概述1数据质量及评估2分布式数据处理模型及测试3大数据的基准测试4数据质量定义目前数据质量还没有统一的定义形式数据质量为信息系统对模式和数据实例的一致性、正确性、完整性和最小性的满足程度数据质量是数据适合使用的程度数据质量是数据满足特定用户期望的程度数据质量的内容 数据真实性：数据真实并且准确地反映实际 的业务数据完备性：数据充分，没有遗漏任何有关的操作数据 数据自治性：数据不是孤立存在而是通过不 同的约束互相关联，在满足数据之间关联关 系的同时不违反相关约束数据质量问题（脏数据来自哪里？） 数据源本身是脏数据 数据转换/集成 数据本身价值的失效 数据质量问

4、题分类10单数据源 数据质量 问题模式层缺少完整性约束，糟糕的设计模式 1) 缺少唯一性约束2) 缺少引用约束实例层数据记录错误 1) 拼写错误2) 相似重复记录3) 互相矛盾的字段多数据源 数据质量 问题模式层异质的数据模型和模式设计 1) 命名冲突2) 结构冲突实例层冗余、互相矛盾或不一致的数据 1) 不一致的汇总2) 不一致的时间选择数据质量控制方法使用静态的模式约束不允许空值、外键的约束等工作流中的动态约束订单额超过200美元的订单交给ID为2的业务员操作约束遵循80-20原则少数几个约束，能解决多数数据质量问题数据预处理 数据预处理通常是指在数据存储、分析之 前对数据的处理。使用数据

5、预处理技术能 够提高数据质量，提升数据分析的效果。数据预处理一般包含以下几个步骤数据清洗（Data Cleaning）数据变换 (Data Transformation)数据集成 (Data Integration)数据规约 (Data Reduction)数据清洗数据清理主要是用如统计分析、预定义规则等相关 技术将“脏数据”转换为满足数据质量要求的数据。数据清洗所处理的主要问题有：清理规则数据清理手工清理自动清理满足数据质量 要求的数据脏数据 缺失的数据（Missing Data）-属性缺失单位误匹配（Unit mismatch）-$ vs. ￥实体解析（Entity Resolution）

6、-IBM vs. International Business Machines孤立点（Outlier）数据错误（Data Error） 业务知识清理算法数据集成/数据变换 数据集成整合来自多个数据存储的数 据，为数据分析、处理、挖掘提供完整的 数据源。数据变换将数据变换或统一成适合于数据分析挖掘的形式。数据集成中数据质量问题分类问题类型问题描述数据表连接不 匹配来自多个数据源中的数据表需要通过相同的主键进行 自然连接，当表中的主键不匹配时，出现无法连接的 现象冗余在连接数据表的过程中，没有对表中的字段严格选择 后就连接，造成了大量的数据冗余数据值冲突不同数据源中不同的属性值，导致数据表连接字

7、段的 类型的冲突。数据变换处理内容数据分类描述属性的数据类型转换当属性之间的取值范围可能相差很大时，要进行 数据的映射处理，映射关系可以与平方根、标准 方差以及区域对应属性构造根据已有的属性集构造新的属性，以帮助数据挖 掘过程数据离散化将连续取值的属性离散化成若干区间，来帮助消减一个连续属性的取值个数数据标准化不同来源所得到的相同字段定义可能不一样，比 如重量统一标准化为kg数据规约 数据规约获得数据集的简化表示（简 称近似子集），并且近似子集的信息表达 能力与原数据集非常接近。 属性选择是根据用户的指标选择一个优化属性子 集的过程。优化属性子集可以是属性数目最小的子 集，也可以是含有最佳预测

8、准确率的子集。 实例选择使用部分数据记录代替原来所有的数据 记录进行数据挖掘，减少了挖掘时间和降低了挖掘 资源的代价，获得了更高效的挖掘性能。数据质量测评数据质量的评估指标类别描述数据的可信性精确性描述数据是否与其对应的客观实体的特征相一致完整性描述数据是否存在缺失记录或缺失字段一致性描述同一实体的同一属性的值在不同的系统是否一致有效性描述数据是否满足用户定义的条件或在一定的域值范围内唯一性描述数据是否存在重复记录数据的可用性时间性描述数据是当前数据还是历史数据稳定性描述数据是否是稳定的，是否在其有效期内成本效益成本效益是数据清洗的代价案例分析 Entity Resolution（实体解析）实

9、体解析从结构化或非结构化数据中识别、链接/分组同 一真实世界对象的不同表现形式。Matched EntityAmazon 数据集包 含1363条记录Google数据集包含3226条记录 ER的目标是找到两 个不同来源数据集 中匹配的实体。案例分析 Entity Resolution（实体解析）20实体解析问题在大数据时代的挑战首先，异构的、非结构化数据集，具有不同的数据模式与表示方法，甚至存在数据质量问题其次，ER算法是可扩展的，并在集群中并行计算第三，从大规模数据集中找到匹配的实体，需要设计时空代价与 通信开销高效的算法案例分析 Entity Resolution（实体解析）实体解析问题的算

10、法流程Record similarity measureEvaluation and AnalysisPrecisionRecallF-measuresInverted indexCosineSimilarityEntityResolutionAmazon “b000hkgj8k” TF-IDF：autocad: 0.883, autodesk: 0.383, courseware: 0. (b00005lzly,http:/ load and preprocessloadData parseDataRDDTupleTF-IDF computingtokenizationdataUnion T

11、F-IDFBroadcast variable目录概述1数据质量及评估2分布式数据处理模型及测试3大数据的基准测试4大数据处理框架Hadoop在大数据领域中，Hadoop是最著名的大数 据处理框架之一，它以可靠、高效、可伸 缩的方式进行大数据的储存、处理和分析。Hadoop由Apache基金会开发，在其实现的 过程中，借鉴了Google的三大核心组件即 GFS、MapReduce 和BigTable。Hadoop的生态圈Hadoop已发展成包含HDFS、MapReduce、YARN、Hbase、ZooKeeper等子项目的集合，用于处理和分析大规模数据MapReduce运行流程应用Master

12、workerworkerworkerworkerworkeroutput file 0Split 0Split 1Split 2Split 3Split 4输入文件Map阶段中间结果Reduce阶段输出文件(3) read(5) remote read(4) local write(6) write(1) fork(1) fork(1) fork(2)assign reduce(2)assign mapoutput file 1MapReduce示例WordCountMapReduce示例WordCount代码（Mapper）MapReduce示例WordCount代码（Reducer）Map

13、Reduce示例WordCount代码（Main）大数据单元测试MRUnit工具30MRUnit-Cloudera公司开发的针对MapReduce的单元测试框 架，其基本原理是利用JUnit4与EasyMock。MRUnit结构简 单，依赖于JUnit的单元测试功能，同时已经通过实现Mock 对象控制OutputCollector操作并且拦截OutputCollector的输 出，对比期望结果以达到自动断言的目的。MRUnit的driverMapDriver：测试单独的MapReduceDriver：测试单独的ReduceMapReduceDriver：将Map与Reduce连贯起来测试Pip

14、elineMapReduceDriver：将多个MapReduce贯串起来测试MRUnit使用：下载MRUnit的jar包，添加到Hadoop的开 发环境的Classpath路径中MRUnit示例以下为Map和Reduce测试的例子。模拟两条记录 的输入：CDRID595877;462198;737283;CDRTypePhone1Phone2SMS Status Code1;747382938472839;0;342839402839482;1;232329483034893;.;898783728372812;238473920384932;384938271928374;.;532“.;

15、查找所有CDRType为1的记录，并根据SMS Status Code进行统计Mapper期望的输出应该是：5,13,1Mapper的单元测试Testpublic void testMapper() mapDriver.withInput(new LongWritable(), new Text( 595877;1; 747382938472839;898783728372812;5);/指定输入mapDriver.withOutput(new Text(5), new IntWritable(1);/预期输出mapDriver.runTest();/运行测试Reducer的单元测试Testp

16、ublic void testReducer() List values = new ArrayList(); values.add(new IntWritable(1);values.add(new IntWritable(1); reduceDriver.withInput(new Text(“5”), values); /指定输入reduceDriver.withOutput(new Text(5), new IntWritable(2);/预期输出 reduceDriver.runTest(); /运行测试MapReduce调试与测试的建议尽早采用MRUnit编写对MapReduce中

17、的Map函数与Reduce 函数进行测试通过Assert（断言）来使得程序满足正确性条件，并通过print语句输出可能的错误首先在本地运行小规模测试数据，再到集群上运行MapReduce程序通过Hadoop日志来分析MapReduce程序运行状况目录概述1面向数据质量的测评2分布式数据模型及测试3大数据的基准测试4大数据的基准测试 基准测试（Benchmark Testing）一种测量和评估软件 性能指标的典型活动。可以在某个时候通过基准测试建立 一个已知的性能水平（称为基准线），当系统的软硬件环 境发生变化之后再进行一次基准测试以确定那些变化对性 能的影响。基准测试领域，最著名的组织是TPC

18、（Transaction Processing Performance Council），TPC主要职责是制定数 据库（数据仓库）领域基准程序的标准规范、性能、性价 比度量的指标。 OLTP基准-TPC-A面向银行事务管理、TPC-C面向仓库订单管理、TPC-E面向市场交易应用 OLAP基准-TPC-DS、TPC-H等OLAP的基准，评测考察复杂查询处理能力；SQL-On-Hadoop基准测试案例分析星环科技SQL-on-Hadoop产品 Transwarp Inceptor 架构图SQL-On-Hadoop基准测试案例分析基准测试内容 功能测试数据加载、数据压缩、数据建表、数据分区、数据 查

19、询 性能测试测试500GB数据（TPC-DS基准数据）规模下SQL查 询的时间效率 兼容性测试测试数据查询的SQL语句是否符合SQL 99和SQL2003标准中的核心SQL及OLAP测试方法SQL-On-Hadoop基准测试案例分析测试数据与SQL的生成 通过TPC-DS 基准提供的DSTools v1.3.0生成测试数据，考虑到测 试环境磁盘的容量及HDFS的复制存储机制，选择500GB的数据总 量，并选用TPC-DS为MySQL生成的99个查询SQL，目的是保留各 种复杂SQL查询，客观反映Transwarp Inceptor在SQL支持与兼容性 的情况。 TPC-DS的基准测试有以下特点

20、：一共99个测试案例，遵循SQL99和SQL 2003的语法标准，SQL案例比较复杂分析的数据量大，并且测试案例是在回答真实的商业问题测试案例中包含各种业务模型（如分析报告性，迭代式的在线 分析性，数据挖掘性等）几乎所有的测试案例都有很高的IO负载和CPU计算需求SQL-On-Hadoop基准测试案例分析40建表与数据分区利用DSTools v1.3.0工具建测试数据仓库与数据表数据压缩与加载考虑到查询优化，测试将采用ORC （Optimized Row Columnar）文件 格式存储原始数据，原始生成的text格式的数据总量大约为500G，转成 ORC格式后将压缩为大约150G。查询执行利

21、用DSTools v1.3.0工具生成的99个查询SQL，并参考TPC-DS 基准规 范并行执行SQL，测试Transwarp Inceptor SQL查询的可靠性、时间性能 及兼容性。SQL-On-Hadoop基准测试案例分析Transwarp Inceptor性能报告在Transwarp Inceptor中执行由DSTools v1.3.0工具生成的99个符合 SQL99与SQL 2003标准的SQL，记录每条SQL三次执行的平均执行时间。 Transwarp Inceptor 在500GB数据，数据库事实表规模1800万-14.4亿条记 录的情况下，执行99个SQL查询，SQL执行时间如

22、下：SQL数目（个）SQL分类总执行时间（秒）平均执行时间（秒）9交互式查询19721.969统计分析7705111.710迭代计算4232423.211数据挖掘3502318.4三、大数据智能算法及测评概述1聚类算法及测评2分类算法及测评3推荐系统及测评4概述 如何从大规模、动态的、异构的数据中， 利用智能算法处理与挖掘有价值的信息， 已成为大数据研究与应用的重要方向这部分主要从大数据的算法层面介绍大数据测评方法数据的聚类和分类是机器学习与数据挖掘领域 的经典算法，大数据时代仍有广泛应用个性化推荐系统是面向终端用户的典型应用，在电子商务、音乐视频网站等有着广泛的应用概述大数据基础算法大规模数

23、据集 聚类算法与评估层次聚类 流聚类大数据应用算法推荐系统算法与评估大规模数据集 分类算法与评估支持向量机 k近邻K-均值朴素贝叶斯物品聚类用户行为分类用户聚类支撑应用推荐算法目录概述1聚类算法及测评2分类算法及测评3推荐系统及测评4聚类及其在大数据中的应用聚类算法：将大量的具有相似特征的对象聚集到不同的簇中聚类的目的：在海量或难以理解的数据集里 发现层次与规律，让数据集更容易被理解聚类算法的特征：不需要预先标注数据集， 属于无监督机器学习算法聚类的应用： 识别某个主题相关的问题，比如新闻聚类 根据用户的职业、收入、购买习惯等属性进行用户聚类聚类及其在大数据中的应用图百度新闻聚类实例图上海商圈

24、聚类实例聚类及其在大数据中的应用特征选择 或抽取数据集聚类算法设 计或选择 聚类算法测试 与评估结果的展示 与解释聚类有价值的知识图聚类分析的流程聚类的典型算法及分析-层次聚类 层次聚类的基本思想：一开始将每个点都 看成一个簇，算法通过合并两个小簇而形 成一个大簇，直到簇聚类满足某些条件从 而结束聚类过程。.1 (2,2)2 (3,4).3 (5,3).5 (5,9)4 (4,8).6 (7,7).8 (9,3) .9 (10,2).7 (10,4)聚类的典型算法及分析-层次聚类首先将每个点视为一个簇Ci, i = 1 m；找出所有簇中距离最近的两个簇 Ci、Cj ；合并Ci、Cj为一个新簇；

25、若目前的簇数多于预期的簇数，则重复步骤2-步骤4，直到簇数 满足预期的簇数。While number of nodes 1 Repeat for i = 1 to mfor j = i + 1 to mi, j merge node(i) and node(j)delete node(i) and node(j) update nodes list注：基本的层次聚类算法效率不高，其算法复杂度为O(n3)，可以通过将所有点对的距离 保存在一个优先队列中，将算法优化为O(n2 log n)。层次聚类的思想非常，但一般应用于 规模较小的数据集。50聚类的典型算法及分析-K-均值聚类K-均值聚类的基本

26、思想：即按照某一顺序依 次遍历所有点，将点分配到最合适的簇中K-均值假定在欧式空间下，聚类数K已知，算法接受一个未标记的数据集，然后将数据聚类成K个不同的簇聚类的典型算法及分析-K-均值聚类 首先选择K个点，称为聚类质心（通常随机选择）； 遍历数据集中的每一个点，按照距离K个质心的距离，将其与距离最 近的质心关联起来，与同一个质心相关联的所有点聚成一类； 计算每一类中所有点位置的均值（新的质心），将该类的质心移动到新质心位置； 重复步骤(2)-步骤(4)，直到满足收敛要求（如质心不再变化）。Repeat for i = 1 to m i : = from 1 to K ifor k = 1 t

27、o K 注：K-均值聚类的算法复杂度为O(mkt)，其中m为需要处理的点数、k为聚类质 心数、t为迭代的次数。聚类的典型算法及分析-K-均值聚类图 K-均值算法的动态迭代聚类的并行化为什么需要并行化？ 大数据时代，聚类算法所面临的数据规模越来越大 聚类算法的算法复杂度比较高，而且数据处理受限于内存Ki数据集 0Mapper 1Ki 代表第i次迭代的 质心的描述Mapper 2Mapper n数据集 1数据集 nReducer 1Reducer kKi - Ki-1 阈值i=i+1Ki-1聚类结束图 基于MapReduce的K-均值算法聚类的并行化Mapper任务的伪代码如下：Input：dat

28、aset and cluster centroids description fileOutput： for each point do beginkey:=cluster centroid listvalue:=index of point belongs to some cluster centroidoutput:Reducer任务的伪代码如下：Input: the key and the value output by map function Output: for each centroid do beginkey:=cluster centroid listvalue:= new

29、 centroid position output:注：MapReduce编程模型并不直接支持迭代模型，因此需要额外编写驱动程序来判断迭代是否终止， 若迭代没有终止，则需要驱动MapReduce程序重新执行任务，直到满足终止条件。Mapper任务：将数据集分成子集并与质心描 述文件一起发送到各个Map节点，每个Map 节点分别执行任务，即将子集中的数据分配 给最近点的质心，并以所属簇质心为key，点 的索引为value，组成中间结果传递到Reducer 节点。Reducer任务：得到中间结果后将属于同一簇的点计算新的质心。 比较新的质心与原有的质心是否一致，如果 一致，代表算法已收敛，否则仍需

30、进一步迭 代，即更新质心描述文件，重新运行整个作 业。大数据智能算法测试的方法论分析智能算法解决问题的领域 需要分析问题的领域与算法的类别 需要分析算法设计者可能没考虑到的数据特征分析智能算法的定义及代码 检查算法的定义是否精确 分析算法的定义及代码，可以推测缺陷可能出现的区域，从而创建测试集来发现潜在的算法缺陷分析智能算法运行时的选项 检查这些算法运行时选项是如何处理或操作输入数据，从而 设计数据集和测试方法，并在输入数据的操作中可能发现缺 陷或不一致智能算法测试的测试方法-蜕变测试蜕变测试的基本观察 测试成功的测试用例没有被进一步有效利用与挖掘，而这些测试用例很可能蕴含着有价值的信息。 软

31、件测试存在“测试准则（Oracle）问题”。注：测试准则，即是确认程序输出正确性的机制。所谓测试准则问题就是不存在测试准则， 或者没有可靠的测试准则，或者即使有测试准则但应用代价非常高。蜕变测试的基本思想 利用这些成功的测试用例，并根据蜕变关系创建衍生（follow-up） 测试用例，然后分析这两类测试用例测试后的结果是否满足蜕变 关系，从而判断程序是否存在缺陷。蜕变测试是一种可有效解决智能算法测试的软件测试方法，它能在一定程度上 解决由于这类软件没有可靠“测试准则”问题带来的挑战。智能算法测试的测试方法-蜕变测试蜕变测试的形式化定义 定义1：假设程序P 用来计算函数f, x1, x2, ,

32、xn, n 1是f的n个变量, 且f(x1), f(x2) , f(xn)是它们所对应的函数值。若x1, x2, , xn, 之间 满足关系r 时, f(x1), f(x2) , f(xn) 满足关系rf 即r(x1, x2, , xn ) rf(f(x1), f(x2) , f(xn)，则称 (r, rf) 是P 的蜕变关系(MetamorphicRelation, MR)。测试人员可以通过检查分析上述推导式是否成立来判断程序P的正确性。 定义2：使用蜕变关系(r, rf)测试程序P时, 起初选择的测试用例称为原 始测试用例； 由原始测试用例根据关系r计算得出的测试用例是该原 始测试用例基于

33、蜕变关系(r, rf)的衍生测试用例。智能算法测试的测试方法-蜕变测试蜕变测试的原理 第一，结合其它测试用例选择的策略（比如路径覆盖测试或等价类划分等）为待 测程序P生成原始测试用例x0； 第二、利用这些原始测试用例来测试程序，若都通过测试，且计算结果P(x0)，然 后进一步分析待测程序的特点，设计构造一系列蜕变关系； 第三，根据这些蜕变关系生成衍生测试用例r1(x0)，r2(x0)，并计算衍生测试用例得到测试结果为P(r1(x0)和P(r2(x0)； 第四，分析原始测试用例的计算结果P(x0)与衍生用例的输出P(r1(x0)、P(r2(x0) 是否满足蜕变关系rf1与rf2，如果满足蜕变关系

34、则测试通过，否则说明待测程序P 可能存在缺陷。1.sin 37.5 ，p(x) = 0.6078（正确吗？）2.MR1: sin x= sin(180 x)3.x = 180 x = 142.54.P x= 0.60825.通过比较P(x)和P x 的值，可以发现它 们之间不满足蜕变关系MR1，因此程序P 中存在缺陷基于蜕变测试的聚类算法测试构造蜕变关系（以K-均值为例）MR 1.1： 属性全局仿射变换的一致性。如果对原始测试用例中的每个属性值(i)做仿射变换( i ) = (i) + ( 0)得到衍生测试用例，则聚类结果不变。60MR 1.2： 属性局部仿射变换的一致性。 如果对原始测试用例

35、中的每个属性列做仿射变换() = + ( 0)得到衍生测试用例，则聚类结果不变。()()()MR 2.1： 数据样本行置换。如果对原始测试用例中的任意两行数据样本做行置换得到衍生测试用例, 则聚类结果不变。MR 2.2： 数据样本列置换。 如果对原始测试用例中的任意两列属性做列置换得到衍生测试用例, 则 聚类结果不变。MR 3：增加不提供信息属性。在原始测试用例的基础上，增加一列属性，增加的属性值全部相同， 即这列属性值与原始测试用例中属性信息无关，得到衍生测试用例，则聚类结果不变。MR 4 ：复制单个数据样本。在原始测试用例基础上, 增加一个数据样本，增加的样本与原始测试用例中某一个样本相同

36、，得到衍生测试用例，则聚类结果不变。基于蜕变测试的聚类算法测试表基于蜕变测试的测试结果及K-均值算法的适用性分析MR预期结果K-均值算法的适用性分析MR 1.1Y属性全局仿射变换的一致性MR 1.2Y属性局部仿射变换的一致性MR 2.1N初始聚类质心的改变将影响聚类结果MR 2.2Y对数据维的顺序不影响聚类结果MR 3Y增加一列无关属性（属性值相同），不改变聚类结果MR 4N增加重复数据样本将改变聚类结果关于蜕变测试应用于大数据智能算法的思考 蜕变测试是一种非常有效、而且容易实现的自动化测试方 法，除了以上的K-均值聚类算法、朴素贝叶斯分类算法测 试以外，还可以应用于其它大数据智能算法，如支持

37、向量 机、K-近邻等算法等。 应用蜕变测试的关键是设计合理、高效的蜕变关系，这些 蜕变关系可以从不同路径、不同方面来检查程序的缺陷。 将蜕变测试应用于大数据智能算法的测试时，还需要考虑 结合其它测试方法，比如随机测试、变异测试等来生成大 规模、高效的测试用例聚类质量的评估外部指标-即计算聚类结果与已有的标准分类结果的吻合程度（1）F-Measure -利用信息检索中的准确率（Precision）与召回率（Recall）思想来进行聚类质量的评价。 , = , =其中，Nij代表类簇j中类别为i的样本数，Nj代表类簇j样本数，Ni代表类别i中的样本数。F-Measure是对查准率与查全率的加权调和

38、平均，其计算公式为： , =2 , (, ) , + (, )整个聚类结果的F-Measure由每个分类i的加权平均得到，其计算公式为： = , 其中，N代表聚类的总样本数。 , = 3 4F-Measure的值越高，则聚类的效果越好。 , = 3 3类簇j的样本类别i的样本Precison与Recall计算实例聚类质量的评估（2）信息熵指标假设数据集C可以分K个簇，其样本数为N，其中类簇Ci的样本数为Ni,则该类簇的信息熵定 义为：Entropy = 1 =1其中q为数据集中类簇的数目，Ni表示类簇Ci与类簇Cj的交集，整个聚类结果的信息熵定 义为：jEntropy = Entropy =1

39、信息熵反映了同一类样本在结果簇中的分散度，同一类样本在结果簇中越分散，则信 息熵值越大，聚类效果越差。当同一类样本属于一个类簇时，信息熵值为0。聚类质量的评估（3）Rand指数和Jaccard指数设数据集X的聚类结果类簇为C = C1, C2, , Cm ，数据集的真实分类为P = P1, P2, , Ps ，C中的类数 m和P中的类数s不一定相同，可以通过对C和P进行比较来评估聚类结果的质量。对数据集中任一对点 xi, xj 计算下列项：a两点属于中同一簇，并且属于中同一类； b两点属于中同一簇，并且属于中不同类； c两点属于中不同簇，并且属于中同一类； d两点属于中不同簇，并且属于中同一类

40、；a和d用来描述两个分类的一致性，b和c用来描述聚类对于真实分类的偏差。C和P的相似程度可以用Rand指数和Jaccard指数来定义：Rand指数： R = a +b a+b+c+dJaccard指数： J = a a+b+cRand指数和Jaccard指数用于度量聚类算法的聚类结果与真实分类的相似度，显然Rand指数 R值越大， 相似程度越好，聚类效果就越好；同理，Jaccard指数J越小，聚类效果越差。聚类质量的评估内部指标-不依赖于外部信息，如分类的先验知识。内部指标的评估是直接从原始数据集中检查聚类的效果。（1）簇内误差 -即任意点与其质心的距离的平方和。V = (, )2 其中，C为

41、所有的簇，k 是Ck 的质心，(,)是距离度量函数，即数据点xi 与其对应的簇的质心的距离。 因此簇内误差越小，聚类效果越好。（2）Cophenetic相关系数层次聚类得到的树形图可用Cophenetic矩阵表示，的元素 是数据 和首次在同一个簇中的距离 值，是数据点的相似性矩阵，的元素为。Cophenetic相关系数可度量层次聚类的质量，公式定义如 下： =( 1 1) =1=+1 ( 1 ) 1 2 2 1 =1=+1=1=+1 2 2其中， = ( 1)/2，是数据的个数；和分别是矩阵和的均值； 的取值范围是 1,1， 的值越接近1，说明两个矩阵相关性越好，层次聚类的效果越好。目录概述1

42、聚类算法及测评2分类算法及测评3推荐系统及测评4分类及其在大数据中的应用 分类算法：根据数据集的特点构造一个分类模型（也 称为分类器），该模型能把未知类别的样本，自动映 射到某一指定类别。分类的目的：计算机判断一个对象是不是属于某种类型，或者该对象是不是含有某些属性 分类算法的特征：需要事先定义好类别，并对训练样 本进行人工标记，属于有监督机器学习算法分类的应用： 判断预测某一次交易是否为行用卡诈骗 判断某一张图片的内容是否属于某一种类型分类及其在大数据中的应用分类算法已标记类别的 训练样本分类算法测试与验证分类器预测类别新的样本图分类的流程分类的典型算法及分析-朴素贝叶斯分类算法朴素贝叶斯算

43、法的基本思想： 假设x = (x1, x2, , xm)为数据集中的某一样本，其中xi是该样本的第i个特征， 并有类别集合 C = y1, y2, , yk ；可以计算概率 p y1 x , p y2 x , , p yk x ； 若p yi x = maxp y1 x , p y2 x , , p yk x ，则x yi，即x属于yi类。 朴素贝叶斯分类算法基于朴素贝叶斯假设，即在给定类别信息yi的条件下， x的特征xi之间互相独立，这也是为什么这个分类算法称为朴素贝叶斯分类 算法。 根据概率论中的贝叶斯定理：p yi x=p x yi p(yi)p(x)考虑到分母对于所有类别为常数，因此只

44、需要考虑分子部分，根据朴素贝叶斯的假设，x的特征xi之间互相条件独立，因此有：m70p x yi p yi= p x1 yip x2 yi p xm yip yi= p yi p xj yij=1分类的典型算法及分析-朴素贝叶斯分类算法朴素贝叶斯算法： 遍历整个数据集，可以统计得到在k个类别下各个特征的条件概率估计，即x1 y1 , p x2 y1 , , p xm y1 p x1 y2 , p x2 y2 , , p xm y2p x1 yk , p x2 yk , , p xm yk .根据以上的贝叶斯公式，可以计算得出p yi x ，i = 1, , k，从而预测样本x属于哪一类。 朴素

45、贝叶斯分类算法的伪代码如下：Computep x yi= mp xj yi, j = 1, , m, i = 1, , kj=1p yi ,i = 1, , karg max p(yi|x) = argyi p x yi p(yi)yi注：尽管朴素贝叶斯分类算法对于样本数据稀疏时非常敏感（需要“拉普拉斯平滑”），但仍然是应 用最广的分类算法之一，被广泛应用于文本分类领域、用户行为分析等大数据分析挖掘领域。分类的典型算法及分析-支持向量机算法支持向量机算法的基本思想： 寻找一个满足分类要求的最优分类超平面，使得该超平面在保证分类精度的 同时，能够使超平面两侧的间隔最大化。图 线性的支持向量机原理

46、图分类的典型算法及分析-支持向量机算法支持向量机算法的数学原理： 支持向量机本质上是约束最小化问题 1 min 22+ C =1+ 1 ，is. t. w = 1,2, , m 0，i = 1,2, , m其中，C是正则化因子，可以通过C来控制样本的过拟合问题；i是松弛变量分类的典型算法及分析-支持向量机算法支持向量机算法的分类实例：图 总体线性可分的例子正则化因子C=1时计算得到的分类决策边界图 线性不可分的例子采用了高斯核计算得到的分类决策边界分类算法（分类器）性能的评估分类器性能评估的方法留置法（Hold-Out）留置法的思想是把数据分为互不相交的两部分，分别称为训练集与测试集。 其中训

47、练集用于构造分类器，而测试集用于评估分类器的性能。训练集与测试 集的比例通常是2:1，即2/3的样本用于训练集，1/3样本用于测试集。分类器的性能根据模型在测试集上的准确率估计，可以定义分类性能为：/380 =1/3 ( , )=1其中，N是样本数，F(,)是分类性能的评估指标。分类算法（分类器）性能的评估分类器性能评估的方法随机子抽样（Random Subsampling）随机子抽样是留置法的改进，其通过留置法的多次迭代，每次随机形成训练集与测试集。随机子抽样的分类器性能为： = =1其中，K代表迭代的次数，Pj是第j迭代时分类器的性能。分类算法（分类器）性能的评估分类器性能评估的方法交叉验

48、证（Cross-validation） 二折交叉验证假设把数据分为相同大小的两个子集，首先选择其中一个子集作为训练集，另一个 作为测试集，然后交换两个子集的角色，这种方法称为二折交叉验证。分类总误差通过 对两次运行的误差求和得到。 K折交叉验证K折交叉验证方法是二折交叉验证的推广，即把数据集分成独立并数量相同的K份。 每次验证时选择其中的一份作为测试集，其余的 K 1 份都作为训练集，该过程重复 K 次， 使得每份数据都用于测试恰好一次。同样，分类的总误差是说有K次误差之和。分类算法（分类器）性能的评估准确性和F-Measure准确性（Accuracy）TP + TNAccuracy = TP

49、 + TN + FP + FNF-MeasurePrecision = + Recall = + F Measure =2 Precision RecallPrecision + Recall准确性值与F-Measure值越大，分类器的性能越好预测类别+-实际 类别+正确的正例（TP）错误的负例（FN）-错误的正例（FP）正确的负例（TN）分类算法（分类器）性能的评估ROC曲线与AUC的一些说明ROC曲线与AUC(FPR=0,TPR=0)意味着分类器将每个样本都预测为负例(FPR=1,TPR=1)意味着分类器将每个 样本都预测为正例(FPR=0,TPR=1)意味着最优的分类器在ROC曲线中，如

50、果曲线A始终位于 曲线B的左上方，则曲线A优于曲线BAUC，即ROC曲线下方面积（the Area Under the ROC curve，AUC）。如果 ROC曲线B的AUC值大于曲线A的值， 则B对应的分类器性能优于A。求AUC 值的最通用方法是通过积分法求ROC 曲线下方的面积。X轴是错误的正例率（False Positive Rate，FPR），FPFPR =FP + TNY轴是正确的正例率（True Positive Rate，TPR），TPTPR =TP + FNROC曲线与AUC目录概述1聚类算法及测评2分类算法及测评3推荐系统及测评4推荐系统概述 个性化推荐系统：是一种利用用户

51、历史行为数据，建 立用户行为模型，帮助用户过滤无关信息、提供最能 满足用户个性化需求信息的智能系统。推荐系统的核心流程用户特征收集模块：该模块负责收集用户的历史行为，比如评分、购买、浏览、评论等行为，这些行 为可以用来描述用户的偏好。用户行为建模与分析模块：该模块根据收集得到的用户历史行为，构建合适的数学模型来分析用户的 偏好或找出相似偏好的用户。物品的排序与推荐模块：该模块将用户的行为信息作为特征，通过推荐算法快速获得用户感兴趣的物 品，并将物品排序后推荐给用户。推荐系统的评估模块：该模块负责评估推荐系统是否满足应用的需求，常见的评估指标包括准确度、 多样性、新颖性、覆盖率等。推荐系统的应用

52、亚马逊的商品推荐Netflix的电影推荐推荐系统算法-基于内容的推荐基于内容的推荐基本思想：根据用户已经选择的物品的内容信息，为用户推荐内容上相似的其它物品。令UserProfile u 为用户u的物品偏好向量，该向量可以定义如下：UserProfile =1(u) ()(u)其中，N(u)是用户u之前偏好的物品集合，Content(s)是物品的内容向量，其可以从物品的 特征信息中获得。那么，对于任意一个用户u和一个他不知道的物品c，用户物品偏好向量 UserProfile u 与Content(c)的相似度可定义如下：s u, c= sim(UserProfile , )接下来，就可以通过比

53、如向量余弦定理度量上述两个向量的相似度，两个向量的夹角越小， 则这两个向量的距离越近，也就是这两个向量相似度越高；反之，两个向量的夹角越大，则这 两个向量的距离越远，两个向量相似度越低。优点：无需使用其它用户数据；能为爱好比较独特的用户进行推荐；能推荐新的或比较冷门的 物品；通过列出推荐物品的内容特征来解释推荐的原因缺点：仅适用于物品特征容易抽取的领域，难以挖掘出用户潜在的兴趣推荐系统算法-基于用户的协同过滤推荐基于用户的协同过滤算法基本思想：一个用户会喜欢和他有相似偏好的用户喜欢的物品用户A用户B用户C电影AA电影BB电影CC电影DD 喜欢 推荐90相似用户/电影电影A电影B电影C电影D用户

54、A推荐用户B用户C推荐系统算法-基于物品的协同过滤推荐基于物品的协同过滤算法基本思想：一个用户会喜欢和他之前喜欢的物品类似的物品92用户/物品物品A物品B物品C用户甲用户乙用户丙推荐推荐系统的测评实验推荐系统的测评仍然是推荐系统设计与应用中的一大挑战 不同的推荐算法在不同的数据集上的表现不同；某些算法可能对于小数据集 表现不错，但当数据集不断增大，算法的性能和运行速度都可能明显下降。 推荐系统的评估指标繁多，而且指标之间并不一致。评估指标包括基本的准 确度、多样性、覆盖率、惊喜度、可扩展性等。而且，准确度指标和多样性 指标本身是一对矛盾。 推荐系统的不同指标需要通过不同的测试方法来计算度量。比

55、如，准确度可 以通过离线计算，但惊喜度就需要通过用户调查才能得出，而有些指标的评 估需要在线实验获得。推荐系统的测评实验离线实验 离线实验使用现有的数据集，利用数据集对用户的行为进行建模，进而来评估 推荐系统的性能，如预测的准确度。离线实验的实施在三类实验中的代价是最 低的，也是最容易实施的。 在进行离线实验时，首先需要预先收集用户的行为数据，比如用户的选择或商 品评分的数据集，这些数据集可以模拟用户与推荐系统交互的行为。 假定收集的用户行为数据，与用户在实际的推荐系统上的行为足够的相似，基于这种假设，可以通过离线实验作出可靠的评估。 用于离线实验的数据集应该尽可能与未来部署后的系统产生的数据

56、一致。换句 话说，用于离线评估的用户行为数据（用户的评分、用户的选择等）尽可能是 无偏的。优点：不需要真实用户的交互，因此可以以较低的代价快速的测试评估各种不同的算法。 缺点：这类实验通常只能计算某一个算法的预测能力，无法评估惊喜度、满意度等其它指标。推荐系统的测评实验用户调查 要求一小部分测试用户使用推荐系统，并执行一组任务，然后回答一些关于他 们使用体验的问题。 当测试人员执行任务时，观察并记录他们的行为，收集任务完成的情况，比如 哪些任务已经完成、执行任务花费的时间、任务结果的准确性等。 可以通过用户调查让测试人员回答一些定性的问题，比如是否喜欢用户界面、或者用户对完成任务难易程度的感受

57、，这些结果一般无法直接观察得到。 需要考虑测试人员的分布问题，比如兴趣爱好、男女比例、年龄、活跃程度的 分布都应和真实系统中的用户分布尽量相同。优点：可以测试用户与推荐系统交互的行为，以及推荐系统对用户行为的影响。用户调查还 可以收集定性的数据，这些数据往往对解释定量的结果至关重要。缺点：用户调查的成本很高，一方面需要招募大量的测试人员，另一方面需要测试人员完成 大量的与推荐系统交互的任务。推荐系统的测评实验在线评估 在一个部署好的推荐系统上运行大规模测试，在线评估中通过真实的用户执行 真实的任务来测评或比较不同的推荐系统。 需要对用户进行随机采样，保证不同推荐系统的测试用户分布尽量相同，这样

58、 不同推荐系统的比较才相对公平。 如果关注推荐系统的某一项指标，那么尽量保持其它影响因素的一致性。优点：可以获得推荐系统整体性能评估，比如长期的商业利润和用户保持度，而不仅仅是某 些单一的指标。缺点：在线评估测试是有一定风险的。推荐系统的评估基于机器学习视角推荐算法的预测准确度度量Mean absolute error（平均绝对误差）： =1 (,) Mean Square Error（均方误差）： =1 ( )2(,)Root Mean Square Error（均方根误差）： =1 ( )2(,)推荐系统的评估基于信息检索视角基本的决策支持度量与基于排名的度量准确率、召回率、F-Measu

59、re准确率 = 或 = 用户喜欢的物品的比例召回率 = 2 不遗漏用户喜欢物品的比率 = + 其中，Nrs是推荐物品中用户喜欢的个数、Ns是推荐的物品数，n代表前n个推荐项Nr是用户喜欢的物品数。推荐系统的评估基于信息检索视角基本的决策支持度量与基于排名的度量平均准确率（Mean Average Precision，MAP）：多个推荐准确率的平均值，推荐的相关物品 越靠前，平均准确率越高 = ()=1，其中 =1# relevant itemQ为物品推荐的次数，k是排名，rel k 代表给定排名的相关性函数，p k 代表给定排名的 精度。ROC曲线ROC曲线也适用于推荐系统的评估，可以通过RO

60、C曲线来调整推荐系统的参数，比如可以 找到推荐系统错误的正例率与正确的正例率之间的折中。此外，通过AUC还可以比较不同推荐 系统的性能。100推荐系统的评估101基于信息检索视角基本的决策支持度量与基于排名的度量平均倒数排名（Mean Reciprocal Rank，MRR）：其概念来自信息检索系统，希望越相关的 检索结果应该排在越前面。平均倒数排名应用于推荐系统时，可以度量推荐系统是否将用户 最喜欢的物品排在最前面，其定义如下： = 1/ = 1 其中，Q为物品推荐的次数，ranki为用户最喜欢的物品的在推荐列表中的排名。 显然MRR的值越大，推荐系统的性能越好。推荐系统的评估基于信息检索视