第四讲数据挖掘概述与关联规则(2013)

1、数据挖掘入门(r mn)什么激发了数据挖掘，为什么它是重要的？什么是数据挖掘？在何种数据上进行(jnxng)数据挖掘？数据挖掘的功能几种较为流行的数据挖掘技术12022/7/19共六十五页1、什么激发(jf)了数据挖掘，为什么它是重要的？数据爆炸性的增长：从兆字节terabytes 到千兆字节petabytes。多种海量数据源商业: 网络, 电子商务, 交易, 股票, 科学: 遥感数据, 生物信息学, 科学模拟, 社会各个角落: 新闻, 数字影像, 视频， “我们(w men)被信息淹没却信息贫乏!” “需要是发明之母” 数据挖掘海量数据库的自动化分析。22022/7/19共六十五页32、什么

2、(shn me)是数据挖掘?数据挖掘（从数据中发现(fxin)知识） 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。2022/7/19共六十五页7/19/20224数据挖掘和商务(shngw)智能Increasing potentialto supportbusiness decisionsEnd UserBusiness Analyst DataAnalystDBADecision MakingData PresentationVisualization TechniquesData MiningInfo

3、rmation DiscoveryData ExplorationStatistical Summary, Querying, and ReportingData Preprocessing/Integration, Data WarehousesData SourcesPaper, Files, Web documents, Scientific experiments, Database Systems数据库管理员OLAP商务智能通常被理解为将企业中现有(xin yu)的数据转化为知识，帮助企业做出明智的业务经营决策的工具。一般由数据仓库、联机分析处理、数据挖掘、数据备份和恢复等部分组成。

4、共六十五页数据挖掘：多种学科(xuk)的交叉5Data MiningDatabase TechnologyStatisticsMachineLearningPatternRecognitionAlgorithmOtherDisciplinesVisualization2022/7/19共六十五页6、数据挖掘的功能(gngnng)关联分析(fnx)分类和预测聚类异常值探测序列模式挖掘62022/7/19共六十五页关联分析是用于挖掘、发现大量数据(shj)中项集之间存在的、重要的、有趣的知识。若两个或多个变量的取值之间存在某种规律性，就称为关联。在不知道关联函数或关联函数不确定的情况下，为了反映所

5、发现规则的有用性和确定性，关联分析生成的规则都要满足最小支持度阈值和最小置信度阈值。7关联(gunlin)分析2022/7/19共六十五页关联分析(fnx)的应用：比 如 人 寿 保 险。 保 险 公 司 在 接 受 保 险 前， 往 往 需 要 记 录 投 保 人 详 尽 的 信 息， 有 时 还 要 到 医 院 做 身 体 检 查。 保 单 上 记 录 有 投 保 人 的 年 龄、 性 别、 健 康 状 况、 工 作 单 位、 工 作 地 址、 工 资 水 平 等。通 过 分 析 这 些 数 据， 可 以 得 到 类 似 以 下 这 样 的 关 联 规 则： 年 龄 在40 岁 以 上，

6、工 作 在A 区 的 投 保 人 当 中， 有45 的 人 曾 经 向 保 险 公 司 索 赔 过。 在 这 条 规 则 中，“ 年 龄 在40 岁 以 上”“ 工 作 在A 区” “向 保 险 公 司 索 赔 过” 可 以 看 出 来，A 区 可 能 污 染 比 较 严 重， 环 境 比 较 差， 导 致 工 作 在 该 区 的 人 健 康 状 况 不 好， 索 赔 率 也 相 对 比 较 高。2022/7/198共六十五页分类(fn li)和预测分类是对一个类别进行描述及概括相关特征，并提取出描述重要数据类的模型。数据挖掘中的分类方法很多，主要有决策树和决策规则、贝叶斯网络、神经网络以及遗

7、传算法等。预测是通过(tnggu)建立连续值函数模型达到预测未来的数据趋势。预测的方法主要有回归分析、时间序列分析等。各种分类模型也可以预测，但主要是预测分类标号。92022/7/19共六十五页聚类聚类是在要划分的类未知的情况下，将数据库中的记录划分为多个类或簇，使得同类内的对象之间具有较高的相似度，不同类间的差异较大。它是概念描述和偏差分析(fnx)的先决条件。数据挖掘中的聚类方法有划分方法、层次的方法、基于密度的方法、基于网格的方法以及基于模型的方法等。102022/7/19共六十五页异常(ychng)值探测异常值指的是数据库中不符合数据一般模型的数据对象。从数据库中探测异常值很有意义，因

