数据挖掘概念与技术.ppt

《数据挖掘概念与技术.ppt》由会员分享，可在线阅读，更多相关《数据挖掘概念与技术.ppt（103页珍藏版）》请在三一办公上搜索。

1、数据挖掘,滕少华 广东工业大学协同计算与知识工程,第二章数据及数据预处理,滕少华 Tel：E-mail：,内容提要,数据及数据类型为什么要预处理数据?描述数据的汇总（为数据预处理提供分析的基础）数据清理数据集成和变换数据归约相似度计算,2023年8月15日星期二,3,协同计算与知识工程,数据及数据类型,相关概念数据狭义：数字。广义：数据对象及其属性的集合，其表现形式可以是数字、符号、文字、图像抑或是计算机代码等等。属性(也称为特征、维或字段)，是指一个对象的某方面性质或特性。一个对象通过若干属性来刻画。数据集数据对象的集合,2023年8月15日星期二,4,协同计算与知识工程,5,属性,包含电信

2、客户信息的样本数据集,案例,对象,2023年8月15日星期二,协同计算与知识工程,不同的属性类型,2023年8月15日星期二,6,协同计算与知识工程,7,数据集的特性,维度指数据集中的对象具有的属性个数总和。因为在高维度数据集中经常会遇到维度灾难，因此数 据预处理的一个重要技术是维归约稀疏性指在某些数据集中，有意义的数据非常少，对象在大部分属性上的取值为0；非零项不到1%。文本数据集分辨率(粒度)不同分辨率或粒度下数据的性质不同,2023年8月15日星期二,协同计算与知识工程,8,数据集的类型,记录数据事务数据或购物篮数据数据矩阵文本数据基于图形的数据万维网化合物结构有序数据时序数据（时态数据

3、）序列数据时间序列数据空间数据流数据,2023年8月15日星期二,协同计算与知识工程,9,记录数据,事务数据(Transaction Data)是一种特殊类型的记录数据，其中每个记录涉及一个项的集合。,典型的事务数据如超市零售数据，顾客一次购物所购买的商品的集合就构成一个事务，而购买的商品就是项。这种类型的数据也称作购物篮数据,因为记录中的每一项都是一位顾客“购物篮”中购买的商品。,2023年8月15日星期二,协同计算与知识工程,10,数据矩阵,如果一个数据集簇中的所有数据对象都具有相同的数值属性集，则数据对象可以看作多维空间中的点，其中每个维代表描述对象的一个不同属性。数据集可以用一个mn的

4、矩阵表示，其中m行，一个对象一行；n列，一个属性一列。,2023年8月15日星期二,协同计算与知识工程,11,文本数据,文档用词向量表示每个词是向量的一个分量(属性)每个分量的值是对应词在文档中出现的次数,2023年8月15日星期二,协同计算与知识工程,12,图形数据,网页链接化合物结构,2023年8月15日星期二,协同计算与知识工程,有序数据,时序数据（时态数据如工资，职称等）序列数据（序列数据库S是元组的集合，其中SID是序列ID，s是一个序列）时间序列数据（由不同时间重复测量得到的值。）.,2023年8月15日星期二,13,协同计算与知识工程,内容提要,数据及数据类型为什么要预处理数据?

5、描述数据的汇总（为数据预处理提供分析的基础）数据清理数据集成和变换数据归约相似度计算,2023年8月15日星期二,14,协同计算与知识工程,为什么进行数据预处理?,现实中的数据都是杂乱无章的不完整的：有些感兴趣的属性缺少属性值，或仅包含聚集数据含噪声的:包含错误或孤立点值不一致的:在代码或名称上存在差异例1：过去的等级：“1,2,3”,现在的等级：“A,B,C”例2：Age=“48”Birthday=“03/07/1963,2023年8月15日星期二,15,协同计算与知识工程,不完整数据的成因数据收集的时候就缺乏合适的值数据收集时和数据分析时的不同考虑因素人为/硬件/软件 问题噪声数据（不正确

