数据挖掘导论PPT学习课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2,数,*,第,2,章 数据,数据类型,数据质量,数据预处理,相似性和相异性度量,1,数,2,2.1,数据类型,2.1.1,属性与度量,2.1.2,数据集的类型,2,数,2,3,数据,数据集是数据对象的集合,数据对象用一组刻画对象基本特性（如物体质量或事件发生时间）的属性描述,数据对象的其他名称,记录、点、向量、模式、事件、案例、样本、观测或实体,属性（,attribute,）是对象的性质或特性，他因对象而异，或随时间而变化,属性的其他名称,变量、特性、字段、特征或维,Attributes,Objects,属性如何测量和描述，既取决于事物本身的客观性质，也和所掌握的技术手段相关。,涉及到 测量精度：海岸线长度。虹膜颜色（分几类颜色描述、,RBG,均值描述、,RBG,直方图描述）,数据挖掘导论,05 九月 2025,2,数,4,测量标度,是将数值或符号与对象的属性相关联的,规则,。,属性的性质不必与用来度量它的值的性质相同。,属性的类型,序性质、可加性,序性质,2,数,5,属性的类型,属性的类型，即测量标度类型，取决于下列,4,种数值性质：,属性值（数值）的性质,1,、,Distinctness,（相异性）,:=,2,、,Order,（序）,:,3,、,Addition,（加法）,:+-,Multiplication,（乘法）,:*/,属性的类型不同，允许的操作不同,2,数,6,属性的类型,There are different types of attributes,标称（,Nominal,）,Examples:,邮编、雇员,ID,序数（,Ordinal,）,Examples:,成绩、街道号码,区间（,Interval,）,Examples:,日期、温度,比率（,Ratio,）,Examples:,绝对温度、长度、年龄、计数,2,数,7,表,2-2,不同的属性类型,属性类型,描,述,例,子,操,作,标称属性的值仅仅只是不同的名字，即标称值只提供足够的信息以区分对象,（,=,，,）,邮政编码、雇员,ID,号、眼球颜色、性别,众数、熵、列联相关、,2,检验,序数属性的值提供足够的信息确定对象的序,（,）,矿石硬度、,好，较好，最好,、成绩、街道号码,中值、百分位、秩相关、游程检验、符号检验,对于区间属性，值之间的差是有意义的，即存在测量单位,（,，,）,日历日期、摄氏或华氏温度,均值、标准差、皮尔逊相关、,t,和,F,检验,对于比率变量，差和比率都是有意义的,（,*,，,/,）,绝对温度、货币量、计数、年龄、质量、长度、电流,几何平均、调和平均、百分比变差,分类的,(,定性的,),数值的,(,定量的,),标称,序数,区间,比率,2,数,8,表,2-3,定义属性层次的变换,属性类型,变,换,注,释,任何一对一变换，例如值的一个排列,如果所有雇员的,ID,号都重新赋值，不会导致任何不同,值的保序变换，即,新值,=,f,(,旧值,),其中,f,是单调函数,包括概念好、较好、最好的属性可以完全等价地用值,1,2,3,或用,0.5,1,10,表示,新值,=,a,旧值,+,b,其中,a,、,b,是常数,华氏和摄氏温度标度零度的位置和,1,度的大小（单位）不同,新值,=,a,旧值,长度可以用米或英尺度量,分类的,(,定性的,),数值的,(,定量的,),标称,序数,区间,比率,2,数,9,用值的个数描述属性：离散,vs.,连续属性,离散属性,(Discrete Attribute),有限或无限可数,(countable infinite),个值,例,:,邮政编码,计数,文档集的词,常表示为整数变量,.,注意,:,二元属性,(binary attributes),是离散属性的特例,连续属性,(Continuous Attribute),属性值为实数,例,:,温度,高度,重量,.,实践中,实数只能用有限位数字的数度量和表示,.,连续属性一般用浮点变量表示,.,2,数,10,数据集的一般特性,维度,(Dimensionality),数据集的维度是数据集中的对象具有的属性数目,维灾难（,Curse of Dimensionality,）,维归约（,dimensionality reduction,）,稀疏性,(Sparsity),如具有非对称特征的数据集，一个对象的大部分属性上的值都为,0,只存储和处理非零值,分辨率,(Resolution),数据的模式依赖于分辨率,度量尺度,(scale),在数米的分辨率下，地球表面看上去很不平坦，但在数十公里的分辨率下却相对平坦,小时标度下的气压变化反映风暴或其他天气系统的移动；在月标度下，这些现象就检测不到,2,数,11,数据集类型（三大类）,记录数据,数据矩阵（,Data Matrix,）,文本数据（,Document Data,）：,每篇文档可以表示成一个文档,-,词矩阵,事务数据（,Transaction Data,）,基于图形,(Graph),的数据,World Wide Web,分子结构（,Molecular Structures,）,有序,(Ordered),数据,空间数据（,Spatial Data,）,时间数据（,Temporal Data,）,序列数据（,Sequential Data,）,2,数,12,数据集类型,1,：记录数据,:,数据矩阵,数据矩阵,:,如果一个数据集中的所有数据对象都具有相同的数值属性集,则数据对象可以看做是多维空间中的点,其中每个位代表描述对象的一个不同属性。,这样的数据集可以用一个,mXn,的矩阵表示,preg,plas,pres,skin,insu,mass,pedi,age,class,6,148,72,35,0,33.6,0.627,50,positive,1,85,66,29,0,26.6,0.351,31,negative,8,183,64,0,0,23.3,0.672,32,positive,2,数,13,数据集类型,1,：记录数据,:,事务数据,典型的记录数据：,事务数据或购物篮数据,2,数,14,数据集类型,2,：基于图形的数据,1,带有对象之间联系的数据,Examples:HTML Links,2,数,15,数据集类型,2,：基于图形的数据,2,具有图形对象的数据,对象具有结构，即对象包含具有联系的子对象,例,:,苯分子的球,棍图，包含碳原子（黑色）和氢原子（灰色）,2,数,16,数据集类型,3,：有序数据,:,时序数据,有序数据有多种,常常涉及时间或空间序,时序数据（,sequential data,）,也称时间数据（,temporal data,）,时间次序重要,但具体时间不重要,例：事务序列,2,数,17,数据集类型,3,：有序数据,:,序列数据,序列数据,（,sequence data,）,个体项的序列,例：基因组序列数据,DNA,都由,4,种核苷酸,A,T,G,和,C,构造,没有时间标记，但与时序数据类似,重要的是在序列中的位置,2,数,18,数据集类型,3,：有序数据,:,时间序列数据,时间序列数据（,time series data,）,特殊的时序数据，其中每个记录都是一个时间序列,(time series),，即一段时间的测量序列,时间自相关（,temporal autocorrelation,），即如果两个测量的时间很接近，这些测量的值通常非常相似,2,数,19,数据集类型,3,：有序数据,:,空间数据,空间数据,具有空间属性，如位置或区域,例,:,不同的地理位置收集的气象数据（降水量、气温、气压）,空间自相关性（,spatial autocorrelation,）,:,物理上靠近的对象趋向于在其他方面也相似,右图每月是空间数据,显示多月是时间,-,空间数据,(Spatial-Temporal Data),2.2,数据质量,20,数,2,2.2,数据质量,2.2.1,测量和数据收集问题,1.,测量误差和数据收集错误,2.,噪声和伪像,3.,精度、偏倚、准确率,4.,离群点,5.,遗漏值,6.,不一致的值,7.,重复的值,2.2.2,数据质量,:,应用问题,21,数,2,2,数,22,测量误差和数据收集错误,测量误差和数据收集错误,测量误差（,measurement error,）,测量过程导致的任何问题，表现为记录值与实际值不同,数据收集错误（,data collection error,）,遗漏数据对象或属性值，或不正确地包含数据对象等错误,测量误差和数据收集错误都可能是系统的或随机的,2,数,23,测量误差和数据收集错误,数据中可能存在的问题,噪声（测量误差的随机部分）,离群点（可能同时涉及测量误差和数据收集错误）,遗漏值（可能同时涉及测量误差和数据收集错误）,不一致的值（可能同时涉及测量误差和数据收集错误）,重复的值（可能同时涉及测量误差和数据收集错误）,2,数,24,噪声和伪像,噪声是测量误差的随机部分,可能扭曲值或附加的谬误对象,Examples:distortion of a person,s voice when talking on a poor phone and,“,snow,”,on television screen,Two Sine Waves,Two Sine Waves+Noise,2,数,25,精度、偏倚、准确率,精度：,precision,偏倚：,bias,准确率：,accuracy,2,数,26,离群点,离群点,(Outliers),data objects with characteristics that are considerably different than most of the other data objects in the data set,2,数,27,遗漏值,原因,Information is not collected(e.g.,people decline to give their age and weight),Attributes may not be applicable to all cases(e.g.,annual income is not applicable to children),处理,Eliminate Data Objects or Attribute,删除数据对象或属性,Estimate Missing Values,估计遗漏值,Ignore the Missing Value During Analysis,分析时忽略遗漏值,2,数,28,不一致的值,数据可能包含不一致的值,例如,地址字段，其中列出了邮政编码和城市，但是特定的邮政编码区域并不包含在该城市,纠正不一致需要附加或冗余信息,时间序列数据中的不一致可能是使用不同的测量手段,例,:,海洋表面温度（,SST,）,1958,1982,年用船或浮标 收集,SST,1983,年之后使用卫星收集,SST,两组数据,每组内的年相互之间趋向于正相关，但与另一组的年负相关,2,数,29,重复数据,Data set may include data objects that are duplicates,or almost duplicates of one another,Major issue when merging data from heterogeneous sources,Examples:,同一个人具有多个,email,地址,Same person with multiple email addresses,Data cleaning,重复数据需要进行数据清洗,Process of dealing with duplicate data issues,2,数,30,数据质量,:,应用问题,时效性,有些数据收集后就开始老化,例如,顾客的购买行为或,Web,浏览模式的快照只代表有限时间内的真实情况,如果数据已经过时，则基于它的模型和模式也已经过时。,相关性,可用的数据必须包含应用所需要的信息,例如,构造一个模型，预测驾驶事故发生率,如果忽略了关于驾驶员的年龄和性别信息，那么除非这些信息可以间接地通过其他属性得到，否则模型的精度可能是有限的,2.3,数据预处理,31,数,2,2,数,32,数据预处理,数据预处理方法,聚集,(Aggregation),抽样,(Sampling),维归约,(Dimensionality Reduction),特征子集选择,(Feature subset selection),特征创建,(Feature creation),离散化与二元化,(Discretization and Binarization),属性变换,(Attribute Transformation),2,数,33,聚集,Aggregation,（聚集）,:,Combining two or more attributes(or objects)into a single attribute(or object),将两个或多个对象合并成单个对象,Purpose,Data reduction,（数据归约）,Reduce the number of attributes or objects,Change of scale,（标度转换）,Cities aggregated into regions,states,countries,etc,More,“,stable,”,data,（更稳定的数据）,Aggregated data tends to have less variability,缺点：丢失有趣的细节,2,数,34,聚集,:,例子,Variation of Precipitation in Australia,（澳大利亚降水量）,平均月降水量标准差直方图,平均年降水量标准差直方图,2,数,35,抽样,抽样是一种选择数据对象子集进行分析的常用方法,统计学抽样,vs,数据挖掘抽样,统计学抽样的原因是因为得到感兴趣的整个数据集的代价太高,数据挖掘使用抽样是因为处理所有数据的代价太高,有效抽样的原则,:,代表性,保留原数据集的性质,抽样方法,简单抽样,(Simple Random Sampling),There is an equal probability of selecting any particular item,简单无放回抽样,(Sampling without replacement),As each item is selected,it is removed from the population,简单有放回抽样,(Sampling with replacement),Objects are not removed from the population as they are selected for the sample.,In sampling with replacement,the same object can be picked up more than once,分层抽样,(Stratified sampling),Split the data into several partitions;then draw random samples from each partition,每组抽相同个数,vs,按比例,自适应,(adaptive),或渐进抽样,(progressive sampling),原因：有时难以预先确定样本集大小,方法：从一个小样本开始，然后增加样本容量直至得到足够容量的样本,36,数据挖掘导论,05 九月 2025,2,数,37,样本大小,:,例子,从,8000,个点分别抽,2000,和,500,个点,2000,个点的样本保留了数据集的大部分结构,500,个点的样本丢失了许多结构,8000 points 2000 Points500 Points,2,数,38,维归约,数据集包含大量特征,例：文档数据集，数以万计的词对应数以万计的属性,维灾难,(curse of dimensionality),随着数据维度的增加，许多数据分析变得非常困难。特殊地，随着维度增加，数据在它所占据的空间中越来越稀疏,对于分类，这可能意味没有足够的数据对象来创建模型,对于聚类，点之间的密度和距离的定义（对聚类是至关重要的）变得不太有意义,结果,:,对于高维数据,许多分类和聚类算法（以及其他数据分析算法）都有麻烦,分类准确率降低，聚类质量下降,技术,PCA,：,Principle Component Analysis,主成分分析,SVD,：,Singular Value Decomposition,奇异值分解,2,数,39,维归约,:PCA,Goal is to find a projection that captures the largest amount of variation in data,Find the eigenvectors of the covariance matrix,The eigenvectors define the new space,x,2,x,1,e,2,数,40,特征子集选择,特征子集选择是降低维度的另一种方法。,当存在,冗余特征（,Redundant features,）、不相关特征（,Irrelevant features,）,时，使用特征的一个子集，能在降低维度的同时避免丢失信息。,特征子集选择的技术,:,Brute-force approach,暴力穷举,:,Embedded approaches,嵌入方法,:,Feature selection occurs naturally as part of the data mining algorithm,Filter approaches,过滤方法,:,Features are selected before data mining algorithm is run,Wrapper approaches,包装方法,:,Use the data mining algorithm as a black box to find best subset of attributes,2,数,41,特征创建,Create new attributes that can capture the important information in a data set much more efficiently than the original attributes,三种一般方法,:,特征提取,Feature Extraction,domain-specific,高度针对具体领域（如：人脸检测、指纹识别）,映射数据到新的空间,Mapping Data to New Space,特征构造,Feature Construction,combining features,从多个原特征构造新的特征,2,数,42,特征创建：映射数据到新空间,傅里叶变换,(Fourier transform),小波变换,(Wavelet transform),例,:,傅里叶变换,左,:,两个,sin,波,;,中,:,两个,sin,波之和,+,噪声,;,检测不到模式,右,:,傅里叶变换到频谱,;,两个尖峰对应于两个无噪声的时间序列,Two Sine Waves,Two Sine Waves+Noise,Frequency,2,数,43,特征创建：特征构造,原始数据集的特征具有必要的信息，但其形式不适合数据挖掘算法,由原特征构造的新特征可能比原特征更有用,例,:,文物数据库,每件文物的特征包括,:,体积和质量，以及其他信息,文物材质,(,类,):,木材、陶土、青铜、黄金,原特征不适合分类,构造新特征,:,密度,=,质量,/,体积,常依据专家意见,05 九月 2025,数据挖掘导论,44,离散化和二元化,为什么要离散化,/,二元化,减少属性值个数，便于挖掘，结果知识表达更简洁、更易于理解、更易使用,离散化产生概念分层结构，可以在不同抽象层进行挖掘,有些算法需要离散属性,有些算法需要二元属性,1,、离散属性二元化,2,、连续属性离散化,3,、具有过多值的离散属性,非监督,vs,监督离散化,差别：是否使用类信息,44,数据挖掘导论,05 九月 2025,2,数,45,变量变换,变量,/,属性变换（,variable/attribute transformation,）,A function that maps the entire set of values of a given attribute to a new set of replacement values such that each old value can be identified with one of the new values,简单变换,Simple functions:,x,k,log(,x,),e,x,|,x,|,1/,x,注意,:,可能改变数据的特性,例,:,变换,1/,x,压缩了大于,1,的值，但是放大了,0,和,1,之间的值,2,数,46,变量变换,:,标准化,/,规范化,标准化（,standardization,）规范化（,normalization,）,在数据挖掘中不区分,在统计学有不同涵义,目标,:,使整个值的集合具有特定的性质,例,:,设 是属性值的均值,s,x,是它们的标准差,变换,创建一个新的变量，它具有均值,0,和标准差,1,可以用中位数取代均值,可以绝对标准差（,absolute standard deviation,）取代标准差,2.4,相似性和相异性的度量,47,数,2,2.4,相似性和相异性的度量,2.4.1,基础,1.,相似性和相异性的定义,2.,相似性和相异性的变换,2.4.2,简单属性间的相似,/,相异度,2.4.3,数据对象间的相异度,2.4.4,数据对象间的相似度,2.4.5,邻近性度量的例子,48,数,2,2,数,49,相似性和相异性,相似性,(Similarity),Numerical measure of how alike two data objects are.,Is higher when objects are more alike.,Often falls in the range 0,1,相异性,(Dissimilarity),Numerical measure of how different are two data objects,Lower when objects are more alike,Minimum dissimilarity is often 0,Upper limit varies,邻近性,(Proximity)refers to a similarity or dissimilarity,2,数,50,p,and,q,are the attribute values for two data objects,简单属性的相似,/,相异度,2,数,51,数据对象的相异度,:,欧几里得距离,欧氏距离,n,是维数，而,x,k,和,y,k,分别是,x,和,y,的第,k,个属性（分量）,2,数,52,闵可夫斯基距离,Minkowski,距离是欧氏距离的推广,Where,r,is a parameter,r,=1.,城市街区距离（又称为曼哈顿距离）,City block(Manhattan,taxicab,L,1,norm)distance.,A common example of this is the Hamming distance,which is just the number of bits that are different between two binary vectors,r,=2.,欧几里得距离,Euclidean distance,r,.,上确界距离,“,supremum,”,(L,max,norm,L,norm)distance.,This is the maximum difference between any component of the vectors,2,数,53,距离的性质,Distances,such as the Euclidean distance,have some well known properties.,非负性。,Non-negativity:,d,(x,y),0 for all x and y,and,d,(x,y)=,0 only if x,=,y.,对称性。,Symmetry:,d,(x,y),=d,(y,x)for all x and y.,三角不等式。,Triangle Inequality:,d,(x,z),d,(x,y)+,d,(y,z)for all points x,y,and z.,where,d,(x,y)is the distance(dissimilarity)between points(data objects),x and y.,A distance that satisfies these properties is a,metric,2,数,54,非度量的相异度,有些相异度都不满足一个或多个度量性质,例,1.,集合差,每个对象是一个集合,相异度用集合差的元素个数定义,d,(,A,B,)=size(,A,B,),一般地，可能,A,B,B,A,，,size(,A,B,),size(,B,A,),定义,d,(,A,B,)=size(,A,B,)+size(,B,A,),例,2.,时间,详见,P43,2.4,相似性和相异性的度量,2.4.1,基础,1.,相似性和相异性的定义,2.,相似性和相异性的变换,2.4.2,简单属性间的相似,/,相异度,2.4.3,数据对象间的相异度,2.4.4,数据对象间的相似度,2.4.5,邻近性度量的例子,55,数据挖掘导论,05 九月 2025,2,数,56,数据对象之间的相似度,设,s,(x,y),是数据点,x,和,y,之间的相似度（通常,0,s,(x,y),1,）,s,(x,y)=1,iff x=y,（,0,s,(x,y),1,）,s,(x,y)=,s,(y,x),三角不等式（或类似的性质）通常不成立,2.4,相似性和相异性的度量,2.4.1,基础,1.,相似性和相异性的定义,2.,相似性和相异性的变换,2.4.2,简单属性间的相似,/,相异度,2.4.3,数据对象间的相异度,2.4.4,数据对象间的相似度,2.4.5,邻近性度量的例子,57,数据挖掘导论,05 九月 2025,2,数,58,简单匹配系数,/Jaccard,系数,设,x,和,y,是两个对象，都由,n,个二元属性组成,f,00,=x,取,0,并且,y,取,0,的属性个数,f,01,=x,取,0,并且,y,取,1,的属性个数,f,10,=x,取,1,并且,y,取,0,的属性个数,f,11,=x,取,1,并且,y,取,1,的属性个数,简单匹配系数,(Simple Matching Coefficient,SMC),Jaccard,系数（,Jaccard Coefficient,）,2,数,59,简单匹配系数,/Jaccard,系数,:,例,例,:,两个对象,x,和,y,x=(1,0,0,0,0,0,0,0,0,0),y=(0,0,0,0,0,0,1,0,0,1),f,01,=2 x,取,0,并且,y,取,1,的属性个数,f,10,=1 x,取,1,并且,y,取,0,的属性个数,f,00,=7 x,取,0,并且,y,取,0,的属性个数,f,11,=0 x,取,1,并且,y,取,1,的属性个数,2,数,60,余弦相似度,设,x,和,y,是两个向量，则,“,”表示向量点积,|x|,是向量,x,的长度,几何解释,其中，,x=x/|x|,，,y=y/|y|,是长度为,1,的向量,2,数,61,余弦相似度：例,例,:,两个数据向量对象,x=(3,2,0,5,0,0,0,2,0,0),y=(1,0,0,0,0,0,0,1,0,2),x,y=3,1+2,0+0,0+5,0+0,0+0,0+0,0+2,1+0,0+0,2=5,cos(x,y)=5/(5.48,2.45)=,0.31,2,数,62,广义,Jaccard,系数,广义,Jaccard,系数,Tanimoto,系数,设,x,和,y,是两个向量，则,2,数,63,相关性,对象之间的相关性是对象属性之间线性联系的度量,设,x,和,y,是两个向量,标准差,协方差,皮尔森相关（,Pearsons correlation,）系数,1,corr(x,y),1.,corr(x,y)=0,不相关,.,corr(x,y)=1(,1),正,(,负,),相关,2,数,64,相关性,:,可视化,Scatter plots showing the similarity from 1 to 1.,2,数,65,邻近度计算问题,1,距离度量的标准化和相关性,属性具有不同的值域,问题,:,距离可能被具有较大值域的属性左右,处理,:,变换到相同值域,某些属性之间相关,:,使用,Mahalanobis,距离,(,马氏距离,),mahalanobis(x,y)=(x,y),1,(x,y),T,其中,1,是数据协方差矩阵的逆,协方差矩阵,是这样的矩阵，它的第,ij,个元素是第,i,个和第,j,个属性的协方差,马氏距离它是一种有效的计算两个未知样本集的相似度的方法。与欧氏距离不同的是它考虑到各种特性之间的联系，即独立于测量尺度。,2,数,66,邻近度计算问题,1:,例,例,:1000,个点，其,x,属性和,y,属性的相关度为,0.6.,在椭圆长轴两端的两个大点之间的欧几里得距离为,14.7,，但,Mahalanobis,距离仅为,6,2,数,67,邻近度计算问题,2,组合异种属性的相似度,Sometimes attributes are of many different types,but an overall similarity is needed,算法,2.1,异种对象的相似度,1,：对于第,k,个属性，计算相似度,s,k,(x,y),，在区间,0,1,中。,2,：对于第,k,个属性，定义一个指示变量,k,，如下：,k,=0,，如果第,k,个属性是非对称属性,并且两个对象在该属性,上的值都是,0,，或者如果一个对象的第,k,个属性具有遗漏值,k,=1,，否则,3,：使用如下公式计算两个对象之间的,总相似度：,附录,68,数据挖掘导论,05 九月 2025,05 九月 2025,数据挖掘导论,69,离散化和二元化,为什么要离散化,/,二元化,减少属性值个数，便于挖掘，结果知识表达更简洁、更易于理解、更易使用,离散化产生概念分层结构，可以在不同抽象层进行挖掘,有些算法需要离散属性,有些算法需要二元属性,非监督,vs,监督离散化,差别：是否使用类信息,69,数据挖掘导论,05 九月 2025,05 九月 2025,数据挖掘导论,70,离散属性二元化,1,方法,1,如果属性具有,m,个值，则将每个原始值唯一地映射到区间,0,m,1,中的一个整数,(,保序,),把,m,个整数都变换成一个二进制数,需要,n,=,log2,m,个二进位表示这些整数,用,n,个二元属性表示这些二进制数,例,:5,个值,awful,poor,OK,good,great,的分类变量需要三个二元变量,x,1,、,x,2,、,x,3,70,数据挖掘导论,05 九月 2025,05 九月 2025,数据挖掘导论,71,离散属性二元化,2,方法,1,的缺点,建立了属性之间的联系，如,good,值用,x,2=1,，,x,3=1,表示,不适合非对称属性处理,非对称的二元属性，,1,比,0,更重要,方法,2,：,对,m,个属性值建立,m,个二元变量，每个对应于一个原属性值,71,数据挖掘导论,05 九月 2025,05 九月 2025,数据挖掘导论,72,连续属性离散化,基本思想,将连续属性值排序后，通过指定,n,1,个分割点（,split point,）把它们分成,n,个区间,将一个区间中的所有值映射到相同的分类值,离散化问题就是决定选择多少个分割点和确定分割点位置的问题,分割点数目一般由用户确定,分割点位置可以用非监督,/,监督方法确定,结果表示,区间集合：,(,x,0,x,1,(,x,1,x,2,.,(,x,n,-1,x,n,),，其中,x,0,和,x,n,可以分别为,-,或,+,一系列不等式：,x,0,x,x,1,.,x,n,-1,x,x,n,72,数据挖掘导论,05 九月 2025,05 九月 2025,数据挖掘导论,73,连续属性离散化,:,非监督,例：四个不同组的数据点，以及两个离群点,分别采用等宽、等频、,K-,均值离散化,x,属性值,Data,Equal interval width,Equal frequency,K-means,73,数据挖掘导论,05 九月 2025,05 九月 2025,数据挖掘导论,74,连续属性离散化,:,监督,监督离散化,假定数据属于不同类,确定分割点的原则,极大化区间纯度,区间中的数据都属于一个类,-,最纯,区间中的数据以相同比例属于各类,-,最不纯,有多种度量纯度的方法,74,数据挖掘导论,05 九月 2025,05 九月 2025,数据挖掘导论,75,监督离散化,:,熵,熵,(entropy),是一种不纯度度量,属性,A,有,m,个值，属于,k,个不同的类,属性,A,的值被划分成,n,个区间,m,i,:,第,i,个区间中值的个数,m,ij,:,区间,i,中类,j,的值的个数,第,i,个区间的熵,e,i,划分的总熵,e,是每个区间的熵的加权平均,75,数据挖掘导论,05 九月 2025,05 九月 2025,数据挖掘导论,76,基于熵的离散化,:,基本思想,开始，将初始值切分成两部分，使得两个结果区间产生最小熵,取两个不同值得中间为分割点,重复分割过程，直到区间的个数达到用户指定的个数，或者满足终止条件,3 categories for both x and y,5 categories for both x and y,76,数据挖掘导论,05 九月 2025,05 九月 2025,数据挖掘导论,77,具有过多值的离散属性,进一步离散化减少不同值的个数,序数属性,用类似于连续属性的方法,标称属性,一般需要领域知识,例如,系名属性可能具有数十个不同的值,可以使用系之间联系的知识，将系合并成较大的组，如工程学、社会科学或生物科学,例如,城市有许多值,合并成省,进一步合并成国家,77,数据挖掘导论,05 九月 2025,05 九月 2025,数据挖掘导论,78,邻近度计算问题,3,May not want to treat all attributes the same.,Use weights,w,k,which are between 0 and 1 and sum to 1.,加权的相似度,加权的闵可夫斯基距离,78,数据挖掘导论,05 九月 2025,