第5章数据挖掘-1

1、数据挖掘数据挖掘的产生n随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来越多。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象。数据挖掘的案例：“啤酒啤酒”和和“尿布尿布”n一则广为流传的案例：啤酒和尿布的故事n美国加州某个超市连锁店发现: 在下班后前来购买婴儿尿布的顾客多数是男性，他们往往也同时购买啤酒。n处理：重新布置了货架，啤酒类商品、婴儿尿布、土豆片之类的佐酒小食品、男士们日常生活用品就近布置。n结果：上述几种商

2、品的销量几乎马上成倍增长。什么是数据挖掘?n从数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程。n非平凡（的过程）：有一定的智能性、自动性（仅仅给出所有数据之和不能算做一个发现过程）。n有效性：所发现的模式对新的数据仍保持一定的可信度。n新颖性：所发现的模式应该是新的。n潜在有用性：所发现的模式将来有实际的效用。n最终可理解性：能被用户理解，如：简洁性n有趣性：有效性、新颖性、潜在有用性、最终可理解性的综合。数据挖掘是多学科的交叉数据挖掘数据库技术统计学其他学科信息科学机器学习可视化数据挖掘与数据仓库的关系n数据挖掘是数据仓库发展的必然结果n数据仓库为数据挖掘提供应用

3、基础n数据挖掘也不必非得建立一个数据仓库n从数据仓库中直接进行数据挖掘有许多好处。数据挖掘和OLAPnOLAP分析过程在本质上是一个演绎推理演绎推理的过程，是决策支持领域的一部分。传统的查询和报表工具是告诉你数据库中都有什么（what happened），OLAP则更进一步告诉你下一步会怎么样（What next）和如果采取这样的措施又会怎么样（What if）。用户首先建立一个假设，然后用OLAP检索数据库来验证这个假设是否正确。n数据挖掘在本质上是一个归纳推理归纳推理的过程，与OLAP不同的地方是，数据挖掘不是用于验证某个假定的模式（模型）的正确性，而是在数据库中自己寻找模型。n数据挖掘和

4、OLAP具有一定的互补性互补性。在利用数据挖掘出来的结论采取行动之前，OLAP工具能起辅助决策作用。而且在知识发现的早期阶段，OLAP工具用来探索数据，找到哪些是对一个问题比较重要的变量，发现异常数据和互相影响的变量。这都有助于更好地理解数据，加快知识发现的过程。数据挖掘的步骤n数据准备 n数据选择：目标数据n数据预处理：消除噪声、不一致、冗余等n数据变换：连续数据离散化、数据转化n数据归约：特征选择或抽取n数据挖掘算法的选择.n首先要明确任务,如数据总结、分类、聚类、关联规则发现、序列模式发现等。n考虑用户的知识需求（得到描述性的知识、预测型的知识）。n根据具体的数据集合，选取有效的挖掘算法

5、。数据挖掘的步骤n结果的解释评估（interpretation and evaluation）n对挖掘出来的结果（模式），经用户或机器评价，剔除冗余或无关的模式。n模式不满足用户需求时，返回到某一步，重新挖掘。如：重新选择数据、采用新的变换方法、设定新的数据挖掘参数，或者换一种挖掘算法（如分类方法，不同的方法对不同的数据有不同的效果）。n挖掘的结果是面向用户的，对挖掘结果进行可视化或者转化为用户易于理解的形式表示。n 评注n影响挖掘结果质量的因素：采用的算法、数据本身的质量与数量n数据挖掘的过程是一个不断反馈的过程n可视化在数据挖掘过程的各个阶段都扮演着重要角色，如用散点图或直方图等统计可视化

6、技术来显示有关数据，以期对数据有一个初步的了解。常用的数据挖掘方法n目前一般常用的数据挖掘方法很多，它们大多属于数学统计方法或人工智能中的机器学习算法，以及人工神经网络/遗传算法。n概念概念/类描述类描述n关联规则挖掘关联规则挖掘n序列模式分析序列模式分析n分类分析分类分析n聚类分析聚类分析n异常点检测异常点检测概念/类描述n概念描述概念描述(concept description)：对含有大量数据的数据集合进行概述性的总结并获得简明、准确的描述。n如一个大学中讲师、副教授的情况n讲师：75% (papers3) and (teaching courses=3) and (teaching c

7、ourses=2)n概念描述与数据泛化密切相关概念描述与数据泛化密切相关n允许数据集在多个抽象层泛化，便于用户考察数据的一般行为n方法:nOLAPOLAP方法方法n面向属性的归纳面向属性的归纳OLAPOLAP方法方法n在数据立方体上进行计算和存储结果n优点n效率高n能够计算多种汇总n如：count,average,sum,min,maxn可以使用roll-down和roll-up操作n限制n只能处理非数值化数据和数值数据的简单汇总。n只能分析，不能自动的选择哪些字段和相应的概念层次面向属性的归纳n不限制于种类字段和特定的汇总方法n方法介绍：n使用SQL等收集相关数据n通过数据属性值删除和属性值