6、的值）的成因数据收集工具的问题数据输入时的人为/计算机 错误数据传输中产生的错误数据不一致性的成因不同的数据源违反了函数依赖性,数据为什么会变脏,2023年8月15日星期二,16,协同计算与知识工程,数据预处理为什么重要？,没有高质量的数据，就没有高质量的挖掘结果有质量的决定必须建立在有质量的数据上例：重复值或者空缺值将会产生不正确的或者令人误导的统计数据仓库需要对高质量的数据进行一致地集成数据预处理将是构建数据仓库或者进行数据挖掘的工作中占工作量最大的一个步骤,2023年8月15日星期二,17,协同计算与知识工程,数据质量的多方位度量,一个广为认可的数据质量多维度量观点：精确度完整度一致性合

7、乎时机可信度附加价值可解释性跟数据本身的含义相关的内在的、上下文的、表象的以及可访问性,2023年8月15日星期二,18,协同计算与知识工程,数据预处理的主要任务,数据清理填写空缺的值，平滑噪声数据，识别、删除孤立点，并解决不一致数据集成合并多个数据源中的数据，即将多数据库，数据立方体或文件的数据集成到一个数据仓库中数据变换规格化（将数据按比率映射到一个特定的区间）和聚集（如由季销售额聚集得到年销售额）数据归约得到数据集的压缩表示，它小的多，但能够产生相同或相似的分析结果数据离散化数据归约的一部分，通过概念分层和数据的离散化来规约数据，对数字型数据特别重要,2023年8月15日星期二,19,协

8、同计算与知识工程,数据预处理的形式,数据集的压缩表示，它小的多，但能够产生相同或相似的分析结果,填写空缺的值，平滑噪声数据，识别、删除孤立点，并解决不一致,将多数据库，数据立方体或文件的数据集成到一个数据仓库中,将数据按比率映射到一个特定的区间,2023年8月15日星期二,20,协同计算与知识工程,内容提要,数据及数据类型为什么要预处理数据?描述数据的汇总（为数据预处理提供分析的基础）数据清理数据集成和变换数据归约相似度计算,2023年8月15日星期二,21,协同计算与知识工程,数据汇总（为数据预处理提供分析的基础）,动机：为了更好的理解数据获得数据的总体印像识别数据的典型特征凸显噪声或离群点

9、对于数据挖掘任务，用户经常关心的数据特征包括数据的中心趋势和离散特征度量数据的中心趋势均值(mean)、中位数(median)、众数（模mode）、中列数(midrange)度量数据的离散程度极差、方差、四分位数极差等,2023年8月15日星期二,22,协同计算与知识工程,度量数据的中心趋势（1）,算术平均值加权算术平均,2023年8月15日星期二,23,协同计算与知识工程,截断均值 尽管均值是描述数据集的最有用的单个量，但不总是度量数据中心的最好方法。均值的主要问题是对于极端值（如离群值）很敏感。即使少量极端值也可能影响均值。例如，公司的平均工资可能被少数高报酬的老总的工资显著抬高。类似地，

10、班级的考试平均成绩可能因为少数几个非常低的成绩而降低相当多。为了抵销少数极端值的影响，我们可以使用截断均值（trimmed mean）。,度量数据的中心趋势（2）,2023年8月15日星期二,24,协同计算与知识工程,截断均值:是去掉高、低极端值得到的均值。指定0和100间的百分位数p，丢弃高端和低端(p/2)%的数据，然后用常规方法计算均值，所得的结果即是截断均值。例：计算1,2,3,4,5,90值集的均值，中位数和p=40%的截断均值.解：均值是17.5，中位数是3.5，p=40%时的截断均值也是3.5,度量数据的中心趋势（3）,2023年8月15日星期二,25,协同计算与知识工程,度量数

