数据库基础

数据库系统与应用——第12章数据挖掘技术

李波电子科技大学 libo@ 028-83205198

第12章.数据挖掘技术

数据挖掘概述数据挖掘的主要任务数据挖掘的主要技术关联规则挖掘聚类分析算法数据挖掘与数据仓库数据挖掘技术应用领域

2009

UESTC Li Bo

12.1数据挖掘技术产生背景

数据库、数据仓库和其它信息存储库中的数据量急剧增加传统的数据库技术却不能发现这些数据内部隐含的规则和规律存在“数据爆炸与知识贫乏”的矛盾数据挖掘是在大量的、不完整的、有噪声的数据中发现潜在的、有价值的模式和数据间关系(或知识)的过程。

2009

UESTC Li Bo

12.2数据挖掘主要过程

数据清理与集成，数据清理消除噪音或不一致数据。数据选择与变换，数据选择目的是辨别出需要分析的数据集合，缩小处理范围，从数据库中提取与分析任务相关的数据，提高数据挖掘质量。数据挖掘是基本部分，由一组功能模块组成，用于特征、关联、分类、聚类分析、演变和偏差分析。模式评估与表示就是根据最终用户的决策目的对提取的信息进行分析，把最有价值的信息区分开来，并通过决策支持工具提交给决策者。

2009

UESTC Li Bo

12.2数据挖掘主要过程(续)

数据挖掘—知识探索过程的核心

模式评价

数据挖掘与任务相关数据数据仓库数据清理数据集成数据库2009 UESTC Li Bo 5

选择与变换

12.3数据挖掘的任务

概念描述:特征化及区分概括,总结,形成数据对比特征

关联 (相关与因果关系)尿布啤酒[0.5%, 75%]

分类与预测为预测构造描述和区分不同类或概念的模型表达方式:决策树,分类法则,神经网络预测某些未知或丢失数字值

2009

UESTC Li Bo

12.3数据挖掘的任务聚类分析类型标记未知:聚类数据成为新的类最大化类内部相似性&最小化类之间相似性

孤立点分析孤立点:与通常行为不吻合的数据对象噪音或均值：欺诈侦测，稀有事件分析趋势与发展分析趋向与偏离：回归分析序列模式挖掘，周期性分析相似性为基础分析其他定向模式或统计分析2009 UESTC Li Bo 7

12.4关联规则的挖掘例超级市场销售系统,记录 5个顾客的购物单。

流水号所购物品清单 1啤酒、薄饼、牛奶 2烤鸭、薄饼、面酱 3啤酒、烤鸭、薄饼、面酱 4面酱 5烤鸭、面酱经理想知道商品间关联，顾客买了面酱就会买烤鸭？要求挖掘出支持度≥2/5(既至少出现两次 )的商品间的关联。

2009

UESTC Li Bo

关联规则的挖掘(例子分析)著名的 Apriori算法，多次扫描数据库，依次得出如图 3的表格(支持度<2的项已经略去)单项统

计支持度{啤酒} 2/5{烤鸭} 3/5{面饼} 3/5{面酱} 4/5解释∶单项统计中看出 60%的顾客买了烤鸭、60%的顾客买了面饼、80%的顾客买了面酱

2009

UESTC Li Bo

关联规则的挖掘(例子分析续)双项统计{啤酒，面饼}{烤鸭，面饼}{烤鸭，面酱}{面饼，面酱}支持度 2/5 2/5 3/5 2/5

从双项统计中看出，60%的顾客买了烤鸭和面酱。三项统计{烤鸭，面饼，面酱}图 3 40%的顾客同时买了烤鸭、面饼和面酱。于是可得出下列三条规则：支持度 2/5

2009

UESTC Li Bo

关联规则的挖掘(挖掘结果的应用)R1:烤鸭面饼、面酱。支持度40%,置信度为66.6% R2:面饼烤鸭、面酱。支持度40%,置信度为66.6% R3:面酱面饼、烤鸭。支持度40%,置信度为50% KDD结果不一定是因果关系。运用之妙成乎于人。例如∶用R1,将烤鸭降价以促销面饼、面酱，很可能会破产用R2将面饼降价，以促销烤鸭，可能会发财；用R3,引不起顾客的热情。

2009

UESTC Li Bo

12.5分类知识的挖掘

