这是大数据挖掘ppt，包括了数据挖掘概览，数据预处理，分类（Classification），聚类（Cluster），关联规则（Association Rule），回归（Regression）等内容，欢迎点击下载。
大数据挖掘ppt是由红软PPT免费下载网推荐的一款课件PPT类型的PowerPoint.
李国良 清华大学计算机系 提纲 数据挖掘概览 数据预处理 分类（Classification） 聚类（Cluster） 关联规则（Association Rule） 回归（Regression） 数据挖掘概览 What? 数据挖掘的定义 Why? 数据挖掘的动机 How? 哪些数据可以用来挖掘？ 数据挖掘的主要内容 数据挖掘定义 什么是数据挖掘（Data Mining）？ Extraction of interesting (non-trivial， implicit， previously unknown and potentially useful) patterns or knowledge from huge amount of data 其他称谓： Knowledge discovery(mining) in database(KDD)， data/pattern analysis， business intelligence， decision-support system， knowledge extraction， data archeology， data dredging and information harvesting etc. 模式有效性度量 Simplicity E.g.， (association) rule length， (decision) tree size Certainty E.g.， confidence， P(A|B) = #(A and B)/ #(B)， classification reliability or accuracy， rule strength， etc. Utility Potential usefulness， e.g.， support (association)， noise threshold (description) Novelty Not previously known， surprising (used to remove redundant rules) 为何需要数据挖掘？ 为何需要数据挖掘？ We are drowning in data， but starving in knowledge Data explosion: Automated data collection tools and mature database technology lead to tremendous amounts of data accumulated and/or to be analyzed in databases， data warehouses， and other information repositories. 数据挖掘的意义 数据挖掘应用 银行 美国银行家协会(ABA)预测数据仓库和数据挖掘技术在美国商业银行的应用增长率是14.9％。 分析客户使用分销渠道的情况和分销渠道的容量 ；建立利润评测模型；客户关系优化；风险控制等 电子商务 网上商品推荐；个性化网页；自适应网站… 生物制药、基因研究 DNA序列查询和匹配；识别基因序列的共发生性 … 电信 欺诈甄别；客户流失… 保险、零售 数据挖掘应用 数据挖掘步骤 数据预处理 数据清理（消除噪音或不一致数据，补缺） 数据集成（多种数据源可以组合在一起） 数据变换（规范化） 数据规约（数据简化） 数据挖掘算法（使用智能方法提取数据模式） 分类、聚类、关联分析、回归预测、文本挖掘 质量评估（识别提供知识的真正有趣模式） 知识表示（可视化和知识表示技术） 数据质量：为何需要数据预处理？ 数据质量衡量： 准确度:correct or wrong， accurate or not 完整度:not recorded unavailable 一致性:some modified but some not， dangling 时效性:timely update? 可信度:how trustable the data are correct? 可解释性:how easily the data can be understood? 数据挖掘预处理的主要任务 数据清理 填写空缺的值，平滑噪声数据，识别、删除孤立点，解决不一致性 数据集成 集成多个数据库、数据立方体或文件 数据变换 规范化和聚集 数据归约 得到数据集的压缩表示，它小得多，但可以得到相同或相近的结果 数据离散化 数据归约的一部分，通过概念分层和数据的离散化来规约数据，对数字型数据特别重要 数据清洗 脏数据：例如设备错误，人或者机器错误，传输错误等 不完整性：属性值缺失或者只有聚集数据 例如：phone=“”; 噪音：包含噪声、错误或者异常值 例如：salary=-10 不一致性: 例如：age=42，birthday=03-07-2010 假值： 例如：使用某一值填补缺失属性 缺失值（Incomplete/Missing Data) 数据并不总是完整的 例如：数据库表中，很多条记录的对应字段没有相应值，比如销售表中的顾客收入 引起空缺值的原因 设备异常 与其他已有数据不一致而被删除 因为误解而没有被输入的数据 在输入时，有些数据因为得不到重视而没有被输入 对数据的改变没有进行日志记载 空缺值要经过推断而补上 如何补充缺失值 忽略元组：当类标号缺少时通常这么做（假定挖掘任务设计分类或描述），当每个属性缺少值的百分比变化很大时，它的效果非常差。 人工填写空缺值：工作量大，可行性低 使用一个全局变量填充空缺值：比如使用unknown或-∞ 使用属性的平均值填充空缺值 使用与给定元组属同一类的所有样本的平均值 使用最可能的值填充空缺值：使用像Bayesian公式或判定树这样的基于推断的方法 噪声数据 噪声：一个测量变量中的随机错误或偏差 引起不正确属性值的原因 数据收集工具的问题 数据输入错误 数据传输错误 技术限制 命名规则的不一致 其它需要数据清理的数据问题 重复记录 不完整的数据 不一致的数据 如何处理噪声数据 分箱: first sort data and partition into (equi-depth) bins then one can smooth by bin means， smooth by bin median， smooth by bin boundaries， etc. 聚类 detect and remove outliers 人机融合 detect suspicious values and check by human (e.g.， deal with possible outliers) 回归 smooth by fitting the data into regression functions 分箱(Binning) 等宽Equal-width (distance) partitioning: Divides the range into N intervals of equal size: uniform grid if A and B are the lowest and highest values of the attribute， the width of intervals will be: W = (B –A)/N. The most straightforward， but outliers may dominate presentation Skewed data is not handled well. 等深Equal-depth (frequency) partitioning: Divides the range into N intervals， each containing approximately same number of samples Good data scaling Managing categorical attributes can be tricky. 数据平滑的分箱方法 price的排序后数据（单位：美元）：4，8，15，21，21，24，25，28，34 划分为（等深的）箱： 箱1：4，8，15 箱2：21，21，24 箱3：25，28，34 用箱平均值平滑： 箱1：9，9，9 箱2：22，22，22 箱3：29，29，29 用箱边界平滑： 箱1：4，4，15 箱2：21，21，24 箱3：25，25，34 聚类：Cluster Analysis Regression 数据集成 实体识别 元数据可帮助避免错误 知识图谱 属性冗余 相关分析 数据重复（元组冗余） 数据值冲突的检测与处理 表示、比例或编码不同 数据变换（规范化） 平滑：去掉数据中的噪声。技术包括分箱、回归、聚类。 聚集：对数据进行汇总或聚集。 数据泛化（概化）：使用概念分层，用高层概念替换低层或“原始”数据。 规范化：将属性数据按比例缩放，使之落入一个小的特定区间。最小-最大、Z-Score、按小数定标规范化。 数据变换 数据规约 海量数据 代表性数据 对海量数据进行复杂的数据分析和挖掘将需要很长时间，使得这种分析不现实或不可行。 数据归约技术可以用来得到数据集的归约表示，它小得多，但仍接近保持原数据的完整性。 对归约后的数据集挖掘将更有效，并产生相同（或几乎相同）的结果。 数据规约 数据归约策略： （1）数据立方体聚集：对数据立方体做聚集操作 （2）属性子集选择：检测并删除不相关、弱相关或冗余的属性和维。 （3）维度归约：删除不重要的属性 （4）数值归约： 用规模较小的数据表示、替换或估计原始数据 （5）离散化和概念分层产生 属性的原始数值用区间值或较高层的概念替换 数据立方体 据立方体存储多维聚集信息，提供对预计算的汇总数据进行快速访问。 如：立方体内存储季度销售额，若对年销售额感兴趣，可对数据执行聚集操作，例如sum()等。 属性子集选择 通过删除不相关或冗余的属性（或维）减小数据集。 其目标是找出最小属性集，使得数据类的概率分布尽可能地接近使用所有属性得到的原分布。 通过穷举搜索找出有属性的最佳子集是不现实的。通常采用压缩搜索空间的启发式算法。 如贪心算法：从局部最优到全局最优。 逐步向前选择 逐步向后删除 向前选择和向后删除的结合 决策树归纳 维度规约 维度归约使用数据编码或变换，以便得到原数据的归约或“压缩”表示。 分为无损和有损两种。 主要方法： 串压缩：无损，但只允许有限的数据操作。 小波变换（DWT）：有损，适合高维数据。 主成分分析（PCA）：有损，能更好地处理稀疏数据。 数值规约 通过选择替代的、“较小的”数据表示形式来减少数据量。 可以分为参数方法和非参数方法。 参数方法：回归（regression ）和对数线性模型 非参数方法：直方图、聚类、抽样 离散化 离散化的用途： （1）适应某些仅接受离散值的算法； （2）减小数据的尺度。 离散化的方法包括几下几种。 （1）等距分割； （2）聚类分割； （3）直方图分割； （4）基于熵的分割； （5）基于自然属性的分割。 抽样 用数据的小得多的随机样本（子集）不是大型数据集。 抽样方法 s个样本无放回简单随机抽样 s个样本有放回简单随机抽样 聚类抽样 分层抽样 分类 分类 分类是指将数据映射到预先定义好的群组或类。 在分析测试数据之前，类别就已经被确定了，所以分类统称被称作有指导的学习。 分类算法要求基于数据属性来定义类别。 分类算法通常通过观察已知所属类别的数据的特征来描述类别。 分类应用 分类具有广泛的应用，例如医疗诊断、信用卡系统的信用分级、图像模式识别等。 为了识别乘客是否是潜在的恐怖分子或罪犯，机场安全摄像站需要对乘客的脸部进行扫描并辨识脸部的基本模式（例如双眼间距、嘴的大小及形状、头的形状）， 然后将得到的模式与数据库中的已知恐怖分子或罪犯的模式进行逐个比较，看看是否与其中的某一模式相匹配。 分类步骤 1．建立一个模型，描述预定的数据类集或概念集 数据元组也称作样本、实例或对象。 为建立模型而被分析的数据元组形成训练数据集。 训练数据集中的单个元组称作训练样本，假定每个元组属于一个预定义的类，由一个称作类标号。 通过分析训练数据集来构造分类模型，可用分类规则、决策树或数学公式等形式提供。 2. 使用模型进行分类 首先评估模型（分类法）的预测准确率。 将已知的类标号与该样本的学习模型类预测比较 准确率等于测试集的样本中被模型正确分类的百分比 测试集应该与训练集的内容相互独立，否则会出现过分适应的情况 如果认为模型的准确率可以接受，就可以用它对类标号未知的数据元组或对象进行分类。 （1）模型的构建 （2）利用模型分类 分类方法评价 预测的准确率 这涉及模型正确地预测新的或先前未见过的数据的类标号的能力 速度 构造模型的速度 利用模型进行分类的速度 强壮性 给定噪声数据或具有空缺值的数据，模型正确预测的能力 可伸缩性 当给定大量数据时，有效地构造模型的能力 可解释性 涉及学习模型提供的理解和洞察的层次 分类器性能评价方式 准确率和召回率 - 混淆矩阵等 给定一个类Cj和一个数据库元组ti，ti可能被分类器判定为属于Cj或不属于Cj，其实ti本身可能属于Cj或不属于Cj，这样就会产生如下一些情况： 真正: 判定ti在Cj中，实际上的确在其中。 假正: 判定ti在Cj中，实际上不在其中。 真负: 判定ti不在Cj中，实际上不在其中。 假负: 判定ti不在Cj中，实际上的确在其中。 准确率:P=A/(A+B) 召回率:R=A/(A+C) 评估分类方法的准确性 保持方法 给定数据随机划分为两个集合：训练集(2/3)和测试集(1/3) 训练集导出分类法，测试集对其准确性进行评估 k-折交叉验证 初始数据被划分为k个不相交的，大小大致相同的子集S1，S2…Sk 进行k次训练和测试，第i次时，以Si做测试集，其他做训练集 准确率为k次迭代正确分类数除以初始数据集样本总数 分类方法 基于距离的分类方法 与一个类中的成员和另一个类中的成员之间的相似性相比，被映射到同一个类中的成员彼此之间被认为是更加相似的。 相似性（距离）度量可以用来识别数据库中不同成员之间的“相似程度”。 基于距离的分类方法的直观解释 距离计算方法 闵可夫斯基距离: 当p=2时，为欧几里得距离 当p=1时，为曼哈顿距离 当p->∞时，为切比雪夫距离 向量内积： 夹角余弦： Jaccard： 还有信息熵、相关系数等其他的度量方法 基于距离的分类方法的一般性描述 算法 基于距离的分类算法 输入：每个类的中心C1，…，Cm；待分类的元组t。 输出：输出类别c。 （1）dist=∞；//距离初始化 （2）FOR i:=1 to m DO （3） IF dis(ci，t)P(Cj|X)，j≠i。即最大化P(Ci|X) P(Ci|X)最大的类Ci称为最大后验假定。 朴素贝叶斯分类 (3) 由于P(X)对于所有类为常数，P(X|Ci)*P(Ci)最大即可。 如果Ci类的先验概率未知，则通常假定这些类是等概率的，即P(C1)=P(C2)=…=P(Cm)，因此问题就转换为对P(X|Ci)的最大化（P(X|Ci)常被称为给定Ci时数据X的似然度，而使P(X|Ci)最大的假设Ci称为最大似然假设）。否则，需要最大化P(X|Ci)*P(Ci)。 类的先验概率可以用P(Ci)=si/s计算，其中si是类Ci中的训练样本数，而s是训练样本总数。 朴素贝叶斯分类 （4）给定具有许多属性的数据集，计算P(X|Ci)的开销可能非常大。为降低计算P(X|Ci)的开销，可以做类条件独立的朴素假定。给定样本的类标号，假定属性值相互条件独立，即在属性间，不存在依赖关系。这样 如果Ak是离散属性，则P(xk|Ci)=sik/si，其中sik是在属性Ak上具有值xk的类Ci的训练样本数，si是Ci中的训练样本数。 如果Ak是连续值属性，常用的处理方法有两种：一是对其离散化，然后按照离散值处理；另一种假定这一属性服从某一分布，通常假定该属性服从高斯分布。 (5)对未知样本X分类，也就是对每个类Ci，计算P(X|Ci)*P(Ci)。样本X被指派到类Ci，当且仅当P(Ci|X)> P(Cj|X)，1≤j≤m，j≠i。 即X被指派到其P(X|Ci)*P(Ci)最大的类。 朴素贝叶斯分类举例 朴素贝叶斯分类举例 设 C1对应于类buys_computer=“yes”， C2对应于类buys_computer=“no”。 (1) 需要最大化P(X|Ci)*P(Ci)，i=1，2。每个类的先验概率P(Ci)可以根据训练样本计算： P(buys_computer=”yes”)=9/14=0.643， P(buys_computer=”no”)=5/14=0.357。 朴素贝叶斯分类举例 (2) 为计算P(X|Ci)，i=1，2，计算下面的条件概率： P(age<=30|buys_computer=“yes” )=2/9=0.222， P(age<=30”|buys_computer=“no” )=3/5=0.600， P(income=“medium”|buys_computer=“yes” )=4/9=0.444， P(income=“medium”|buys_computer=“no” )=2/5=0.400， P(student=“yes”|buys_computer=“yes” )=6/9=0.677， P(student=“yes”|buys_computer=“no” )=1/5=0.200， P(credit_rating=“fair”|buys_computer=“yes” )=6/9=0.667， P(credit_rating=“fair”|buys_computer=“no” )=2/5=0.400。 朴素贝叶斯分类举例 (3) 假设条件独立性，使用以上概率，得到： P(X|buys_computer=“yes” )=0.222*0.444*0.667*0.667=0.044， P(X|buys_computer=“no” )=0.600*0.400*0.200*0.400=0.019， P(X|buys_computer=“yes”)*P(buys_computer=“yes”)= 0.044*0.643=0.028， P(X|buys_computer=“no”)*P(buys_computer=“no”)= 0.019*0.357=0.007。 因此，对于样本X，朴素贝叶斯分类预测buys_computer=“yes” 聚类 聚类：Cluster 聚类就是对大量未知标注的数据集，按数据的内在相似性将数据集划分为多个类别 在同一个类中，对象之间具有相似性； 不同类的对象之间是相异的。 聚类分析 把一个给定的数据对象集合分成不同的簇； 聚类是一种无监督分类法: 没有预先指定的类别； 典型的应用 作为一个独立的分析工具，用于了解数据的分布； 作为其它算法的一个数据预处理步骤； 聚类图示 聚类与分类的区别 有类别标记和无类别标记; 有监督与无监督; （有训练语料与无训练语料） Train And Classification （分类）; No Train（聚类）; 聚类分析 为达到全局最优，基于划分的聚类会要求穷举所有可能的划分。聚类技术将数据元组视为对象。它将对象划分为群或聚类，使得在一个聚类中的对象“类似”，但与其它聚类中的对象“不类似”。 绝大多数应用采用了以下两个比较流行的基于划分的方法，这些基于划分的聚类方法对在中小规模的数据库中发现球状簇很适用。 （1）k-means算法，在该算法中，每个簇用该簇中对象的平均值来表示。 （2）k-medoids算法，在该算法中，每个簇用接近聚类中心的一个对象来表示。 K-means 初始参数-类别数&初始类别中心; 聚类有效性函数-最小误差; 优点： 聚类时间快; 缺点： 对初始参数敏感; 容易陷入局部最优; K-means步骤 1 设置初始类别中心和类别数; 2 根据类别中心对数据进行类别划分; 3 重新计算当前类别划分下每类的中心; 4 在得到类别中心下继续进行类别划分; 5 如果连续两次的类别划分结果不变则停止算法;否则循环2～5 ; O（kndt） 初始值敏感 K-mediods步骤 1 任意选取K个对象作为medoids; 2 将余下的对象分到各个类中去（根据与medoid最相近的原则）; 3 对于每个类（Oi）中，顺序选取一个Or，计算用Or代替Oi后的消耗—E（Or）。选择E最小的那个Or来代替Oi。 4 重复2-3直到medoids不变; O（n2dt） 聚类方法性能评价 一个好的聚类方法要能产生高质量的聚类结果——簇，这些簇要具备以下两个特点： 高的簇内相似性 低的簇间相似性 聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现； 聚类方法的好坏还取决于该方法是能发现某些还是所有的隐含模式； 聚类方法性能评价 可伸缩性 能够处理不同类型的属性 能发现任意形状的簇 在决定输入参数的时候，尽量不需要特定的领域知识； 能够处理噪声和异常 对输入数据对象的顺序不敏感 能处理高维数据 能产生一个好的、能满足用户指定约束的聚类结果 结果是可解释的、可理解的和可用的 聚类评价 准备率：找到正确的结果数/找到结果数 召回率：找到正确的结果数/正确结果数 常用的相似性度量方法 相似性度量方法 聚类分析（续） 基于层次的方法：层次的方法对给定数据集合进行层次的分解。根据层次的分解如何形成，层次的方法可以被分为凝聚或分裂方法。 （Chameleon ，CURE，BIRCH） 基于密度的方法：只要临近区域的密度超过某个阈值，就继续聚类。避免仅生成球状聚类。（DBSCAN，OPTICS，DENCLUE） 基于网格的方法：基于网格的方法把对象空间量化为有限数目的单元，所有的聚类操作都在这个量化的空间上进行。这种方法的主要优点是它的处理速度很快。（STING，CLIQUE，WaveCluster） 基于模型的方法：为每个簇假设一个模型，发现数据对模型的最好匹配。（COBWEB，CLASSIT，AutoClass） DBSCAN 基于密度的簇是密度相连的点的集合 主要思想 寻找被低密度区域分离的高密度区域 只要临近区域的密度（单位大小上对象或数据点的数目）超过某个阈值，就继续聚类 DBSCAN 两个参数： Eps: 邻域的最大半径 MinPts: 一个核心对象以 Eps为半径的邻域内的最小顶点数 DBSCAN 密度 = 制定半径 (Eps)内点的个数 如果一个对象的 Eps 邻域至少包含最小数目MinPts 个对象，则称该对象为核心对象（Core point） 如果一个对象是非核心对象， 但它的邻域中有核心对象，则称该对象为边界点（ Border point ） 除核心对象和边界点之外的点是噪声点（ Noise point ） DBSCAN DBSCAN 密度可达的（Density-reachable） 对于对象p和核心对象q(关于E和MinPts)，我们称p是从q(关于E和MinPts)直接密度可达，若对象p在对象q的E邻域内。 如果存在一个对象链 p1， …， pn， p1 = q， pn = p ，pi+1 是从pi关于Eps和MinPts 直接密度可达的，则对象p是从对象q关于Eps和MinPts 密度可达的。 密度可达性是直接密度可达性的传递闭包，这种关系是非对称的。 只有核心对象之间是相互可达的。 DBSCAN 密度相连的（Density-connected） 如果对象集合D中存在一个对象o，使得对象p和q是从o关于Eps 和 MinPts密度可达的，那么对象p和q是关于Eps 和 MinPts 密度相连的。 密度相连性是一个对称的关系。 DBSCAN DBSCAN算法描述： 输入：包含n个对象的数据库，半径ε，最少数目MinPts。 输出：所有生成的簇，达到密度要求。 1. REPEAT 2. 从数据库中抽取一个未处理过的点； 3. IF 抽出的点是核心点 THEN找出所有从该点密度可达的对象，形成一个簇 4. ELSE 抽出的点是边缘点(非核心对象)，跳出本次循环，寻找下一点； 5. UNTIL 所有点都被处理； 基于密度方法的聚类- DBSCAN 下面给出一个样本事务数据库（见下表），对它实施DBSCAN算法。 根据所给的数据通过对其进行DBSCAN算法，以下为算法的步骤（设n=12，用户输入ε=1，MinPts=4） DBSCAN聚类过程 第1步，在数据库中选择一点1，由于在以它为圆心的，以1为半径的圆内包含2个点（小于4），因此它不是核心点，选择下一个点。 第2步，在数据库中选择一点2，由于在以它为圆心的，以1为半径的圆内包含2个点，因此它不是核心点，选择下一个点。 第3步，在数据库中选择一点3，由于在以它为圆心的，以1为半径的圆内包含3个点，因此它不是核心点，选择下一个点。 DBSCAN聚类过程 第4步，在数据库中选择一点4，由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，寻找从它出发可达的点（直接可达4个，间接可达3个），聚出的新类{1，3，4，5，9，10，12}，选择下一个点。 DBSCAN聚类过程 第5步，在数据库中选择一点5，已经在簇1中，选择下一个点。 第6步，在数据库中选择一点6，由于在以它为圆心的，以1为半径的圆内包含3个点，因此它不是核心点，选择下一个点。 DBSCAN聚类过程 第7步，在数据库中选择一点7，由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，寻找从它出发可达的点，聚出的新类{2，6，7，8，11}，选择下一个点。 DBSCAN聚类过程 第8步，在数据库中选择一点8，已经在簇2中，选择下一个点。 第9步，在数据库中选择一点9，已经在簇1中，选择下一个点。 第10步，在数据库中选择一点10，已经在簇1中，选择下一个点。 第11步，在数据库中选择一点11，已经在簇2中，选择下一个点。 第12步，选择12点，已经在簇1中，由于这已经是最后一点所有点都以处理，程序终止。 基于密度方法的聚类- DBSCAN DBSCAN 关联规则 关联规则：Association Rule 关联规则挖掘： 在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。 应用： 购物篮分析、交叉销售、产品目录设计等。 举例： 规则形式:“Body => Head [support， confidence]” buys(x， “diapers”) => buys(x， “beers”) [0.5%， 60%] major(x， “CS”) ^ takes(x， “DB”) => grade(x， “A”) [1%， 75%] 规则度量：支持度与可信度 查找所有的规则 X & Y => Z 具有最小支持度和可信度 支持度， s， 一次交易中包含{X 、 Y 、 Z}的可能性 可信度， c， 包含{X 、 Y}的交易中也包含Z的条件概率 关联规则挖掘问题就是根据用户指定的最小支持度和最小可信度来寻找强关联规则。 关联规则挖掘问题可以划分成两个子问题： 1.发现频繁项目集:通过用户给定最小支持度，寻找所有频繁项目集或者最大频繁项目集。 2.生成关联规则:通过用户给定最小可信度，在频繁项目集中，寻找关联规则。 第1个子问题是近年来关联规则挖掘算法研究的重点。 经典的发现频繁项目集算法 Apriori算法是通过项目集元素数目不断增长来完成频繁项目集发现的。首先产生1_频繁项目集L1，然后产生2_频繁项目集L2，直到不能再扩展频繁项目集的元素数目为止。 Apriori算法例子 根据上面介绍的关联规则挖掘的两个步骤，在得到了所有频繁项目集后，可以按照下面的步骤生成关联规则： 对于每一个频繁项目集 l ，生成其所有的非空子集； 对于l 的每一个非空子集x，计算Conference（x），如果Confidence（x）≥minconfidence，那么“ x(l-x) ”成立。 关联规则生成算法: 从给定的频繁项目集中生成强关联规则 该算法的核心是genrules递归过程，它实现一个频繁项目集中所有强关联规则的生成。 Rule-generate算法例子 Minconfidence=80% 算法问题 Apriori作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。 Apriori算法有两个致命的性能瓶颈: 1．多次扫描事务数据库，需要很大的I/O负载 对每次k循环，侯选集Ck中的每个元素都必须通过扫描数据库一次来验证其是否加入Lk。假如有一个频繁大项目集包含10个项的话，那么就至少需要扫描事务数据库10遍。 2．可能产生庞大的侯选集 由Lk-1产生k-侯选集Ck是指数增长的，例如104个1-频繁项目集就有可能产生接近107个元素的2-侯选集。如此大的侯选集对时间和主存空间都是一种挑战。 FP-tree算法的基本原理 2000年Han等提出了一个称为FP-Tree（频繁模式树）的算法，该算法只进行 2 次数据库扫描，不使用侯选集，直接压缩数据库成一个FP-Tree ，然后通过该树生成关联规则。构造FP-Tree的过程如下 ： 按Apriori算法，扫描数据库一次生成1-频繁项目集，并按频度降序排序，放入L列表中； 创建根结点，标志为null，扫描数据库一次，当得到数据库的一个项目（元组）时，就把其中的元素按L表中的次序排列，然后通过递归实现FP-Tree的增长； FP-tree算法的基本原理 FP-tree算法的基本原理 FP-tree算法的基本原理 序列模式概念 序列模式的概念最早是由Agrawal和Srikant 提出的 序列模式定义： 给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值 序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值 序列模式表示 例子：设序列数据库如下图所示，并设用户指定的最小支持度min-support = 2。 序列模式挖掘 问题描述：给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式 系统规定：由于同一个元素中的项目之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部的不同项目按照字典顺序排列 序列模式挖掘算法 序列模式挖掘的主要算法 GSP(Generalized Sequential Patterns)算法：类似于Apriori算法 PrefixSpan(Prefix-project Sequential Pattern mining)算法：采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘 预测：Prediction 预测是构造和使用模型评估无样本类，或评估给定样本可能具有的属性或值空间。 预测和分类的异同 相同点 两者都需要构建模型 都用模型来估计未知值 预测当中主要的估计方法是回归分析 线性回归和多元回归 非线性回归 不同点 分类法主要是用来预测类标号（分类属性值） 预测法主要是用来估计连续值（量化属性值） 分类vs.预测 分类： 预测分类标号（或离散值） 根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据 预测： 建立连续函数值模型，比如预测空缺值 典型应用 信誉证实 目标市场 医疗诊断 性能预测 回归方法（Regression） 线性回归：Y = α+ βX 其中a和b是回归系数，可以根据给定的数据点，通过最小二乘法来求得 多元回归：Y = α+ α1X1 + α2 X2 线性回归的扩展，设计多个预测变量，可以用最小二乘法求得上式中的α，α1 和α2 非线性回归：Y = α + α1X1 + α2 X22+ α3 X33 对不呈线性依赖的数据建模 使用多项式回归建模方法，然后进行变量变换，将非线性模型转换为线性模型，然后用最小二乘法求解 谢谢！ 大型数据库中描述统计计量 对于数据挖掘任务，用户经常关心的数据特征包括数据的中心趋势和离散特征 中心趋势的度量包括：mean， median， mode 和 midrange 数据离散度量包括：quartiles， outliers， variance 和其他度量 关系数据库中，系统提供了以下聚集函数：count()， sum()， avg()， max()， min() 在大型数据库中挖掘用户感兴趣的描述统计计量涉及到如何利用关系数据库现有的函数来计算上述两类用户感兴趣的度量值 度量中心趋势 算术平均值 加权算术平均: 中位值：使用一个近似的计算来度量 如果值的个数n是奇数，则中位数(median)是有序集合的中间值，否则它是中间两个数的平均值 用插值法(interpolation)来近似计算 模(mode) 表示数据集中出现频率最高的值 单模态、双模态、三模态、多模态和没有模的情况 单模态近似值计算的经验公式: 中列数：最大值和最小值的平均 度量数据的离散度 最常用度量：五数概括（基于四分位数）、中间四分位数区间和标准差 四分位数、孤立点和盒图 百分位数(percentile)：第k个百分位数是具有如下性质的值x：数据项的k%在x上或低于x 四分位数：Q1 (25th percentile)， Q3 (75th percentile) 中间四分位数区间(IQR)： IQR = Q3 – Q1 对倾斜分布的描述，除了IQR还常需两个四分位数Q1和Q3，以及中位数M，一个识别孤立点的常用规则是：挑出落在至少高于第三个四分位数或低于第一个四分位数 1.5×IQR处的值 度量数据的离散度 五数概括: min， Q1， M， Q3， max 盒图：数据分布的一种直观表示。 方差和标准差 方差s2：n个观测之x1，x2...xn的方差是 标准差s是方差s2的平方根 s是关于平均值的离散的度量，因此仅当选平均值做中心度量时使用 所有观测值相同则 s＝0，否则 s>0 方差和标准差都是代数度量 盒图-示例 在盒图中： 端点在四分位数上，使得盒图的长度是IQR 中位数M用盒内的线标记 胡须延伸到最大最小观测值 该盒图为在给定时间段在AllElectronics的4个分店销售的商品单价的盒图 分店1 中位数$80 Q1: $60 Q3: $100 基本统计类描述的图像显示-直方图 常用的显示数据汇总和分布的方法： 直方图、分位数图、q-q图、散布图和局部回归曲线 直方图 一种单变量图形方法 由一组矩形组成，这些矩形反映类在给定数据中出现的技术或频率 vxV红软基地