8、为它们本身可能隐藏着重要的信息，比正常的数据更有用，忽略或删除它们都会导致信息的丢失。例如(lr)，发现金融和保险领域的欺诈行为、税款的脱逃、通信费用的恶意欠费、网络中的黑客入侵、追寻极低或极高收入者的消费行为以及对多种治疗方式不寻常反映的发现等。112022/7/19共六十五页序列(xli)模式挖掘序列模式挖掘是指挖掘相对时间或其他序列出现频率高的规律或趋势，并建模。这里的序列一般(ybn)指时间序列数据库和序列数据库（Web日志分析和DNA分析）。在许多行业产生的数据库都是时间序列数据库，例如，商业交易、电信部门、天气数据等等，因此，序列模式的挖掘是非常有意义的。122022/7/19共六

9、十五页序列分析和关联规则的相似之处在于，它们所用的样本数据中，每一个(y )样本都包含了一个(y )项集或状态集合。其不同之处在于序列分析研究的是项集(或状态)间的转换，而关联规则模型研究的是项集之间的相关性。在序列分析模型中，先购买计算机再购买音箱，和先购买音箱再购买计算机是两种不同的序列。而在关联规则中这两种行为都表达了一个同样的项集计算机，音箱。2022/7/1913共六十五页14决策树聚类时间序列关联规则贝叶斯分类类神经网络罗吉斯回归线性回归(hugu)文本(wnbn)数据挖掘7、几种数据挖掘技术2022/7/19共六十五页算法(sun f)与任务对应共六十五页数据挖掘的任务(rn w

10、u)：分类：基于一个可预测属性(shxng)把事例分成多个类。典型的分类算法包括决策树算法、神经网络算法和贝叶斯算法聚类：基于一组属性对事例进行分组，是一种无监督的数据挖掘任务，没有一个属性用于指导模型的构建过程。回归：类似于分类任务，最大的区别在回归任务中可预测的属性是连续的。线性回归和逻辑回归是最常用的回归算法。其他的回归分类技术包括回归树和神经网络关联：也称为购物篮分析。用于确定一组项集和规则。预测：预测技术处理一般的趋势分析、周期分析和噪声过滤。常用的时间序列技术是ARIMA，它代表AutoRegressive Integrated Moving Average模型序列分析：用来发现离

11、散序列中的模式。序列分析的是状态的转移，关联模型认为客户购物车中的每一个商品都是平等和相互独立的。偏差分析：是为了找出一些特殊事例。如信用卡欺诈等共六十五页数据挖掘模型：可以认为数据挖掘模型（或者简称挖掘模型）是一个关系表。他包括键列、输入列和可预测列。一个模型的设定与挖掘算法有关，模型由该数据挖掘算法训练。通过使用指定的挖掘算法和适当的算法参数值，训练一个挖掘模型就是在训练数据集中发现模式。在对模型进行训练之后，数据挖掘模型讲存储模式，这些模式是关于某个数据集的，并且这些模式是由数据挖掘算法发现。如果说关系表是一个存储记录的容器(rngq)，那么数据挖掘模型就是一个存储模式的容器(rngq)

12、。共六十五页数据挖掘的三个步骤：(1)建立数据挖掘模型（DMM）；(2)利用已用数据和挖掘算法培训挖掘模型；(3)预测查询。数据挖掘模型从某种意义上可以被视为一个关系(gun x)表，它包含一些不同数据类型的列，分别为输入列和预测列。共六十五页共六十五页4.1 关联(gunlin)规则挖掘关联规则挖掘发现大量数据(shj)中项集之间有趣的关联或相关联系。随着大量数据不停地收集和存储，人们对于从数据库中挖掘关联规则越来越感兴趣。从大量商业事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和促销分析等。2共六十五页4.1 关联(gunlin)规则挖掘如何从事务(shw)

13、DB或关系DB的大量数据中挖掘出关联规则知识？什么样的关联规则才是最有意义的？如何才能使挖掘过程尽快发现有价值的关联规则知识？这就是本章要讨论的内容。3共六十五页4.1 关联(gunlin)规则挖掘1. 购物篮分析(fnx)购物篮分析是关联规则挖掘的最初形式。假定作为某商店经理，你想更加了解你的顾客的购物习惯。例如：“顾客多半会在一次购物时同时购买什么商品组或集合？”，为解答这个问题，可以在商店顾客事务零售数据上运行购物篮分析。分析的结果可用于市场规划、广告策划和分类设计。4共六十五页54.1 关联(gunlin)规则挖掘购物篮分析(fnx)若设商店中所有销售商品为一个集合，则每个商品均为一个