11、据的中心趋势（4）,中位数:对于倾斜的（非对称的）数据，数据中心的一个较好度量是中位数。设给定的N个不同值的数据集按数值序排序。如果N是奇数，则中位数是有序集的中间值；否则（即，如果N是偶数），中位数是中间两个值的平均值。,2023年8月15日星期二,26,协同计算与知识工程,度量数据的中心趋势（5）,众数（Mode，也叫模）：集合中出现频率最高的值单峰的（unimodal，也叫单模态）、双峰的（bimodal）、三峰的（trimodal）；多峰的（multimodal）对于适度倾斜（非对称的）的单峰频率曲线，可以使用以下经验公式计算众数中列数（midrange):是数据集的最大和最小值的平均

12、值。,均值 众数 中位数,2023年8月15日星期二,27,协同计算与知识工程,对称与正倾斜、负倾斜数据的中位数、均值和众数,2023年8月15日星期二,28,协同计算与知识工程,对于倾斜的（非对称的）数据，数据中心的一个较好度量是中位数。对于完全对称的数据分布中，均值、中位数具有相同的值。,2023年8月15日星期二,29,协同计算与知识工程,度量数据的离散度-1,极差和方差是值集的散布度量，表明属性值是否散布很宽，或者是否相对集中在单个点(如均值)附近最简单的散布度量是极差，即最大值和最小值之差假设属性x具有m个值,其极差定义为：range(x)=max(x)-min(x)=x(m)-x(

13、1)方差(variance)定义如下:,2023年8月15日星期二,30,协同计算与知识工程,31,数据离散度度量-2,因为方差用到了均值，而均值容易被离群值扭曲，所以方差对离群值很敏感。更加稳健的值集散布估计方法：四分位数极差(IQR),2023年8月15日星期二,31,协同计算与知识工程,2023年8月15日星期二,32,协同计算与知识工程,盒图：数据分布的一种直观表示，在典型情况下，在盒图中：端点在四分位数上，使得盒图的长度是IQR中位数M 用盒内的线标记胡须延伸到最大最小观测值 当处理数量适中的观测值时，值得个别地绘出潜在的离群点。在盒图中这样做：仅当这些值超过四分位数不到1.5IQR

14、 时，胡须扩展到最高和最低观测值。否则，胡须出现在四分 位数的1.5IQR之内的最极端的观测值处终止。剩下的情况 个别地绘出。,盒图分析-1,2023年8月15日星期二,33,协同计算与知识工程,图中出在给定的时间段，AllElectronics的4个分店销售的商品单价数据的盒图。对于分店1，中位数是80美元，Q1是60美元，Q3是100美元。两个边远的观测值个别 地绘制，因为它们的 值175和202超过 IQR的1.5倍，这里1.5IQR=1.5*40=60。,盒图分析-2,2023年8月15日星期二,34,协同计算与知识工程,内容提要,数据及数据类型为什么要预处理数据?描述数据的汇总（为数

15、据预处理提供分析的基础）数据清理数据集成和变换数据归约相似度计算,2023年8月15日星期二,35,协同计算与知识工程,数据清理,数据清理的任务填写空缺值识别孤立点和平滑噪声数据纠正不一致数据,2023年8月15日星期二,36,协同计算与知识工程,空缺值,数据出现空缺值的原因设备异常与其他已有数据不一致而被删除因为误解而没有被输入的数据在输入时，有些数据应为得不到重视而没有被输入对数据的改变没有进行日志记载,2023年8月15日星期二,37,协同计算与知识工程,怎样处理空缺数据?,忽略元组：当属性值缺少的元组数不多时可用这种方法，否则该方法不是很有效，因为如果这样的元组数很多的话，就会删除很多

16、的记录。人工填写空缺值：该方法很繁琐，可能行不通使用一个全局常量填写空缺值：例如：每个空缺值都用“unknown”替代!如果缺失值都用“unknown”替代,则挖掘程序可能误认为形成了一个有趣的概念，因此该方法不十分可靠。使用属性的平均值填写空缺值，如：假定顾客的平均收入为56000美元，则使用该平均值替换income的缺失值使用与给定元组属同一类的所有样本的平均值,例如：将顾客按credit_risk分类，则用具有相同信用度给定元组的平均收入替换income的缺失值使用最有可能的值填充空缺值:使用贝叶斯形式化方法和决策树等.,2023年8月15日星期二,38,协同计算与知识工程,噪声数据,噪

