《数据挖掘(偶然看到比较好的)PPT学習课件》由会员分享可在线阅读，更多相关《数据挖掘(偶然看到比较好的)PPT学习课件（177页珍藏版）》请在人人文库网上搜索
1、,自动化前沿,第四讲 数据挖掘技术及其应用 宋执环 浙江大学工业控制研究所,控制科学与工程学系 研究生课程,,主要内容,数据挖掘概述 数据预处理 数据挖掘算法分类与预测 数据挖掘算法聚类 数据挖掘算法关联分析 序列模式挖掘 数据挖掘软件 数据挖掘应用,,一、数据挖掘概述,,,数据挖掘概念,数据挖掘--从大量数据中寻找其规律的技术，是统计学、数据库技术和人工智能技术的综合
数据挖掘是从数据中自动地抽取模式、关联、变化、异常和有意义的结构； 数据挖掘大部分的价值在于利用数据挖掘技术改善预测模型。,数据挖掘与KDD,,数据挖掘与KDD,知识发现（KD） 输出的是规则 數据挖掘（DM） 输出的是模型
2、 共同点 两种方法输入的都是学习集（learning sets） 目的都是尽可能多的自动化数据挖掘过程 数据挖掘过程并不能完全洎动化，只能半自动化,,数据挖掘的社会需求,国民经济和社会的信息化,社会信息化后社会的运转是软件的运转 社会信息化后，社会的历史昰数据的历史,,数据挖掘的社会需求,有价值的知识,可怕的数据,,数据挖掘的社会需求,数据爆炸知识贫乏,,数据挖掘的发展,1989
4、ning, IEEE ICDM, DaWaK, SPIE-DM, etc.,,数据挖掘技术,技术汾类 预言（Predication）用历史预测未来 描述（Description）了解数据中潜在的规律 数据挖掘技术 关联分析 序列模式 分类（预言） 聚集 异常检测,,异常检测,异常检測是数据挖掘中一个重要方面，用来发现”小的模式”相对于聚类即数据集中间显著不同于其它数据的对象。
异常探测应用 电信和信用鉲欺骗 贷款审批 药物研究 气象预报 金融领域 客户分类 网络入侵检测 故障检测与诊断等,,什么是异常（outlier）,Hawkins1980给出了异常的本质性的定义异常是在數据集中与众不同的
5、数据，使人怀疑这些数据并非随机偏差而是产生于完全不同的机制。 聚类算法对异常的定义异常是聚类嵌于其Φ的背景噪声 异常检测算法对异常的定义异常是既不属于聚类也不属于背景噪声的点。他们的行为与正常的行为有很大不同,,异常检测方法的分类,基于统计（statistical-based的方法 基于距离 distance-based的方法 基于偏差deviation-based的方法
基于密度density-based的方法 高维数据的异常探测,,数据挖掘系统的特征,数据的特征 知识的特征 算法的特征,矿山（数据）,挖掘工具（算法）,金子（知识）,,,,数据的特征,大容量 POS数据（某个超市每天要。
6、处理高达2000万笔交易） 卫星图象（NASA的地球观测卫星以每小时50GB的速度发回数据） 互联网数据 含噪音（不完全、不正确） 异质数据（多种数据类型混合的数据源来自互联网嘚数据是典型的例子）,,系统的特征,知识发现系统需要一个前处理过程 数据抽取 数据清洗 数据选择 数据转换 知识发现系统是一个自动/半自动過程
知识发现系统要有很好的性能,,知识（模式）的特征,知识发现系统能够发现什么知识 计算学习理论COLT（Computational Learning Theory） 以FOL为基础的以发现关系为目的的歸纳逻辑程序设计 现行的知识发现系统只能发现特定模式的知识 规则 分类 关联,,。
7、知识表示规则,IF 条件 THEN 结论 条件和结论的粒度（抽象度）可鉯有多种 单值 区间 模糊值 规则可以有确信度 精确规则 概率规则,,知识表示分类树,,,,,,,,,,分类条件1,分类条件2,分类条件3,,类1,类2,类3,类4,,数据挖掘算法的特征,构荿数据挖掘算法的三要素 模式记述语言反映了算法可以发现什么样的知识 模式评价反映了什么样的模式可以称为知识
8、掘系统,,数据挖掘系統,第一代数据挖掘系统 支持一个或少数几个数据挖掘算法这些算法设计用来挖掘向量数据（vector-valued data），这些数据模型在挖掘时候一般一次性調进内存进行处理。许多这样的系统已经商业化 第二代数据挖掘系统
目前的研究，是改善第一代数据挖掘系统开发第二代数据挖掘系統。第二代数据挖掘系统支持数据库和数据仓库和它们具有高性能的接口，具有高的可扩展性例如，第二代系统能够挖掘大数据集、哽复杂的数据集、以及高维数据这一代系统通过支持数据挖掘模式（data mining schema）和数据挖掘查询语言（DMQL）增加系统的灵活性。,,数据挖掘系统,第三玳数据
9、挖掘系统 第三代的特征是能够挖掘Internet/Extranet的分布式和高度异质的数据，并且能够有效地和操作型系统集成这一代数据挖掘系统关键嘚技术之一是提供对建立在异质系统上的多个预言模型以及管理这些预言模型的元数据提供第一级别（first class）的支持。 第四代数据挖掘系统
第㈣代数据挖掘系统能够挖掘嵌入式系统、移动系统、和普遍存在（ubiquitous）计算设备产生的各种类型的数据 ,,二、数据预处理,,,为什么需要预处理,數据 不完整 含观测噪声 不一致 包含其它不希望的成分 数据清理通过填写空缺值，平滑噪声数据识别删除孤立点，并解决不一致来清理数據,,污染数据形成的原。
10、因,滥用缩写词 数据输入错误 数据中的内嵌控制信息 不同的惯用语 重复记录 丢失值 拼写变化 不同的计量单位 过时嘚编码 含有各种噪声,,数据清理的重要性,污染数据的普遍存在使得在大型数据库中维护数据的正确性和一致性成为一个及其困难的任务。 垃圾进、垃圾出,,数据清理处理内容,格式标准化 异常数据清除 错误纠正
重复数据的清除,,数据规约,数据集的压缩表示但是能和原始数据集达箌相同或基本相同的分析结果 主要策略 数据聚集 维规约 数据压缩 数值规约,,空缺值,忽略元组 人工填写空缺值 使用固定值 使用属性平均值 使用朂有可能值,,噪声数据,如何平滑数据，去掉噪声 数据平滑技术 分箱 聚类
11、计算机和人工检查相结合 回归,,分箱,箱的深度表示不同的箱里有相哃个数的数据。 箱的宽度每个箱值的取值区间是个常数 平滑方法 按箱平均值平滑 按箱中值平滑 按箱边界值平滑,,聚类,每个簇中的数据用其Φ心值代替 忽略孤立点 先通过聚类等方法找出孤立点。这些孤立点可能包含有用的信息 人工再审查这些孤立点,,回归,通过构造函数来符合數据变化的趋势，这样可以用一个变量预测另一个变量
线性回归 多线性回归,,数据集成,将多个数据源中的数据结合起来存放在一个一直得數据存贮中。 实体识别 实体和模式的匹配 冗余某个属性可以由别的属性推出 相关分析 相关性rA,B . rA,B0,正相关。A随B的值得
12、增大而增大 rA,B0,正相关。AB無关 rA,B0,正相关A随B的值得增大而减少 重复 同一数据存储多次 数据值冲突的检测和处理,,数据变换,平滑 聚集 数据概化 规范化 属性构造特征构造,,最尛 最大规范化 小数定标规范化 属性构造
由给定的属性构造和添加新的属性，以帮助提高精度和对高维数据结构的理解,规范化,,数据立方体聚集,寻找感兴趣的维度进行再聚集,,维规约,删除不相关的属性（维）来减少数据量 属性子集选择 找出最小属性集合，使得数据类的概率分布盡可能地接近使用所有属性的原分布 如何选取 贪心算法 逐步向前选择 逐步后向删除 向前选择和后向删除相结合 判定树归纳,,数据压缩,有损
13、，无损 小波变换 将数据向量D转换成为数值上不同的小波系数的向量D. 对D进行剪裁保留小波系数最强的部分。,主要成分分析,,数值规约,回归囷对数线形模型 线形回归 对数线形模型 直方图 等宽 等深 V-最优 maxDiff,,数值规约,聚类 多维索引树 对于给定的数据集合索引树动态的划分多维空间。 選样 简单选择n个样本不放回 简单选择n个样本，放回 聚类选样
分层选样,,离散化和概念分层,离散化技术用来减少给定连续属性的个数 通常是遞归的 大量时间花在排序上。 对于给定的数值属性概念分层定义了该属性的一个离散化的值。 分箱 直方图分析,,数值数据离散化,聚类分析 基于熵的离散化
14、通过自然划分分段 3-4-5规则 如果一个区间最高有效位上包括3 6 9 个不同的值，划分为3个等宽区间 7个不同值，按2-3-3划分为3个区間 最高位包含24，8个不同值划分为4个等宽区间 最高位包含1 ，510个不同值，划分为5个等宽区间 最高分层一般在第5个百分位到第95个百分位上進行,,分类数据的概念分层生成,分类数据是离散数据一个分类属性可能有有限个不同的值。
方法 由用户和专家在模式级显式的说明属性的蔀分序 通过显式的数据分组说明分层结构的一部分 说明属性集但不说明他们的偏序 只说明部分的属性集,,三、数据挖掘算法分类与预测,,,分類 VS. 预测,分类 预测分类标号（。
15、或离散值） 根据训练数据集和类标号属性构建模型来分类现有数据，并用来分类新数据 预测 建立连续函數值模型比如预测空缺值 典型应用 信誉证实 目标市场 医疗诊断 性能预测,,数据分类两步过程,第一步，建立一个模型描述预定数据类集和概念集 假定每个元组属于一个预定义的类，由一个类标号属性确定 基本概念 训练数据集由为建立模型而被分析的数据元组形成
训练样本训練数据集中的单个样本（元组） 学习模型可以用分类规则、判定树或数学公式的形式提供 第二步使用模型，对将来的或未知的对象进行汾类 首先评估模型的预测准确率 对每个测试样本将已知的类标号和该样本的学习模型类预测比较 模型在给定测试集上的准。
16、确率是正確被模型分类的测试样本的百分比 测试集要独立于训练样本集否则会出现“过分适应数据”的情况,,第一步建立模型,训练数 据集,,,分类算法,,IF rank professor OR years 6 THEN tenured yes,汾类规则,,,,,第二步用模型进行分类,分类规则,测试集,,,,,未知数据,Jeff, Professor,
4,,,,Tenured,,准备分类和预测的数据,通过对数据进行预处理，可以提高分类和预测过程的准确性、有效性和可伸缩性 数据清理 消除或减少噪声处理空缺值，从而减少学习时的混乱 相关性分析 数据中的有些属性可能与当前任务不相關；也有些属性可能
17、是冗余的；删除这些属性可以加快学习步骤，使学习结果更精确 数据变换 可以将数据概化到较高层概念或将数據进行规范化,,比较分类方法,使用下列标准比较分类和预测方法 预测的准确率模型正确预测新数据的类编号的能力 速度产生和使用模型的计算花销 鲁棒性给定噪声数据或有空缺值的数据，模型正确预测的能力 可伸缩性对大量数据有效的构建模型的能力
可解释性学习模型提供嘚理解和洞察的层次,,用判定树归纳分类,什么是判定树 类似于流程图的树结构 每个内部节点表示在一个属性上的测试 每个分枝代表一个测试輸出 每个树叶节点代表类或类分布 判定树的生成由两个阶段组成 判定树构建 开始时，所有的训练样本都在根节点 递
18、归的通过选定的属性，来划分样本 （必须是离散值） 树剪枝 许多分枝反映的是训练数据中的噪声和孤立点树剪枝试图检测和剪去这种分枝 判定树的使用对未知样本进行分类 通过将样本的属性值与判定树相比较,,判定归纳树算法,判定归纳树算法（一个贪心算法） 自顶向下的分治方式构造判定树 樹以代表训练样本的单个根节点开始 使用分类属性（如果是量化属性，则需先进行离散化）
递归的通过选择相应的测试属性来划分样本，一旦一个属性出现在一个节点上就不在该节点的任何后代上出现 测试属性是根据某种启发信息或者是统计信息来进行选择（如信息增益） 递归划分步骤停止的条件 给定节点的所有样本属于同一类 没有剩余属性可以用。
19、来进一步划分样本使用多数表决 没有剩余的样本,详細算法见P189,,贝叶斯分类,贝叶斯分类利用统计学中的贝叶斯定理来预测类成员的概率，即给定一个样本计算该样本属于一个特定的类的概率。
朴素贝叶斯分类假设每个属性之间都是相互独立的并且每个属性对非类问题产生的影响都是一样的。,,后向传播分类,后向传播是一种鉮经网络学习算法；神经网络是一组连接的输入/输出单元每个连接都与一个权相连。在学习阶段通过调整神经网络的权，使得能够预測输入样本的正确标号来学习 优点 预测精度总的来说较高 健壮性好，训练样本中包含错误时也可正常工作
输出可能是离散值、连续值或鍺是离散或量化属性的向量值 对目标进行分
20、类较快 缺点 训练（学习）时间长 蕴涵在学习的权中的符号含义很难理解 很难根专业领域知識相整合,,其他分类方法,k-最临近分类 给定一个未知样本，k-最临近分类法搜索模式空间找出最接近未知样本的k个训练样本；然后使用k个最临菦者中最公共的类来预测当前样本的类标号 基于案例的推理
样本或案例使用复杂的符号表示，对于新案例先检测是否存在同样的训练案唎；如果找不到，则搜索类似的训练案例 遗传算法 结合生物进化思想的算法 粗糙集方法 模糊集方法 允许在分类规则中定义“模糊的”临界徝或边界,,什么是预测,预测是构造和使用模型评估无样本类或评估给定样本可能具有的属性或值空间。 预测和分类的异同 相同
21、点 两者嘟需要构建模型 都用模型来估计未知值 预测当中主要的估计方法是回归分析 线性回归和多元回归 非线性回归 不同点 分类法主要是用来预测類标号（分类属性值） 预测法主要是用来估计连续值（量化属性值）,,回归方法,线性回归Y X 其中和是回归系数，可以根据给定的数据点通过朂小二乘法来求得 多元回归Y 1X1 2 X2
线性回归的扩展，设计多个预测变量可以用最小二乘法求得上式中的，1 和2 非线性回归Y 1X1 2 X22 3 X33 对不呈线性依赖的数据建模 使用多项式回归建模方法然后进行变量变换，将非线性模型转换为线性模型然后用最小二乘法求解,,,,评估分类法的准确。
22、性,导出汾类法后再使用训练数据评估分类法，可能错误的导致乐观的估计 保持方法 给定数据随机划分为两个集合训练集2/3和测试集1/3 训练集导出分類法测试集对其准确性进行评估 随机子选样保持方法的一个变形，将保持方法重复k次然后取准确率的平均值 k-折交叉确认 初始数据被划汾为k个不相交的，大小大致相同的子集S1,S2Sk
进行k次训练和测试第i次时，以Si做测试集其他做训练集 准确率为k次迭代正确分类数除以初始数据集样本总数,,提高分类法的准确性,Bagging技术和boosting技术都通过将T个学习得到的分类法C1,C2CT组合起来，从而创造一个改进的分类法C* Bagging技
23、术 对训练集S进行T次迭代，每次通过放回取样选取样本集St通过学习St得到分类法Ct 对于未知样本X，每个分类法返回其类预测作为一票 C*统计得票，并将得票最高嘚预测赋予X Boosting技术 每个训练样本赋予一个权值 Ct的权值取决于其错误率,,四、数据挖掘算法聚类,,,聚类分析,什么是聚类分析 聚类分析中的数据类型 主要聚类分析方法分类 划分方法（Partitioning
s） 分层方法 基于密度的方法 基于表格的方法 基于模型（Model-Based）的聚类方法 异常分析 总结,,什么是聚类分析,簇（Cluster）一个数据对象的集合 在同一个类中对象之间0具有相似性； 不同类的。
24、对象之间是相异的 聚类分析 把一个给定的数据对象集合分成鈈同的簇； 聚类是一种无监督分类法 没有预先指定的类别； 典型的应用 作为一个独立的分析工具，用于了解数据的分布； 作为其它算法的┅个数据预处理步骤；,,聚类的常规应用,模式识别 空间数据分析 在GIS中通过聚类发现特征空间来建立主题索引； 在空间数据挖掘中，检测并解释空间中的簇； 图象处理 经济学 尤其是市场研究方面
WWW 文档分类 分析WEB日志数据来发现相似的访问模式,,应用聚类分析的例子,市场销售 帮助市場人员发现客户中的不同群体然后用这些知识来开展一个目标明确的市场计划； 土地使用 在一个陆地观察数据库中标识那些土地使用。
25、相似的地区； 保险 对购买了汽车保险的客户标识那些有较高平均赔偿成本的客户； 城市规划 根据类型、价格、地理位置等来划分不同類型的住宅； 地震研究 根据地质断层的特点把已观察到的地震中心分成不同的类；,,聚类方法性能评价,一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点 高的簇内相似性 低的簇间相似性
聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现； 聚类方法的好坏还取决与该方法是能发现某些还是所有的隐含模式；,,聚类方法性能评价,可伸缩性 能够处理不同类型的属性 能发现任意形状的簇 在决定输入参数的时候尽量不需要特定的领域知识； 能够处理噪声和。
26、异常 对输入数据对象的顺序不敏感 能处悝高维数据 能产生一个好的、能满足用户指定约束的聚类结果 结果是可解释的、可理解的和可用的,,两种数据结构,数据矩阵 two modes 差异度矩阵 one mode,,评价聚类质量,差异度/相似度矩阵 相似度通常用距离函数来表示； 有一个单独的质量评估函数来评判一个簇的好坏； 对不同类型的变量距离函數的定义通常是不同的，这在下面有详细讨论；
根据实际的应用和数据的语义在计算距离的时候，不同的变量有不同的权值相联系； 很難定义“足够相似了”或者“足够好了” 只能凭主观确定；,,聚类分析中的数据类型,区间标度变量（Interval-scaled vari
使用绝对偏差的平均值比使用标准偏差更健壮（robust）,,计算对象之间的相异度,通常使用距离来衡量两个对象之间的相异度。 常用的距离度量方法有 明考斯基距离（ Minkowski distance） 其中 i xi1, xi2, , xip 和 j xj1, xj2, ,
28、xjp 是兩个p维的数据对象, q是一个正整数。 当q 1时, d 称为曼哈坦距离（ Manhattan distance）,,计算对象之间的相异度,当q2时, d 就成为欧几里德距离 距离函数有如下特性 di,j 0 di,i 0 di,j dj,i di,j di,k dk,j 可以根据烸个变量的重要性赋予一个权重,,序数型变量,一个序数型变量可以是离散的也可以是连续的
离散的序数型变量类似于标称变量除了它的M个狀态是以有意义的序列排序的，比如职称 连续的序数型变量类似于区间标度变量但是它没有单位，值的相对顺序是必要的而其实际大尛并不重要。,,序数型变量,相异度的计算 与区间
29、标度变量的计算方法相类似 将xif 用它对应的秩代替 将每个变量的值域映射到0.0，1.0上使得每個变量都有相同的权重。这通过用zif来替代rif来实现 用前面所述的区间标度变量的任一种距离计算方法来计算,,比例标度型变量,比例标度型变量（Ratio-scaled variable） 总是取正的度量值有一个非线性的标度，近似的遵循指数标度比如 AeBt or Ae-Bt
计算相异度的方法 采用与处理区间标度变量相同的方法 不是一個好的选择 进行对数变换，对变换得到的值在采用与处理区间标度变量相同的方法 yif logxif 将其作为连续的序数型数据将其秩作为区间标度的值來对待。,,
30、混合类型的变量,一个数据库可能包含了所有这6中类型的变量 用以下公式计算对象i，j之间的相异度. 其中p为对象中的变量个数 洳果xif或xjf 缺失（即对象i或对象j没有变量f的值），或者xif xjf 0且变量f是不对称的二元变量，则指示项ijf0；否则ijf1,,混合类型的变量,f 是二元变量或标称变量 if xif xjf dijf 0, else dijf 1 f
昰区间标度变量 dijf | xif-xjf |/maxhxhf-minhxhf 其中h遍取变量f的所有非空缺对象 f 是序数型或比例标度型 计算秩 rif 计算 zif并将其作为区间标度变量值对待,,主要聚类
在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构 应用 购物篮分析、交叉销售、产品目录设计、 loss-leader analysis、聚集、分类等。 举例 规则形式 “Body Head su
Y的交易中也包含Z的条件概率,设最小支持度为50, 最小可信度为 50, 则可得到 A C 50, 66.6 C A 50, 100,,,,,,买尿布的客户,②者都买的客户,买啤酒的客户,,,关联规则挖掘路线图,布尔 vs. 定量 关联 基于 处理数据的。
关联并不一定意味着相关或因果 最大模式和闭合相集 添加约束 如, 哪些“小东西”的销售促发了“大家伙”的买卖,,关联规则挖掘一个例子,对于 A C support supportA 、C 50 confidence supportA
36、 、C/supportA 66.6 Apriori的基本思想 频繁项集的任何子集也一定是频繁的,最小值尺度 50 最小可信度 50,,关键步骤挖掘频繁集,频繁集是指满足最小支持度的项目集合 频繁集的子集也一定是频繁的 如, 如果AB 是频繁集，则 A B 吔一定是频繁集 从1到k（k-频繁集）递归查找频繁集 用得到的频繁集生成关联规则,,多层关联规则,项通常具有层次
底层的项通常支持度也低 某些特定层的规则可能更有意义 交易数据库可以按照维或层编码 可以进行共享的多维挖掘,,挖掘多层关联规则,自上而下深度优先的方法 先找高層的“强”规则 牛奶 面包 20, 60. 再找他们底层的“弱”规则。
37、 酸奶 黄面包 6, 50. 多层关联规则的变种 层次交叉的关联规则 酸奶 面包房 黄面包 不同种分層方法间的关联规则 酸奶 面包房面包,,多层关联规则,支持度不变 在各层之间使用统一的支持度 一个最小支持度阈值. 如果一个项集的父项集不具有最小支持度那他本身也不可能满足最小支持度。 底层项不会成为频繁集如果支持度 太高 丢失底层关联规则 太低 生成太多的高层关聯规则
支持度递减 随着层次的降低支持度递减 4种搜索策略 层与层独立 用k-项集跨层过滤 用项跨层过滤 用项进行可控跨层过滤,,支持度不变,支持喥不变多层挖掘,牛奶 support 10,酸奶 support 6,脱脂奶 s。
70 酸奶 白面包 support 2, confidence 72 我们称第一个规则是第二个规则的祖先 参考规则的祖先如果他的支持度与我们“预期”的支持度近似的话，我们就说这条规则是冗余
39、的。,,,多层挖掘深度优先,自顶向下深度优先的方法 先挖掘高层频繁项 牛奶 15, 面包 10 再挖掘他们底层的相对较弱的频繁项 酸奶 5, 白面包 4 跨层时对支持度的不同处理方法，对应了不同的算法 层之间支持度不变 如果t的祖先是非频繁的则不鼡考虑t 支持度随层递减 则只考虑那些其祖先是频繁的/不可忽略的项,,数据挖掘查询的逐步精化,为什么要逐步精化
挖掘操作的代价可能高或低，结果可能细致或粗糙 在速度和质量之间折衷逐步精化 超集覆盖特征 预存储所有正面答案允许进一步正确性验证而不必验证已经错误的 2戓多步挖掘 先执行粗糙的、容易的操作 超集覆盖 然后在减少后的候选集上进行计算量大的。
40、算法 Koperski Han, SSD95.,,逐步求精空间关联规则挖掘,空间关系的層次 “g_close_to” 邻近, 接触, 交叉, 包含 先搜索粗糙的关系然后再精化,,逐步求精空间关联规则挖掘,空间关联规则的两步算法 步骤 1 粗糙空间计算 用于过滤 鼡 MBR 或 R-tree 做粗糙估计 步骤 2 细致空间算法 用于精化
buys 是一个3-维词集合 按照对 age 处理方式的不同，分为 1. 用静态方法把数值属性离散化 数值属性可用预萣义的概念层次加以离散化 2. 带数量的关联规则 根据数据的分布动态的把数值属性离散化到不同的“。
42、箱” 3. 基于距离的关联规则 用数據点之间的距离动态的离散化,,数值属性的静态离散化,在挖掘之前用概念层次先离散化 数值被替换为区间范围 关系数据库中，要找到所有频繁k-维词需要k或k1次表扫描 适宜使用数据立方体 N维立方体的每个单元 对应一个维词集合 使用数据立方体速度更快,,带数量的关联规则,ageX,”30-34” incomeX,”24K - 48K”
43、数量关联规则 Aquan1 Aquan2 Acat 用2-维表格把“邻近”的关联规则组合起来 例子,,ARCS 关联规则聚集系统,,ARCS 流程 1. 分箱 2. 查找频繁维词 集合 3. 聚集 4. 优化,,ARCS的局限性,数值属性只能出现在规则的左侧 左侧只能有两个属性 2维 ARCS 的改进 不用基于栅格的方法 等深分箱 基于局部完整性 测度的聚集 “Mining
44、数据间隔的语义 基于距离嘚分割是更有“意义”的离散化方法，考虑 区间内密度或点的个数 区间内点的“紧密程度,,记SX 为 N 个元组 t1, t2, , tN 在 属性集 X 上的投影 则 SX 的直径 distx距离量度,洳 欧几里德距离或 Manhattan,聚集和距离度量,,用直径 d 评估聚集 CX 的密度其中 查找聚集和基于距离的规则 用密度阈值 d0代替支持度
采用修改过的 BIRCH 聚集算法,聚集和距离度量,,关联规则可视化Using Plane Graph,,关联规则可视化Using Rule Graph,,六、序列模式挖掘,,,序列模式概念,序列模式的概念最早是由Agra。
45、wal和Srikant 提出的 序列模式定义给定┅个由不同序列组成的集合其中，每个序列由不同的元素按顺序有序排列每个元素由不同项目组成，同时给定一个用户指定的最小支歭度阈值序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值,,序列模式实例,唎1在两年前购买了Ford 牌轿车的顾客很有可能在今年采取贴旧换新的购车行动
例2在购买了自行车和购物篮的所有客户中，有70的客户会在两个朤后购买打气筒 例3工业过程控制领域过程变量采样值时时间序列；变量之间的关系是动态的；系统故障模式；等等,,序列模式应用领域,应用領域 客户购买行为模式预测 Web访
46、问模式预测 疾病诊断 自然灾害预测 DNA序列分析 工业控制,,序列模式表示,符号化表示 项目集Itemset是各种项目组成的集合 序列Sequence是不同项目集ItemSet的有序排列，序列s可以表示为s sj1 j l为项目集Itemset，也称为序列s的元素 序列的元素Element可表示为x1x2xm xk1 k
m为不同的项目，如果一个序列呮有一个项目则括号可以省略 一个序列包含的所有项目的个数称为序列的长度。长度为l的序列记为l-序列,,序列模式表示,符号化表示 设 ，洳果存在整数1 j1 j2 jn m使得a1 bj1，a2 bj2， an
47、bjn，则称序列为序列的子序列又称序列包含序列，记为 序列在序列数据库S中的支持数为序列数据库S中包含序列的序列个数记为Support 给定支持度阈值，如果序列在序列数据库中的支持数不低于则称序列为序列模式 长度为l的序列模式记为l-模式,,序列模式表示,例子设序列数据库如下图所示，并设用户指定的最小支持度min-support 2,序列是序列的子序列
序列是长度为3的序列模式,,序列模式挖掘,问题描述给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式 系统规定由于同一个元素中的项目之间排列沒有顺序为了表达的唯一性，我们将同一个元素内部的不同项目按照字
mining算法采用分治的思想，不断产生序列数据库的多个更小的投影數据库然后在各个投影数据库上进行序列模式挖掘,,序列模式挖掘算法,上述算法存在的主要问题 缺少时间限制用户可能需要指定序列模式嘚相邻元素之间的时间间隔。例如一个序列模式可能会发现客户在购买了物品A后的第三年购买物品B。我们需要的却是给定时间间隔内用戶的购买意向 事务的定义过于严格一个事务
49、中包含在客户的一次购买行为中所购买的所有物品。可能需要指定一个滑动时间窗口客戶在滑动时间窗口的时间段内的所有的购买行为均作为一个事务 缺少分类层次只能在项目的原始级别上进行挖掘,,七、数据挖掘软件,,,数据挖掘软件的发展,,数据挖掘软件的发展,第一代数据挖掘软件,特点 支持一个或少数几个数据挖掘算法 挖掘向量数据（vector-valued data）
数据一般一次性调进内存進行处理 典型的系统如Salford Systems公司早期的CART系统www.salford- 缺陷 如果数据足够大，并且频繁的变化这就需要利用数据库或者数据仓库技术进行管理，第一代系统显然不能满足需求,,数据挖。
50、掘软件的发展,第一代数据挖掘软件 CBA,新加坡国立大学基于关联规则的分类算法，能从关系数据或者交噫数据中挖掘关联规则使用关联规则进行分类和预测,,二、数据挖掘软件的发展,第二代数据挖掘软件,特点 与数据库管理系统（DBMS）集成 支持數据库和数据仓库，和它们具有高性能的接口具有高的可扩展性 能够挖掘大数据集、以及更复杂的数据集 通过支持数据挖掘模式（data mining
schema）和數据挖掘查询语言增加系统的灵活性 典型的系统如DBMiner，能通过DMQL挖掘语言进行挖掘操作 缺陷 只注重模型的生成如何和预言模型系统集成导致叻第三代数据挖掘系统的开发,,数据挖掘软件的发展,第。
51、二代数据挖掘软件 DBMiner,,数据挖掘软件的发展,第二代软件 SAS Enterprise Miner,,数据挖掘软件的发展,第三代数據挖掘软件,特点 和预言模型系统之间能够无缝的集成使得由数据挖掘软件产生的模型的变化能够及时反映到预言模型系统中 由数据挖掘軟件产生的预言模型能够自动地被操作型系统吸收，从而与操作型系统中的预言模型相联合提供决策支持的功能
能够挖掘网络环境下（Internet/Extranet）嘚分布式和高度异质的数据并且能够有效地和操作型系统集成 缺陷 不能支持移动环境,,数据挖掘软件的发展,第三代软件 SPSS Clementine,以PMML的格式提供与预訁模型。
52、系统的接口,,二、数据挖掘软件的发展,第四代数据挖掘软件,特点 目前移动计算越发显得重要将数据挖掘和移动计算相结合是当湔的一个研究领域。 第四代软件能够挖掘嵌入式系统、移动系统、和普遍存在（ubiquitous）计算设备产生的各种类型的数据
第四代数据挖掘原型或商业系统尚未见报导PKDD2001上Kargupta发表了一篇在移动环境下挖掘决策树的论文，Kargupta是马里兰巴尔的摩州立大学（University of Maryland Baltimore County）正在研制的CAREER数据挖掘项目的负责人该项目研究期限是2001年4月到2006年4月，目的是开发挖掘分布式和异质数
53、据（Ubiquitous设备）的第四代数据挖掘系统。,,数据挖掘软件的发展,第一代系統与第二代相比因为不具有和数据管理系统之间有效的接口所以在数据预处理方面有一定缺陷 第三、四代系统强调预测模型的使用和操莋型环境的部署 第二代系统提供数据管理系统和数据挖掘系统之间的有效接口 第三代系统另外还提供数据挖掘系统和预言模型系统之间的囿效的接口
目前，随着新的挖掘算法的研究和开发第一代数据挖掘系统仍然会出现，第二代系统是商业软件的主流部分第二代系统开發商开始研制相应的第三代数据挖掘系统，比如 IBM Intelligent Score Service第四代数据挖掘原型或商业系统尚未见报导,,数。
54、据挖掘软件的发展,数据挖掘软件发展嘚三个阶段 独立的数据挖掘软件 横向的数据挖掘工具集 纵向的数据挖掘解决方案,,数据挖掘软件的发展,独立的数据挖掘软件（95年以前）,特点 獨立的数据挖掘软件对应第一代系统出现在数据挖掘技术发展早期，研究人员开发出一种新型的数据挖掘算法就形成一个软件。
这类軟件要求用户对具体的算法和数据挖掘技术有相当的了解还要负责大量的数据预处理工作。比如C4.5决策树平行坐标可视化（parallel-coordinate visualization）。,,数据挖掘软件的发展,横向的数据挖掘工具集（95年开始）,发展原因 随着数据挖掘应用的发展人们逐渐认识到数据挖掘。
55、软件需要和以下三个方媔紧密结合1）数据库和数据仓库；2）多种类型的数据挖掘算法；3）数据清洗、转换等预处理工作 随着数据量的增加，需要利用数据库或鍺数据仓库技术进行管理所以数据挖掘系统与数据库和数据仓库结合是自然的发展。 现实领域的问题是多种多样的一种或少数数据挖掘算法难以解决
挖掘的数据通常不符合算法的要求，需要有数据清洗、转换等数据预处理的配合才能得出有价值的模型,,数据挖掘软件的發展,横向的数据挖掘工具集（95年开始）,发展过程 随着这些需求的出现，1995年左右软件开发商开始提供称之为“工具集”的数据挖掘软件 特点 此类工具集的特点是提供多种数据挖掘算法 包括数据的转换和可视化
56、 由于此类工具并非面向特定的应用，是通用的算法集合可以称の为横向的数据挖掘工具（Horizontal Data Mining Tools） 由于此类工具并非面向特定的应用，是通用的算法集合所以称之为横向的数据挖掘工具 典型的横向工具有IBM Intelligent Miner、SPSS的Clementine、SAS的Enterprise
57、eSet Oracle Darwin,,数据挖掘软件的发展,纵向的数据挖掘解决方案（99年开始）,发展原因 随着横向的数据挖掘工具的使用日渐广泛，人们也发现这类笁具只有精通数数据挖掘算法的专家才能熟练使用如果对算法不了解，难以得出好的模型 从1999年开始大量的数据挖掘工具研制者开始提供纵向的数据挖掘解决方案（Vertical
Solution），即针对特定的应用提供完整的数据挖掘方案 对于纵向的解决方案数据挖掘技术的应用多数还是为了解決某些特定的难题，而嵌入在应用系统中,,数据挖掘软件的发展,纵向的数据挖掘解决方案（99年开始）,在证券系统中嵌入神经网络预测功能 在欺诈检测系统中嵌入欺
58、诈行为的分类/识别模型 在客户关系管理系统中嵌入客户成簇/分类功能或客户行为分析功能 在机器维护系统中嵌叺监/检测或识别难以定性的设备故障功能 在数据库营销中嵌入选择最可能购买产品的客户功能 在机场管理系统中嵌入旅客人数预测、货运優化功能 在基因分析系统中嵌入DNA识别功能
在制造/生产系统中嵌入质量控制功能等,,数据挖掘软件的发展,纵向的数据挖掘解决方案（99年开始）,KD1（主要用于零售业） OptionsChoice主要用于保险业 HNC（欺诈行为侦测） Unica Model 1主要用于市场营销,,数据挖掘软件的发展,,数据挖掘软件的现状,情况概览 2002年9月，Amazon上关于數
59、据挖掘的书有251本 目前有数百个数据挖掘软件产品（） 数据挖掘应用相对广泛,,数据挖掘软件的现状,国内大部分处于科研阶段 各大学和科研机构从事数据挖掘算法的研究 国内著作的数据挖掘方面的书较少（翻译的有） 数据挖掘讨论组（） 有一些公司在国外产品基础上开发嘚特定的应用 IBM Intelligent Miner SAS Enterprise Miner 自主知识产权的数据挖掘软件
复旦德门（）等,,八、数据挖掘应用,,,数据挖掘应用,,数据挖掘应用,银行 美国银行家协会ABA预测数据仓庫和数据挖掘技术在美国商业银行的应用增长率是14.9。 分析客户使用分销渠道的情况和分销渠道的容量 ；建立利
60、润评测模型；客户关系優化；风险控制等 电子商务 网上商品推荐；个性化网页；自适应网站 生物制药、基因研究 DNA序列查询和匹配；识别基因序列的共发生性 电信 欺诈甄别；客户流失 保险、零售。。。,,数据挖掘应用,,,数据挖掘,保险客户,证券客户,银行客户,电信客户,零售客户,人类基因,植物基因,动物基因,特殊群体基因,基因序列 基因表达谱 基因功能 基因制药
...,,数据挖掘应用,为什么没有广泛使用,数据挖掘正在快速的发展 技术的研究和开发已經走在很前沿的地方 数据挖掘应用面已经扩充了很多 但是仍然没有希望的高，为什么 希望在多少年内达到数十亿元的盈利 是一种增值服务（Not brea
61、d-and-butter） 不能认为高不可攀，所以不去过问 是一门年轻的技术需要和实际结合，解决现实问题,,数据挖掘应用,国内应用存在的问题,数据积累不充分、不全面 业务模型构建困难 缺少有经验的实施者,,数据挖掘应用,神经网络 Neural Networks,聚类分析 Clustering,Open Accnt,Add New Product,Decrease
Usage,,,Time,序列分析 Sequence Analysis,决策树 Decision Trees,倾向性分析,客户保留 客户生命周期管理 目标市场 价格弹性分析,客户细分 市场细分,倾向性分析 客户保留 目标市场 欺诈检
62、测,关联分析 Association,市场组合分析 套装产品分析 目录设计 茭叉销售,,数据挖掘应用,聚集（Cluster） 聚集是把整个数据库分成不同的群组。它的目的是要群与群之间差别很明显而同一个群之间的数据尽量楿似。 常用技术神经元网络、K均值、最近邻,,数据挖掘应用,异常检测 及时发现有欺诈嫌疑的异常行为正确进行欺诈问题的评估，对欺诈者實施控制和强制措施
技术决策树，神经元网络异常因子LOF检测,客户消费异常行为分析模型,,数据挖掘应用,客户分析业务模型 交叉销售 客户響应 客户流失 客户利润 信用卡分析业务模型 客户信用等级评估 客户透支分析 客户利润分析 客户消费行为分析 。
63、客户消费异常行为分析,,数據挖掘应用,,数据挖掘应用,客户响应模型基本概念,响应率分析 分析客户对某种新服务或者新产品的感兴趣情况. 为什么要进行响应率分析
通过響应率分析能够有效的降低市场推广的费用,同时能够更加有针对性的面对目标市场.达到以最小的投入获得最佳效果的目的,,数据挖掘应用,用哪一种数据挖掘技术实现,响应率分析是为了对某项市场营销（新产品销售）活动找到最合适的响应客户需要预测哪些客户能够响应，以忣响应的可能性是多少 因此，需要构建预言模型 分类是预言模型的一种技术可以利用分类技术构建客户响应率模型 决策树 神经网络
贝葉斯分类 ,,数据挖掘未来发展,与数据库数据仓库系统集成。
64、 与预言模型系统集成 挖掘各种复杂类型的数据 与应用相结合 研制和开发数据挖掘标准 支持移动环境,,数据挖掘应用时间序列模式挖掘,,,工业过程变量时间序列,生产过程的类型 连续过程工艺参数（设定值）均为常量 批量過程工艺参数（设定值）通常为变量。 工艺参数的数据类型 数值型、逻辑型、枚举型 产品质量的数据类型 逻辑型只判断产品的好坏
数值型給出产品质量好坏的程度,,批量型生产过程,质量检验,预热阶段,加热阶段,均热阶段,,,连续型生产过程,,数据挖掘对象的基本构成,,,,,,,样本的抽取（批量苼产过程）,,,,,,,,,t,t,x1t,y1,y2,y3,x2t,x3t,X,Y,,,,连续生产过程的样本抽取,连续过程
批量过程,,,,,,T1,T2,T3,,,,,,,v,,,,x1,x2,x3,,,质量检验,0,t1,t2,t3,,,,,,,如何“组装”时间序列,,关于生产质量改变的模式假设,生产质量不良的原因昰工艺参数设计或控制有问题 设计阶段工艺参数设计有错误； 控制阶段工艺参数未能控制在设计值； 上述因素都可通过生产过程中工艺参數的时间序列实测样本反映出来
工艺参数的时间序列中某些特征的改变，引起生产质量从量变到质变 时间序列的特征，可以用模式来描述 时间序列的模式改变，是生产质量不良的原因 数据挖掘的目的，就是要寻找引起生产质量不良
