基于图结构的分类数据距离度量.pdf

doi:10.12052/gdutxb.220051基于图结构的分类数据距离度量郑丽苹1，邓秀勤1，张逸群2（1.广东工业大学数学与统计学院，广东广州510520；2.广东工业大学计算机学院，广东广州510006）摘要:针对现有的大多数分类数据的度量方法效果不佳的问题，本文提出了一种基于有序属性和标称属性图结构的分类数据距离度量方法(NewDistanceMetric，NewDM)。首先总结了分类数据距离定义的基本框架公式并分析度量该类型数据的挑战，然后利用不同属性的图结构定义了2个概率分布列距离，紧接着联立权重给出了分类数据的距离度量新方法，最后在6个公开数据集上进行实验，结果表明本文提出的NewDM度量性能优于其他度量方法。关键词:分类数据；距离度量；图结构；有序属性中图分类号:TP311.13文献标志码:A文章编号:10077162(2023)04010908Distance Metric of Categorical Data Based on Graph StructureZhengLi-ping1,DengXiu-qin1,ZhangYi-qun2(1.SchoolofMathematicsandStatistics,GuangdongUniversityofTechnology,Guangzhou510520,China;2.SchoolofComputerScienceandTechnology,GuangdongUniversityofTechnology,Guangzhou510006,China)Abstract:Thispaperproposesanewdistancemetric(NewDM)ofcategoricaldatabasedonthegraphstructureofordinalandnominalattributestoaddressthepooreffectofmostexistingmeasurementmethodsforcategoricaldata.InNewDM,itfirstsummarizesthebasicframeworkformulaofdistancedefinitionofcategoricaldataandanalyzesthechallengesofmeasuringcategoricaldata.Then,thegraphstructuresofordinalattributesandnominalonesareutilizedtodefinethedistancebetweentwoprobabilitydistributioncolumns.Finally,anewdistancemetricofcategoricaldataisobtainedthroughsimultaneousweight.ExperimentalresultsonsixpublicdatasetsshowthattheproposedNewDMissuperiortothestate-of-the-artapproaches.Key words:categoricaldata;distancemetric;graphstructure;ordinalattribute衡量2个对象之间的距离和相似度在数据挖掘1和机器学习2任务中起着重要作用，它往往只是算法3嵌入式的一个小步骤，却能对整个学习算法效果产生巨大影响。所以，确定一个合适的距离度量是数据挖掘和机器学习的重要研究内容。当对象数据是数值数据，常用闵可夫斯基距离、欧氏距离和马氏距离4衡量对象的距离。但当对象数据是分类数据5，它的属性值是类别属性而不是数字，因此数值数据的距离度量不能在分类数据上使用。为了解决这个问题，最简单的方法就是将分类数据转化成数值数据，然后运用数值数据的距离度量。然而将分类数据转化成数值数据的方法会丢失分类数据原有的数据分布和结构特点，因此很多学者利用分类数据的特点来衡量分类数据的距离和相似度。文献6提出汉明距离(HammingDistanceMetric,HDM)，它给相同属性值距离定义为0，不同属性值距离定义为1。这种简单的方式不仅忽略了属性值的分布特征，而且平等地对待每一个属性。所以越来越多的学者从分类数据的分布特征和属性之间关系定义分类数据的距离度量。如Ahmad等7提出了一种无监督分类数据距离度量(AhmadsDistanceMetric,ADM)，Ienco等8-9提出基于上下文的距离(Context-BasedDistanceMetric,CBDM)，这些度量在定义一个属性的2个值之间的距离时利用了相关属第40卷第4期广东工业大学学报Vol.40No.42023年7月Journal of Guangdong University of TechnologyJuly2023收稿日期：2022-03-17基金项目：广东省研究生教育创新计划项目(2021SFKC030)；广东省自然科学基金资助面上项目(2022A1515011592)作者简介：郑丽苹(1998)，女，硕士研究生，主要研究方向为机器学习、数据挖掘通信作者：邓秀勤(1966)，女，教授，本科，主要研究方向为机器学习、数据挖掘，E-mail：性的数据信息，所以它们都不适用于独立属性数据集。Jia等10利用目标属性的频率信息提出了一个新的距离度量(JiasDistanceMetric,JDM)，Chen等11提出了一个概率分布函数来衡量属性的距离，Jian等12基于分类数据的内在异构关系，针对非独立同分布数据提出了分类数据耦合相似度量(CoupledMetricSimilarity,CMS)，但是，这些度量方法都没有区分分类数据的有序属性13-14，而是将有序属性当作标称属性来对待。针对这一问题，有学者提出了区分有序属性的分类数据距离度量方法。其中最简单的方式是在汉明距离的基础上用连续的整数来编码有序属性的等级结构，并用数字之间的距离除以最大整数与最小整数差的商来衡量2个有序值的距离15。但这样的定义方式同样忽略了属性之间的影响。近几年来，既区分有序属性又考虑属性之间关系的分类数据距离度量方法被提出16-18。其中文献16提出了一种基于熵的距离度量(Entropy-BasedDistanceMetric,EBDM)，EBDM利用了信息熵的和来定义同一个属性中的2个属性值之间的距离；文献17提出了一种统一的分类数据距离度量(UnifiedDistanceMetric,UDM)，UDM在定义同一个属性中的2个属性值之间的距离不仅考虑了这个属性的影响，还考虑了其他属性的影响。EBDM和UDM都考虑了有序属性的顺序结构关系，并提出了有序属性和标称属性统一的分类数据距离度量。但是这2种度量方法都利用信息熵来定义分类数据距离，而信息熵是从数据的概率分布中得到的，它依赖于数据的概率分布，间接地描述了分类数据的特征，并没有直接从分类数据的数据特征中定义距离。因此针对这个问题，本文提出了一种基于图结构的分类数据距离度量(NewDistanceMetric,NewDM)。它利用有序属性和标称属性的图结构，定义了2个概率分布列之间的距离，并利用平均信息熵占总体平均信息熵的比值来衡量属性的重要性。NewDM同时兼备了概率和信息熵的优点，使异构属性距离的度量更准确且更具可比性。NewDM是无参数的，在6个数据集上的实验结果验证了NewDM的度量性能优于其他度量方法。同时本文总结了区分有序属性的分类数据距离定义的基本框架公式，使分类数据的距离定义更加简单明了。1 相关工作 1.1 分类属性的图结构分类数据按属性划分为有序属性和标称属性，有序属性和标称属性的相同点是它们都由类别属性值构成，不同点是有序属性的属性值之间具有等级关系，例如学生成绩的属性值：优秀、良好、及格、不及格。这些属性值都是由类别属性构成，但是很明显它们之间还具有等级顺序关系，所以有序属性也可以看作是特殊的标称属性。ar,1,ar,2,ar,3,ar,4ar,1,ar,2,ar,3,ar,4在数学领域中，图论19是一个以图为研究对象的重要分支。其中图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。由于有序属性中的属性值之间具有等级关系，当有序属性的属性值按等级从高到低排列并用线将每一个属性值与邻近的属性值连接，同时将属性值当作是顶点，则有序属性的图结构是单链状的树20。对于标称属性，标称属性值之间没有等级关系，所以每两个属性之间都可以连接起来，因此标称属性值之间的图结构是完全图21。若有序属性的属性值按等级从高到低排列分别为，则有序属性的图结构如图1(a)所示。若标称属性的属性值分别是，则标称属性的图结构如图1(b)所示。(a)有序属性(b)标称属性ar,1ar,2ar,3ar,4ar,1ar,2ar,3ar,4图1图结构Fig.1Graphstructure 1.2 区分有序属性的分类数据距离度量目前区分有序属性的分类距离度量的方式可分成2种。第1种，仅利用有序属性之间具有等级结构的思路出发，在原有不区分有序属性的分类距离度量中单独定义有序属性值之间的距离。例如文献15中将有序属性编码数值后，用数值数据的方法来定义有序属性之间的距离。第2种，利用有序属性是特殊的标称属性的思路，在原有不区分有序属性的分类距离度量中将有序属性的结构特点融入到距离定义中加以区分16-18。对于这2种区分有序属性的思路，第1种单独区分的方式，容易造成标称属性和有序属性尺度之间的差异，不能很好地揭示分类数据的数据特征。第110广东工业大学学报第40卷2种区分的方式既考虑到有序属性和标称属性之间的共同特性，又考虑到这2种不同属性之间的差异，所以第2种区分的方式会优于第1种。由于文献16-18中区分有序属性的思路大致相同，所以这些度量方法在定义分类数据任意属性下2个属性值之间距离的基本框架公式也大致相同。不同的是它们量化2个属性值之间距离的方法和属性之间权重的定义。rmh(m,h)wrr(m,h)r1,2,3,n(m,h)max(m,h)1s=min(m,h)(s,s+1)min(m,h)mhmax(m,h)1mhwmhD(m,h)因此将同一个属性下2个属性值之间距离的基本框架公式进行梳理。先给定第 个属性中2个属性值 和 之间距离的公式，记为，权重记为。然后，2个属性值之间距离的基本框架公式需要有以下2个步骤：第1步，区分第 个属性是有序属性还是标称属性，当第 个属性是标称属性时，无需改变，当第 个属性是有序属性时，因为有序属性中属性值之间具有等级结构，将所有属性值按等级从低到高用连续整数编码后，则需要变为，式中：为属性值 和 中等级较低的那个属性值，为属性值 和中等级较高的那个属性值还要低一级的属性值；第2步，加入权重 衡量属性的重要程度。通过这2个步骤，最终得到了第r个属性下2个属性值 和 之间距离的基本框架公式，用表示，可记为D(m,h)=wmax(m,h)1s=min(m,h)(s,s+1),当r为有序属性w(m,h),当r为标称属性(1)D(m,h)(m,h)w不仅将有序属性的等级结构融入到距离定义中，还考虑了属性之间的重要程度。它使区分有序属性的分类数据的距离定义变得更加清晰明了，仅需定义和 即可。也为本文提出的距离度量提供了基本框架公式和定义的思路。2 本文方法nX=x1,x2,xnixi=(xi1,xi2,xid)dA1,A2,Addorddnomd=dord+dnomArar,1,ar,2,ar,vr|Ar|ArArar,1 ar,2 ar,vr给定分类数据 个对象，第 个对象记为，个属性分别由表示，且前个属性表示有序属性，后个属性表示标称属性，则。对任意由属性值构成，表示中属性值的数量。当为有序属性，其属性值之间等级关系从高到低排列可写成：，符号“”表示左边属性值等级高于右边属性值。xixjDist(xi,xj)Dist(xi,xj)d对任意2个数据对象 与，它们的距离表示为，则可用 个子距离的欧氏距离来表示，记为Dist(xi,xj)=dr=1dist(xir,xjr)2(2)dist(xir,xjr)xixjArxirxjrxir,xjrar,t,ar,h子距离为，在属性中和的距离，若分别为，则有dist(xir,xjr)=dist(ar,t,ar,h)(3)ar,t,ar,hArr,m(ar,t,ar,h)Arar,t,ar,hAmr,m(ar,t,ar,h)文献17中提出了的距离不仅与有关系，还与其他属性有关系。所以令表示属性值在属性中的距离，的公式详见2.1。2.1 图结构下两个概率分布列的距离Arar,tAmam,1,am,2,am,vmpar,t1,par,t2,par,tvm Arar,hAmam,1,am,2,am,vmpar,h1,par,h2,par,hvmpar,tvmArar,tAmvmpar,t1,par,t2,par,tvmpar,h1,par,h2,par,hvmAm1,0,00,1,01,0,00,0,11,0,00,0,11,0,00,1,0在属性值为的条件下属性值分别是的概率分布列表示为，属性值为的条件下属性值分别是的概率分布列表示为，其中是的属性值的条件下属性值为的概率。对于这2个概率分布列与的距离，最常用的方法是把这2个概率分布列当成数值向量，利用闵可夫斯基距离和欧氏距离等数值距离方法来度量11。但是这些度量方法仅从数值的差异量化这2个分布列的距离，未能真正从不同属性的结构特征中量化这2个分布列的距离。例如，当是有序属性，概率分布列与的欧氏距离与和的欧氏距离是相等，但是因为有序属性值具有等级结构，所以和的距离要比与的距离大18。所以本文分别利用标称属性和有序属性图结构来定义2个概率分布列之间的距离。par,t1,par,t2,par,tvmpar,h1,par,h2,par,hvmpar,t1,par,t2,par,tvmpar,h1,par,h2,par,hvmpar,t1,par,t2,par,tvmpar,h1,par,h2,par,hvmpar,t1 par,h1,par,t2 par,h2,par,tvm par,hvm0,0,0首先将与的距离看作是转变成的最小转变量，所以和之间的最小转化量与和之间的最小转化量是等价的。Am0,0,0par,t1 par,h1,par,t2 par,h2,par,tvm par,hvm12vmi=1?par,ti par,hi?定义1定义1当为标称属性时，与之间的最小转化量可定义为。0.4,0.4,0.1,0.10.3,0.2,0.1,0.40.1,0.2,0,0.30.4,0.4,0.1,0.10.3,0.2,0.1,0.40.1,0.2,0,0.30,0,0,0当2个分布列分别为和时，这2个分布列相减后得，很明显与之间的最小转化量就是将变为所需要的最小转化量。由于标称属性值的图结构为完全图，每个属性值之间都直接相连，所以每个属性之间的转化距离可定义为1，其中每一步的转化量会等于这一步第4期郑丽苹，等：基于图结构的分类数据距离度量1110.10.30.110.20.30.210.3Am0.3的数值乘以距离，若最小转化过程是用正数将负数抵消，则转化过程如图2所示，其中虚线表示的是最小转化过程。这个最小转化过程是将转化到的位置，这一步的转化量为；将转到的位置，这一步的转化量为，所以这2个分布列的最小转化量是这2步转化量的和：。因此当为标称属性时，这2个分布列的距离是。0.210.10.200.30.11图2标称属性转化过程Fig.2TheprocessofnominalattributeconversionAm0,0,，0par,t1 par,h1,par,t2 par,h2,，par,tvm par,hvm1vm1vm1i=1?iw=1(par,tw par,hw)?定义2定义2当为有序属性时，与之间的最小转化量可定义为。Amvmvm11/(vm1)当为有序属性，个属性值之间按等级将属性值连接后的图结构是单链状的树。每个属性值只与它们邻近等级的属性值相连，所以，转化的过程只能从最高级的属性值到最低级的属性值的方向或者从最低级属性值到最高级属性值的方向进行。由于最高级的属性值到最低级属性值需要走步，若最高级的属性值到最低级属性值的总距离定义为1，则每一步的距离应该是。和标称属性一样，每一步的转化量是这一步转化的数值乘以距离。Am0.1,0.2,0,0.30,0,0,00.10.30.10.1/30.1+0.2=0.30.30.3/30.30.30.3/30.3+(0.3)=0(0.1+0.3+0.3)/3也就是说当为有序属性，转变为所需要的最小转化过程若是从的位置向的位置方向进行会有以下3个步骤，转化过程图详见图3，其中虚线表示每一步的转化过程，虚线中间的数值是这一步的转化量：第1步，将第1位置中的移到第2位置，转化量为，此时第2位置上的值应为；第2步，将第2位置的移到第3位置，转化量为，此时第3位置上的值是仍是；第3步，将第3位置上的移到第4列，转化量为，此时第4个位置上的值为，转化结束。因此转化过程的最小转化量是每一步转化量的和。0.130.10.1000.200.300.330.3300.30.200.30.30.30.3图3有序属性转化过程Fig.3Theprocessoforderedattributeconversionr,m(ar,t,ar,h)综上所述，的公式可记为r,m(ar,t,ar,h)=1vm1vm1i=1?iw=1(par,tw par,hw)?，当ar,t,ar,h,mdord0,当ar,t=ar,h12vmi=1?par,ti par,hi?，当ar,t,ar,h,m dord(4)12vmi=1?par,ti par,hi?1vm1vm1i=1?iw=1(par,tw par,hw)?0,1Am12vmi=1?par,ti par,hi?=1Am1vm1vm1i=1?iw=1(par,tw par,hw)?式中：和的取值范围都为。若为标称属性，2个分布列形如两个不同的单位向量，。若为有序属性，当且仅当2个分布列分别形如首尾取值的单位向量时，的值为1。2.2 权重的定义在同一个数据集中，每一个属性的重要程度是不一样的，信息理论用信息熵来描述数据的不确定性，不确定越大代表着数据的信息量越大，信息量越大也代表着这个数据是更重要的，因此可用信息熵来量化每个属性的重要程度。Arar,1,ar,2,ar,vrp1,p2,pvrps=(ar,s)/n(ar,s)Arar,ss1,2,vrAr若属性中的属性值的概率分布列表示成，其中，是属性值为的数量，可取。则属性的信息熵可表示为W(Ar)=vrs=1pslnps(5)W(Ar)W(Ar)H(Ar)但是，一个属性的属性值的类别数量越多，信息熵也会越大，为了使不受属性值类别数量的影响，利用平均信息熵来衡量一个属性的信息量。Arp1,定义3定义3若属性的概率分布列表示成112广东工业大学学报第40卷p2,pvr，则平均信息熵可定义为H(Ar)=1ln(1/vr)vrs=1pslnps(6)H(Ar)0,1式中：的取值范围为。ArArwrwr所以属性的重要程度可以利用属性的平均信息熵占所有属性的平均信息熵和的比值来表示，则的公式可记为wr=H(Ar)di=1H(Ai)(7)2.3 一种新的分类数据距离度量方法(NewDM)ar,tar,hAmr,m(ar,t,ar,h)wrArwrdist(ar,t,ar,h)本文利用有序属性和标称属性的图结构特征定义了和在中2个概率分布列的距离，并利用平均信息熵占总体平均信息熵的比值来衡量属性的重要程度。根据式(1)的基本框架公式，将区分有序属性并加入权重后，可记为dist(ar,t,ar,h)=wrmax(t,h)1s=min(t,h)dm=1r,m(ar,s,ar,s+1),当t,h且rdordwrdm=1r,m(ar,t,ar,h)，当t,h且r dord0,当t=h(8)本文提出的NewDM计算步骤详见算法1。算法1算法1NewDMX=x1,x2,xn d dord输入：数据集，,Dist(xi,xj)i,j 1,2,n输出：，其中r=1d1.fortowr2.根据式(6)和(7)计算；3.endforr=1d4.fortom=1d5.fortor,m(xir,xjr)6.根据式(4)计算；7.endfordist(xir,xjr)8.根据式(8)计算；9.endforDist(xi,xj)10.根据式(2)计算。wrdist(xir,xjr)首先利用式(6)、(7)计算出每个属性的权重，然后利用式(4)、(8)计算这2个对象在每个属性中的距离，最后利用式(2)求出这2个对象的距离。3 实验为了验证NewDM在分类数据中的有效性，使用6个公开的分类数据集，利用3种聚类评价指标，设计2个实验来验证NewDM的有效性。3.1 实验设置3.1.1数据集说明ndorddnom本文使用6个分类数据集来进行实验，这6个数据集都来自美国加州大学UCI机器学习数据库，它们分别是Qualitative、Car、Zoo、Solar、Hayes、Student。其中Qualitative、Car是只有有序属性的分类数据，Zoo、Solar是只有标称属性的分类数据，Hayes、Student是既有有序属性又有标称属性的混合型分类数据，所有数据集中缺失属性值的数据都被忽略，具体数据集信息如表1所示。其中 表示数据集的样本数量，和分别表示数据集中有序属性和标称属性的个数。表1数据集属性说明Table1Statisticsofthe6datasets数据集n/个dord/个dnom/个Qualitative25060Car172860Zoo101016Solar32309Hayes13222Student666383.1.2实验评价指标说明为了衡量不同分类数据距离度量的聚类效果，采用3种评价指标，分别是聚类精度(ClusteringAccuracy,CA)22，调整的兰德指数(AdjustedRandIndex,ARI)23和归一化信息(NormalizedMutualInformation,NMI)24。CA为分类正确的数据对象的百分比，表达式为CA=1nni=1(ci,map(li)ciimap(li)ci=map(li),(ci,map(li)=1ci,map(li)(ci,map(li)=00,1式中：为第 个数据的真实标签，为映射到真实标签后的预测标签值，当，当，。CA的取值范围是，且CA值越大聚类效果越好。ARI比RI更有区分度，表达式为ARI=(RIE(RI)/(max(RI)E(RI)E(RI)max(RI)1,1式中：，为RI的均值和最大值。ARI的取值范围是，值越大效果越好。当ARI为负数时，用符号“”表示。NMI从信息理论角度来衡量预测标签和真实标签的一致性，表达式为第4期郑丽苹，等：基于图结构的分类数据距离度量113NMI=(kr=1kt=1cr,tlg(ncr,t)/crct)(kr=1crlgcr/N)(kt=1ctlgct/N)kcrrcttcr,trt0,1式中：为类标签的数量，为预测标签值为 的数量，为真实标签值为 的数量，为同时满足预测标签值为、真实标签值为 的数量。NMI取值范围是，NMI越大效果越好。3.1.3实验方案为了验证NewDM的有效性，设置了2个实验。实验1将分类数据距离度量HDM、JDM、EBDM、UDM和NewDM分别嵌入到K-Modes算法25，比较这5种度量方法的聚类效果，来验证NewDM的有效性。其中以HDM为度量基准，JDM是未区分有序属性的度量中较为经典的一种分类数据距离度量。EBDM和UDM都是区分有序属性和标称属性的分类数据距离度量方法，所以NewDM的主要对比距离是EBDM和UDM。实验2将NewDM嵌入到不同的分类数据聚类算法中，与原有算法的聚类效果进行比较，来验证NewDM在不同聚类算法的有效性。选择K-Modes算法作为算法基准，基于子空间的聚类算法有较好的聚类效果，所以选择文献26中的熵加权聚类算法(EntropyWeightingK-Means,EWKM)和文献27中的加权OCIL聚类算法(WeightedObject-cluster:Similaritymetric,WOCIL)作为经典的聚类算法。为了实验的公平，所有算法都随机选取聚类中心，其中聚类中心数从真实标签中获取，并对每个数据集运行10次后取平均值及其标准差作为最后结果，用“平均值标准差”来表示。对实验1的结果用黑体、“”“”来分别表示K-Modes算法，EWKM和WOCIL与它们各自嵌入NewDM的聚类算法中效果更好的实验结果。3.2 实验结果及分析实验1的结果如表2所示。在只有有序属性的数据集Qualitative和Car中，NewDM的优势非常明显，表明了基于有序属性图结构的概率分布列距离比利用信息熵的度量方法更好地揭示和量化了有序属性数据的特征。在只有标称属性的数据集Zoo和Solar中，NewDM效果不如有序属性中显著，但在其他4种分类数据距离度量中的效果仍是最好的。它表明了在纯标称属性的分类数据中利用2个概率分布列之间的距离和利用平均信息熵信息作为权重也是可行的。在既有有序属性又有标称属性的数据集Hayes和Student中，NewDM效果仍然优于其他几种距离度量,这表明了NewDM分别利用有序属性和标称属性图结构定义的概率分布列距离，使异构属性距离的度量更加准确。综上所述，在每个数据集中，NewDM在K-Modes聚类算法中的3个指标的结果都是最好表2不同距离度量在K-Modes算法中实验结果Table2ExperimentalresultsofdifferentdistancemetricsinK-Modesalgorithm评价指标数据集HDMJDMEBDMUDMNewDMCAQualitative0.8720.050.9200.000.9080.010.9400.000.9760.00Car0.3670.020.3530.020.3420.030.3400.030.5350.06Zoo0.7180.100.7370.110.6530.110.7340.100.7490.09Solar0.4920.050.4070.040.5240.050.4770.060.5530.07Hayes0.3890.020.3860.030.4070.030.4460.040.4640.03Student0.3120.010.3010.010.3190.030.3140.020.3390.03ARIQualitative0.5580.140.7050.010.6650.030.7740.000.9060.00Car0.0210.020.0250.020.0220.020.0320.030.0530.07Zoo0.6750.160.6980.160.5860.180.6920.170.7110.15Solar0.2310.050.1280.030.3030.070.2240.070.3540.07Hayes0.0080.020.0320.020.0460.03Student0.0060.010.0040.000.0190.020.0080.010.0240.02NMIQualitative0.5680.100.6490.010.6290.010.7070.000.8430.00Car0.0450.020.0590.020.0750.030.0780.030.0470.03Zoo0.7810.060.8050.070.7290.070.8120.060.8230.05Solar0.3100.030.2100.030.3640.070.3070.080.4510.09Hayes0.0160.010.0130.010.0240.020.0610.040.0740.03Student0.0160.010.0120.010.0300.030.0160.010.0370.03114广东工业大学学报第40卷的，它验证了NewDM不仅优于不区分有序属性的距离度量，也优于区分有序属性中利用熵来定义距离的EBDM和UDM。实验2用来验证NewDM嵌入到3个不同聚类算法的有效性。表3的实验结果表明，嵌入了NewDM的聚类算法的聚类效果整体上都优于原有的聚类算法距离或相似度量，这验证了将NewDM嵌入到分类数据聚类算法中不仅可行而且可以提升聚类的效果。同时也验证了NewDM兼备了概率和信息熵的优点，使异构属性距离的度量更准确且更具可比性。表3NewDM在不同聚类算法中的实验结果Table3ExperimentalresultsoftheNewDMindifferentclusteringalgorithms评价指标数据集K-ModesNewDM+K-ModesEWKMNewDM+EWKMWOCILNewDM+WOCILCAQualitative0.8720.050.9760.000.8320.030.9630.010.9160.141.0000.00:Car0.3670.020.5350.060.3430.030.6990.000.4130.050.5350.06:Zoo0.7180.100.7490.090.7190.100.7490.090.7110.090.7360.10:Solar0.4920.050.5530.070.4690.060.5340.060.4380.050.5270.07:Hayes0.3890.020.4640.030.3890.020.4670.040.4330.070.4730.08:Student0.3120.010.3390.030.3000.010.3390.040.2990.020.3060.01:ARIQualitative0.5580.140.9060.000.4420.080.8580.020.7630.301.0000.00:Car0.0210.020.0530.070.0270.010.0040.010.0760.06:0.0520.07Zoo0.6750.160.7110.150.6750.160.7110.150.6580.130.6950.15:Solar0.2310.050.3540.070.2180.060.3200.070.1760.080.3110.09:Hayes0.0460.030.0420.030.0260.040.0570.04:Student0.0060.010.0240.020.0030.000.0260.020.0010.000.0050.00:NMIQualitative0.5680.100.8430.000.4250.070.7970.010.7330.291.0000.00:Car0.0450.020.0470.030.0670.030.0010.000.1390.08:0.0460.03Zoo0.7810.060.8230.050.7810.060.8230.050.7890.040.8240.06:Solar0.3100.030.4510.090.2980.050.4200.080.2770.090.4320.09:Hayes0.0160.010.0740.030.0160.010.0710.040.0340.030.0750.06:Student0.0160.010.0370.030.0120.010.0400.020.0090.00:0.0090.00:4 结论为了更好地揭示和量化分类数据中不同属性的数据特点，本文利用标称属性和有序属性的图结构定义了2种概率分布列之间的距离，并利用平均信息熵占总体平均信息熵的比值作为权重，提出了一种新的分类数据距离度量方法NewDM，通过与现有的几种分类数据距离度量方法和聚类算法进行对比，验证了NewDM的度量性能优于其他度量方法。同时本文还总结了2个属性值之间距离的基本框架公式，它为区分有序属性的分类数据距离度量提供了更加清晰的定义思路和改进方向。参考文献：SONGS,SUNY,ZHANGA,et al.Enrichingdataimputa-tionundersimilarityruleconstraintsJ.IEEETransactionsonKnowledgeandDataEngineering,2020,32(2):275-287.1ALABDULMOHSINI,CISSEM,GAOX,et al.LargemarginclassificationwithindefinitesimilaritiesJ.Ma-2chineLearning,2016,103(2):215-237.张巍,张圳彬.联合图嵌入与特征加权的无监督特征选择J.广东工业大学学报,2021,38(5):16-23.ZHANGW,ZHANGZB.Jointgraphembeddingandfea-tureweightingforunsupervisedfeatureselectionJ.Journ-alofGuangdongUniversityofTechnology,2021,38(5):16-23.3ZENGS,WANGX,DUANX,et al.Kernelizedmahalan-obisdistanceforfuzzyclusteringJ.IEEETransactionsonFuzzySystems,2021,29(10):3103-3117.4AGRESTIA.AnintroductiontocategoricaldataanalysisM.NewYork:JohnWiley&Sons,2018.5HAMMINGRW.ErrordetectinganderrorcorrectingcodesJ.BellLabsTechnicalJournal,2014,29(2):147-160.6AHMADA,DEYL.AmethodtocomputedistancebetweentwocategoricalvaluesofsameattributeinunsupervisedlearningforcategoricaldatasetJ.PatternRecognitionLet-ters,2007,28(1):110-118.7IENCOD,PENSARG,MEOR.Context-baseddistancelearningforcategoricaldataclusteringC/AdvancesinIn-telligentDataAnalysisVIII:8thInternationalSymposium8第4期郑丽苹，等：基于图结构的分类数据距离度量115onIntelligentDataAnalysis.Lyon:Springer,2009:83-94.IENCOD,PENSARG,MEOR.Fromcontexttodistance:learningdissimilarityforcategoricaldataclusteringJ.ACMTransactionsonKnowledgeDiscoveryfromData,2012,6(1):1-25.9JIAH,CHEUNGY,LIUJ.Anewdistancemetricforunsu-pervisedlearningofcategoricaldataJ.IEEETransactionsonNeuralNetworksLearningSystems,2015,27(5):1065-1079.10CHENL,WANGS,WANGK,et al.Softsubspacecluster-ingofcategoricaldatawithprobabilisticdist