17、声：一个测量变量中的随机错误和偏差造成错误属性值的原因：错误的数据收集手段数据输入问题数据传输问题技术限制命名习惯的不一致,2023年8月15日星期二,39,协同计算与知识工程,怎样处理噪声数据？,分箱方法:首先把数据排序，把排序后数据分到等深的箱中接着，用按箱中值平滑、按箱平均值平滑、按箱边界平滑等平滑技术平滑数据聚类探测和删除孤立点计算机和人工检查结合计算机先探测到可疑值，然后进行人工检查回归通过让数据来适合一个回归函数，进行平滑数据,2023年8月15日星期二,40,协同计算与知识工程,分箱,分箱法包括等宽分箱，等深（等频）分箱，我们在这里主要介绍等深（等频）分箱。等深（等频）分箱法:它

18、把区域划分为N个间隔，每个间隔大约包含了等数量的样本,2023年8月15日星期二,41,协同计算与知识工程,数据平滑的分箱方法,如：price 的排序后数据(美元):4,8,9,15,21,21,24,25,26,28,29,34划分为（等深的）箱-箱1:4,8,9,15-箱2:21,21,24,25-箱3:26,28,29,34用箱平均值平滑:-箱1:9,9,9,9-箱2:23,23,23,23-箱3:29,29,29,29用箱边界值平滑:-Bin 1:4,4,4,15-Bin 2:21,21,25,25-Bin 3:26,26,26,34,2023年8月15日星期二,42,协同计算与知识工

19、程,聚类分析,通过聚类分析检测离群点，消除噪声聚类将类似的值聚成簇。直观的，落在簇集合之外的值被视为离群点,2023年8月15日星期二,43,协同计算与知识工程,计算机和人工检查结合,计算机检测可疑数据，然后对它们进行人工判断 例如：在针对银行信用欺诈行为的探测中，计算机将差异程度大于阈值的模式记录到一个表中，再通过人工审查表中的模式可以识别孤立点。,2023年8月15日星期二,44,协同计算与知识工程,回归,可以用一个函数（如回归函数）拟合数据来光滑数据。,2023年8月15日星期二,45,协同计算与知识工程,内容提要,数据及数据类型为什么要预处理数据?描述数据的汇总（为数据预处理提供分析的

20、基础）数据清理数据集成和变换数据归约相似度计算,2023年8月15日星期二,46,协同计算与知识工程,数据集成,将多个数据源中的数据结合起来存放在一个一致的数据存储（数据仓库）中。这些数据源可能包括多个数据库，数据立方体或一般文件,2023年8月15日星期二,47,协同计算与知识工程,在数据集成要考虑的问题,在数据集成时，有许多问题需要考虑，数据一致性和冗余是两个重要问题。数据一致性:不同表中可能使用不同名称来指示同一属性，正如一个人有多个不同的别名或不同的人拥有相同的名字，这样将导致数据的不一致或冲突。冗余:一个属性是冗余的，如果它能由表中其它属性列“导出”；如工资表中的应发工资、应扣部分、

21、实发工资都是由其它属性导出。由属性或维命名的不一致也可能导致数据集中的冗余。,2023年8月15日星期二,48,协同计算与知识工程,数据集成的举例,应用A 长度 cm应用B 长度 inches 应用C 长度 mcf应用D 长度 yds,cm,2023年8月15日星期二,49,协同计算与知识工程,数据值冲突的检测和处理：对同一现实世界的实体，来自于不同数据源的属性值可能是不同的,原因：不同的数据表示，不同的度量等等 如重量属性可能在一个系统中按公制单位存放,而在另一系统中按英制单位存放.数据在语义上的差异是数据集成经常遇见的问题.解决冲突的简单办法是指定某一系统在冲突中占主要地位.,在数据集成时