14、布尔变量，表示该商品是否被(一个)顾客购买。因此每个购物篮就可以用一个布尔向量表示。分析相应布尔向量，得到反映商品频繁关联或同时购买的购买模式，并可用关联规则的形式表示模式。例如，购买计算机也趋向于同时购买财务管理软件可用以下关联规则表示：共六十五页4.1 关联(gunlin)规则挖掘购物篮分析(fnx)computer = financial _ management _ softwaresupport = 2%, confidence = 60%关联规则的支持度(support)2% 表示：分析中的全部事务的2% 同时购买计算机和财务管理软件。关联规则的置信度(confidence)60%

15、 表示：购买计算机的顾客60% 也购买财务管理软件。6共六十五页规则的支持度和置信度是两个规则兴趣度量值，它们分别表示发现规则的有用性和确定性规则A = B在事务级中D中成立，具有支持度s，其中s是D中事务包含（即A和B二者）的百分比，它是概率p(AU B)关联模式(msh)的支持度是模式(msh)为真的任务相关的元组（或事务）所占的百分比。对于关联规则 A= B（其中A和B是项目的集合），支持度定义为：共六十五页规则(guz)A = B在事务集中具有置信度c，其中D中包含A的事务同时也包含B的百分比是c。这是条件概率P ( B | A)共六十五页4.1 关联规则挖掘基本概念【例1 】任务相关

16、数据由某商店(shngdin)计算机部购买物品的事务数组成，一个置信度为80% 的关联规则：buys ( X , “ computer” ) = buys ( X , “ software ” )意味着买计算机的顾客(gk)80% 也买软件。10共六十五页4.1 关联(gunlin)规则挖掘基本概念【例2 】例1中一个支持度为30% 的关联规则，意味着计算机部的所有顾客的30%,同时(tngsh)购买了计算机和软件。支持度和置信度是两个兴趣度度量,分别反映发现规则的有用性和确定性。支持度小：规则使用面窄置信度小：规则无意义12共六十五页4.1 关联规则(guz)挖掘基本概念满足最小支持度阈值和

17、最小置信度阈值的关联规则被认为是有趣(yuq)的。阈值由用户或专家设定。强规则：同时满足用户定义的最小支持度阈值（min_sup）和最小置信度阈值(min_conf)的规则称为强规则。为方便计，用0% 和100%之间的值表示支持度和置信度。13共六十五页4.1 关联规则(guz)挖掘基本概念项集的频率：即包含项集的事务数，也称为项集的支持计数(support_count)。如果项集的出现频率大于或等于(dngy)min_sup与D中事务总数的乘积，就称该项集满足最小支持度min_sup 。频繁项集：满足最小支持度的项集称为频繁项集。频繁k-项集的集合通常记作Lk。14共六十五页4.1 关联(g

18、unlin)规则挖掘基本概念关联规则挖掘包含两个(lin )步骤：1）找出所有频繁项集：根据定义，这些项集的频繁性至少和预定义的最小支持计数一样。2）由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小置信度。15共六十五页4.1 关联规则(guz)挖掘3.关联(gunlin)规则挖掘分类根据不同的标准，关联规则可以分成若干类型：(1)根据规则所处理的值的类型，关联规则可以分为布尔的和量化的如果规则考虑的关联是项的在与不在，则它是布尔关联规则。例如，由购物篮分析得到的就是布尔关联规则。16共六十五页4.1 关联规则(guz)挖掘关联规则(guz)挖掘分类如果规则描述的是量化的项

19、或属性之间的关联，则它是量化关联规则。在这种规则中，项或属性的量化值划分为区间。例如，下面的规则就是量化关联规则，其中X是代表顾客的变量。age ( X，“31 -35 ”) income ( X， 5万 - 8万)= buys ( X， computer )注：量化属性age和income已离散化。17共六十五页4.1 关联(gunlin)规则挖掘关联规则(guz)挖掘分类(2)根据规则中数据涉及的维，关联规则可以分为单维的和多维的如果关联规则中的每个项或属性只涉及一个维，则它是单维关联规则。下面的规则buys(X , “computer”) = buys(X , “software”)由于