例住房分配(监督下分类 ) (1)输入∶训练数据集(符合群众利益或领导意图)姓名张三李四王五张 C李 D王 E职称高工助工助工高工高工高工图 4工龄 25 20 10 25 30 20成果计分 5 4 1 3 6 5家庭人口 3 4 2 2 3 5身高 1. 7 1. 7 1. 8 1. 7 1. 7 1. 8体重 80 85 65 80 85 65应住面积 85 75 50 75 85 70

关于住房分配的训练数据

2009

UESTC Li Bo

分类知识的挖掘(住房分配例子分析)(2)输出从训练数据中"发现"出一个分房计分公式(知识) (3)调用特征选择过程 .比较张三与张C,李四与李D,王五与王E发现身高、体重与住房无关，删去 (4)交互生成加权机制Total=∑PiFi,其中Fi为各条件量化值， Pi为加权值，总分为应住面积。 (5)根据训练数据，调整加权。例如张三及类似与张三条件的应住 85平方米等等。,使得在训练集中各记录的∑PiFi刚好在应住面积的分数段中。 (6)用测试数据测试和修改公式Total=∑PiFi

2009

UESTC Li Bo

分类知识的挖掘(住房分配例子分析续)

(7)公式Total=∑PiFi就是从数据中“挖”出来的分类知识，可以推广使用。 KDD先从实践中来，然后，用到实践中去。

2009

UESTC Li Bo

12.6基于决策树的分类

结点淘汰率信息增益(熵)理论较深例高校招生德智体三标准(门限值)。决策树德不合格 0.1%不合格 60%

智(总分) 99.9%

体39.9%

不合格6.9%

录取33%

2009

UESTC Li Bo

基于决策树的分类(高考招生例，续)

上述决策树把德育放在第一位。绝大多数考生都符合标准。第一节点(德育)分流后，候选空间并未迅速减少 (信息增益小)如果把智育节点提前，可在第一步将候选集缩小到 1/3,提高整个系统

效率。事实上的招生过程采用了这一方法。决策树分类技术研究节点集的选择，节点的次序，门限值的确定公式等等，其目的是使分类比较准确，比较快。

2009

UESTC Li Bo

决策树分类熵 Info. gain (信息增益)Entropy (熵). E.g., e=1表示数据集合中正反例相等. Info. gain (信息增益)∶给定属性作节点把目标集从训练集分离出来的快慢的程度(淘汰率).

entropy

c ( S )=∑ p log p . i 2 i i=1

Gain(S, A)是节点比较和熵的减少量信息增益用了所有训练例，对干扰不敏感.

gain(S,A)≡ entropy(S)

|Sv| entropy(Sv ).∑ v∈values(A)|S|

2009

UESTC Li Bo

决策树分类熵 Info. gain (信息增益)

信息增益在某些书信值上大.信息增益比，penalize(处罚)某些值.|Si||Si| . SplitInfo( S, A)≡ ∑ log|S| 2|S|

GainRatio ( S, A )=

Gain ( S, A ) . SplitInfo ( S, A )

问题:分母接近0,使得 GainRatio很大.基于距离的度量 (Lopez de Mantaras’91): define a distance metric between partitions of the data. chose the one closest to the perfect partition.其他度量方法. Mingers’91经验分析选择的效率

2009

UESTC Li Bo

12.6聚类分析

“物以类聚，人以群分”,自然类类中差异小，类间差异大。又称无监督的分类( Unsupervised Classification)。宗旨∶实事求是，按被处理对象的特征分类。方法∶ (1)含k字段的记录<---> K维空间一点。 (2)对各维施加权，构造k维空间的距离公式，如最简单的欧氏空间距离(∑ΔXI 2)1/2, (3)被分类对象视为k维星云，以距离原则分为星系或星团。

2009

UESTC Li Bo

聚类分析 (续)

(4)不同考察角度，不同距离公式，不同聚类结果例：高考分数线。按一定加权规则计总分。按总分划线，分为重点、非重点和落榜生。考生因一分之差而落选，埋没人才(分数是众多标准之一)。采用KDD来分类，把分数线划分在稀疏带，使得因一分之差落选的人尽可能少，使得大多数不同类的考生有较大的分数差。

2009

UESTC Li Bo

聚类分析 K-重心方法

初始,点集和3重心

2009

UESTC Li Bo

本文来源：https://www.bwwdw.com/article/28xj.html