22、要考虑的问题（续）,2023年8月15日星期二,50,协同计算与知识工程,数据变换,平滑：去掉数据中的噪声聚集：汇总，数据立方体的构建，例如:可以聚集日销售数据,计算月和年销售额。通常可用来为多粒度数据分析构建数据立方体。数据泛化：沿概念分层向上汇总规范化：将属性数据按比例缩放，使之落入一个小的特定区间(如0.0到1.0）最小最大规范化z-score（或零均值）规范化小数定标规范化属性构造由给定的属性构造新的属性离散化和概念分层,2023年8月15日星期二,51,协同计算与知识工程,minA和maxA为A的最小值和最大值，将A的值映射到区间new_maxA，new _maxA,meanA是A的

23、均值，stand_devA是A的标准差,2023年8月15日星期二,52,协同计算与知识工程,最小-最大规范化的举例,例：假定属性income的最小值分别是12000美元和98000美元。我们想把映射到区间0.0,1.0。根据最小最大规范化，income值73600美元变换为：(73600-12000)(1.0-0)/(98000-12000)+0=0.716,2023年8月15日星期二,53,协同计算与知识工程,Z-score规范化的举例,例:假定属性income的均值和标准差分别为54000美元和16000美元，使用Z-score规范化值73600美元转换为：（73600-54000）/1

24、6000=1.225,2023年8月15日星期二,54,协同计算与知识工程,小数定标规范化举例,例：假定A的值由-986917。A的最大绝对值为986，使用小数定标规范化用1000（j=3)除这个值，这样，-986规范为-0.986，而917规范为0.917,2023年8月15日星期二,55,协同计算与知识工程,56,数据变换属性构造（特征构造）,特征提取(Feature Extraction)由原始数据创建新的特征集称为特征提取。由于原始数据中有许多信息，但其形式不适合数据挖掘算法。在这种情况下，就要由原始的一个或多个特征来构造新的特征。例如：我们可能根据电信客户在一个季度内每个月的消费金额

25、特征构造季度消费金额特征。（将每个月的消费金额相加）,2023年8月15日星期二,协同计算与知识工程,57,数据变换离散化与概念分层,离散化通过将属性域划分为区间，减少给定连续属性值的个数(如学生成绩数据），区间的标号可以代替实际的数据值概念分层通过使用高层的概念（比如：青年、中年、老年）来替代底层的属性值（比如：实际的年龄数据值）来规约数据,2023年8月15日星期二,协同计算与知识工程,离散化,三种类型的属性值：名称型：无序集合中的值；e.g.颜色、职业序数：有序集合中的值；e.g.军衔、职称连续值；e.g.实数离散化数值型数据的离散化分类数据的离散化,2023年8月15日星期二,58,协

26、同计算与知识工程,数值数据的离散化和概念分层生成,等宽离散化等深（等频）离散化聚类分析基于熵的离散化通过自然划分分段,2023年8月15日星期二,59,协同计算与知识工程,60,无监督离散化,原始数据,等宽离散化,等频离散化,K-means,等宽方法是将属性值域划分成相同宽度的区间。可能造成有的区间包含许多实例，有的区间很少实例。,等频方法将相同数量的对象放到每个区间。,2023年8月15日星期二,协同计算与知识工程,61,有监督离散化,基于熵的离散化(Entropy based approach),2023年8月15日星期二,协同计算与知识工程,通过自然划分分段,将数值区域划分为相对一致的、

27、易于阅读的、看上去更直观或自然的区间。聚类分析产生概念分层可能会将一个工资区间划分为：51263.98,60872.34通常数据分析人员希望看到划分的形式为50000，60000自然划分的3-4-5规则常被用来将数值数据划分为相对一致，“更自然”的区间,2023年8月15日星期二,62,协同计算与知识工程,自然划分的3-4-5规则,规则的划分步骤：如果一个区间最高有效位上包含3，6，7或9个不同的值，就将该区间划分为3个等宽子区间；(72,3,2)例如区间：-1000020000,该区间的最高有效位msd=10000,则该区间跨越了（20000-（-10000)/10000=3 个不同的值。如