20、只涉及一个维(属性buys),因此它是一个单维关联规则。18共六十五页4.1 关联(gunlin)规则挖掘关联规则挖掘(wju)分类如果规则涉及两个或多个维，则它是多维关联规则。下面的规则age ( X，31-35 ) income ( X，5万 - 8万)= buys ( X，computer )涉及三个维age、income和buys，它是一个多维关联规则。19共六十五页4.1 关联规则(guz)挖掘关联规则挖掘(wju)分类单维关联规则展示的是属性内联系，即同一个属性或维内的关联；多维关联规则展示的是属性间联系，即属性/维之间的关联。20共六十五页4.1 关联规则(guz)挖掘关联规则(

21、guz)挖掘分类(3)根据规则涉及的抽象层，关联规则可以分为单层的和多层的有些挖掘关联规则的方法可以在不同的抽象层发现关联规则。例如，假定挖掘的关联规则集包含下面规则：age ( X, 31 - 35 ) = buys ( X, notebook_computer )age ( X, 31 - 35 ) = buys ( X, computer )21共六十五页4.1 关联规则(guz)挖掘关联(gunlin)规则挖掘分类在上面的规则集中，购买的商品涉及不同的抽象层。则称所挖掘的规则集由多层关联规则组成。反之，若在给定的规则集中，规则不涉及不同抽象层的项或属性，则该集合包含单层关联规则。(4)

22、根据对关联挖掘的不同扩充，关联挖掘可以扩充到相关分析，最大模式，频繁闭项集的挖掘。22共六十五页4.2 挖掘单维布尔关联(gunlin)规则本节介绍(jisho)最简单关联规则(单维、单层、布尔关联规则)的挖掘方法。购物篮分析就是挖掘这种关联规则。Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的基本算法。24共六十五页Apriori算法(sun f)25共六十五页4.2 挖掘单维布尔关联(gunlin)规则1.Apriori 算法(sun f)Apriori算法是根据有关频繁项集性质的先验知识而命名的。该算法使用一种逐层搜索的迭代方法，利用k-项集探索(k+1)-项集。具体做法：首

23、先找出频繁1-项集的集合，记为L1 ；再用L1找频繁2-项集的集合L2 ；再用L2找L3 如此下去，直到不能找到频繁k-项集为止。找每个Lk需要一次数据库扫描。26共六十五页4.2 挖掘(wju)单维布尔关联规则Apriori 算法(sun f)Apriori算法的有效性,在于它利用了一个非常重要的原理,即Apriori性质。Apriori性质：如果一个项集是频繁的，则这个项集的任意一个非空子集都是频繁的。它基于如下观察：如果项集I不满足最小支持度阈值min_sup，则I 不是频繁的。如果增加项i到I，则结果项集 I Ui不可能比I更频繁出现。因此，也不是频繁的。27共六十五页4.2 挖掘单维

24、布尔关联(gunlin)规则Apriori 算法该性质属于一种特殊的分类，也称作反单调性。意指如果一个集合不能通过测试，则它的所有超集也都不能通过相同的测试。反单调性能迅速剪枝，提高(t go)搜索频繁项集的处理效率。下面我们来看Apriori算法是如何利用反单调性，用Lk-1寻找Lk 。28共六十五页4.2 挖掘单维布尔关联规则(guz)Apriori 算法整个过程由连接和剪枝两步组成，即：连接步产生(chnshng)候选项集剪枝步确定频繁项集(1)连接步为找Lk，可通过Lk-1与自己连接，产生一个候选k-项集的集合，该候选项集的集合记作Ck 。29共六十五页4.2 挖掘单维布尔关联(gun

25、lin)规则Apriori 算法设l1和l2是Lk-1中的项集，记号(j ho)lij表示li的第j项。为方便计，假定事务或项集中的项按字典次序排序。执行连接 Lk-1 Lk-1 ， 其中Lk-1的元素是可连接的，如果它们前(k-2 )个项相同。30共六十五页4.2 挖掘单维布尔关联(gunlin)规则Apriori 算法即，Lk-1的元素(yun s)l1和l2是可连接的，若：（ l11 = l21 l1 2 = l2 2 l1k-2 = l2k-2 l1k-1 l2k-1 ）而条件（l1k-1 l2k-1）可确保不产生重复的项集。31共六十五页4.2 挖掘(wju)单维布尔关联规则Apri

26、ori 算法(2)剪枝(jin zh)步Ck是Lk的超集，即它的成员不一定都是频繁项集，但所有的频繁k-项集都包含在Ck中。扫描数据库，确定Ck中每个候选项集的计数，从而确定Lk。然而， Ck可能很大，这样所涉及的计算量就很大。32共六十五页4.2 挖掘(wju)单维布尔关联规则Apriori 算法为了压缩(y su)Ck，可利用Apriori性质：任何非频繁的(k-1)-项集都不可能是频繁k-项集的子集。因此，若一个候选k-项集的(k-1)-项子集不在Lk-1中，则该候选也不可能是频繁的，从而可以从Ck中删除。33共六十五页344.2 挖掘单维布尔关联(gunlin)规则Apriori 算法

