数据仓库与数据挖掘ppt习题剖析

1、数据仓库与数 据 挖 掘,主讲教师：王浩畅 E-mail: wanghch_angel School of Computer & Information Technology of NEPU,第2章数据预处理,练习1,假定用于分析的数据包含属性age.数据元组age值(以递增序)是：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. (a) 该数据的均值是什么?中位数是什么? (b) 该数据的众数是什么？讨论数据的峰 (c)数据的中

2、列数是什么？,解答,(a)均值： 中位数：有序集中间值或者中间两个值平均。奇数个，中间值：25 (b)：表示数据集中出现频率最高的值 两个值出现了相同的最高频率，25和35，都出现了4次，也就是双峰 (c)中列数：最大值和最小值的平均 （13+70）/2=41.5,练习2,假定用于分析的数据包含属性age.数据元组age值(以递增序)是：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. (d)找出数据的第一个四分位数Q1和第三个四

3、分位数Q3 (e)给出数据的五数概括,解答,(d) 第一个四分位数Q1 ：20 第三个四分位数Q3 ：35 中位数：有序集中间值或者中间两个值平均。奇数个，中间值：25 (e)五数概括: 13, 20, 25, 35, 70,练习3,假定用于分析的数据包含属性age.数据元组age值(以递增序)是：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、据（单位：美元）：4，8，15，21，21，24，25，28，34 划分为（等深的）箱： 箱1：4，8，15 箱2：21，21，24 箱3：25，28，34 用箱平均值平滑： 箱1：9，9，9 箱2：22，22，22 箱3：29，29，29 用箱边界平滑： 箱1：4，4，15 箱2：21，21，24 箱3：25，25，34,练习,假定用于分析的数据包含属性age.数据元组age值(以递增序)是：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, 5

5、2, 70. 使用分箱均值光滑对以上数据进行光滑，箱的深度为3.解释你的步骤,解答,Step 1: 排序数据. Step 2: 将有序值划分到大小为3的等频箱中 Step 3: 计算每个箱中数据的算术平均值. Step 4:.将每个箱中的每个值用此箱的算术平均值替换 Bin1: 44/3, 44/3, 44/3 Bin2: 55/3, 55/3, 55/3 Bin3: 21, 21, 21 Bin4: 24, 24, 24 ,规范化 最小最大规范化：对原始数据进行线性变换。假定minA 和 maxA 分别为属性A 的最小和最大值。将A的值v映射到区间new _ minA, new _ maxA

6、中的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),小数定标规范化：通过移动属性A 的小数点位置进行规范化。小数点的移动位数依赖于A 的最大绝对值。

7、 例：假定A的取值由-986917。A的最大绝对值为986。使用小数定标规范化，用1 000（即j = 3）除每个值，这样，986规范化为0.986，而917被规范化为0.917。,数据变换(4),其中，j是使 Max(| |) 喝麦片粥 40%, 66.7%是错误的，因为全部学生中喝麦片粥的比率是75%，比打篮球学生的66.7%要高 打篮球 = 不喝麦片粥 20%, 33.3%这个规则远比上面那个要精确，尽管支持度和置信度都要低的多,June 30, 2020,39,由关联分析到相关分析,打篮球 = 喝麦片粥,打篮球 = 不喝麦片粥,对强关联规则的批评（2）,例1： 上述数据可以得出 buy

8、s(X, “computer games”) = buys(X, “videos”) 40%, 60% 但其实全部人中购买录像带的人数是75%，比60%多；事实上录像带和游戏是负相关的。 由此可见A = B的置信度有欺骗性，它只是给出A,B条件概率的估计，而不度量A,B间蕴涵的实际强度。,由关联分析到相关分析,我们需要一种度量事件间的相关性或者是依赖性的指标 当项集A的出现独立于项集B的出现时，P(AB)=P(A)P(B)，即lift1，表明A与B无关， lift 1表明A与B正相关， lift 40” AND credit_rating = “fair” THEN buys_computer

9、 = “no”,举例说明,目标概念PlayTennis的训练样例,统计个数,表1 类别为cj及在cj条件下Ai取ai的样例数,估计先验概率和条件概率,表2 先验概率P(cj) 和条件概率P(ai|cj),样例判别,现在假设有一个样例x x = 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(

10、Hot| No)* p(High| No)* p(Weak| No)* =0.357*0.6*0.4*0.8*0.4=0.027418 max (P(Yes|x), P(No|x) ) = P(No|x) ,所以我们把x分类为No,June 30, 2020,54,朴素贝叶斯分类 实例2,Class: C1:buys_computer = yes C2:buys_computer = no Data sample X = (age =30, Income = medium, Student = yes Credit_rating = Fair),估计 先验概率P(cj) 和条件概率P(ai|c

11、j),朴素贝叶斯分类 实例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 =0.444 P(income=“medium” | buys_computer=“no”) = 2/5 = 0.4 P(student=“yes” | buys_computer=“yes)= 6/9 =0.667 P(student

12、=“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=fair) 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