28、果一个区间最高有效位上包含2，4，或8个不同的值，就将该区间划分为4个等宽子区间；如果一个区间最高有效位上包含1，5，或10个不同的值，就将该区间划分为5个等宽子区间；将该规则递归的应用于每个子区间，产生给定数值属性的概念分层；对于数据集中出现的最大值和最小值的极端分布，为了避免上述方法出现的结果扭曲，可以在顶层分段时，选用一个大部分的概率空间。e.g.5%-95%,2023年8月15日星期二,63,协同计算与知识工程,(-$400-$5,000),第四步,-$400,$5000,2023年8月15日星期二,64,协同计算与知识工程,分类数据的概念分层生成,分类数据是指无序的离散数据，它有有限

29、个值（可能很多个）。,2023年8月15日星期二,65,协同计算与知识工程,分类数据的概念分层生成方法,由用户或专家在模式级显示地说明属性的偏序(或全序)可以很容易地定义概念分层。如：关系数据库或数据仓库的维location可能包含如下属性组：street,city,province_or_state和country。可以在模式级说明这些属性的全序，如：streetcityprovince_or_statecountry,来定义分层。,2023年8月15日星期二,66,协同计算与知识工程,分类数据的概念分层生成方法,2023年8月15日星期二,67,协同计算与知识工程,内容提要,数据及数据类型

30、为什么要预处理数据?描述数据的汇总（为数据预处理提供分析的基础）数据清理数据集成和变换数据归约相似度计算,2023年8月15日星期二,68,协同计算与知识工程,数据归约,为什么需要进行数据规约？数据仓库中往往存有海量数据在整个数据集上进行复杂的数据分析与挖掘需要很长的时间数据归约数据归约可以用来得到数据集的归约表示，它小得多，但可以产生相同的（或几乎相同的）分析结果数据归约策略数据立方体聚集维归约 数据压缩数值归约,2023年8月15日星期二,69,协同计算与知识工程,数据立方体聚集（例子）,例如你收集的数据是20022004年每个季度的销售数据，然而，你感兴趣的是年销售（每年的总和），而不是

31、每个季度的总和，你可以对这种数据进行聚集，该聚集结果数据集小得多，并不丢失分析任务所需的信息。,2023年8月15日星期二,70,协同计算与知识工程,维度(数据特征的数目)归约 是指通过使用数据编码或变换，得到原始数据的归约或“压缩”表示。目的：去除不相关和冗余的特征，降低时间空间复杂度，提高数据质量及数据泛化能力。通过删除不相干的属性或维减少数据量属性子集选择（特征选择）：从一组已知特征集合中选择最具代表性的特征子集。通过特征选择，一些和任务无关或是冗余的特征被 删除，从而提高数据处理的效率。,维归约,2023年8月15日星期二,71,协同计算与知识工程,维归约（属性选择）,启发式（探索式）

32、搜索方法逐步向前选择逐步向后删除判定归纳树,2023年8月15日星期二,72,协同计算与知识工程,启发式（探索式）搜索方法,逐步向前选择由空属性集开始，选择原属性集中最好的属性，并将其添加入该集合，重复该步骤直到无法选择出最优属性或满足一定阈值约束为止。逐步向后删除由整个属性集开始，每一步都删除掉尚在属性集中的最坏属性。直到无法选择出最差属性为止或满足一定阈值约束为止。判定归纳树利用决策树的归纳方法对初始数据进行分类归纳学习，获得一个初始决策树，所有没有出现这个决策树上的属性均认为是无关属性，因此将这些属性从初始属性集合删除掉，就可以获得一个较优的属性子集。,2023年8月15日星期二,73,

33、协同计算与知识工程,2023年8月15日星期二,74,协同计算与知识工程,数据压缩,在数据压缩时，应用数据编码或变换，以便得到原数据的归约或压缩表示。如果原数据可以由压缩数据重新构造而不丢失信息，则为无损压缩。否则为有损压缩。,2023年8月15日星期二,75,协同计算与知识工程,2023年8月15日星期二,76,协同计算与知识工程,数值归约,有参方法 使用一个模型估算数据。常用方法：线性回归方法；多元回归；对数线性模型无参方法 不必假设模型 主要包括：直方图，聚类和选样,2023年8月15日星期二,77,协同计算与知识工程,线性回归模型,线性回归：对数据建模，使之拟合一条直线。Y=+X在数据