8、概化来实现概化n聚集通过合并相等的广义元组，并累计他们对应的计数值进行n和使用者之间交互式的呈现方式.示例示例nDMQL: use Big_University_DBmine characteristics as “Science_Students”in relevance to name, gender, major, birth_place, birth_date, residence, phone#, gpafrom studentwhere status in “graduate”n相应的相应的SQL:SQL:Select name, gender, major, birth_plac

9、e, birth_date, residence, phone#, gpafrom studentwhere status in “Msc”, “MBA”, “PhD” 关联规则挖掘关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。随着大量数据不停地收集和存储，人们对于从数据库中挖掘关联规则越来越感兴趣。从大量商业事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和促销分析等。2computer = financial _ management _ softwaresupport = 2%, confidence = 60%关联规则的支持度(support)2

10、% 表示：分析中的全部事务的2% 同时购买计算机和财务管理软件。关联规则的置信度(confidence)60% 表示：购买计算机的顾客60% 也购买财务管理软件。6事务数据库 n设I= i1，i2，im 是一个项目集合，事务数据库D= t1，t2，tn 是由一系列具有唯一标识TID的事务组成，每个事务ti（i=1，2，n）都对应I上的一个子集。n一个事务数据库可以用来刻画：n购物记录： I是全部物品集合， D是购物清单，每个元组ti是一次购买物品的集合（它当然是I的一个子集）。p项集：项的集合，包含k个项的项集称为k-项集。p关联规则： 形如 A = B 的蕴涵式，其中 A I , B I ,

11、 并且 A B =每个发现的模式都应当有一个表示其有效性的确定性度量，关联规则的确定性度量为：8=置信度c:confidence ( A = B ) = P ( B | A)置信度为100% 或1，意味着数据分析时，该规则总是对的，这种规则称为准确的。9support _ count ( A U B )support_count ( A)【例】任务相关数据由某商店计算机部购买物品的事务数组成，一个置信度为80% 的关联规则：buys ( X , “ computer ” ) = buys ( X , “ software ” )意味着买计算机的顾客80% 也买软件。10一个模式潜在的有用性是定

12、义其兴趣度的一个重要因素，可以用一个实用性函数(如支持度)来评估。关联规则的支持度是模式为真的任务相关数据的事务所占的百分比。支持度s:support(A=B) =P ( A U B )support _ count(AU B) count (T)11 =【例2 】例1中一个支持度为30% 的关联规则，意味着计算机部的所有顾客的30%,同时购买了计算机和软件。支持度和置信度是两个兴趣度度量,分别反映发现规则的有用性和确定性。支持度小：规则使用面窄置信度小：规则无意义12满足最小支持度阈值和最小置信度阈值的关联规则被认为是有趣的。阈值由用户或专家设定。强规则：同时满足用户定义的最小支持度阈值（m

13、in_sup）和最小置信度阈值(min_conf)的规则称为强规则。为方便计，用0% 和100%之间的值表示支持度和置信度。13项集的频率：即包含项集的事务数，也称为项集的支持计数(support_count)。如果项集的出现频率大于或等于min_sup与D中事务总数的乘积，就称该项集满足最小支持度min_sup 。频繁项集：满足最小支持度的项集称为频繁项集。频繁k-项集的集合通常记作Lk。14关联规则挖掘包含两个步骤：1）找出所有频繁项集：根据定义，这些项集的频繁性至少和预定义的最小支持计数一样。2）由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小置信度。15Aprior

14、i算法算法25Apriori 算法Apriori算法是根据有关频繁项集性质的先验知识而命名的。该算法使用一种逐层搜索的迭代方法，利用k-项集探索(k+1)-项集。具体做法：首先找出频繁1-项集的集合，记为L1 ；再用L1找频繁2-项集的集合L2 ；再用L2找L3 如此下去，直到不能找到频繁k-项集为止。找每个Lk需要一次数据库扫描。26Apriori算法的有效性,在于它利用了一个非常重要的原理,即Apriori性质。Apriori性质：如果一个项集是频繁的，则这个项集的任意一个非空子集都是频繁的。它基于如下观察：如果项集I不满足最小支持度阈值min_sup，则I 不是频繁的。如果增加项i到I，

15、则结果项集 I Ui不可能比I更频繁出现。因此，也不是频繁的。27整个过程由连接和剪枝两步组成，即：连接步产生候选项集剪枝步确定频繁项集(1)连接步为找Lk，可通过Lk-1与自己连接，产生一个候选k-项集的集合，该候选项集的集合记作Ck 。29设l1和l2是Lk-1中的项集，记号lij表示li的第j项。为方便计，假定事务或项集中的项按字典次序排序。执行连接 Lk-1 Lk-1 ， 其中Lk-1的元素是可连接的，如果它们前(k-2 )个项相同。30即，Lk-1的元素l1和l2是可连接的，若：（ l11 = l21 l1 2 = l2 2 l1k-2 = l2k-2 l1k-1 l2k-1 ）而条件（l1k-1 B）=confidence（A=B）/support(B)=p(B|A)/p(B)=P( A U B )/ P(A) P(B)n如果提升度=1，表示A与B相互独立，即规