基于实例的学习,包括最近邻学习、局部加权学习、以及基于记忆的推理等,都依靠一个好的距离度量获得成功。可以说,距离度量问题是基于距离的机器学习算法的核心所在。此外,距离度量还被广泛应用到模式识别、神经网络、统计学、以及认知心理学等各个领域。实例之间的距离度量一直是一个非常重要的问题。为此,学者们提出了许多距离度量。比如,Euclidean距离、Manhattan距离、Minkowsky距离、Mahalanobis距离、Camberra距离等等。然而,这些距离度量都只适用于数值属性而不适用于名词性属性。相比数值属性的距离度量,名词性属性的距离度量是一个更加复杂的问题。为了给名词性属性值之间的距离以合理的估计,学者们做出了很多努力,提出了一些距离度量。比如,重叠度量(Overlap Metric, OM),值差度量(Value Difference Metric, VDM),修正的值差度量(Modified Value Difference Metric, MVDM),Short-Fukunaga度量(Short and Fukunaga Metric, SFM),最小风险化度量(Minimum Risk Metric, MRM),基于熵的度量(Entropy-Based Metric, EBM),及基于频率的度量(Frequency-Based Metric, FBM)等等。在现实问题中,大量的数据集都涉及到名词性属性。名词性属性距离度量相比数值属性更加复杂。本论文将主要针对名词性属性的距离度量问题展开研究。主要考虑的问题有以下几点：1、如何理解距离度量中的属性独立性假设?VDM是一个被广泛应用的名词性属性距离度量,而据我们分析,VDM是作了属性独立假设的。在VDM中,两个实例之间的距离是每一维距离的叠加,维与维之间没有关联。事实上,大多数的距离度量都是如此,如最简单的处理名词性属性的距离度量OM,还有处理数值属性的Euclidean距离和Hamming距离等,都是利用的这种每一维距离的简单叠加来度量实例之间的距离的。我们认为,这种简单的叠加实质上就是假设每一维是相互独立的。Kasif等人也指出,VDM作了和朴素贝叶斯分类器一样的属性独立假设。尽管这个不现实的属性独立假设,朴素贝叶斯分类器表现出了令人惊讶的分类性能,而VDM也是目前为止被应用最为广泛的名词性属性距离度量之一。那么,如何理解并应用这种属性独立假设,构造改进的或者新的距离度量,使之具有简洁、可理解、容易计算的特点呢?2、如何在距离度量中体现属性之间的依赖关系?现实数据中,属性之间多半是存在依赖关系的。而大多数的距离度量,就像朴素贝叶斯分类器一样,作了属性独立假设。尽管朴素贝叶斯分类器表现出了令人惊讶的分类性能,但是当属性间存在强依赖关系时,朴素贝叶斯的分类性能受到了一定程度的伤害。为此,学者们利用各种技术对朴素贝叶斯分类器进行改进,一个有效的途径就是结构扩展。结构扩展的中心思想就是在朴素贝叶斯模型中利用有限的有向边来表达属性之间的依赖关系,得到扩展的贝叶斯网络分类器。现在已有很多学者提出了许多扩展的贝叶斯网络分类器,这些扩展的贝叶斯网络分类器用有向边来表达属性之间的依赖关系,在一定程度上放宽了属性独立假设,从而具有比朴素贝叶斯分类器更好的分类性能。既然表达属性依赖关系可以改进朴素贝叶斯分类器的性能,那么,能不能仿效扩展的贝叶斯网络分类器,把这种属性依赖关系也引入到距离度量中来,从而改进现有距离度量的性能,甚至构造新的距离度量,使这些距离度量在属性有强依赖关系的数据上表现出更好的性能呢?3、如何尽可能准确地估测基于概率的距离度量中的类成员概率?在处理名词性属性的距离度量中,有一部分需要估测概率,这部分距离度量被称为基于概率的距离度量,比如VDM,MVDM, SFM, MRM等。其中,一部分基于概率的距离度量又需要估测类成员概率。比如,上节中提到的SFM和MRM都需要估测实例x属于类成员c的概率P(c|x)。要使得这些基于概率的距离度量获得成功,如何尽可能准确地估测类成员概率P(c|x)是一个非常关键的问题。有研究表明：完全地估测类成员概率P(c|x)等同于学习一个最优的贝叶斯网络,是一个NP-hard问题。为降低计算复杂性,现有文献都是用朴素贝叶斯分类器进行近似估测,这在一定程度上影响了距离度量的性能。已有学者在人工数据集上的实验证明,如果可以准确的知道类成员概率,SFM和MRM可以比VDM具有更好的性能。其实,已有研究表明：朴素贝叶斯的类概率估测能力较差(尽管它是一个性能良好的分类器)。为了提高朴素贝叶斯的类概率估测能力,学者们提出了一些改进的贝叶斯模型。那么,能不能把类概率估测方面的研究成果应用于基于概率的距离度量中,提高各种距离度量中的类成员概率估测精度,从而改进相关距离度量的性能呢?4、如何克服维度灾难问题?本论文立意研究距离度量问题,而与距离度量密切相关的一个问题就是维度灾难问题(the Curse of Dimensionality Problem)。维度灾难问题已被众多的学者所关注,维度灾难问题是指当数据中有大量冗余或者不相关属性时,算法的性能会受到影响。维度灾难对距离度量所导致的问题在于,当数据中存在大量不相关属性时,如果用所有的属性来计算实例之间的距离,那么近邻间的距离会被大量不相关的属性所支配,从而导致计算出来的所谓近邻可能相去甚远。克服维度灾难问题的一种方法是属性加权,也就是考虑每个属性与类变量之间不同的相关性,给相关性较大的属性赋予较大的权值,从而抑制不相关属性对距离计算的影响。另一种更加强有力的方法是属性选择,也就是从属性空间中完全消除不相关的属性。近年来,学者们对属性加权和属性选择问题都已经作了大量的研究工作。现有文献已有大量的属性加权和属性选择方法方面的研究成果,本论文将特别针对名词性属性距离度量对这个问题继续进行深入探讨。比如OM因为其简单性,得到了广泛的应用。那么,能不能利用属性加权技术保持距离度量的简洁性,同时提高它的性能呢?对著名的VDM,既然这个距离度量作了属性独立假设。那么,能不能在这个假设的基础上,设计适合VDM的属性选择方法呢?如前所述,机器学习、模式识别、神经网络、统计学、以及认知心理学等领域中的很多算法都涉及到距离度量,并且它们的性能都依赖于所使用的距离度量。比如,k-近邻(k-Nearest Neighbor, KNN)算法及其改进：距离加权的k-近邻(Distance Weighted k-Nearest Neighbor, KNNDW)算法、局部加权的朴素贝叶斯(Locally Weighted Naive Bayes, LWNB)算法等等。经过对前几个问题的研究势必会提出一些高性能的距离度量。因此,如何利用这些新提出的距离度量来改进上述这些距离相关算法的性能显得尤为重要。本论文将对这个问题进行深入研究。鉴于上面提出的几点问题,本论文以名词性属性距离度量为研究对象,从不同的角度对现有的名词性属性距离度量进行了研究和改进。主要的工作如下1、研究了距离度量中的属性独立假设；尽管朴素贝叶斯分类器的属性独立假设众所周知,但距离度量中的属性独立假设还未引起学者们的广泛关注。论文第二章详细地讨论了值差度量(Value Difference Metric, VDM)中的属性独立假设,指出这个属性独立假设和朴素贝叶斯分类器的假设是一致的。在这个假设的基础上,以Short-Fukunaga度量(Short and Fukunaga Metric, SFM)为原型,提出了修正的Short-Fukunaga度量(Modified Short and Fukunaga Metric, MSFM)。实验证明,MSFM和VDM性能相当,超过了SFM和SFM的另一个修改版本SF2LOG。2、将属性依赖关系引入距离度量中;扩展的贝叶斯网络分类器通过引入属性依赖关系,获得了比朴素贝叶斯分类器更好的性能。论文第三章从理论和实验两方面调查了朴素贝叶斯分类器和一些扩展的贝叶斯网络分类器的性能。扩展的贝叶斯网络分类器利用有向边来表达属性之间的依赖关系,一定程度上释放了朴素贝叶斯的属性独立假设,由此改进了朴素贝叶斯分类器的性能。受扩展的贝叶斯网络模型的启迪,本论文将属性依赖关系引入到距离度量中,利用扩展的贝叶斯网络分类器来学习属性依赖关系,根据学到的属性依赖关系构造相应的距离度量。以值差度量(Value Difference Metric, VDM)为原型,提出了表达属性依赖关系的距离度量：一依赖的值差度量(One Dependence Value Difference Metric, ODVDM)。实验证明,在具有强依赖关系的数据上,ODVDM比VDM表现出了更好的性能。3、提高基于概率的距离度量中的类成员概率估测精度；基于概率的距离度量中有一部分需要估测类成员概率P(c|x),这些距离度量的性能直接受类成员概率估测精度的影响。论文第四章以基于概率的距离度量Short-Fukunaga度量(Short and Fukunaga Metric, SFM)和最小风险化度量(Minimum Risk Metric, MRM)为研究对象。因为SFM和MRM的性能极大地依赖于类成员概率P(c|x)的估测精度,现有文献一般用朴素贝叶斯来估测类成员概率。但已有文献表明朴素贝叶斯的类成员概率估测能力不高。为了提高朴素贝叶斯的类概率估测性能,学者们提出了大量改进的算法。论文第四章重点调查了这些算法的类概率估测性能,并利用它们来估测SFM和MRM的类成员概率值。实验表明,精确的类成员概率估测方法可以极大的提高SFM和MRM的性能。4、利用属性加权途径改进距离度量；属性加权途径是克服维度灾难问题的一个有效途径。论文第五章考察了最简单的名词性属性距离度量：重叠度量(Overlap Metric, OM),和最简单的可以同时处理名词性属性和数值属性的距离度量：异构欧几里得—重叠度量(Heterogeneous Euclidean-Overlap Metric, HEOM),利用属性加权的途径对其进行改进,提出了相关性加权的异构欧几里得—重叠度量(Correlation Weighted Heterogeneous Euclidean-Overlap Metric, CWHEOM)。在CWHEOM中,针对分类和回归问题,我们应用不同的技术提出了加权方案。在36个分类数据和36个回归数据上的实验表明,相关性加权的途径极大的改进了HEOM的性能,同时保持了距离度量的简洁性和可理解性。5、利用属性选择途径改进距离度量；前面章节中主要关注距离度量应用到距离相关算法时,是否能改进距离相关算法的的分类性能。其实,类概率估测也是机器学习和数据挖掘领域一个重要的问题。论文第六章以类概率估测为任务,研究了KNN及其改进KNNDW的类概率估测性能,关注当距离度量VDM被应用到KNN和KNNDW时,如何改进方法的性能。论文第六章应用属性选择的途径去改进VDM的性能。基于VDM作了属性独立假设这个基础,找到了适合VDM的属性选择方法CFS和SBC-CLL。实验结果表明,利用CFS和SBC-CLL为VDM作属性选择后,KNN和KNNDW的类概率估测性能有了很大提高。6、应用论文中提出的距离度量到距离相关算法去处理地球物理和工程方面的实际应用问题。本论文所有章节的实验都以UCI数据库(http://archive.ics.uci.edu/ml/datasets.html)中的大量数据集为实验数据,广泛调查了我们所提出的距离度量应用到距离相关算法时的泛化性能。除此之外,论文还以孔隙度预测、瓦斯量涌出预测、岩爆预测和边坡稳定性预测等一些地球物理和工程方而的实际应用问题为背景,调查了我们的距离度量应用到距离相关算法时在这些地球物理和工程问题数据集上的表现。综上所述,本文将重点依托贝叶斯网络模型,对名词性属性的距离度量问题进行系统深入的研究。借鉴朴素贝叶斯分类器的研究成果,来研究距离度量中的属性独立假设；应用贝叶斯网络表达属性依赖关系的方法来学习距离度量,将距离度量的构造问题转化为属性依赖关系的学习问题；全面调查现有的类概率估测算法,并用来计算距离度量中的类成员概率,从而提高距离度量的性能,推动基于概率的距离度量的应用,使得距离相关的学习算法有更好的性能。因此本文的研究可以为名词性属性的距离度量新方法研究提供示例,具有重大的理论意义和应用前景。但因用贝叶斯网络来表达属性依赖关系和估测类成员概率本身具有一定难度,将其与距离度量问题联系起来,有几个关键科学问题尚待解决,这使得对这一问题的研究面临着不小的挑战。论文的主要创新点如下：1、朴素贝叶斯分类器的属性独立假设受到了学者们广泛的关注,但距离度量中同样存在的属性独立假设还未受到学者们广泛的关注。本论文对距离度量中的属性独立假设作了详细研究,并在此基础上提出了改进的距离度量。2、提出将属性依赖关系引入距离度量问题中,构造新的距离度量,使之在有强依赖关系的数据上表现出更好的性能。主要借助贝叶斯网络分类器来学习属性依赖关系,将距离度量的构造问题转化为属性依赖关系的学习问题。3、详细地研究了现有类成员概率估测方面的成果,并借助贝叶斯网络类成员概率估测器来提高基于概率的距离度量中的类成员概率估测精度。将距离度量问题和贝叶斯网络学习模型结合。