34、挖掘中，x,y是数值属性，两个系数,和确定这条直线，能够利用手头的数据进行估计，用最小二乘法估算。给定s个样本形如：(x1,y1),(x2,y2),(xs,ys)用最小二乘法的公式计算和。使得分离数据的实际直线与该直线的误差最小。,2023年8月15日星期二,78,协同计算与知识工程,直方图,直方图使用分箱近似数据分布，是一种数据归约形式。属性A的数据分布为不相交的子集或桶。如果每一个桶只代表单个属性值/频率对，则该桶为单桶(见后面的例子图)。,2023年8月15日星期二,79,协同计算与知识工程,直方图的例子,例2-5 直方图。下面的数据是AllElectronics通常销售的商品的单价表（

35、按美元取整）。已对数据进行了排序：1,1,5,5,5,5,5,8,8,10,10,10,10,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,28,28,30,30,30。,2023年8月15日星期二,80,协同计算与知识工程,。,2023年8月15日星期二,81,协同计算与知识工程,为进一步压缩数据，通常让每个桶代表给定属性的一个连续值域。在图2-19中每个桶代表price的一个不同的10美元区间。,2023年8月15日星期二,82,协同

36、计算与知识工程,聚类,它将对象划分为群或聚类，使得每个聚类中的对象“类似”，但与其他聚类中的对象“相异”。有关聚类的定义和算法有很多种，我们将在后面章节详细讨论,2023年8月15日星期二,83,协同计算与知识工程,选样,它允许用数据小得多的随机样本（子集）表示大型的数据集。常用的抽样方法s个样本无放回简单随机抽样（SRSWOR）：由D的N个元组中抽取s个样本（sN）s个样本有放回简单随机抽样（SRSWR）：过程同上，只是元组被抽取后，将被回放，可能再次被抽取聚类选样：D中元组被分入M个互不相交的聚类中，可在其中的s个聚类上进行简单随机选择（SRS，sM）分层选样：D被划分为互不相交的“层”，

37、则可通过对每一层的简单随机选样（SRS）得到D的分层选样,2023年8月15日星期二,84,协同计算与知识工程,2023年8月15日星期二,85,协同计算与知识工程,86,案例,T1T2T3T4T5T6T7T8,T5T1T8T6,T4T7T4T1,SRWOR(不放回）(S=4),SRWR（放回）(S=4),2023年8月15日星期二,协同计算与知识工程,分层选样（按年龄分层),2023年8月15日星期二,87,协同计算与知识工程,原始数据,聚类/分层选样,聚类抽样,同分层抽样的原理一样,2023年8月15日星期二,88,协同计算与知识工程,内容提要,数据及数据类型为什么要预处理数据?描述数据的

38、汇总（为数据预处理提供分析的基础）数据清理数据集成和变换数据归约相似度计算,2023年8月15日星期二,89,协同计算与知识工程,相似性度量-聚类分析中采用的数据预处理方法,我们知道聚类：在同一个聚类（簇）中的对象彼此相似不同簇中的对象则相异因此我们要进行相似度的计算,2023年8月15日星期二,90,协同计算与知识工程,属性之间的相似度,通常，具有若干属性的对象之间的相似性用单个属性的相似性组合来定义。所以我们先讨论具有单个属性的对象之间的相似性单个属性对象间的相似度度量 两对象越相似，它们的相似度就越高。相异度与相似度相反。,2023年8月15日星期二,91,协同计算与知识工程,属性之间的

