数据预处理与知识发现

为什么要进行数据预处理？
因为在现实生活中存在着大量的“脏”数据

• 数据不完整的性
• 数据有噪音数据
• 数据不一致性

技术主要四种：数据清理，数据集成，数据变换，数据归约

数据清洗：

主要删去数据中的重复数据，消除数据中的噪音数据，纠正不完整和不一致的数据

噪声数据是指数据中存在着错误或异常(偏离期望值)的数据;
不完整数据是指数据中缺乏某些属性值:
不一致数据则是指数据内涵出现不-致情况(如作为关键字的同一部门编码出现不同的值)。

产生原因：
◆数据采集设备有问题
◆与其他已有数据不一致而被删除
◆因为误解而没有被输人
◆在输人时，有些数据因为得不到重视而没有被输人
◆对数据的改变没有进行日志记载

解决方法:

• 人工填写
• 使用一个全局变量填充
• 使用属性的平均值填充

数据清洗处理过程:

• 填补遗漏的数据值
• 平滑有噪声的数据
• 识别或除去异常值
• 解决不一致问题

数据集成：

数据集成是将这些数据源中的数据集中存放在一个统一的数据存储(如数据仓库)中。
数据集成能够减少或避免数据的冗余和不一致性，将有助于提高数据挖掘的精度和效率。

数据转换：

当原始数据的形式不适合数据挖掘算法需要的时候，就要进行数据转换，为了使数据和将来要建立的模型拟合得更好，形成适合挖掘的形式。
数据转换主要涉及平滑、聚集、数据概化、规范化以及属性构造等内容。

数据归约：

在尽可能保持数据原貌的情况下，最大限度地精简数据量，因此也称为数据消减。
主要有两种途径:属性选择和数据采集
分别针对原始数据中的属性和记录，缩小所挖掘数据的规模，提高挖掘的效率，并能产生相同的效果

常用的数据归约策略包括:：数据立方体、聚集、维归约、数据压缩、数值压缩、离散化和概念分层产生等。

知识发现：

广义知识发现

数据立方体是实现某些常用的、代价较高的聚集函数的计算。
面向属性的归约则是以类SQL语言表示数据挖掘查询，收集数据库中的相关
数据集，然后在相关数据集上应用一系列数据推广计数进行数据推广技术。

狭义知识发现

关联知识发现–反映一个事件和其他事件乏间依赖或关联。
从资料集合中找出所有的高频项目组;由这些高频项目组中产生关联规则。

分类知识发现–反映同类事物共同性质的特征型知识和不同事物乏间的差异型特征。
常用的数据分类方法有决策树、统计粗糙集、线性回归和神经网络等。

预测知识发现–由历史的和当前的数据去推测未来的数据，也可以认为是以时间为关键属性的关联知识发现。
常用的预测方法有经典的统计方法、神经网络和机器学习等。

数据挖掘

数据发掘的方法:

• 关联分析
• 分类分析
• 聚类分析

若两个或多个变量的取值之间存在某种规律性，就称为关联。
关联分析:指从一个项目集中发现关联规则，该规则显示了给定数据集中经常一起出现的属性-值条件元组。
例如:关联规则X=>Y所表达的含义是满足X的数据库元组很可能满足Y。关联分析在交易数据分析、支持定向市场、商品目录设计和其他业务决策等方面有着广泛的应用。

关联分析算法–Apriori

该算法利用频繁项集所具有的任意频繁项集的子集都是频繁项集的这一性质对数据库进行多次扫描:第一次扫描得到频繁项集的集合L0，第K趟扫描前先利用上次扫描的结果项目集Lk-1,产生候选K项集的集合Ck，然后再通过扫描数据库确定C中每一候选K项集的支持数，最后在该次扫描结束时求出频繁K项集的集合Lk，算法的终止条件是Ck或Lk为空。

优点：所产生的候选项集少，效率高。它被视为关联规则挖掘最经典的算法，其他很多算法都是其变种或改进。
缺点：可能产生大量的候选集以及可能需要重复扫描数据库。
为了对其进行改进，Han等提出了不产生候选挖掘频繁项集的方法-----FP–树频繁集算法。

分类分析

分析一个类别己知的数据集的特征来建立一组模型，该模型可用以预测类别未知的数据项的类别。
表现形式:分类规则，决策树或者数学公式，乃至神经网络

分类分析的实现主要有两个步骤:

第一步构建模型:
对每个样本进行类别标记。
先假设一个样本集合中的每一个样本属于预先定义的某一个类别，这可由一个类标号属性来确定。这些样本的集合称为训练集，用于构建模型。最终的模型即是分类器，可以用决策树、分类规则或者数学公式等来表示。
第二步使用模型:
运用分类器对未知的数据对象进行分类。
模型正确性的评价是用已标记分类的测试样本与模型的实际分类结果进行比较，模型的正确率是指测试集中被正确分类的样本数与样本总数的百分比。测试集与训练集相分离，否则将出现过批合现象。

聚类分析

聚类分析又称为“同质分组”或者‘无监督的分类”，指把一组数据分成不同的“簇”，每簇中的数据相似而不同簇间的数据则距离较远。相似性可以由用户或者专家定义的距离函数加以度量。
好的聚类方法应保证不同类间数据的相似性尽可能地小，而类内数据的相似性尽可能地大。

常用的聚类分析方法:

基于划分的聚类方法
给定一个由n个对象组成的数据集合，对此数据集合构建k个划分(k≤n),每个划分代表一个簇，即将数据集合分成多个簇的算法。
要求:①每个簇至少有一个对象②每个对象必须且仅属于一个簇
典型算法k-均值和k-中心点算法等

基于层次的聚类方法
基于层次的聚类方法对给定的数据集合进行层层分解的聚类过程，包括凝聚法和分裂法凝聚法指起初每个对象被认为是一个簇，然后不断合并相似的簇，直到达到一一个令人满意的终止条件。
分裂法先把所有的数据归于一个簇，然后不断分裂彼此相似度最小的数据集，使簇被分裂成更小的簇，直到达到一个令人满意的终止条件。
常用的距离度量方法包括:最小距离、最大距离、平均值距离和平均距离等。

基于密度的聚类方法
该算法通过不断生长足够高密度区域来进行聚类；它能从含有噪声的空间数据库中发现任意形状的聚类。此方法将一个聚类定义为一组“密度连接”的点集
。
基于网格的聚类方法
首先将对象空间划分为有限个单元以构成网格结构；然后利用网格结构完成聚类。
STING 就是一个利用网格单元保存的统计信息进行基于网格聚类的方法。
基于模型的聚类方法
它假设每个聚类的模型并发现适合相应模型的数据
统计方法COBWEB:是一个常用的且简单的增量式概念聚类方法。它的输入对象是采用符号量（属性-值）对来加以描述的。
采用分类树的形式来创建一个层次聚类

MapReduce

MapReduce是面向大数据并行处理的计算模型、框架和平台，它隐含了以下三层含义：
1）MapReduce是一个基于集群的高性能并行计算平台。它允许用市场上普通的商用服务器构成一个包含数十、数百至数千个节点的分布和并行计算集群。
2）MapReduce是一个并行计算与运行软件框架。它提供了一个庞大但设计精良的并行计算软件框架，能自动完成计算任务的并行化处理，自动划分计算数据和计算任务，在集群节点上自动分配和执行任务以及收集计算结果，将数据分布存储、数据通信、容错处理等并行计算涉及到的很多系统底层的复杂细节交由系统负责处理，大大减少了软件开发人员的负担。
3）MapReduce是一个并行程序设计模型与方法）。它借助于函数式程序设计语言Lisp的设计思想，提供了一种简便的并行程序设计方法，用Map和Reduce两个函数编程实现基本的并行计算任务，提供了抽象的操作和并行编程接口，以简单方便地完成大规模数据的编程和计算处理
核心思想：

功能：

数据划分和计算任务调度
系统自动将一个作业（Job）待处理的大数据划分为很多个数据块，每个数据块对应于一个计算任务（Task），并自动 调度计算节点来处理相应的数据块。作业和任务调度功能主要负责分配和调度计算节点（Map节点或Reduce节点），同时负责监控这些节点的执行状态，并 负责Map节点执行的同步控制
数据划分和计算任务调度
为了减少数据通信，一个基本原则是本地化数据处理，即一个计算节点尽可能处理其本地磁盘上所分布存储的数据，这实现了代码向 数据的迁移；当无法进行这种本地化数据处理时，再寻找其他可用节点并将数据从网络上传送给该节点（数据向代码迁），但将尽可能从数据所在的本地机架上寻 找可用节点以减少通信延迟
系统优化
为了减少数据通信开销，中间结果数据进入Reduce节点前会进行一定的合并处理；一个Reduce节点所处理的数据可能会来自多个 Map节点，为了避免Reduce计算阶段发生数据相关性，Map节点输出的中间结果需使用一定的策略进行适当的划分处理，保证相关性数据发送到同一个 Reduce节点；此外，系统还进行一些计算性能优化处理，如对最慢的计算任务采用多备份执行、选最快完成者作为结果
出错检测和恢复
以低端商用服务器构成的大规模MapReduce计算集群中，节点硬件（主机、磁盘、内存等）出错和软件出错是常态，因此 MapReduce需要能检测并隔离出错节点，并调度分配新的节点接管出错节点的计算任务。同时，系统还将维护数据存储的可靠性，用多备份冗余存储机制提 高数据存储的可靠性，并能及时检测和恢复出错的数据