13、”)= 0.6 x 0.4 x 0.2 x 0.4 =0.019 P(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.007 X belongs to class “buys_computer=yes”,June 30, 2020,56,打网球实例: 估计 P(xi|C),打网球实例: 分类 X,X = P(X|p)P(p) = P(rain|p)P(hot|p)P(high|p)P(weak|p)P(

14、p) = 3/92/93/96/99/14 = 0.010582 P(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. 不对称的 二元变量 对称的二元变量指变量的两个状态具有同等价值，相同权重；e.g. 性别 基于对称的二元变量的相似度称为恒定的

15、相似度，可以使用简单匹配系数评估它们的相异度： 不对称的二元变量中，变量的两个状态的重要性是不同的；e.g. HIV阳性 VS HIV阴性 给定两个不对称的二元变量，两个都取值1的情况被认为比两个都取值0的情况更有意义。两个都取值0的数目被认为是不重要的，因此被忽略。 基于不对称的二元变量的相似度称为非恒定的相似度，可以使用Jaccard系数评估,二元变量的相异度示例,例 二元变量之间的相异度 （病人记录表）,Name是对象标识 gender是对称的二元变量 其余属性都是非对称的二元变量 如过Y和P（positive阳性）为1，N为0，则：,分类变量(2),求下面分类变量的相异度矩阵 ，p=1

16、,当对象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 第二步利于区间标度变量计算方法，如使用欧几里得距离公式，对到如下相异度矩阵,K-Me

17、ans 聚类: 例 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、对象聚类：将数据对象赋给最近距离的簇集.即medicine A归为gr

18、oup 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、再确定中心点，计算新的分簇的中

19、心点，Group1和Group2各有两个对象，中心点计算如下式所示：,K-Means 聚类: 例 2(6),8、重复第2步，计算每个对象到新的中心点的距离，得到一个新的距离矩阵 9、重复第3步,对象重新聚类：将数据对象赋给最近距离的簇集.,K-Means 聚类: 例 2(7),最后一次的聚类结果表明聚类结果不再改变，达到稳定，我们得到了最后的聚类结果，如下表所示,73,假如空间中的五个点A、如图1所示，各点之间的距离关系如表1所示，根据所给的数据对其运行PAM算法实现划分聚类（设k=2）。 样本点间距离如下表所示: 样本点 起始中心点为A,B,PAM算法基本思想(续),74,PAM算法基本思想

20、(续),第一步 建立阶段：假如从5个对象中随机抽取的2个中心点为A，B,则样本被划分为A、C、D和B、E，如图所示。 第二步 交换阶段：假定中心点A、B分别被非中心点 C、D、E替换，根据PAM算法需要计算下列代价TCAC、 TCAD、 TCAE、TCBC、TCBD、 TCBE。 我们以TCAC为例说明计算过程： a) 当A被C替换以后，A不再是一个中心点，因为A离B比A离C近，A被分配到B中心点代表的簇，CAAC=d(A,B)-d(A,A)=1。 b) B是一个中心点，当A被C替换以后，B不受影响，CBAC=0。 c) C原先属于A中心点所在的簇，当A被C替换以后，C是新中心点，符合PAM算

21、法代价函数的第二种情况CCAC=d(C,C)-d(C,A)=0-2=-2。 d) D原先属于A中心点所在的簇，当A被C替换以后，离D最近的中心点是C，根据PAM算法代价函数的第二种情况CDAC=d(D,C)-d(D,A)=1-2=-1。 e) E原先属于B中心点所在的簇，当A被C替换以后，离E最近的中心仍然是 B，根据PAM算法代价函数的第三种情况CEAC=0。 因此，TCAC=CAAC+ CBAC+ CBAC+ CDAC+ CEAC=1+0-2-1+0=-2。,75,PAM算法基本思想(续),在上述代价计算完毕后，我们要选取一个最小的代价，显然有多种替换可以选择，我们选择第一个最小代价的替换

22、（也就是C替换A），根据图（a）所示，样本点被划分为 B、A、E和C、D两个簇。图（b）和图（c）分别表示了D替换A，E替换A的情况和相应的代价 a) C替换A, TCAC=-2 (b) D替换A, TCAD=-2 (c) E替换A, TCAE=-1,76,PAM算法基本思想(续),C替换B, TCBC=-2 (b) D替换B, TCBD=-2 (c) E替换B, TCBE=-2 通过上述计算，已经完成了PAM算法的第一次迭代。在下一迭代中，将用其他的非中心点A、D、E替换中心点B、C，找出具有最小代价的替换。一直重复上述过程，直到代价不再减小为止。,77,AGNES算法例子,序号 属性 1

23、属性 2 1 1 1 2 1 2 3 2 1 4 2 2 5 3 4 6 3 5 7 4 4 8 4 5,第1步：根据初始簇计算每个簇之间的距离，随机找出距离最小的两个簇，进行合并，最小距离为1，合并后1，2点合并为一个簇。 第2步：，对上一次合并后的簇计算簇间距离，找出距离最近的两个簇进行合并，合并后3，4点成为一簇。 第3步：重复第2步的工作，5，6点成为一簇。 第4步：重复第2步的工作，7，8点成为一簇。 第5步：合并1，2，3，4成为一个包含四个点的簇。 第6步：合并5，6，7，8，由于合并后的簇的数目已经达到了用户输入的终止条件程序结束。,AGNES算法例子(续),DIANA算法例子

24、,序号 属性 1 属性 2 1 1 1 2 1 2 3 2 1 4 2 2 5 3 4 6 3 5 7 4 4 8 4 5,第1步，找到具有最大直径的簇，对簇中的每个点计算平均相异度（假定采用是欧式距离）。 1的平均距离：（1+1+1.414+3.6+4.24+4.47+5）/7=2.96 类似地，2的平均距离为2.526；3的平均距离为2.68；4的平均距离为2.18；5的平均距离为2.18；6的平均距离为2.68；7的平均距离为2.526；8的平均距离为2.96。 挑出平均相异度最大的点1放到splinter group中，剩余点在old party中。 第2步，在old party里找出到最近的splinter group中的点的距离不大于到old party中最近的点的距离的点，将该点放入splinter group中，该点是2。 第3步，重复第2步的工作，splinter group中放入点3。 第4步，重复第2步的工作，splinter group中放入点4。 第5步，没有在old party中的点放入了splinter group中且达到终止条件（k=2），程序终止。如果没有到终止条件，因该从分裂好的簇中选一个直径最大的簇继续分裂