39、相似度,2023年8月15日星期二,92,协同计算与知识工程,对象之间的相似性的具体计算会因所使用的属性的数据类型不同而不同，常用属性数据类型包括：数值型属性二值（分类）属性混合类型的属性,对象间的相似度,2023年8月15日星期二,93,协同计算与知识工程,（1）距离度量欧几里得距离距离i=(xi1,xi2,xip)和j=(xj1,xj2,xjp)是 两个p维数据对象Manhattan距离,数值型属性的相似性度量距离度量,2023年8月15日星期二,94,协同计算与知识工程,Manhattan距离和Euclidean距离的性质d(i,j)0 非负性d(i,i)=0 对象自身距离等于零d(i,

40、j)=d(j,i)对称性d(i,j)d(i,k)+d(k,j)三角不等式空间对象i到j的直接距离不会大于途径其他对象k的距离。,数值型属性的相似性度量距离度量,2023年8月15日星期二,95,协同计算与知识工程,闵可夫斯基(Minkowski)距离上式中，q为正整数，如果q=1则表示Manhattan距离，如果q=2则表示Euclidean距离,数值型属性的相似性度量距离度量,2023年8月15日星期二,96,协同计算与知识工程,97,相似系数余弦相似度（余弦值越大，相似度越高）如果(文档)d1 和 d2 是两(文档)向量，则 cos(d1,d2)=(d1 d2)/|d1|d2|,其中，表示

41、向量点积，|d|是向量d的长度.例:d1=3 2 0 5 0 0 0 2 0 0 d2=1 0 0 0 0 0 0 1 0 2 d1 d2=3*1+2*0+0*0+5*0+0*0+0*0+0*0+2*1+0*0+0*2=5|d1|=(3*3+2*2+0*0+5*5+0*0+0*0+0*0+2*2+0*0+0*0)0.5=(42)0.5=6.481|d2|=(1*1+0*0+0*0+0*0+0*0+0*0+0*0+1*1+0*0+2*2)0.5=(6)0.5=2.245cos(d1,d2)=0.3150,数值型属性的相似性度量相似系数,2023年8月15日星期二,协同计算与知识工程,98,相关系

42、数的计算公式：r的取值范围在-1，1，r的值越接近1或-1，表示两特征的相关性越强，越接近于0，相关性越弱。,数值型属性的相似性度量相似系数,2023年8月15日星期二,协同计算与知识工程,对称的 VS.不对称的 二值属性对称的二值属性指属性的两个状态值所表示的内容同等重要；e.g.性别基于对称的二值属性的相似度称为恒定的相似度，可以使用简单匹配系数评估它们的相似度：不对称的二值属性变量，值变量的两个状态的重要性是不同的；e.g.HIV阳性 VS HIV阴性基于不对称的二值属性变量的相似度称为非恒定的相似度，可以使用Jaccard系数评估它们的相似度,二值属性,2023年8月15日星期二,99

43、,协同计算与知识工程,100,二值属性,二元数据相似性度量M01=x取0并且y取1的属性的个数M10=x取1并且y取0的属性的个数M00=x取0并且y取0的属性的个数M11=x取1并且y取1的属性的个数简单匹配系数(Simple Matching Coefficient,SMC)：SMC=值匹配的属性个数/属性个数=(M11+M00)/(M01+M10+M11+M00)Jaccard系数J=匹配的个数/不涉及0-0匹配的属性个数=(M11)/(M01+M10+M11),2023年8月15日星期二,协同计算与知识工程,101,例子,X=（1 0 0 0 0 0 0 0 0 0）Y=（0 0 0

44、0 0 0 1 0 0 1）M01=2(x取0并且y取1的属性的个数)M10=1(x取1并且y取0的属性的个数)M00=7(x取0并且y取0的属性的个数)M11=0(x取1并且y取1的属性的个数)SMC=(M11+M00)/(M01+M10+M11+M00)=(0+7)/(2+1+0+7)=0.7 J=M11/(M01+M10+M11)=0/(2+1+0)=0,2023年8月15日星期二,协同计算与知识工程,小结,数据预处理对于建立数据仓库和数据挖掘都是一个重要的问题数据预处理主要包括：数据清理和数据集成数据归约和特征选择离散化尽管已提出了一些预处理的方法，数据预处理仍然是一个活跃的研究领域,2023年8月15日星期二,102,协同计算与知识工程,2023年8月15日星期二,103,谢谢大家!Email:phone#:(020)39322279(O)(020)39322280(O),协同计算与知识工程,