1、13,15,16,16,19,20,20,21,22,22,25,25,25,25,30,33,33,35,35,35,35,36,40,45,46,52,70.（f）画出数据的盒图,解答,噪声数据（3）,数据平滑的分箱方法price的排序后数据（单位：美元）：4，8，15，21，21，24，25，28，34划分为（等深的）箱：箱1：4，8，15箱2：21，21，24箱3：25，28，34用箱平均值平滑：9，9，9箱2：22，22，22箱3：29，29，29用箱边界平滑：4，4，15箱2：25，25，34,练习,假定用于分析的数据包含属性age.数据元组age值（以递增序）是：13,15,16
2、,16,19,20,20,21,22,22,25,25,25,25,30,33,33,35,35,35,35,36,40,45,46,52,70.使用分箱均值光滑对以上数据进行光滑，箱的深度为3.解释你的步骤,解答,Step 1:排序数据.Step 2:将有序值划分到大小为3的等频箱中Step 3:计算每个箱中数据的算术平均值.Step 4:.将每个箱中的每个值用此箱的算术平均值替换Bin1:44/3,44/3,44/3 Bin2:55/3,55/3,55/3Bin3:21,21,21 Bin4:24,24,24,规范化最小最大规范化：对原始数据进行线性变换。假定minA 和 maxA 分别为
3、属性A 的最小和最大值。将A的值v映射到区间new _ minA,new _ maxA中的v最小-最大规范化通过计算例：假定属性income的最小与最大值分别为12 000美元和98 000美元。我们想把income映射到区间0.0,0.1。根据最小最大规范化，income值73 600美元将变换为：,数据变换（2）,z-score规范化：属性A 的值基于A 的平均值和标准差规范化。最大最小值未知，或者离群点影响较大的时候适用例：假定属性income的均值和标准差分别为54 000美元和16 000美元。使用z-score规范化，值73 600美元转换为,数据变换（3）,小数定标规范化：通过移
4、动属性A 的小数点位置进行规范化。小数点的移动位数依赖于A 的最大绝对值。例：假定A的取值由-986917。A的最大绝对值为986。使用小数定标规范化，用1 000（即j=3）除每个值，这样，986规范化为0.986，而917被规范化为0.917。,数据变换（4）,其中，j是使 Max（|）1的最小整数,练习,用如下两种方法规范化如下数据组200;300;400;600;1000（a）min-max 规范化 令 min=0，max=1（b）z-score 规范化,解答,（a）min-max 规范化 令 min=0，max=1（b）z-score 规范化,例 下面的数据是AllElectroni
5、cs 通常销售的商品的单价表（按$取整）。已对数据进行了排序：1,1,5,5,5,5,5,5,8,8,10,10,10,10,12,12,12,12,14,14,14,15,15,15,15,15,15,18,18,18,18,18,18,18,18,20,20,20,20,20,20,20,21,21,21,21,25,25,25,25,25,25,28,28,30,30,30为进一步压缩数据，让每个桶代表price 的一个不同值。,通过自然划分分段,将数值区域划分为相对一致的、易于阅读的、看上去更直观或自然的区间。聚类分析产生概念分层可能会将一个工资区间划分为：51263.98,60872
6、.34通常数据分析人员希望看到划分的形式为50000，60000自然划分的3-4-5规则常被用来将数值数据划分为相对一致，“更自然”的区间,自然划分的3-4-5规则,规则的划分步骤：如果一个区间最高有效位上包含3，6，7或9个不同的值，就将该区间划分为3个等宽子区间；（72,3,2）如果一个区间最高有效位上包含2，4，或8个不同的值，就将该区间划分为4个等宽子区间；如果一个区间最高有效位上包含1，5，或10个不同的值，就将该区间划分为5个等宽子区间；将该规则递归的应用于每个子区间，产生给定数值属性的概念分层；对于数据集中出现的最大值和最小值的极端分布，为了避免上述方法出现的结果扭曲，可以在顶层
7、分段时，选用一个大部分的概率空间。e.g.5%-95%,3-4-5规则例子,假定AllElectronics 所有分部1999 年的利润覆盖了一个很宽的区间，由-$351,976.00 到$4,700,896.50。用户希望自动地产生利润的概念分层。为了改进可读性，我们使用记号（l.r表示区间（l,r。例如，（-$1,000,000.$0表示由-$1,000,000（开的）到$0（闭的）的区间。1 根据以上信息，最小和最大值分别为MIN=-$351,976.00 和MAX=$4,700,896.50。对于分段的顶层或第一层，要考虑的最低（第5 个百分位数）和最高（第95 个百分位数）值是：LO
8、W=-$159,876，HIGH=$1,838,761。2 给定LOW 和HIGH，最高有效位在百万美元数字位（即，msd=1,000,000）。LOW 向下对百万美元数字位取整，得到LOW=-$1,000,000；HIGH 向上对百万美元数字位取整，得到HIGH=+$2,000,000。,3-4-5规则例子,3 由于该区间在最高有效位上跨越了三个值，即，（2,000,000（1,000,000）/1,000,000=3，根据3-4-5 规则，该区间被划分成三个等宽的区间：（-$1,000,000.$0,（$0.$1,000,000 和（$1,000,000.$2,000,000。这代表分层结
9、构的最顶层。4.现在，我们考察MIN 和MAX，看它们“适合”在第一层分划的什么地方。由于第一个区间（-$1,000,000.$0覆盖了MIN 值（即，LOW HIGH，我们需要创建一个新的区间来覆盖它。对MAX 向上对最高有效位取整，新的区间为（$2,000,000$5,000,000。因此，分层结构的最顶层包含4 个区间：（-$400,000.$0，（$0.$1,000,000，（$1,000,000.$2,000,000和（$2,000,000.$5,000,000。,3-4-5规则例子,5.递归地，每一个区间可以根据3-4-5 规则进一步划分，形成分层结构的下一个较低层：第一个区间（-
10、$400,000.$0划分成4 个子区间：（-$400,000.-$300,000,（-$300,000.-$200,000,（-$200,000.-$100,000和（-$100,000.$0。第二个区间（$0.$1,000,000划分成5 个子区间：（$0.$200,000,（$200,000.$400,000,（$400,000.$600,000,（$600,000.$800,000和（$800,000.$1,000,000。第三个区间（$1,000,000.$2,000,000 划分成5 个子区间：（$1,000,000.$1,200,000,（$1,200,000.$1,400,00
11、0,（$1,400,000.$1,600,000,（$1,600,000.$1,800,000和（$1,800,000$2,000,000。最后一个区间（$2,000,000.$5,000,000 划分成3 个子区间:（$2,000,000.$3,000,000,（$3,000,000.$4,000,000和（$4,000,000.$5,000,000。类似地，如果必要的话，3-4-5 规则可以在较低的层上继续迭代,3-4-5规则例子,第3章数据仓库和数据挖掘的OLAP技术,习题,假定 数据仓库包含三个维：time,doctor 和patient；两个度量：count 和charge；其中，c
12、harge 是医生对一位病人的一次来访的收费。（a）列举三种流行的数据仓库建模模式。（b）使用星型模式，画出上面数据仓库的模式图。,解答,（a）星型模式、雪花模式、或事实星座模式（b）,习题,假定 数据仓库包含三个维：（c）由基本方体day,doctor,patient开始，为列出2004 年每位医生的收费总数，应当执行哪些OLAP 操作？,解答,上卷（Roll-up）操作，时间维的概念分层向上攀升，从day攀升到year.切片（Slice）操作，for time=2004.上卷（Roll-up）操作：维规约，对patient维进行规约。patient from individual pati
13、ent to all.,第4章 挖掘频繁模式、关联和相关,由事务数据库挖掘单维布尔关联规则,最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘。,最小支持度 50%最小置信度 50%,对规则A D，其支持度=60%置信度,D A（60%,75%）,Apriori算法步骤,Apriori算法由连接和剪枝两个步骤组成。连接：为了找Lk，通过Lk-1与自己连接产生候选k-项集的集合，该候选k项集记为Ck。Lk-1中的两个元素L1和L2可以执行连接操作 的条件是Ck是Lk的超集，即它的成员可能不是频繁的，但是所有频繁的k-项集都在Ck中（为什么？）。因此可以通过扫描数据库，通过计算每个k-项集的支
14、持度来得到Lk。为了减少计算量，可以使用Apriori性质，即如果一个k-项集的（k-1）-子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。,Apriori算法示例,Database TDB,1st scan,C1,L1,L2,C2,C2,2nd scan,C3,L3,3rd scan,最小支持计数：2,使用Apiori性质由L2产生C3,1 连接：C3=L2 L2=A,C,B,C,B,EC,E A,C,B,C,B,EC,E=A,B,C,A,C,E,B,C,E2使用Apriori性质剪枝：频繁项集的所有子集必须是频繁的，对候选项C3，我们可以删除其子集为非频繁的选项：A,B,C
15、的2项子集是A,B,A,C,B,C，其中A,B不是L2的元素，所以删除这个选项；A,C,E的2项子集是A,C,A,E,C,E，其中A,E 不是L2的元素，所以删除这个选项；B,C,E的2项子集是B,C,B,E,C,E，它的所有2项子集都是L2的元素，因此保留这个选项。3这样，剪枝后得到C3=B,C,E,从FP-tree的项头表开始,由频率低的节点开始按照每个频繁项的连接遍历 FP-tree列出能够到达此项的所有前缀路径，得到条件模式基,条件模式基itemcond.pattern basecf:3afc:3bfca:1,f:1,c:1mfca:2,fcab:1pfcam:2,cb:1,步骤1:从
16、 FP-tree 到条件模式基,对每个模式基计算基中每个项累积计数用模式基中的频繁项建立条件FP-tree,m-条件模式库:fca:1,All frequent patterns concerning mm,fm,cm,am,fcm,fam,cam,fcam,f:4,c:1,b:1,p:3,a:3,b:1,m:2,p:2,m:1,头表Item frequency head f4c4a3b3m3p3,步骤2:建立条件 FP-tree,通过建立条件模式库得到频繁集,对强关联规则的批评（1）,例1：（Aggarwal&Yu,PODS98）在5000个学生中3000个打篮球3750个喝麦片粥2000个
17、学生既打篮球又喝麦片粥然而，打篮球=喝麦片粥 40%,66.7%是错误的，因为全部学生中喝麦片粥的比率是75%，比打篮球学生的66.7%要高打篮球=不喝麦片粥 20%,33.3%这个规则远比上面那个要精确，尽管支持度和置信度都要低的多,May 9,2023,39,由关联分析到相关分析,打篮球=喝麦片粥,打篮球=不喝麦片粥,对强关联规则的批评（2）,例1：上述数据可以得出buys（X,“computer games”）=buys（X,“videos”）40%,60%但其实全部人中购买录像带的人数是75%，比60%多；事实上录像带和游戏是负相关的。由此可见A=B的置信度有欺骗性，它只是给出A,B条
18、件概率的估计，而不度量A,B间蕴涵的实际强度。,由关联分析到相关分析,我们需要一种度量事件间的相关性或者是依赖性的指标当项集A的出现独立于项集B的出现时，P（AB）=P（A）P（B），即lift1，表明A与B无关，lift 1表明A与B正相关，lift 1表明A与B负相关将相关性指标用于前面的例子，可以得出录像带和游戏将的相关性为：P（game,video）/（P（game）P（video）=0.4/（0.750.6）=0.89结论：录像带和游戏之间存在负相关,第6章分类和预测,May 9,2023,43,信息增益（2）,设属性A 具有v 个不同值a1,a2,av。可以用属性A 将S 划分为v
19、 个子集S1,.,Sv；其中，Sj 包含S 中这样一些样本，它们在A 上具有值aj。如果A 选作测试属性（即，最好的划分属性），则这些子集对应于由包含集合S 的结点生长出来的分枝。设Sij 是子集Sj 中类Ci 的样本数。根据A划分子集的熵或期望信息由下式给出：A 上该划分的获得的信息增益定义为具有最高信息增益的属性,是给定集合中具有高度区分度的属性.所以可以通过计算集合S中样本的每个属性的信息增益,来得到一个属性的相关性的排序,判定归纳树算法示例,通过信息增益的属性选择,Class:buys_computer=“yes”Class:buys_computer=“no”I（s1,s2）=I（9
20、,5）=0.940Compute the entropy for age:,HenceSimilarly,判定归纳树算法示例（1）,计算基于熵的度量信息增益，作为样本划分的根据Gain（age）=0.246Gain（income）=0.029Gain（student）=0.151Gain（credit_rating）=0.048然后，对测试属性每个已知的值，创建一个分支，并以此划分样本，得到第一次划分,判定归纳树算法示例（2）,判定归纳树算法示例（3）,由决策树提取分类规则,可以提取决策树表示的知识，并以IF-THEN形式的分类规则表示对从根到树叶的每条路径创建一个规则沿着给定路径上的每个属性
21、-值对形成规则前件（IF部分）的一个合取项叶节点包含类预测，形成规则后件（THEN部分）IF-THEN规则易于理解，尤其树很大时示例：IF age=“40”AND credit_rating=“excellent”THEN buys_computer=“yes”IF age=“40”AND credit_rating=“fair”THEN buys_computer=“no”,举例说明,目标概念PlayTennis的训练样例,统计个数,表1 类别为cj及在cj条件下Ai取ai的样例数,估计先验概率和条件概率,表2 先验概率P（cj）和条件概率P（ai|cj）,样例判别,现在假设有一个样例x x
22、=Sunny,Hot,High,Weak等于yes的概率 P（Yes|x）=p（Yes）*p（Sunny|Yes）*p（Hot|Yes）*p（High|Yes）*p（Weak|Yes）*=0.643*0.222*0.222*0.333*0.667=0.007039等于No的概率 P（No|x）=p（No）*p（Sunny|No）*p（Hot|No）*p（High|No）*p（Weak|No）*=0.357*0.6*0.4*0.8*0.4=0.027418max（P（Yes|x）,P（No|x）=P（No|x）,所以我们把x分类为No,May 9,2023,54,朴素贝叶斯分类 实例2,Clas
23、s:C1:buys_computer=yesC2:buys_computer=noData sample X=（age=30,Income=medium,Student=yesCredit_rating=Fair）,估计 先验概率P（cj）和条件概率P（ai|cj）,朴素贝叶斯分类 实例2,Compute P（X/Ci）for each class P（age=“30”|buys_computer=“yes”）=2/9=0.222 P（age=“30”|buys_computer=“no”）=3/5=0.6 P（income=“medium”|buys_computer=“yes”）=4/9=
24、0.444 P（income=“medium”|buys_computer=“no”）=2/5=0.4 P（student=“yes”|buys_computer=“yes）=6/9=0.667 P（student=“yes”|buys_computer=“no”）=1/5=0.2 P（credit_rating=“fair”|buys_computer=“yes”）=6/9=0.667 P（credit_rating=“fair”|buys_computer=“no”）=2/5=0.4 X=（age=30,income=medium,student=yes,credit_rating=fai
25、r）P（X|Ci）:P（X|buys_computer=“yes”）=0.222 x 0.444 x 0.667 x 0.667=0.044 P（X|buys_computer=“no”）=0.6 x 0.4 x 0.2 x 0.4=0.019P（X|Ci）*P（Ci）:P（X|buys_computer=“yes”）*P（buys_computer=“yes”）=0.028 P（X|buys_computer=“no”）*P（buys_computer=“no”）=0.007X belongs to class“buys_computer=yes”,May 9,2023,56,打网球实例:估
26、计 P（xi|C）,打网球实例:分类 X,X=P（X|p）P（p）=P（rain|p）P（hot|p）P（high|p）P（weak|p）P（p）=3/92/93/96/99/14=0.010582P（X|n）P（n）=P（rain|n）P（hot|n）P（high|n）P（weak|n）P（n）=2/52/54/52/55/14=0.018286样本 X分类为n（dont play）,第7章聚类分析,对象间的相似度和相异度（2）,例：用x1=（1,2）和x2=（3,5）表示两个对象。求两点之间的欧几里得距离和曼哈顿距离。欧几里得距离曼哈顿距离,二元变量（2）,对称的 VS.不对称的 二元变量
27、对称的二元变量指变量的两个状态具有同等价值，相同权重；e.g.性别基于对称的二元变量的相似度称为恒定的相似度，可以使用简单匹配系数评估它们的相异度：不对称的二元变量中，变量的两个状态的重要性是不同的；e.g.HIV阳性 VS HIV阴性给定两个不对称的二元变量，两个都取值1的情况被认为比两个都取值0的情况更有意义。两个都取值0的数目被认为是不重要的，因此被忽略。基于不对称的二元变量的相似度称为非恒定的相似度，可以使用Jaccard系数评估,二元变量的相异度示例,例 二元变量之间的相异度（病人记录表）,Name是对象标识gender是对称的二元变量其余属性都是非对称的二元变量如过Y和P（posi
28、tive阳性）为1，N为0，则：,分类变量（2）,求下面分类变量的相异度矩阵，p=1,当对象i和j匹配时，d（i,j）=0,当对象不同时，d（i,j）=1。,=,序数型变量（2）,求下面序数型变量的相异度矩阵Test-2有三个状态，分别是一般，好，优秀，也就是=3第一步：把Test-2的每个值替换为它的秩，四个对象分别赋值为3,1,2,3第二步：将秩映射到【0.0,1.0】区间第三步，采用区间标度变量的相异度计算 方法计算f的相异度，如使用欧几里得距离,比例标度变量（2）,求下面比例标度变量的相异度矩阵第一步对属性Test-3取对数，分别为2.65，1.34，2.21和3.08第二步利于区间标
29、度变量计算方法，如使用欧几里得距离公式，对到如下相异度矩阵,K-Means 聚类:例 2（1）,假设有四种药品，每种药品有两个属性如下表表示。我们的目标是将这四种药品聚为两个类，即K=2,K-Means 聚类:例 2（2）,每种药品的两个属性表示为坐标上的一个点（X,Y），如下图所示,K-Means 聚类:例 2（3）,1、初始中心点的选择：假设选择medicine A 和 medicine B 作为初始的两个的簇的中心点。表示为c1=（1,1）和c2=（2,1）。2、计算每个对象到中心点的距离：使用欧几里得公式，我们得到距离矩阵,K-Means 聚类:例 2（4）,3、对象聚类：将数据对象赋
30、给最近距离的簇集.即medicine A归为group 1，medicine B归为group 2，medicine C归为group 2，medicine D归为group 2.4.迭代,重新确定中心点:我们重新计算中心点，Group 1只有一个对象medicine A，中心点仍为c1=（1,1），Group 2现有3个对象，中心点位3个对象的坐标的平均值。,K-Means 聚类:例 2（5）,5、计算每个对象到新的中心点的距离：和第2步类似，使用欧几里得公式，我们得到距离矩阵如下6、对象聚类：将数据对象赋给最近距离的簇集.和第3步类似。将medicine B移到Group 1中，其他不变7、再确定中心点，计算新的分簇的中心点，Group1和Group2各有两个对象，中心点计算如下式所示：例 2（6）,8、重复第2步，计算每个对象到新的中心点的距离，得到一个新的距离矩阵9、重复第3步,对象重新聚类：将数据对象赋给最近距离的簇集.,K-Means 聚类:例 2（7）,最后一次的聚类结果表明聚类结果不再改变，达到稳定，我们得到了最后的聚类结果，如下表所示,73,假如空间中的五个点A、如图1所示，各点之间的距离关系如表1所示，根据所给
