数据仓库数据挖掘知识梳理
1 数据分析的基本步骤有哪些？每个步骤的主要工作
2 关于大数据的4V理论是什么？
数据规模大
从TB跃升到PB甚至EB。
数据类型多
越来越多非结构化数据；音频、 食品，地理位置信息等多类型数 据对数据处理能力提出更高要求。
数据价值高
海量数据带来了巨大的商业价值。数 据之间关联性支持深层的数据挖掘。
数据处理速度快
对数据实时处理有着极高的要求， 通过传统数据库查询方式得到的 “当前结果”很可能已经没有价值。
3 四种基本度量尺度适用的集中趋势和离散度量方法有哪些？
按照对事物计量的精确程度，可将所采用的计量尺度由低级到高级分为四个层次：
定类尺度(Nominal Level)
定序尺度(Ordinal Level)
定距尺度(Interval Level)
定比尺度(Ratio Level)
定类数据：众数
定序数据：中位数
定距和定比数据：平均数（均值）
众数、中位数和均值的比较
数据的离散程度即衡量一组数据的分散程度如何
定类数据：异众比率
定序数据：四分位差
定距和定比数据：方差和标准差
相对离散程度：离散系数
4 数据对象的相似性有哪些方法
5 数据属性的相关性有哪些方法（斯皮尔曼等级相关系数，皮尔森）
•相关性计算：
•相合系数
•（二元，标称类型）
•二元属性相关性
•多元属性相关性
•等级相关系数
•（序数类型）
•Gamma统计量
•斯皮尔曼等级相关系数
•Kendall´s Tau-b系数
•简单相关系数
•皮尔森（Pearson）简单相关系数
•夹角余弦
•相关指数
6 数据预处理的主要任务有哪些？每个任务要解决的问题主要有哪些？
•数据清理
•填充缺失值, 识别/去除离群点, 光滑噪音, 并纠正数据中的不一致
•数据集成
•多个数据库, 数据立方体, 或文件的集成
•数据变换
•规范化和聚集
•数据归约
•得到数据的归约表示, 它小得多, 但产生相同或类似的分析结果：维度规约、数值规约、数据压缩
7 脏数据主要有哪几种？产生的主要原因是什么？
•incomplete:缺少属性值, 缺少某些有趣的属性, 或仅包含聚集数据
•e.g., 职业=“ ” (missing data)
•noisy:包含错误或孤立点
•e.g., Salary=“−10” (an error)
•inconsistent:编码或名字存在差异, e.g.,
•Age=“42”, Birthday=“03/07/2010”
•以前的等级 “1, 2, 3”, 现在等级 “A, B, C”
•重复记录间的差异
•有意的(e.g.,变相丢失的数据)
•Jan. 1 as everyone’s birthday?
原因：
•滥用缩写词
•数据输入错误
•数据中的内嵌控制信息
•不同的惯用语
•重复记录
•丢失值
•拼写变化
•不同的计量单位
•过时的编码
•含有各种噪声
8 缺失值的处理方法有哪些？
•忽略元组: 缺少类别标签时常用(假定涉及分类)—不是很有效，当每个属性的缺失百分比变化大时
•手工填写缺失数据: 乏味+费时+不可行 ?
•自动填充：如
•一个全局常量 : e.g., “unknown”, a new class?!
•使用属性均值
•与目标元组同一类的所有样本的属性均值: 更巧妙
•最可能的值: 基于推理的方法，如贝叶斯公式或决策树
9 什么是噪音数据？产生的原因有哪些？
•噪声：在测量一个变量时可能出现的测量值相对于真实值的偏差或者错误。
•孤立点：不符合数据模型的数据。
•噪声处理的目的：降低对数据分析和结果的影响
•引起噪声数据的原因
•错误的数据收集工具
•数据录入问题 data entry problems
•数据传输问题data transmission problems
•技术限制 technology limitation
•不一致的命名惯例 inconsistency in naming convention
10噪声数据的检测和处理方法有哪些？
噪声数据的判别方法 ：
•简单统计分析
对属性值进行一个描述性的统计（规定范围），从而查看哪些值是不合理的（范围以外的值）。
•3δ原则
若数据服从正态分布：根据正态分布的定义可知，距离平均值3δ之外的概率为 P(|x-μ|>3δ) <= 0.003 ，这属于极小概率事件，在默认情况下我们可以认定，距离超过平均值3δ的样本是不存在的。因此，当样本距离平均值大于3δ，认为该样本为异常值
•使用距离检测多元离群点
当数据不服从正态分布时，可以通过远离平均距离多少倍的标准差来判定，多少倍的取值需要根据经验和实际情况来决定。
•基于模型检测
•首先建立一个数据模型，异常是那些同模型不能完美拟合的对象；如果模型是簇的集合，则异常是不显著属于任何簇的对象；在使用回归模型时，异常是相对远离预测值的对象
•基于密度
•当一个点的局部密度显著低于它的大部分近邻时才将其分类为离群点。适合非均匀分布的数据。
•优点：给出了对象是离群点的定量度量，并且即使数据具有不同的区域也能够很好的处理
•缺点：时间复杂度O(m^2)；参数选择困难，虽然算法通过观察不同的k值，取得最大离群点得分来处理该问题，但是，仍然需要选择这些值的上下界。
基于模型的噪声检测和处理——回归
•回归：发现两个相关的变量之间的变化模式，通过使数据适合一个函数来平滑数据，即利用拟合函数对数据进行平滑及除去噪声。
•通过构造函数来符合数据变化的趋势，这样可以用一个变量预测另一个变量。
噪声数据的处理——聚类
噪声数据的处理——分箱
11 什么叫数据集成？数据集成解决的主要问题有哪些？
定义：将互相关联的分布式异构数据源集成到一起，使用户能够以透明的方式访问这些数据源。
•涉及几个主要问题：
•模式集成Schema integration /schema matching
•实体识别:多个数据源的真实世界的实体的识别
•数据冗余
•属性冗余：某个属性可以由别的属性推出
•相关分析
•重复记录检测/数据去重（元组冗余）
•冲突检测
12 什么叫数据归约？主要有哪几类归约问题？
Ø数据规约目的
用于帮助从原有庞大数据集中获得一个精简的数据集合，并使这一精简数据集保持原有数据集的完整性，这样在精简数据集上进行数据挖掘显然效率更高，并且挖掘出来的结果与使用原有数据集所获得结果是基本相同。
有以下五类问题：
•维归约（dimensionality reduction）减少所考虑的随机变量或属性的个数。
•维归约方法包括小波变换和主成分分析，它们把原数据变换或投影到较小的空间。
•属性子集选择是一种维归约方法，其中不相关、弱相关或冗余的属性或维被检测和删除。
•数值归约（numerosity reduction）用替代的、较小的数据表示形式替换原数据。这些技术可以是参数的或非参数的。
•参数方法而言，使用模型估计数据，使得一般只需要存放模型参数，而不是实际数据（离群点可能也要存放）。回归和对数-线性模型就是例子。
•非参数方法包括直方图、聚类、抽样和数据立方体聚集。
•数据立方体聚集
•数据压缩（data compression）使用变换，以便得到原数据的归约或“压缩”表示。
•无损：如果原数据能够从压缩后的数据重构，而不损失信息，
•有损：如果我们只能近似重构原数据，则该数据归约称为有损的。
•对于串压缩，有一些无损压缩算法。然而，它们一般只允许有限的数据操作。
•维归约和数量归约也可以视为某种形式的数据压缩。
•离散化与概念分层生成
13 维度归约有哪两类技术？有什么区别？
•特征选择：
从原始特征中选择出和任务相关的特征
•特征提取（属性/特征产生）： 将原始特征通过线性或者非线性组合的方式转化为新的特征表示
14 什么是数据离散化和概念分层？
•离散化技术
•通过将属性（连续取值）域值范围分为若干区间，来帮助消减一个连续（取值）属性的取值个数。是一种数量归约的方法
•离散化 Discretization: 把连续属性的区域分成区间
•适用于数值型和序数型数据
•区间标号可以代替实际数据值
•利用离散化减少数据量
•有监督 vs. 无监督：是否使用类的信息
•某个属性上可以递归离散化
•分裂 Split (top-down) vs. 合并merge (bottom-up)
•自顶向下：由一个/几个点开始递归划分整个属性区间
•概念分层
•概念分层定义了一组由低层概念集到高层概念集的映射。它允许在各种抽象级别上处理数据，从而在多个抽象层上发现知识。用较高层次的概念替换低层次（如年龄的数值）的概念，以此来减少取值个数。虽然一些细节在数据泛化过程中消失了，但这样所获得的泛化数据或许会更易于理解、更有意义。在消减后的数据集上进行数据挖掘显然效率更高。
•概念分层结构可以用树来表示，树的每个节点代表一个概念。
•适用于标称型数据的数量归约，也可用于数值型和序数型
•概念分层的目的是为了实现离散化，实现数量归约
15 数据规范化/标准化的方法有哪些？形式，有什么作用？
•方法：
（1）最小-最大规范化
（2）零-均值规范化（z-score规范化）
（3）小数定标规范化
•数据规范化的目的就是消除量纲的影响
16 数据仓库的主要特征是什么，对每一特征给予简要解释
•1.面向主题的
• 主题:在较高层次上将企业信息系统中的数据综合、归类并进行分析利用的抽象；在逻辑意义上，它对应企业中某一宏观分析领域所涉及的分析对象。
2、集成的
数据仓库中的数据是在对原有分散的数据库数据抽取、清理的基础上经过系统加工、汇总和整理得到的
3、反映历史变化
数据仓库中的数据通常包含历史信息，系统记录了企业从过去某一时点(如开始应用数据仓库的时点)到目前的各个阶段的信息，通过这些信息，可以对企业的发展历程和未来趋势做出定量分析和预测。
4、相对稳定的
数据仓库的数据主要供企业决策分析之用，所涉及的数据操作主要是数据查询，一旦某个数据进入数据仓库以后，一般情况下将被长期保留，也就是数据仓库中一般有大量的查询操作，但修改和删除操作很少，通常只需要定期的加载、刷新。
17 数据仓库的作用
数据仓库提供用户用于决策支持的当前和历史数据，这些数据在传统的操作型数据库中很难或不能得到。数据仓库技术是为了有效的把操作形数据集成到统一的环境中以提供决策型数据访问的各种技术和模块的总称。所做的一切都是为了让用户更快更方便查询所需要的信息，提供决策支持
18 典型的数据仓库体系结构，各层简要说明
•经典模型：数据仓库一般采用三层结构
•底层: 数据仓库服务器, 几乎总是一个关系型数据库系统;
•DW服务器从操作型数据库或外部数据源(如:咨询机构提供的客户背景)提取数据，并进行清洗、转换、集成等,装入到数据仓库中。
•中间层: OLAP服务器,提供对多维数据的存储和操作。
•ROLAP: 将多维数据上的操作映射为标准的关系操作
•MOLAP: 直接在多维模型上实现多维数据操作
•顶层: 前端工具, 包括查询和报表、分析、数据挖掘工具等。
19数据库与数据仓库系统在设计上的差别
1.系统设计的目标不同：
数据库是面向事务型处理的，所以事务型处理性能是系统设计的一个主要目标。
而数据仓库是为了支持决策分析而建立的一种数据存储集合。在系统设计时，更关心的是建立起一个全局一致的分析型处理环境来支持企业的决策分析。
2.面向的需求不同：
数据库系统是面向应用的，所以在系统设计时应以此为出发点和基础。
而在决策分析时，决策者分析问题的角度多种多样，所以数据处理流和信息流不固定，甚至决策者对所要进行的分析处理都不太明了，数据的分析处理的需求更灵活。这就决定了在数据仓库系统设计时，不可能从用户需求出发来进行设计。
3.数据来源不同：
数据库系统中数据是从企业外部通过输入得到的，所以系统设计时就是设计如何与外部对话得到数据，如何存储这些数据，它关心的是数据的安全性和完整性等。
数据仓库中的数据大部分是从企业内部的数据库系统得到的，还有一部分是企业外部的非结构化数据，这些数据都是安全可靠且正确有效的，所以在系统设计时它关心的不是数据的安全性和完整性，而是数据的一致性。
4.数据的处理类型不同
数据库系统支持的是事务型处理，主要指数据的增、删、改、查等等，系统设计时都是针对某一具体应用。
数据仓库是面向分析的，它的数据处理大都是对数据的复杂查询，所以在设计时考虑的是如何更好的面向主题，如何提高查询的效率等。
5.设计方法不同：
由于在数据库系统中业务过程和规则比较规范固定，系统设计人员能清楚的知道应用需求和数据流程，所以系统设计一般采用系统生命周期法(Systems Development Life Cycle ，SDLC)。
在决策分析时，决策人员往往无法给决策需求一个规范的说明，只能给出一个模糊的描述，对这种需求不确定的开发过程，设计方法有很大的不同，采用与SDLC相反的CLDS法。
20数据仓库设计的过程有哪些
DW设计实施阶段
根据DW的逻辑模型设计DW体系结构；
设计DW与物理数据库，用物理数据库元数据装载面向最终用户的元数据库；
为DW中每个目标字段确定他在业务系统或外部数据源中的数据来源；
开发或购买用于抽取、清洗、转换和聚合数据等中间件程序；
将数据从数据源加载到DW，并且进行测试
21模型设计（概念——逻辑；星型模型；粒度选择）
设计概念模型的目的，是对数据仓库所涉及的现实世界中的所有客观实体进行科学的、全面的分析和抽象，为数据仓库的构建制定出“蓝图”。这是成功构建数据仓库的第一步。
概念模型设计的关键，是要保证所有与数据仓库相关的客观实体（即业务内容）均能得到准确的理解，并被完整地包含在模型当中。因此，在设计概念模型时，拥有足够的专业业务知识不仅是重要的，而且是必须的。
逻辑模型设计主要工作为：
（1）进行概念模型（E—R图）到逻辑模型（星型模型）的转换
（2）粒度层次划分
（3）关系模式定义
（4）定义记录系统
星形模型：
•事实表
•主要包含了描述特定商业事件的数据，即某些特定商业事件的度量值。
•在星型模式或雪花模式中用来记录业务事实并作相应指标统计的表。
•一般情况下，事实表中的数据不允许修改，新的数据只是简单地添加进事实表中
关于粒度选择：
ü粒度
指数据仓库中数据单元的详细程度和级别。
ü数据仓库中数据的级别
※ 早期细节级
※ 当前细节级
※ 轻度综合级
※ 高度综合级
数据越详细，粒度就越小，级别也就越低；数据综合度越高，粒度就越大，级别也就越高。
1)粒度的不同选择会导致逻辑模型的差异
2)粒度的不同选择会导致数据存储容量的差异
对于业务量大，分析要求比较高的情况下，最佳解决办法则是采用多重粒度的形式。
双重粒度
在数据仓库的细节级上创建两种粒度
短期储存的低粒度（真实档案），满足细节查询
具有综合的高粒度（轻度综合），做分析
22ETL的内容
ETL是数据从业务系统抽取转化到数据仓库的过程，包括4个子过程：数据抽取、数据转换、数据清洗、数据装载
用户从数据源抽取出所需数据，经过数据清洗，按照预先定义好的数据仓库模型，将数据装载到数据仓库中去
23 写出至少五种OLAP的操作，并说明每种的具体内容
•上卷 (drill-up，roll up): 概括数据
•通过沿一个维的概念分层向上攀升或者通过维归约，对数据立方进行聚集
•下钻 (Drill down ，roll down): 上卷的逆操作
•从高层概括到底层概括，从不太详细到更加详细的数据
•给数据添加更多细节，添加新的维到立方体来实现
•切片和切块（Slice and dice）:投影和选择 ：在多维数据结构中,按二维进行切片,按三维进行切块,可得到所需要的数据。如在“城市、产品、时间”三维立方体中进行切块和切片,可得到各城市、各产品的销售情况
•转轴或旋转（Pivot or rotate):
•转换立方体的视角, 可视化, 从3D 到 2D 平面序列
•其他操作
•钻过（drill across）: 涉及多个事实表的查询
•钻透（drill through）: 钻透立方体的底层，到后端关系表 (using SQL)
24 MOLAP和ROLAP的体系结构，工作原理
MOLAP利用一个专有的多维数据库来存储OLAP分析所需的数据，数据以多维方式存储，并以多维视图方式显示。
MOLAP事先将汇总数据计算好，存放在自己特定的多维数据库中，用户的OLAP操作可以直接映射到多维数据库的访问，不通过SQL访问。
多维数据库服务器（MDDB）不仅负责数据的存储、存取及检索，同时也负责所有OLAP需求的执行。
应用过程中，用户在客户端的应用软件的界面上提交分析需求给OLAP服务器，然后由OLAP服务器检索MDDB数据库得到结果，最后返回给用户。
•ROLAP将分析用的多维数据存储在关系数据库中并根据应用的需要有选择的定义一批实视图作为表也存储在关系数据库中。
•不必要将每一个SQL查询都作为实视图保存，只定义那些应用频率比较高、计算工作量比较大的查询作为实视图。
•对每个针对OLAP服务器的查询，优先利用已经计算好的实视图来生成查询结果以提高查询效率。
•同时用作ROLAP存储器的RDBMS也针对OLAP作相应的优化，比如并行存储、并行查询、并行数据管理、基于成本的查询优化、位图索引、SQL的OLAP扩展(cube, rollup)等等。
25 什么叫数据立方体的预计算？为什么要进行预决算？面临的问题有哪些？有哪些策略？
数据立方体有利于多维数据的联机分析处理
数据立方体使得从不同的角度对数据进行观察成为可能
多维分析中需要对具有不同综合程度的数据进行查询，因而需要对细节数据进行综合。
综合的过程称为预计算。
预计算（物化）的挑战：海量数据，有限的内存和时间
海量数据运算对大量计算时间和存储空间的要求
在存储空间充足的情况下，可以采取将一个完整的数据立方体全部预计算出来，并进行存储的方法。
可以大大加快查询响应时间：以空间换时间策略。
常用的策略：
尽量一次同时计算多个数据立方体；
对每个数据立方体，计算时尽量选择在数据立方格结构中离自己最近的数据立方体进行聚集计算；
多个数据立方体同时计算时尽量共享排序结果、扫描结果、缓存结果、划分结果等。
26完整数据立方体的预计算方法
完整数据立方体预计算方法很多。
常用的策略：
尽量一次同时计算多个数据立方体；
对每个数据立方体，计算时尽量选择在数据立方格结构中离自己最近的数据立方体进行聚集计算；
多个数据立方体同时计算时尽量共享排序结果、扫描结果、缓存结果、划分结果等。
27什么叫数据泛化，哪两种方法及规则
•数据泛化的两种常用方法：属性删除和属性泛化
•属性删除的适用规则：对初始工作关系中具有大量不同值的属性，符合以下情况，可使用属性删除：
•在此属性上没有泛化操作符（比如该属性没有定义相关的概念分层）
•该属性的较高层概念用其他属性表示,如street，其高层次概念用属性（city,province,country）等描述，可删除
•属性泛化的使用规则：如果初始工作关系中的某个属性具有大量不同值，且该属性上存在泛化操作符，则使用该泛化操作符对该属性进行数据泛化操作
28面向属性的泛化方法
•属性泛化控制的两种常用方法：
•属性泛化阈值控制：如果初始工作关系的某个属性的不同值个数大于属性泛化阈值，则应当进一步删除或者泛化该属性。
•泛化关系阈值控制：如果泛化关系中不同元组的个数超过泛化(广义）关系临界值，则应当进一步泛化。
•两种技术的顺序使用：使用属性泛化阈值控制来泛化每个属性，然后使用关系阈值控制进一步压缩泛化的关系
29频繁模式挖掘相关概念（关联规则，支持度，置信度，）
关联规则挖掘用来发现大量数据中项集之间有趣的关联联系。如果两项或多项属性之间存在关联，那么其中一项的属性就可以依据其他属性值进行预测。
关联规则是形如XY的蕴含式，其中XI，YI且XY=，则X称为规则的条件，Y称为规则的结果。
如果事务数据库D中有s%的事务包含XY，则称关联规则XY的支持度为s%。
XY其并非概率论中的随机事件，仅看做X中项集和Y中项集的并集，P(XY)即包含X中项集同时包含Y中项集的事务数（所占比例）
置信度是指在数据库D中项集X出现的前提下Y出现的概率。
置信度反应了关联规则的可信度——购买了项目集X中的商品的顾客同时也购买了Y中商品的可能性有多大
30关联规则挖掘的步骤
一般来说，关联规则的挖掘可以看作两步的过程：
找出所有频繁项集
该项集的每一个出现的频繁性 ≥ min_sup
由频繁项集产生强关联规则
即满足最小支持度和最小置信度的规则
31Apriori方法（原理，例子）
Apriori算法的基本思想
Apriori算法是一种最有影响的挖掘布尔关联规则大（频繁）项目集的算法。它使用一种称作逐层搜索的迭代算法，通过k-项集用于探索（k+1）-项集。已经为大部分商业产品所使用。
Apriori算法在具体实现时，将关联规则的挖掘过程分解为两个子问题。
1、发现频繁项集
根据用户给定的最小支持度min sup ，寻找出所有的频繁项集，即满足支持度Support不低于min sup的所有项集。由于这些频繁项集之间有可能存在包含关系，因此，我们可以只关心所有的最大频繁项集，即那些不被其它频繁项集所包含的所有频繁项集。
2、生成关联规则
根据用户给定的最小置信度min conf ，在每个最大频繁项集中，寻找置信度Confidence不小于min conf的关联规则。
32 FP-TREE（原理，例子）
一种采用divide and conquer（分治策略）的方法
在经过第一遍扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息；
将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，然后再对这些条件库分别进行挖掘。
具体步骤分为：
构造FP-Tree
扫描一次数据集，确定每个项的支持度计数。丢弃非频繁项，而将频繁项按照支持度的递减排序
FP树的创建
1.创建树的根节点，用null标记；
2.将每个事务中的项按递减支持度计数排列，并对每个事务创建一个分枝；
3.当为一个事务考虑增加分枝时，沿共同前缀上的每个节点的计数加1，为跟随前缀后的项创建节点并连接
4.创建一个项头表，以方便遍历，每个项通过一个节点链指向它在树中的出现。
算法第二次扫描数据集，构建FP树。读入第一个事务{A，B}之后，创建标记为A和B的结点。然后形成null->A->B路径，对该事务编码。该路径上的所有结点的频度计数为1.
读入第二个事务{B，C，D}之后，为项B，C和D创建新的结点集。然后，连接结点null->B->C->D，形成一条代表该事务的路径。该路径上的每个结点的频度计数也等于1.尽管前两个事务具有一个共同项B，但是它们的路径不相交，因为这两个事务没有共同的前缀。
第三个事务{A，C，D，E}与第一个事务共享一个共同的前缀项A，所以第三个事务的路径null->a->c->d->e与第一个事务的路径null->A->B部分重叠。因为它们的路径重叠，所以结点A的频度计数增加为2.
继续该过程，直到每个事务都映射到FP树的一条路径。
挖掘FP-Tree
构造FP-Tree时是按照1-项集频度的降序进行的，对构造后的FP-Ｔree进行挖掘时，需要按照1-项集频度的升序进行。
对于每一个1-项集，首先构造它的条件模式基。
所谓条件模式基，是一个“子数据库”，由FP-Tree中与该1-项集一起出现的前缀路径组成。即以要挖掘的节点作为叶子节点所对应的FP子树
具体实现：
1从数据项头表中首先找到该1-项集，然后顺着链表找到它在树中出现的位置，每找到一个位置，则得到从树根到该位置的一条路径，该路径就构成了条件模式基中的一部分。
2构造该初始后缀模式的条件FP树，重复1,2
3直到结果FP-tree为空，或只含唯一的一个路径（此路径的每个子路径对应的项目集都是频繁集）
假设一棵 FP-树 T 有个单路径P
模式基T的完整的频繁项通过列举路径P的所有子路径的结合得到。
33 为什么进行关联规则的主观性测试？有哪些指标及其特点
强关联规则不一定有趣
规则是否有趣可以主观或客观地评估。最终，只有用户能够确定规则是否有趣，并且这种判断是主观的， 因用户而异。然而，根据数据“背后”的统计，客观兴趣度度量可以用于清除无趣的规则，而不向用户提供。通常认为一个规则（模式）是有趣的，如果：
•它是出人意料的
•可操作的（用户可以使用该规则做某些事情）
34 过拟合的主要原因及其解决方法
欠拟合或称：拟合不足、欠配，是指模型在训练数据上没有获得充分小的误差
过拟合：为了得到一致假设而使假设变得过度严格。原因：
•数据量太小：训练集的数量级和模型的复杂度不匹配。
•训练集和测试集特征分布不一致
•样本里的噪音数据干扰过大，大到模型过分记住了噪音的特征，反而忽略了真实的输入输出间的关系，从而减小了具有一般性的规律。
•过度训练，权值学习迭代次数足够多(Overtraining)，拟合了训练数据中的噪声和训练样例中没有代表性的特征
•模型复杂度太大，使⽤了过强的模型复杂度(model complexity)的能⼒。（参数多并且过训练），训练集的数量级要小于模型的复杂度，这使得模型⽆法真正了解整个数据的真实分布。
解决方案：
模型层面：
•simpler model structure
调小模型复杂度，使其适合自己训练集的数量级(缩小宽度和减小深度)
•regularization
在损失函数中加入正则项来惩罚模型的参数，以此来降低模型的复杂度，常见的添加正则项的正则化技术有L1，L2正则化。
•dropout
这个方法在神经网络里面很常用。dropout方法是ImageNet中提出的一种方法，通俗一点讲就是dropout方法在训练的时候让神经元以一定的概率不工作
•Batch Normalization
• BM算法是一种非常有用的正则化方法，可以让大型的卷积神经网络快速收敛，同时还能提高分类的准确率，而且可以不需要使用局部响应归一化处理，也可以不需要加入Dropout。
•BM算法会将每一层的输入值做归一化处理，并且会重构归一化处理之后的数据，确保数据的分布不会发生变化。
•ensemble
集成学习算法也可以有效的减轻过拟合。Bagging通过平均多个模型的结果，来降低模型的方差。Boosting不仅能够减小偏差，还能减小方差。
•Bagging和Boosting
数据层面：
•从数据源头获取更多数据
•数据增强（Data Augmentation）：通过一定规则扩充数据。如在物体分类问题里，物体在图像中的位置、姿态、尺度，整体图片明暗度等都不会影响分类结果。我们就可以通过图像平移、翻转、缩放、切割等手段将数据库成倍扩充
训练层面：
•提前终止迭代（Early stopping）
对模型进行训练的过程即是对模型的参数进行学习更新的过程，这个参数学习的过程往往会用到一些选代方法，如梯度下降(Gradientdescent)学习算法。Earlystopping便是一种迭代次数截断的方法来防止过拟合的方法，即在模型对训练数据集迭代收敛之前停止迭代来防止过拟合。
Early stopping方法的具体做法是，在每一个Epoch结束时(一个Epoch集为对所有的训练数据的一轮遍历)计算validationdata的accuracy，当accuracy不再提高时，就停止训练。
•这种做法很符合直观感受，因为accurary都不再提高了，在继续训练也是无益的，只会提高训练的时间。
•在训练的过程中，记录到目前为止最好的validation accuracy，当连续（10次或其他值）Epoch(或者更多次)没达到最佳accuracy时，则可以认为accuracy不再提高了。此时便可以停止迭代了(Early Stopping)。
35 关于基于混淆矩阵的几个主要指标及其作用
- 准确率与误分类率
准确率(Accuracy rate) =(tp+tn) )/(tp+fn+fp+tn)
误分类率(error rate)=(fn+fp)/(tp+fn+fp+tn)
真正率(True Positive Rate)TPR（灵敏度）
=tp/(tp+fn)
真负率(True Negative Rate)TNR（特异度）
=tn/(fp+tn)
假正率 (False Postive Rate)FPR
=fp/(fp+tn)
假负率 （False Negative Rate）FNR
=fn/(tp+fn)
精度(查准率）
P=tp / (tp+fp)召回率（真正率、灵敏度，查全率）
R=tp/(tp+fn)
4.FSCORE
精度和召回率的调和均值：
召回率和精度的权重相同：
F = 2RP/(R+P)
将召回率的权重设为精度的β倍：
36 ROC曲线及其特点，计算
接收者操作特征(receiver operating characteristic)
roc曲线上每个点反映着对同一信号刺激的感受性。
纵轴：真正类率(true postive rate TPR)，也叫真阳性率
横轴：假正类率(false postive rate FPR)，也叫伪阳性率
横，纵轴的计算公式
(1)真正类率(True Postive Rate)TPR: TP/(TP+FN), 代表分类器 所有正例样本中被预测为正例的比例。
(2)假正类率(False Postive Rate)FPR: FP/(FP+TN)，代表分类器 所有负例样本中被预测为正例的比例。
图中实线为ROC曲线，（深绿色）线上每个点对应一个阈值（threshold）。假设是二分类分类器，输出为每个实例预测为正类的概率。那么通过设定一个特定阈值（threshold），预测为正类的概率值 大于等于 特定阈值的为 正类，小于 特定阈值的为 负类，然后统计TP、TN、FP、FN每个类别的数目
根据上面的公式，可对应的算出一组 特定阈值下(FPR,TPR)的值，即在平面中得到对应坐标点。
•FPR表示模型虚报的响应程度，而TPR表示模型预测响应的覆盖程度。我们所希望：虚报的越少越好，覆盖的越多越好。
•所以TPR越高，同时FPR越低（即ROC曲线越陡），那么模型的性能就越好
37 序列挖掘的相关概念
•序列挖掘或称序列模式挖掘，是指从序列数据库中发现蕴涵的序列模式。
•序列挖掘一般是指相对时间或者其他顺序出现的序列的高频率子序列的发现，典型的应用还是限于离散型的序列。
序列数据是由有序元素或事件的序列组成的，可以不包括具体的时间概念，序列数据的例子有客户购物序列、Web点击流和生物学序列等。
这类数据处理的不是一个时间点上的数据，而是大量时间点上的数据，因而具有自身的特殊性。
设I={i1，i2，…，in}是所有项的集合，在购物篮例子中，每种商品就是一个项。项集是由项组成的一个非空集合。
定义6.1 事件（events）是一个项集，在购物篮例子中，一个事件表示一个客户在特定商店的一次购物，一次购物可以购买多种商品，所以事件表示为（x1，x2，…，xq），其中xk（1≤k≤q）是I中的一个项，一个事件中所有项均不相同，每个事件可以有一个事件时间标识TID，也可以表示事件的顺序。
定义6.2 序列（sequence）是事件的有序列表，序列s记作
通常一个序列中的事件有时间先后关系，也就是说，ej（1≤j≤l）出现在ej+1之前。序列中的事件个数称为序列的长度，长度为k的序列称为k-序列。在有些算法中，将含有k个项的序列称为k-序列。
定义6.3 序列数据库（sequence databases）S是元组
在序列数据库中每个序列的事件在时间或空间上是有序排列的。
定义6.4 对于序列t和s，如果t中每个有序元素都是s中一个有序元素的子集，则称t是s的子序列。
如果t是s的子序列，则称t包含在s中。
例如序列<{2}，{1，3}>是序列<{1，2}，{5}，{1，3，4}>的子序列，因为{2}包含在{1，2}中，{1，3}包含在{1，3，4}中。
而<{2，5}，{3}>不是序列<{1，2}，{5}，{1，3，4}>的子序列，因为前者中项2和项5是一次购买的，而后者中项2和项5是先后购买的，这就是区别所在。
定义6.5 如果一个序列s不包含在序列数据库S中的任何其他序列中，则称序列s为最大序列。
序列α在序列数据库S中的支持度为序列数据库S中包含序列α的序列个数，记为Support(α)
给定支持度阈值β，如果序列α在序列数据库中的支持数不低于β，则称序列α为序列模式
长度为l的序列模式记为l-模式
定义6.6 一个序列α的支持度计数是指在整个序列数据库S中包含α的序列个数。即：
supportS(α)=|{(SID，s)| (SID，s)∈S ∧α是s的子序列}|
其中，|·|表示集合中·出现的次数。若序列α的支持度计数不小于最小支持度阈值min_sup，则称之为频繁序列，频繁序列也称为序列模式。
长度为k的频繁序列称为频繁k-序列。
序列模式挖掘的问题定义为：给定一个序列数据库D以及最小支持度阈值min_sup，从中找出所有支持度计数不小于min_sup的序列，这些频繁序列也称为序列模式。
有的算法还可以找出最大序列，即这些最大序列构成序列模式。
38 apriori-all算法（原理，例子）
AprioriAll本质上是Apriori思想的扩张，只是在产生候选序列和频繁序列方面考虑序列元素有序的特点，将项集的处理改为序列的处理。
基于水平格式的Apriori类算法将序列模式挖掘过程分为5个具体阶段，即排序阶段、找频繁项集阶段、转换阶段、产生频繁序列阶段以及最大化阶段。
步骤（以客户交易数据为例）
1) 排序阶段。数据库D以客户号为主键，交易时间为次键进行排序。这个阶段将原来的事务数据库转换成由客户的序列组成的数据库。
2) 频繁项集阶段。找出所有频繁项集组成的集合L。也同步得到所有频繁1-序列组成的集合。
3) 转换阶段。在找序列模式的过程中，要不断地进行检测一个给定的频繁集是否包含于一个客户序列中。
4) 序列阶段。利用已知的频繁集的集合来找到所需的序列。类似于关联的Apriori算法。
5）最大化阶段。在频繁序列模式集合中找出最大频繁序列模式集合
39 GSP算法（原理，例子）
•Generalized Sequential Pattern
•其核心思想是：
•1、长度为1的序列模式L1，作为初始的种子集
•2、根据长度为i的种子集Li，通过连接操作和剪切操作生成长度为i+1的候选序列模式 ，然后扫描数据库，计算每个候选序列模式的支持度，产生长度为i+1的序列模式并作为新的种子集。
•3、重复第二步，直到没有新的序列模式或新的候选序列模式产生为止。
GSP算法主要包括三个步骤：
1.扫描序列数据库，得到长度为1的序列模式L1，作为初始的种子集合。
2.根据长度为i的种子集合Li通过连接操作和剪枝操作生成长度为i+1的候选序列模式Ci+1；然后扫描序列数据库，计算每个候选序列模式的支持度计数，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集合。
3.重复第②步，直到没有新的序列模式或新的候选序列模式产生为止。
整个过程为：L1→C2→L2→C3→L3→C4→L4→…
注意：在GSP算法中，k-序列是指序列中包含k个项，这与前面的定义有所不同。
40 k-means, K-medoid, AGNES, DIANA算法（原理，例子）
k-means算法（k-均值方法）首先随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。对离群点敏感！
K-medoid算法：集群内最接近丛集中心者为集群中心。
基本上和K-means类似，不同在于K-means是以集群内各对象的平均值为集群的中心点，而K-medoid是以集群内最接近中心位置的对象为集群的中心点，每一轮都只针对扣除作为集群中对象外的所有剩余对象，重新寻找最近似的集群中心。
典型算法：PAM算法。比k-means健壮，但对于大数据集效率不高。
当存在 “噪声”和离群数据时，k-中心点方法比k均值方法更健壮，这是因为中心点不像平均值那样易被极端数据影响。
k-中心点方法的执行代价比k-平均高。
层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。
AGNES (AGglomerative NESting)算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。
两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定。
聚类的合并过程反复进行直到所有的对象最终满足簇数目。
算法 AGNES（自底向上凝聚算法）
输入：包含n个对象的数据库，终止条件簇的数目k。
输出：k个簇，达到终止条件规定簇数目。
(1) 将每个对象当成一个初始簇；
(2) REPEAT
(3) 根据两个簇中最近的数据点找到最近的两个簇；
(4) 合并两个簇，生成新的簇的集合；
(5) UNTIL 达到定义的簇的数目；
单联接：两个簇的距离由不同簇的两个最近的对象间的距离决定
完全连接（最远邻）：两个簇的距离隶属于不同簇的距离最远的两个对象的距离所决定（最远邻的距离）
组平均：两个簇的距离就是隶属不同簇的所有对象的距离的平均（加权平均、组质心、加权组质心、沃德法）
算法 DIANA（自顶向下分裂算法）
输入：包含n个对象的数据库，终止条件簇的数目k。
输出：k个簇，达到终止条件规定簇数目。
（1）将所有对象整个当成一个初始簇；
（2） FOR （i=1; i≠k; i++) DO BEGIN
（3） 在所有簇中挑出具有最大直径的簇C；
（4） 找出C中与其它点平均相异度最大的一个点p并把p放入splinter group，剩余的放在old party中；
（5）. REPEAT
（6） 在old party里找出到最近的splinter group中的点的距离不大于到old party中最近点的距离的点，并将该点加入splinter group。
（7） UNTIL 没有新的old party的点被分配给splinter group；
（8） splinter group和old party为被选中的簇分裂成的两个簇，与其它簇一起组成新的簇集合。
（9） END.
41 密度聚类相关概念（邻域，密度可达等）
定义 1 ε-邻域：给定对象半径ε内的领域
定义 2 核心对象 (Core object): 一个对象的ε–邻域至少包含最小数目MinPts个对象，则称该对象为核心对象
定义 3 直接密度可达：给定一个对象集合D，如果p是在q的ε-邻域内，而q是一个核心对象，我们说对象p从对象q出发是直接密度可达的
定义 4 密度可达的：存在 一个从p到q的DDR(直接密度可达的)对象链。即如果存在一个对象链p1，p2，…，pn，p1=q，pn=p，对pi∈D，（1<=i<=n），pi+1是从pi关于ε和MitPts直接密度可达的，则对象p是从对象q关于ε和MinPts密度可达的。
定义 5 密度相连的：如果对象集合D中存在一个对象o，使得对象p和q是从o关于ε和MinPts密度可达的，那么对象p和q是关于ε和MinPts密度相连的。
定义 6 噪声: 一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含在任何簇中的对象被认为是“噪声”。
42 DB-SCAN算法
DBSCAN通过检查数据集中每个对象的ε-邻域来寻找聚类。如果一个点p的ε-邻域包含多于MinPts个对象，则创建一个p作为核心对象的新簇。然后，DBSCAN反复地寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。具体如下：
DBSCAN算法描述
算法5-5 DBSCAN
输入：包含n个对象的数据库，半径ε，最少数目MinPts。
输出：所有生成的簇，达到密度要求。
1任意选取一个点 p
2repeat
得到所有从p 关于 Eps 和 MinPts密度可达的点.
如果p 是一个核心点, 则找到一个聚类.
如果 p 是一个边界点, 没有从p 密度可达的点, DBSCAN 将访问数据库中的下一个点.
3until 数据库中的所有点都被处理.
43 什么是离群点？离群点挖掘有什么意义？主要有哪五类方法
在样本空间中，与其他样本点的一般行为或特征不一致的点，我们称为离群点
意义：少量的数据可能蕴含着重要的研究价值
五类方法：
一.基于统计的离群点检测：这类方法大部分是从针对不同分布的离群点检验方法发展起来的，通常用户使用分布来拟合数据集。
假定所给定的数据集存在一个分布或概率模型(例如，正态分布或泊松分布)，然后将与模型不一致(即分布不符合)的数据标识为离群数据。
二.基于距离方法：
两种不同策略：
k-近邻邻域——采用给定邻域半径，依据点的邻域中包含的对象多少来判定离群点。如果一个点的邻域内包含的对象少于整个数据集的一定比例则标识它为离群点，也就是将没有足够邻居的对象看成是基于距离的离群点。
利用k最近邻距离的大小来判定离群。使用k-最近邻的距离度量一个对象是否远离大部分点，一个对象的离群程度由到它的k-最近邻的距离给定 。这种方法对k的取值比较敏感。k太小(例如1)，则少量的邻近离群点可能导致较低的离群程度。k太大，则点数少于k的簇中所有的对象可能都成了离群点。
三.基于密度的离群点检测
当数据集含有多种分布或数据集由不同密度子集混合而成时，数据是否离群不仅仅取决于它与周围数据的距离大小，而且与邻域内的密度状况有关。
这里使用每个对象到第k个最近邻的距离大小来度量密度。
局部离群点：一个对象相对于它的局部邻域，特别是关于局部密度，它是远离的。
四.基于聚类的方法:
•该对象属于某个簇吗？如果不，则它被识别为离群点。
•该对象与最近的簇之间的距离很远吗？如果是，则它是离群点。
•该对象是小簇或稀疏簇的一部分吗？如果是，则该簇中的所有对象都是离群点。
五.基于偏差的离群点检测
基本思想
基于偏离的孤立点检测（ deviation-based outlier detection ）不采用统计检验或基于距离的度量值来确定异常对象。相反，它通过检查一组对象的主要特征来确定孤立点。偏离主要特征的对象被认为是孤立点
序列异常技术（sequential exception technique ）
模仿了人类从一系列推测类似的对象中识别异常对象的方式
OLAP数据立方体方法（ OLAP data cube technique）
在大型多维数据中使用数据立方体来确定反常区域
44 基于距离和密度的离群点发现方法（原理，例子）
基于距离方法：
两种不同策略：
k-近邻邻域——采用给定邻域半径，依据点的邻域中包含的对象多少来判定离群点。如果一个点的邻域内包含的对象少于整个数据集的一定比例则标识它为离群点，也就是将没有足够邻居的对象看成是基于距离的离群点。
利用k最近邻距离的大小来判定离群。使用k-最近邻的距离度量一个对象是否远离大部分点，一个对象的离群程度由到它的k-最近邻的距离给定 。这种方法对k的取值比较敏感。k太小(例如1)，则少量的邻近离群点可能导致较低的离群程度。k太大，则点数少于k的簇中所有的对象可能都成了离群点。
基于密度的离群点检测
当数据集含有多种分布或数据集由不同密度子集混合而成时，数据是否离群不仅仅取决于它与周围数据的距离大小，而且与邻域内的密度状况有关。
这里使用每个对象到第k个最近邻的距离大小来度量密度。
局部离群点：一个对象相对于它的局部邻域，特别是关于局部密度，它是远离的。
45 基于聚类的离群点发现方法（原理，例子）
基于聚类的方法:
•该对象属于某个簇吗？如果不，则它被识别为离群点。
•该对象与最近的簇之间的距离很远吗？如果是，则它是离群点。
•该对象是小簇或稀疏簇的一部分吗？如果是，则该簇中的所有对象都是离群点。
44 基于物品的协同推荐算法（原理，例子）
1.基本思想:与基于用户的CF类似，计算邻居时采用物品本身，而不是从用户的角度，即基于用户对物品的偏好找到相似的物品，然后根据用户的历史偏好，推荐相似的物品给他
2.计算方法：所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度，得到物品的相似物品后，根据用户历史的偏好预测当前用户还没有表示偏好的 物品，计算得到一个排序的物品列表作为推荐
45 基于用户的协同推荐算法（原理，例子）
1.基本思想:基于用户对物品的偏好找到相邻邻居用户，然后将邻居用户喜欢的推荐给当前用户
2.计算方法：将一个用户对所有物品的偏好作为一个向量 来计算用户之间的相似度，找到 K 邻居后，根据邻居的相似度权重以及他们对物品的偏好，预测当前用户没有偏好的未涉及物品，计算得到一个排序的物品列表作为推荐
46 基于内容的推荐算法（原理）
1、为每个物品（Item）构建一个物品的属性资料（Item Profile）
2、为每个用户（User）构建一个用户的喜好资料（User Profile）
3、计算用户喜好资料与物品属性资料的相似度，相似度高意味着用户可能喜欢这个物品，相似度低往往意味着用户不喜欢这个物品。
47 数据流的概念和基本特征
概念：一个实时的、连续的、潜在无界的、不确定的、随时间变化的(隐含的通过到达时间或者明确的时间戳)数据项的序列，又称流数据或流式数据。其到达的速度可能突然发生变化、数据流的更新通常以插入为主。令t表示任一时间戳，at表示在该时间戳到达的数据，数据流可以表示成{…，at-1，at， at+1，…}。
特点：
①数据流中的数据元素是联机实时、快速到达的;
②系统无法控制将被处理的数据元素的到达次序;
③数据规模宏大, 不可能把所有的数据都放入内存甚至是硬盘
④数据流中的数据元素一旦被处理，要么丢弃，要么存档。除非显示地存储在内存里，否则很难检索，因为内存相对于数据流的尺寸要小得多。
48 DGIM和衰减窗口的计算
[Datar , Gionis, Indyk, Motwani]
指数窗口，包含若干桶
每个桶中包括 i 个1， i : 2的幂（指数增长）
同样i的桶最多可以有两个
桶不重叠，可以不连续（中间可以隔0）
将整个窗口划分成多个桶 ，每个桶中包含
(1） 最右部的时间戳 （ 即最近的时间戳 ）；
(2） 桶中1的数目，该数目必须是2的幂，我们将该数称为桶的大小
新元素到了
如果一个Bucket的end time已超过当前时刻 - N，drop它
检查最左边的 （ 即最早的 ） 桶 ，如果该桶的时间戳已经达到当前时间戳减去N，那么该桶 的所有1不再在窗口之内。因此，此时将该桶丢弃。
如果新元素是0，什么也不做
如果是1
基于当前时间戳建立一个新的大小为1的桶。 如果仅有一个大小为1的桶，那么不需要做进一步的修改。但是，如果此时有3个大小为1的桶的话 ，其数目就多了l个。此时，可以通过将最左边 （ 最早 ） 的两个大小为 1的桶进行合并来解 决问题。
为合并任两个相同大小的连续桶 ，将它们替换为一个2倍大小的桶。新的桶的时间戳为被 合并的最右边 （ 时间上稍晚 ） 那个桶的时间戳。
将两个大小为 1的桶合并之后 ，可能会得到第3个大小为2的桶。这样的话，就需要将最左边 的两个大小为2的桶合并为一个大小为4的桶。这样，又可能产生第3个大小为4的桶。如果这样 ， 将最左边的两个桶合并为一个大小为 8的桶。上述过程会在不同的桶大小上持续下去。
除了最后一个bucket，把其他bucket的size相加
Size就是其中1的个数
再加上最后一个Bucket size的一半
因为最后一个bucket，只是最后一位还在N里，不知道它的头还是不是在N里，所以，只能算一半。
衰减窗口：指数衰减窗口可以平滑的选取最近的元素和已过去的一些元素，其中最近元素赋予较高的权重。
指数衰减窗方法（EDW）
启发式方法
我们关心的是“现在”流行啥？
过去的计数，让它们慢慢衰减
热度 = 
ai：计数
c：衰减系数，一般取10-6, 10-9
ai表示第i个到达的元素，c为一个很小的常数。流中元素的权重取决于其离当前元素时间的远近，流中越早元素的权重越小。在指数衰减窗口中，新元素到来只需要将原有元素乘以（1-c）,再加上新的元素即可。
等价于
来一个新的a，把老热度乘1 - c（即衰减），然后加上这个新a
实现起来非常方便
49 布隆过滤器的原理
一个布隆过滤器由如下几部分组成 。
(1) n个位组成的数组 ，每个位的初始值都为0
(2） 一系列哈希函数h1 ，h2，… ，hk组成的集合 。每个哈希函数将 “键” 值映射到上述的n个桶（ 对 应于位数组中n个位 ） 中。
(3) m个键值组成的集合S。
布隆过滤器的目的是让所有键值在S中的流元素通过 ，而阻挡大部分键值不在S中的流元素。 位数组的所有位的初始值为 0。对S中的每个键值K，利用每个哈希函数进行处理。
对于一些哈希函数h，及S中的键值K，将每个hi(K)对应的位设为 1
当键值为K的流元素到达时 ，检查所有的h1,h2 ，hk(K)对应的位是否全部为 1，如果是 ， 则允许该流元素通过 ，如果有一位或多位为0，则认为K不可能在S中，于是拒绝该流元素通过