27、TID项ID的列表(li bio)【例3 】一个Apriori的具体例子，该例基于右图某商店的事务DB。DB中有9个事务，Apriori假定事务中的项按字典次序存放。T100T200T300T400T500T600T700T800T900I1，I2，I5I2，I4I2，I3I1，I2，I4I1，I3I2，I3I1，I3I1，I2，I3，I5I1，I2，I3共六十五页（1）在算法(sun f)的第一次迭代，每个项都是候选1-项集的集合C1的成员。算法简单地扫描所有的事务，对每个项的出现次数计数(j sh)。C1项集 支持度计数扫描D,对每个候选计数I1I2I3I4I56762235共六十五页（2

28、）设最小支持计数为2，可以确定频繁1-项集的集合L1 。它由具有最小支持度的候选(hu xun)1-项集组成。L1项集 支持度计数比较候选支持(zhch)度计数与最小支持度计数I1I2I3I4I56762236共六十五页（3）为发现频繁2-项集的集合L2 ，算法(sun f)使用 L1 L1 产生候选2-项集集合C2 。由L1产生(chnshng)候选C2C2项集I1，I2I1，I3I1，I4I1，I5I2，I3I2，I4I2，I5I3，I4I3，I5I4，I537共六十五页42（4）扫描D中事务，计算(j sun)C2中每个候选项集的支持计数。 C2项集I1，I2I1，I3I1，I4I1，I

29、5支持(zhch)度计数4412扫描D,对每个候选计数I2，I3I2，I4I2，I5I3，I4I3，I5201I4，I5038共六十五页42（5）确定频繁2-项集的集合L2 ，它由具有最小支持(zhch)度的C2中的候选2-项集组成。L2项集I1，I2支持(zhch)度计数4比较候选支持度计数与最小支持度计数I1，I3I1，I5I2，I3I2，I4I2，I542239共六十五页（6）候选(hu xun)3-项集的集合C3 的产生如下： 连接(linji)： C3 = L2 L2 = I1,I2，I1,I3，I1,I5，I2,I3，I2,I4，I2,I5 I1,I2，I1,I3，I1,I5，I2

30、,I3，I2,I4，I2,I5 =I1,I2,I3，I1,I2,I5，I1,I3,I5，I1,I2,I4I2,I3,I4， I2,I3,I5，I2,I4,I540共六十五页 利用(lyng)Apriori性质剪枝：频繁项集的所有子集(z j)必须是频繁的。存在候选项集，判断其子集是否频繁。I1,I2,I3的2-项子集是I1,I2，I1,I3和I2,I3,它们都是L2的元素。因此保留I1,I2,I3在C3中。I1,I2,I5的2-项子集是I1,I2，I1,I5和I2,I5,它们都是L2的元素。因此保留I1,I2,I5在C3中。I1,I3,I5的2-项子集是I1,I3，I1,I5和I3,I5,I3

31、,I5不是L2的元素，因而不是频繁的，由C3中删除I1,I3,I5。41共六十五页42I2,I3,I4的2-项子集(z j)是I2,I3，I2,I4和I3,I4,其中I3,I4不是(b shi)L2的元素，因而不是频繁的，由C3中删除I2,I3,I4。I2,I3,I5的2-项子集是I2,I3，I2,I5和I3,I5,其中I3,I5不是L2的元素，因而不是频繁的，由C3中删除 I2,I3,I5。I2,I4,I5的2-项子集是I2,I4，I2,I5和I4,I5,其中I4,I5不是L2的元素，因而不是频繁的，由C3中删除I2,I4,I5 。共六十五页43 这样(zhyng)，剪枝后C3 = I1,I2,I3，I1,I2,I5。（7）扫描D中事务，以确定L3 ，它由C3中具有最小支持度的的候选3-项集组成。C3由L2产生(chnshng)候选C3C3项集I1，I2，I3I1，I2，I5扫描D,对每个候选计数项集I1，I2，I3I1，I2，I5支持度计数22共六十五页（8）算法使用(shyng) L3 L3 产生候选4-项集的集合C4 。尽管连接产生结果 I1,I2,I3,I5,这个项集被剪去，因为它的子集I2,I3,I5不是频繁的。则 C4 = ,因此算法终止，找出了所有的频繁项集。L3比较候选(hu xun)支持度计数与最小支持度计数项集I