Spark

专为大规模数据处理而设计的快速通用的计算引擎

• 运行速度快
• 运行模式多样
• 通用性
• 容易使用

Scala语言
◆Scala是一门现代的多范式编程语言
◆Scala具备强大的并发性，支持函数式编程，可以更好地支持分布式系统
◆Scala语法简洁，能提供优雅的API


运行架构

• RDD，是Spark-个非常基础的概念
• DAG，有向无环图的简称，反映了RDD之间的依赖关系
• Executor,是运行在各个工作节点上的一个进程，负责运行Task
• Application,它是用户编写的Spark应用程序
• Task,运行在Executor上的工作单元
• Job,包含多个RDD及作用于相应RDD上的各种操作
• Stage,是Job的基本调度单元
  

优点：

• 利用多线程来执行具体的任务，减少了任务的启动开销
• Executor中有一个BLockManager存储模块，会将内存和磁盘共同作为存储设备，有效减少10开销

文本检索

文本检索
文本检索是围绕相关度展开的
◆基于文字的检索
◆基于结构的检索
◆基于用户信息的检索

向量空间模型
关键字和权重组成向量
◆把对文本内容的处理简化为向量空间中的向量运算，并且它以空间上的相似度表达语义的相似度，直观易懂。
◆当文档表示为文档空间的向量的时候，可以通过计算向量之间的相似性来度量度量文档之间的相似性。

概率模型-查询中的关键字在相关和不相关文档中的概率。
概率检索模型是当前信息检索领域效果最好的模型之一，它基于对已有反馈结果的分析，根据贝叶斯原理为当前查询排序。
这个比值越大，代表该文档与查询的相关度越大，因此我们就把该比值看做是相关度得分将文档排序。
概率模型原理
◆对于-一个查询q,已知文档集中哪些与q是相关的( 这类文档的类标号记为C1)，哪些与q是不相关的(这类文档的类标号记为C0)。
◆概率检索模型的核心是对于每一个文档X，通过概率公式计算出文档X属于“相关”类的概率与属于“ 不相关”类的概率的比值。
◆这个比值越大，代表该文档与查询的相关度越大，因此我们就把该比值看做是相关度得分将文档排序。

统计语言模型-通过语言的方法将查询和文档联系起来
◆统计语言模型(Statistical Language ModeL)即是用来描述词、语句乃至于整个文档这些不同的语法单元的概率分布的模型。
◆区别于其他大多数检索模型从查询到文档(即给定用户查询，如何找出相关的文档)

流媒体检索

图像检索

基于内容的图像检索
◆将视觉特征，例如颜色、纹理结构和形状等，作为图像内容抽取出来进行匹配查找
◆特征提取(颜色、纹理、形状)
◆查询方式:示例查询和草图查询
基于语义的图像检索
◆利用系统知识的语义提取(特定应用领域)
◆利用系统的交互(人工标注)
◆基于外部信息

音频检索

◆原始音频预处理(语音处理、音频分隔、特征提取)
◆长音频分割，获得结构关系:特征提取记人特征数据库;分类，建立分类目录;转换成文本，记人文本库
◆用户查询(提交查询的音频信号，返回结果;或者浏览库)

视频检索：目标检测、目标跟踪、目标识别、行为分析、基于内容的视频检索。

◆目标检测(Object Detection)
按一定时间间隔从视频图像中抽取像素,采用软件技术来分析数字化的像素，将运动物体从视频序列中分离出来。运动目标检测技术是智能化分析的基础。
◆目标跟踪（Object Tracking）
不需要目标识别，可以根据运动特征来进行跟踪，而无需确切知道跟踪的是什么，所以如果利用视频画面之间（帧之间）的临时关系，单纯的目标跟踪可以很高效的实现。
◆目标识别(Object Recognize)
利用物体颜色、速度、形状、尺寸等信息进行判别，区分人、交通工具和其他对象。
目标识别常用人脸识别和车辆识别。