论文部分内容阅读
传统的机器学习、数据挖掘算法是基于向量型数据提出的。由于结构化数据在现实应用中广泛存在,图形数据的表示和分析正得到越来越广泛的关注。由于图数据结构的复杂性,不能仅用向量对其进行表达,这使得多数传统的学习算法不能应用于图形数据的分析。通过降维或向量空间嵌入的方式,对复杂的图形数据进行低维向量表示,在保留图的原有结构特征的同时,也扩大了传统算法对图形数据的适用性。另一方面,以往的研究主要集中在定义图数据间相似性度量(图核或图编辑距离)上,且利用了图中节点和边的标签信息。但作为标识图数据属于哪一类的类别信息较少被使用。成对约束,即标识两图是否属于同一类,作为一种半监督信息,由于其较类别标签更容易获取的特性,已经在机器学习的很多领域得到了成功的应用。因此,本文对成对约束信息在图形数据中的应用进行研究,提出基于图数据分析的新的算法,并进一步对约束集的选取进行改进,提高算法性能。主要的创新和研究工作总结如下:(1)对图核诱导的高维特征空间中的数据进行降维,使得传统算法能够对图数据对应的低维向量进行分析。进一步将成对约束信息加入到降维过程,得到基于图核的半监督降维算法(GK-SSDR),使低维向量表达更有助于图的分类。在标准图数据集上验证了上述算法的有效性。(2)利用负约束对标识两图不属于同一类的特性,提出了将图形数据改写成向量形式的图约束嵌入算法(GCE)。GCE既保留了图的判别信息,使向量表达更利于分类,又使传统学习算法能应用于图数据分析。通过与传统核方法、相关嵌入算法、及GK-SSDR算法的比较显示了GCE算法的性能。(3)针对GK-SSDR和GCE的性能易受约束集具体组成影响的缺点,将集成的思想应用到约束集的选取上,形成约束集成算法(CE)。通过在标准图数据集上的比较,对GK-SSDR和GCE在约束集的选取上使用CE算法,有效提高了其算法性能。