（计算机软件与理论专业论文）基于免参数据挖掘的相异度度量研究.pdf

摘要 摘要 近年来随着数据挖掘的迅速发展，各种聚类、分类等技术己广泛应用于各种 领域，但其中参数设置带来的问题也越来越引起研究人员的注意。于是，免参数 据挖掘思想应运而生。 本文深入分析了参数设置对数据挖掘结果的各种影响，大量研究表明参数的 设定是影响甚至导致数据挖掘结果出错的重要因素之一，因此在数据挖掘的各个 环节实现免参是解决这些问题的一个途径。文章从相异度度量方法入手，在对 k o l m o g o r o v ( 描述) 复杂理论研究的基础上，将其和免参数据挖掘思想相结合， 提出了一种基于压缩的相异度度量方法s c d m ( s y m m c 缸- i c a lc o m p r e s s i o n - b a s e d d i s s i m i l a r i t ym e a s u r e ) 。该方法采用压缩算法估计k o l m o g o r o v 复杂度，由于压缩 算法本身的高效性，使得该方法也具有较高的效率。 本文使用m a t l a b 仿真软件、标准压缩软件以及d n a 序列专用的 g e n c o m p r e s s 压缩软件实现了s c d m 的功能，在d n a 序列和实时序列上做了大 量实验，与带参的距离度量方法及欧氏距离的结果进行了比较，分析了s c d m 方法的正确率 本文还将s c d m 方法应用到了层次聚类算法中，实验结果表明，由于s c d m 方法采用了压缩算法，所以对被比较对象要求不高，只要维数相近就不需要标准 化，也允许少量数据点的丢失，再加上压缩算法本身的时间空间高效性，对高维 数据的处理也比较容易，可以省去其它方法对高维数据进行降维处理这一步骤。 而且s c d m 方法不需要参数设定，因而不需要参数训练和选择，避免了参数设 置不当对聚类结果的影响，很好地提高了算法的正确率。应用s c d m 方法的层 次聚类算法的聚类准确率也较高。 关键词：免参数据挖掘；k o l m o g o r o v 复杂度；s c d m 相异度度量；g e n c o m p r e s s 压缩算法 a b s t r a ( ? r a b s t r a c t i nr e c e n ty e a r s ，d a t am i n i n gt e c h n i q u ed e v e l o p e mq u i c k l y t h ec l u s t e r i n ga n dc l a s s i f i - c a t i o nm e t h o d sh a v eb e e na p p l i e di nm a n yf i e l d s b u ta l lt h e s em e t h o d sn e e d p a r a m e t e r ss e t t i n g ；t h ep r o b l e m sp r o d u c e db yp a r a m e t e rs e t t i n ga t t r a c tm a n ya t t e n - t i o n sf r o mr e s e a r c h e r s i no r d e rt or e s o l v et h ep r o b l e m s ，t h ei d e ao fp a r a m e t e r - f l e e d a t am i n i n gw a sp r o p o s e db ys o m er e s e a r c h e r s i nt h i sw o r k , w e p r e s e n t e dt h et h e o r yo f d a t am i n i n g , a n a l y z e dt h ei n t l u e n c eo f p a r a - m e t c fs e t t i n g , a n di n d i c a t e di tw a so n ef a c t so fl e a d i n gt h er e s u l to fd a t am i n i n gt o f a l s e s oi no r d e rt oa v o i dt h ep r o b l e mw em u s tr e m o v et h ep a r a m e t e r sf t o me v e r y s t e po fd a t am i n i n gp r o c e d u r e w ec h o o s et h ed i s s i m i l a r i t ym e a s u r e an e wm e t h o d s c d m ( s 卵吼喊c a lc o m p r 懿s i o n - b a s o dd i s s i m i l a r i t ym e a s u r e ) w h i c hb a s eo n k o l m o g o r o vc o m p l e x i t yt h e o r yc o u p l e dw i t hc o m p r e s s i o nw a sp r o p o s e d t h es c d m a d a p t sc o m p r e s s i o na l g o r i t h mt oe s t i m a t ek o l m o g o r o vc o m p l e x i t y b e c a u s ec o m p r e - s s i o na l g o r i t h mi st y p i c a l l ys p a c ea n dt i m ee f f i c i e n t , s c d mi n h e r i tt h e s ea d v a n t a g e s i nt h i sp a p e r , s c d m sf u n c t i o nw a f ti m p l e m e n t e du s i n gm a t l a b 、s t a n d a r d e d c o m p r e s s o ra n dg e n c o m p r e s so nd n as e q u e n c e m a n ye x p e r i m e n t sw e r ep e r f o r m e d o nd n aa n dt i m e - s e r i e ss e q u e n c e s a n dc o m p a r i s o no fo u rr e s u l t sw i t ho t h e rr e s u l t s w h i c hu f l ee u c l i d e a nd i s t a n c e t h e ns c d mw a sa p p l i e df o rh i e r a r c h i c a lc l u s t e r i n g a ss h o w ni nt h ee x p e r i m e n t a lr e s u l t s , s c d md o n tr e q u i r et h ed i m e n s i o n a l i t yo f t w oi n s t a n c e sb e i n gc o m p a r e di se x a c t l yt h es a m e , a l l o wt h em i s s i n go fs i n g l ed a t a p o i n t i th o o d s ts e tp a r a m e t e ra n dw i t hi t sh i 曲e f f i c i e n c y , i tc a ne a s i l yr e s o l v et h e h i 曲d i m e n s i o n a l i t yi n s t a n c e s c d ma v o i dt h ei n f l u e n c eo fp a r a m e t e r , i m p r o v et h e r i g h t n e s so f a l g o r i t h ma n du s i n gi ti n t oh i e r a r c h i c a lc l u s t e r i n gc a ng e tg o o dr e s u l t k e y w o r d ：p a r a m e t e r - f l e ed a t am i n i n g ；k o l m o g o r o vc o m p l e x i t y ；s c d md i s s i m i l a r i t y m e a s u r e ；g e n c o m p r e s s 第1 章引言 1 1 研究背景与意义 第1 章引言 近年来，随着自动数据收集工具和成熟的数据库技术的蓬勃发展，千万个数 据库被用于商业管理、政府办公、科学研究和工程开发等领域，这一势头仍将持 续发展下去。越来越多的数据被存放在数据库、数据仓库和其他信息存储工具中， 这样就导致了数据爆炸的问题，从而出现了“人们正被数据淹没，却缺乏知识” 这一现象【1 1 。因此为了不被信息的汪洋大海所淹没，人们急迫的需要将这些大量 的数据转化为有用的信息和知识，从而提高信息的利用率。数据库系统虽然可以 高效地实现数据的录入、查询、统计等功能，但无法发现隐藏在这些数据后的更 重要的关联和规则，无法根据现有的数据预测未来的发展趋势。为此，人们结合 统计学、数据库、机器学习、神经网络、模式识别、模糊数学、粗糙集理论等技 术，提出数据挖掘这一新的数据处理技术来解决这一问题【2 】。数据挖掘技术渐 渐显示出其强大的生命力。 随着数据挖掘技术的飞速发展，出现了各种各样的挖掘算法。这些算法中 大多数都含有参数，参数设置显然成为数据挖掘过程中的一个重要环节，并在一 定程度上影响数据挖掘结果，所以参数设置越来越引起研究人员的注意。在许多 情况下对参数的设定都有明显的问题 3 1 ，有时因为参数设置不当可能挖掘出并不 存在的模式【4 】，或者是出现过渡拟合的危险【5 l 。这些问题的出现是因为参数设定 有很大的随机性，没有规律可以遵循，有时需要在一个数据集上做多次实验来调 整参数值，有时则依赖于研究人员的经验或是对数据集的了解。为此一些学者提 出了免参数据挖掘思想。免参数据挖掘是要通过减少算法中参数的设置在一定程 度上避免参数设定带来的问题。这个课题主要研究的内容包含：免去那些参数、 怎么实现免参、可以在哪些领域实现免参等。要达到这个目标，需要从挖掘过程 中的每一个环节入手目前，免参数据挖掘的研究还处于初级阶段，各方面的研 究还不成熟，相关工作大多数是以k o l m o g o r o v 复杂度理论为主要研究基础的， 本文将在下一章中将对数据挖掘、免参数据挖掘、k o l m o g o r o v 复杂度理论进行 一些介绍。 第1 章引言 1 2 研究内容与思路 根据上面对数据挖掘出现的问题和免参数据挖掘的现状分析，可知要实现免 参数据挖掘就要在数据挖掘的每一个环节入手，本文选择相异度度量作为工作的 起点，首先在这个环节免参。 现在常用的距离度量方法有e u c l i d e a n 距离、动态时间规整d t w ( d y n a m i c t i m ew a r p i n g ) 、支持向量机s v m ( s u p p o r tv e c t o rm a c h i n e s ) 等，它们既有优点又 有不足e u c l i d e a n 距离的优点在于使用起来比较简单，不需要参数的设定，但 其不足之处是要求相比较的两个对象之间的维数完全相同，对数据失真和噪声很 敏感，并且在处理较高维的数据集时需要对数据进行降维处理。动态时间规整 ( d t w ) 它的缺点就是含有一个参数w ，而且不允许数据中单个数据点的丢失【6 】 支持向量机( s v m ) 具有全局优化、泛化性能好、算法复杂度与特征空间维数 无关等优点，但缺点就是核函数和参数的选择缺乏理论指导【7 j ，这些在第三章将 进行更详细的介绍。除此之外查阅的资料中的大部分方法都含有参数，如对二维 轨迹进行距离计算的l c s s 模型含有两个参数，基于支持向量机( s v m ) 的一种 方法含有6 个参剡引，基于免疫的一种方法i m m 含有5 个参数【9 1 从现有的资 料可以看出，现在大部分的相异度度量都是含有参数的，为了解决参数设定带来 的一系列问题，并且克服现有相异度度量存在的问题，所以希望提出一个无参的 相异度度量。 根据k o l m o g o r o v 复杂度理论和免参数据挖掘思想，本文首先应用了压缩算 法对k o h n o g o r o v 复杂度进行近似估计，提出一种基于压缩的相异度度量方法 s c d m ( s y m m e t r i c a lc o m p r e s s i o n - b a s e dd i s s i m i l a r i t ym e 硒u r c ) ，然后使用 m a t l a b 仿真软件和压缩软件实现其功能，最后将s c d m 方法应用到了层次聚 类算法中，在d n a 序列和实时序列数据集上对其性能进行了实验，给出实验结 果分析并总结了s c d m 的优点和缺点。 1 3 论文组织结构 本文共分六章，具体的组织结构如下： 第一章主要介绍了课题研究的背景与意义，数据挖掘发展现状和文章组织结 2 第1 章引言 构。 第二章简单介绍了数据挖掘知识、免参数据挖掘发展现状和k o l m o g o r o v 复 杂度理论。 第三章主要针对本文所研究的相异度度量方法的发展现状作了一些总结，并 分析了其中所存在的问题。 第四章在k o l m o g o r o v 复杂度理论的基础上，根据l im i n g 等人提出的距离 公式对其进行可计算化和满足对称性处理，然后再进一步简化得到本文的新相异 度度量方法s c d m 解释了其实现步骤、特点和应用。 第五章把s c d m 方法应用到了层次聚类算法中，对算法进行描述，然后对 d n a 序列和实时序列进行聚类，给出聚类结果并对其做了充分的分析，最后总 结了s c d m 方法的优缺点。 第六章对本文的工作进行了总结，并对下一步工作做了展望。 3 第2 章相关知识介绍 第2 章相关知识介绍 本章主要是相关知识介绍，分为三个方面，首先是数据挖掘，然后是免参数 据挖掘，它是一种新兴的趋势，也是本文所做工作希望达到的效果，最后是 k o l m o g o r o v 复杂度理论，这是本文工作的基础下面具体介绍。 2 1 数据挖掘概述 本文的工作以数据挖掘作为大背景，因此在本章的第一小节中先来了解一下 数据挖掘。下面从五个方面来介绍。 2 1 1 数据挖掘概念及发展简史 1 、数据挖掘概念 根据文献【m l 中所说到目前为止数据挖掘还没有一个确切的定义，对它的定 义取决于定义者的观点和应用背景。下面给出一些应用较多的定义以作参考。文 献【2 】中提到较为常见的数据挖掘定义有甄种：l 、g p i a t e t s k ys h a p i o r , w j f r a w t e y 将数据挖掘定义为从数据库的大量数据中提取出隐含的、先进而未知的、潜在有 用信息的频繁过程2 、数据挖掘的广义观点：数据挖掘是从存放在数据库、数 据仓库或其他信息库中的大量数据中挖掘有趣知识的过程。 总言之数据挖掘是从大量数据中提取出可信的、新颖的、有效的并能被人理 解的模式的高级处理过程g 从大量数据中寻找其规律的技术；是统计学、数据库 技术和人工智能技术的综合i l 】。 2 、数据处理技术和数据挖掘的简史 数据挖掘这一术语是从英文的d a t am i n i n g 翻译而来，但有许多人认为数据 挖掘这个词无法准确地表述其含义，因此把另一个常用的术语k d d ( k n o w l e d g e d i s c o v e r y i n d a t a b a s e s ) 作为数据挖掘( d a t a m i n i n g ) 的同义词，并且有时用k d d 来代替数据挖掘f 2 1 从数据库中发现知识( k d d ) 一词最先出现在1 9 8 9 年举行 的第十一届国际联合人工智能学术会议上。在1 9 9 9 年亚太地区在北京招开的第 三届p a k d d 会议收到1 5 8 篇论文，研讨空前热烈。目前，数据挖掘技术在市场 4 第2 章相关知识介绍 销售，金融风险预测和基因工程研究等众多领域中也得到了成功应用【l l 】 2 1 2 数据挖掘的对象 数据挖掘又可以定义为是从大量的、不完全的、有噪声的、模糊的、随机的 数据中提取出隐含在其中的、人们事先不知道的、但又是潜在的有用的信息和知 识的过程而数据挖掘的对象可以是结构化的( 如，关系数据库中的数据等) ， 半结构化的( 如，文本、图形、图像、音频等多媒体数据) ，分布在网络上的异 构性数据等【1 2 1 ，以下是数据挖掘对象的主要来源【1 l = 关系数据库 数据仓库 事务数据库 面向对象数据库 对象关系数据库 空间数据库 时间数据库和时间序列数据库 文本数据库和多媒体数据库 异种数据库和遗产数据库 万维网m b ) 2 1 3 数据挖掘的方法 数据挖掘的核心技术是人工智能、机器学习、数据统计等，但它并非多种技 术的简单结合，而是不可分割的整体，还需其他技术的支持，才能挖掘出令用户 满意的结果 2 1 。目前常用的数据挖掘方法有聚类、分类、关联规则、w e b 网页挖 掘掣1 2 1 接下来较为具体的介绍一些常用的数据挖掘方法： i 、聚类分析( c l u s t e r i n g ) 聚类分析是将对象集合分组为由类似的对象所组成的多个簇的过程，也就是 将对象集合划分成几个组，使得同一簇内的对象具有较高的相似度，不同簇内的 对象的则具有较高的相异度，即“物以类聚”。它的特点是没有预先定义的类，即 5 第2 章相关知识介绍 它是一种无指导的分类。常用的技术有划分方法、层次方法( 包括两种：1 分 裂方法，也称为自顶向下的方法；2 凝聚方法，也称为自底向上的方法) 、基于 密度的方法、基于网格的方法、基于模型的方澍1 3 】。 2 、分类和预测分析 2 1 分类 分类在数据挖掘中是一项非常重要的任务。分类分析方法又分为决策树分 类、贝叶斯分类、基于神经网络的分类、支持向量机分类、基于源于关联规则挖 掘的分类等。下面对其中两种作较为详细的介绍。 2 1 1 决策树方法( d e c i s i o nt r e , o ) 决策树方法是一种常用的方法，它是为人工智能所开发的有指导的归纳学习 方法，可以用来数据分析和预测。它通过将大量数据有目的分类，从中找到一些 有价值的潜在的信息。其基本思想是：决策树以自顶向下。递归分治( d i v i d e - a n d c o n q u e r ) 的方式构造，所有的属性都是分类的( c a t e g o r i c a l ) 。连续值属性要预先离 散化，开始时所有的训练样本都在根上，节点上的样本递归基于选定的属性划分， 属性的选择基于启发式或统计度量( 如：信息增益) ；决策树停止划分的条件是： 给定节点上的所有样本都属于一个类，或没有属性用于进一步的划分( 使用多数 表决来决定树叶节点的分类) ，或给定节点上没有样本。决策树方法主要包括c l s 方法、i d 3 算法、c 4 5 算法及对应的剪枝算法【l 】 2 1 2 神经网络( n e u r a ln e r w o r k ) 典型的神经网络模型主要分3 大类：以感知机、b p 反向传播模型、函数型 网络为代表的，用于特征抽取和模式识别的前馈式神经网络模型；以h o p f i e l d 的离散模型和连续模型为代表的，分别用于联想记忆和优化计算的反馈式神经网 络模型；以a r t 模型、k o h o n e n 模型为代表的，用于聚类的自组织影射方法【1 4 l 。 神经网络方法的优势在于带有反向传播学习和k o h o n e n 网络的多层感知机、且 具有很好的防噪声功能和自组织适应性，这就使得它能精确的对复杂问题进行预 测，而且对未知对象的分类能力也较好。其最大的缺点是没有对自身行为的理解 能力，即它的“黑箱”性，人们难以理解它是如何学习和决策的；另外在检验数据 方面也有缺陷，人工神经网络易于受训练过渡的影响；构造神经网络要对其训练 6 第2 章相关知识介绍 许多遍，需要花费许多时间；它需要大量的参数，这些通常主要靠经验确定，如 网络拓扑或“结构” 2 2 预测 预测分析与分类分析不同的是预测分析用于预测连续或有序值而不是加类 标号比如：根据以往产品的定价和销售等信息，预测分析一个给定价格的新产 品的销售量。 预测分析方法常用回归统计技术。建立模型常用的有线性回归、多元回归和 非线性回归。线性回归、多元回归常用最小二乘法作回归处理，许多非线性问题 都可以通过预测变量上的变化，转换成为线性问题。 3 、关联规则( a s s o c i a t i o nr u l e ) 关联规则是一种简单、实用的分析规则，就是要发现事物数据库、关系数据 库或其它信息库中项或数据对象集合之间的频繁模式、关联相关或因果关系结 构。它描述了一个事物中某些属性同时出现的规律和模式，是数据挖掘中最成熟 的主要技术之一关联规则分为布尔关联规则与量化关联规则，这区分于它们所 处理值的类型。并根据其涉及的属性维数分为单维关联规则或多维关联规则。关 联规则这一概念是由r a g r a w a l 等人首先提出的，最经典的关联规则的挖掘算法 是a p r i o r i 算法，该算法的思想是：首先挖掘出所有的频繁项集，然后由频繁项 集产生关联规则，许多关联规则频繁项集的挖掘算法都是由它演变而来的1 1 0 】【1 2 1 。 除此之外数据挖掘方法还包含统计方法( s t a t i s t i c ) 、模糊数学方法、w e b 网 页挖掘、孤立点分析等。 2 1 4 数据挖掘的应用 数据挖掘是一门具有广泛应用的新兴学科，只要存在大量的数据并需要从中 提取出有用信息就可能用到数据挖掘，以下是数据挖掘技术可能的应用领域【l 习： l 、市场分析与管理：是数据挖掘技术应用最早也是最重要的领域之一。在 这个领域中可以有下面几方面的应用。可以挖掘出顾客群，他们具有相同的特征， 如：年龄相近，收入水平相当，消费观点一致，喜好相同等；还可以对客户进行 分类，什么样的客户会买什么样的产品：另外还可以识别顾客的需求，发现什么 因素能影响顾客的购买趋势，如一些顾客偏爱物美价廉的商品，一些顾客偏爱具 7 第2 章相关知识介绍 有知名度的商品等。 2 、风险分析和管理：财经规划和资产评估中的现金流分析和预测以及其中 的临时提出的资产评估。顾客关系，改进保险，质量控制，资源规划中的资源与 开销的汇总与比较，竞争能力分析。 3 、欺骗检测与管理：使用历史数据建立欺骗行为模型，使用数据挖掘帮助 识别类似的实例。 4 、其它应用；文本挖掘、流数据挖掘、w e b 挖掘、d n a 数据分析。 2 2 免参数据挖掘 数据挖掘算法中一般都含有参数，参数的设定很显然成为一个需要解决的问 题。对参数设定的好坏没有任何的标准，在分类中是通过在训练样本集上对参数 进行一次次的训练来得出较为合适的参数，有时能得到很好的结果，但只是在同 种数据集上能出现好的结果，一旦变换数据集就不能使用。更糟的情况是训练时 出现了过渡拟和现象。对于聚类而言，聚类是无指导的分类，需要设定聚类后的 簇数，簇数设定的正确与否没有标准，只能是看设定参数的人对整个数据集的了 解有多少和个人经验。对子序列进行聚类时因为参数设定不当会导致挖掘出并不 存在的模式 4 1 各种各样参数设置带来的问题越来越引起研究人员的注意，为了 解决这些问题，一些研究人员提出了免参数据挖掘思想。 免参数据挖掘思想不是绝对的免参，而是尽量少的设置参数。免去哪些参数、 怎样实现免参、可以在哪些领域实现免参都是这个课题所要研究的内容。由于免 参数据挖掘刚刚处于萌芽状态，与其相关的文献较少，下面对其中的一些为大家 做简单介绍。 文章【1 6 】中首先提出了如何度量两个序列之间相似度的问题，如何比较两个 基因序列或者是两篇文章的内容等。为了解决这一问题他们希望能设计出一种不 是为某个特定应用领域所定义的一个相似度度量的方法。因此作者研究了一种基 于标准距离概念的相似度数学理论，这个理论不需要用应用领域的背景知识和专 业特征。不需要进行什么改变就可应用于不同领域的甚至应用于从不同领域得到 的数据对象的集合。为了实现这个目标，作者首先定义一个相似度的宽泛类。然 后，说明这个类包含一个特殊距离，这个距离普遍包含在下面的情况中：对每一 0 第2 章相关知识介绍 对对象特殊距离比在这个类中这两个对象的任何有效距离都小。这个通用距离被 起名为标准信息距离，而且被证明其是一个公制，它同时揭示了所有相似度在类 中的有效距离和揭示了一个单一的相似度。基于真实世界的压缩器提出了一个实 际的应用距离，称为标准压缩距离。 一句话概括就是为可计算标准距离定义一个新距离。这个新距离是一个没有 固定上界的可计算标准距离的低界由一个简单公式给出，它是一个公制，属于 标准距离类，并且减小上面的非定值低界。它不是上界半可计算的，但它是第一 个通用的相似度度量，也是图灵理论的一个客观不变的概念。但由于它是以不可 计算的相关对象的k o l m o g o r o v 复杂度的形式来表达的，所以其本身也具有不可 计算性。因此根据k o l m o g o r o v 复杂度理论中所提到的用压缩的方法来估计其近 似值的方法，作者采用同样的方法来实现所研究的理论 整篇文章对适合于度量两序列之间相似性关系的一种新的距离进行了研究。 基于k o l m o g o r o v 复杂性不可计算概念提出了一种新的标准化的信息距离，并且 证明了它是一个公制并且称它为相似度公尺。从理论的角度来看获得了一个通用 的数学理论，它产生了一个固定的框架可以产生实际的距离来应用于许多不同的 领域中。一些显著成功的实验证明了方法的基本正确性这个方法的优点在于其 通用性很强，因为它可以在完全不同的领域中挖掘模式，且不需要任何特定对象 领域的背景知识最重要的是介绍这篇文章的目的和主要原因就是，这种方法不 需要设定特定领域参数，这一点与本文的思想非常接近。有兴趣的话可以参看相 关参考文献。 文章【1 7 1 比较正式的提出了免参数据挖掘这个概念和思想，其中提到大多数 数据挖掘算法需要设置许多输入参数，应用带参算法存在两个主要问题：第一。 错误的设置可能导致一个算法无法找到真正的模式。第二，一个更严重的问题是 算法可能给出根本不存在的假模式，或过高估计所给出模式的重要性。这种情况 经常发生在用户没有正确理解参数在数据挖掘过程中的作用的时候。作者指出数 据挖掘算法应该含有尽量少的参数，最好是没有参数。一个没有参数的算法就可 以把人为影响算法效果的可能性减小到最低，实现真正的自动化。 文章中，作者实现了一个完全没有参数的聚类算法他们的方法是以 k o l m o g o r o v 复杂度理论为基础，并且应用了压缩算法他们提出的方法允许免 9 第2 章相关知识介绍 参或少参的数据挖掘算法解决许多典型的数据挖掘任务，如：聚类，分类和异常 发现等等。 提出的方法有以下的优点： 它允许真正的探测式的数据挖掘，不受任何主观因素的影响； 方法的精确度也能优于那些带参算法，并且他们所能处理的问题更为 广泛。 方法中应用了压缩算法，而压缩算法是典型的空间和时间高效性算法 因此该方法也具有了这样的优点。 许多带参数的挖掘算法要求数据以一种特殊格式存储。但该方法没有 这样的要求，它对数据本身没有过多要求。 此外文章指出带有许多参数的数据挖掘算法对用户来说是很难有效应用的。 而且也通过实验说明带参数据挖掘存在过渡拟合的现象，如果采用免参的算法就 可以避免这一问题。但是提出的方法也存在着很多问题，还需进一步改善。 文章【1 8 】对由二进制特征集合所组成的空间数据进行了研究，提出了一种不 需任何参数就可以同时发现空间相关联和共同特征( g o - o c c u i t e n c e ) 的模式。这 样就解决同时并且自动地找出空间相关联的模式和共同特征模式的问题。作者希 望在所有的空间数据集合中( 如：生物异样性数据、地理数据、环境数据、历史 和语言数据等) 发现有意义的共同特征和空间相关联模型。现存的方法都存在弊 端，他们不是只能独立的发现这两种模式中的一种，就是需要用户来指定特定的 参数或者是阈值，也就是说发现特征和空间相关联模型不能同时进行，而且需要 用户设置一些参数，所以作者把m d l 原理和基本的压缩技术结合起来应用于提 出的新方法中新方法从简洁总结数据的视角出发来看待问题，并且应用m d l 原理来使这个过程自动化。同时对位置和特征进行分组；特征模式有助于更好的 压缩空间相关联模式，反之亦然。 总之作者提出了一种自动发现空间相关联模式和特征模式的方法，一般来 说： 它可以同时分组单元和特征：特征模式有助于更好的压缩空间相关联模 式，反之亦然 对于单元分组，提出一种以基础和原理的方法来合并和开拓空间相似的 1 0 第2 章相关知识介绍 实用方法。 采用了m d l 原理，直接从数据并且不需要任何参数来发现组群、合组 群的数日。 该方法除了不需要任何参数设置外，还易于扩展到其他基础的空间层次方 法，并且算法的执行效率也较高且具有很好的可扩展性 除此之外，文章【1 9 2 0 1 中也涉及到了免参。比较前两篇文章可以发现，这两 篇文章的共同之处在于他们都是以k o l m o g o r o v 复杂度为基础，而且需要用到压 缩算法。而第三篇文章虽然没有直接用到k o l m o g o r o v 复杂度理论但用到了m d l 原理和压缩算法，而其中的m d l 原理也是由k o l m o r o g o v 复杂度理论所构造， 所以从本质上说这三篇文章的共同点就是都以k o l m o g o r o v 复杂度理论为基础， 并且应用了压缩算法。从总结出可以看出由于压缩算法的时间空间高效性和其他 的一些优点，它经常被人们应用于各种算法中而k o l m o g o r o v 复杂度理论由于 最近对它的研究结果显示，成为研究免参算法的基础，所以一些研究学者常以这 个理论为研究基础进行研究。 2 3k o l m o g o r o v 复杂度 对免参数据挖掘的发展情况进行分析后发现目前实现免参挖掘的关键就在 于k o l m o g o r o v 复杂度理论，本文也考虑以k o l m o g o r o v 复杂度理论为基础，并 且应用压缩算法，接下来就介绍一下k o l m o g o r o v 复杂度理论。 2 3 1k o l m o g o r o v 复杂度的通用性( u n l v e r s a l i t y ) k o l m o g o r o v 复杂度理论的产生基于1 9 3 6 年图灵对通用图灵机的发现。在图 灵机作为一种计算机器概念的解释被提出后，图灵发现存在一种图灵机它可以模 仿其他的任何图灵机。据k o l m o g o r o v 所说复杂度可以由一个通用图灵机正确产 生被观察数据的最短程序的长度来度量。这样就有人会提出如果用不同的图灵机 那将会得到不同的复杂度，其实不然，已经有学者证明了虽然有许多种通用图灵 机但相应的复杂度最多是一个常量的差别。 k o l m o g o r o v 复杂度理论的主要推动力是其通用性，它努力在通用的编码方 法基础上构建通用的学习方法这个方法是由s o l m o n n o f f 首先提出，然后由 第2 章相关知识介绍 k o l m o g o r o v 发展到数学领域的这种方法只在很有限的环境中可计算。因此在 应用中只能希望去估计k o l m o g o r o v 复杂度和相关的值。 2 3 2 理论内容 通常来讲k o l m o g o r o v 复杂度理论分为三部分：复杂度，随机性，信息。在 这里的k o l m o g o r o v 复杂度强调复杂度。另外两个常用的术语是算法信息理论和 算法概率理论。在本节中简单的介绍一下这三个部分。 l 、复杂度 在k o l r n o g o r o v 复杂度理论中最重要的发展是由i 七v i n 介绍的前缀复杂度概 念。前缀复杂度用于解决一些算法信息理论和算法随机性理论中的技术问题。除 了前缀复杂度外，也介绍了其他的几个复杂度。a l e x a n d e rs h 吼提出了一种可以 用一个统一的模型来描述不同复杂度度量的通用构架。所有这四个k o l m o g o r o v 复杂度的变形在对数术语中都是一致的。 2 、随机性 随机性本质上意味着k o l m o g o r o v 复杂度接近于一些上界值。k o l m o g o r o v 在 他的两篇著作中粗略的描述了一个方案可以用它的随机性概念在概率的数学理 论和概率的应用之间建立起更为紧密的联系。但是这个方案的命运与他先前所提 理论的命运完全不同随机性理论主要是在无限序列的情况下发展的，虽然 k o l m o g o r o v 发现无限序列的研究很有趣，但是也很清楚当注意力放在了以经验 为基础的不存在的无限序列上时就会丢失任何与现实的联系。 3 、信息 k o l m o g o r o v 除了一生喜爱概率理论的基础外，另一个他致力于算法复杂度 的动力是信息理论的新想法。在一篇文章中他把一个对象x 中所包含的另一个对 象y 的信息量定义为下：i ( x ：y ) = k ( y ) - k ( y l x ) 。k o l m o g o r o v 注意到这个信息定义的 主要问题是一些这个标准概率信息概念的基本性质，如：对称性，对算法信息i ( x ：y ) 来说已经不满足这个性质了。l e v i n 、g a c s 和c h a i t i n 提出了一种解决这个问题的 方法；他们把公有信息定义为l ( x ：y ) = 取y ) - 取y l x ，磁x ) ) ，其中k 是前缀复杂度， 这样使得它又满足了对称性。但是这个理论没有很好的发展起来，一个可能的解 释就是信息i ( x ：y ) 是不可计算的，所以不能直接应用，需要进行估计，这样就会 1 2 第2 章相关知识介绍 导致很多问题的出现【2 l 】。 描述复杂度把一个串x 的复杂度定义为在一个普通的图灵机上对x 的最短描 述p 的长度，即u ( k ( x ) - - m i n l ( p ) ：u ) = x ) ) 如果一个串可以被一个短程序描述， 那么它就是一个简单串，如一个由几百万个1 组成的串，虽然它很长但是用一个 很简单的程序就可以得到如果没有可以描述它的简单程序存在，那么这个串就 是一个复杂串，如一个没有任何重复的串，因为组成它的每一个字母或项都不同 所以要产生这个串就只能一位一位的做。描述复杂度是信息( i n f o r m a t i o n ) 理论 中的核心概念。k 的一个很重要的性质就是它几乎独立于对u 的选择，并且它 引导了比其他有效性编码更短的编码。k 与s h a n n o n 的熵s 有很多相似的性质， 但k 在许多方面比s 要更优越一些，总之，k 是一个极好的通用的复杂度度量。 k 作为复杂度度量的一个主要缺点就是它的不可计算性。所以在实际应用中它通 常是估计而来，如用m m i m d l 或者l e m p e l - z i v 压缩器，或者是其他的压缩 工具瞄】下面是对其更为直观的介绍。 描述复杂度0 ，1 串x 所含信息可用对x 的描述之长短来刻划，可以认为串 x 的描述是构造x 的指令组，串x 的描述复杂度可直观地定义为生成x 的最短程 序的长度，记作k t x ) 这个程序无输入，其输出为x 。 作为普遍定义，k ( x ) 必须客观地反映x 所含信息多少，不会由于采用不同计 算模型下的程序概念而使对应的取x ) 值截然不同。在可计算理论中已证明，现 存的不同的计算模型a ，b 之间可以相互模拟，于是a 模型下的程序p a 结合模拟 程序后，就成为b 模型下的程序p n ，因此在相差一个常数的意义下i ( x ) 值是唯 一确定的。 描述复杂度理论是在可计算性理论的发展和计算机广泛应用的推动下发展 起来的6 0 年代a h 柯尔奠戈罗夫与柴廷各自独立地提出描述复杂度概念，用 以定义数的随机性，并能较全面地提出关于程序长度的描述复杂度理论。 理论内容描述复杂度理论的研究对象是0 ，l 串以及它们变换时所含信息 的变化它可用于研究形式系统，分析公理所含信息与它推出的定理所含信息之 间的关系，也可用于研究计算过程，从而得出计算所耗费资源的下界( 见计算复 杂性理论) 和时间与空间的折换关系 柴廷定理 柴廷1 9 7 4 年得出下列重要结果；对任何相容的公理化理论t 1 3 蔓! 童塑茎塑堡坌塑 都存在一个常数c t o ( 它只依赖于d ，使k ( x ) c t 这样的命题在t 内是不可证 的 若把t 取作数论公理系统，在t 内可表达k ( x l l c t 这样的命题，并且由k ( x ) 的基本性质可知：对任何1 1 都有长为1 1 的串x 使k ( x ) - - n , 因此当n 足够大时，命题 l 【( x ) 劬是成立的，但在t 中却不可证明。由此可推出，串的随机性是不可证的。 它改进了k 哥德尔关于数论公理统系不完全性定理，给出一个更具体的不可证命 题：k ( x ) c b 从信息角度阐明了公理方法的局限性【捌。 描述复杂度是研究某些性质不可证时的有力工具。通过发展、改进现有的方 法，有希望对计算复杂性理论中某些重大问题提供一些方法，而且对某些具体问 题的下界得出新的结果。 对当前k o l m o g o r o v 复杂度理论的发展进行分析，实现具有重要用途的m d l 原理和m m l 原理构架是其最重大的应用。下面的一些章节里将具体的叙述 k o l m o g o r o v 理论如何应用于本文提出的相异度度量。为了与本文提出的相异度 方法进行比较，在接下来的章节中先来介绍一下目前常用的相异度度量。 第3 章相似，相异度度量 第3 章相似相异度度量 免参数据挖掘是要通过减少算法中参数的设置在一定程度上避免参数设定 对数据挖掘结果的影响。要达到免参数据挖掘这个目标，需要从挖掘过程中的每 一个环节入手。本文选择相异度度量作为工作的起点，因此接下来介绍一下相似 异度的概念和目前常用的相似异度度量及其发展现状总结出它们所存在的问 题，为本文工作的展开奠定基础 3 1 相似相异度简介 d e k a n gl i n 曾从信息论的角度给出了一个统一的、与应用领域无关的相似度 非形式化定义【矧。他认为，两对象之间的相似度与两方面问题有关，一方面是 它们的共性，共性越多，相似度越高；另一方面是它们的区别，区别越大，相似 度越低；当两对象完全相同时，相似度达到最大值。因此，要根据具体情况去寻 找合适的定义，并且在不同的应用中，相似度的含义也有所不同。 两对象之间的相似度是使用一定的公式来计算的，这种能计算相似度的公式 被称为相似度计算方法，简称相似度算法。目前可供选择的相似度算法很多，包 括相关系数法、夹角余弦法、距离方法( 马氏距离、欧氏距离、明氏距离) 、模糊 相关法等等从理论上讲，任何一个可以计算两向量关系的函数都可以作为一种 相似度算法。不同的相似度计算方法，可以从不同角度反映两对象的相似情况， 可能得到不同结论，并不存在矛盾。 3 2 一些常用的相似相异度度量介绍 数据挖掘中常用的距离度量有欧氏距离( e u c l i d e a n ) 、动态时问规整( d t w ) ， 支持向量机( s v m ) 等，下面就详细介绍一下这些距离度量。 第3 章相似相异度度量 3 2 1 欧氏距离 在这个部分中，首先介绍一下通常用于计算用区间标度变量描述的对象之间 的相异度的距离度量。包括e u c l i d e a n 、m a n h a t t a n 、m i n k o w s k i 距离，而其中最 常用的距离度量就是欧几里德距离( e u c l i d e a n ) ，定义为下： d g 力= 属i i 石可 其中i f f i ( x l l ，x i 2 ，x o 而j = ( x j l ，距，嘞) ，i 和j 是两个p - 维的数据对象 参看下面的图3 - l 能更直观的理解e u c l i d e a n 距离的定义，其中图3 - k a ) 表示两个 p 维数据对象i 和j ，而图3 1 ( b ) 中的阴影部分表示 i 和j 之间的e u c l i d e a n 距离。 e u c l i d e a n 距离的缺陷在于它对数据中的噪 声和失真现象较为敏感，而且从e u c l i d e a n 距离 的定义公式可以看出，他要求被比较的两个串要 具有相同的维数。除了上面定义的距离公式外还 可以使用加权e u c l i d e a n 距离，其定义如下： a ( i , j 3 2 j w l ( h o p + w 2 l 一o f + 一i 一0 1 2 ) 除了e u c l i d e a n 距离外，其他比较常用的距离包 括曼哈坦( m a n b a n 锄) 距离和明考斯基( m i n k o w s k i ) 距离。其中m a n h a t t a n 距离定义如下： d ( 1 d ： 一勺。i + 1 一o i + + i 勺一o l e u c l i d e a n 距离和m a n h a t t