33周志华：数据挖掘与机器学习

机器学习与数据挖掘周志华南京大学计算机软件新技术国家重点实验室，南京210093“机器学习”是人工智能的核心研究领域之一，其昀初的研究动机是为了让计算机系统具有人的学习能力以便实现人工智能，因为众所周知，没有学习能力的系统很难被认为是具有智能的。目前被广泛采用的机器学习的定义是“利用经验来改善计算机系统自身的性能”[1]。事实上，由于“经验”在计算机系统中主要是以数据的形式存在的，因此机器学习需要设法对数据进行分析，这就使得它逐渐成为智能数据分析技术的创新源之一，并且为此而受到越来越多的关注。“数据挖掘”和“知识发现”通常被相提并论，并在许多场合被认为是可以相互替代的术语。对数据挖掘有多种文字不同但含义接近的定义，例如“识别出巨量数据中有效的、新颖的、潜在有用的、昀终可理解的模式的非平凡过程”[2]。其实顾名思义，数据挖掘就是试图从海量数据中找出有用的知识。大体上看，数据挖掘可以视为机器学习和数据库的交叉，它主要利用机器学习界提供的技术来分析海量数据，利用数据库界提供的技术来管理海量数据。因为机器学习和数据挖掘有密切的联系，受主编之邀，本文把它们放在一起做一个粗浅的介绍。1无处不在随着计算机技术的飞速发展，人类收集数据、存储数据的能力得到了极大的提高，无论是科学研究还是社会生活的各个领域中都积累了大量的数据，对这些数据进行分析以发掘数据中蕴含的有用信息，成为几乎所有领域的共同需求。正是在这样的大趋势下，机器学习和数据挖掘技术的作用日渐重要，受到了广泛的关注。例如，网络安全是计算机界的一个热门研究领域，特别是在入侵检测方面，不仅有很多理论成果，还出现了不少实用系统。那么，人们如何进行入侵检测呢？首先，人们可以通过检查服务器日志等手段来收集大量的网络访问数据，这些数据中不仅包含正常访问模式还包含入侵模式。然后，人们就可以利用这些数据建立一个可以很好地把正常访问模式和入侵模式分开的模型。这样，在今后接收到一个新的访问模式时，就可以利用这个模型来判断这个模式是正常模式还是入侵模式，甚至判断出具体是何种类型的入侵。显然，这里的关键问题是如何利用以往的网络访问数据来建立可以对今后的访问模式进行分类的模型，而这正是机器学习和数据挖掘技术的强项。实际上，机器学习和数据挖掘技术已经开始在多媒体、计算机图形学、计算机网络乃至操作系统、软件工程等计算机科学的众多领域中发挥作用，特别是在计算机视觉和自然语言处理领域，机器学习和数据挖掘已经成为昀流行、昀热门的技术，以至于在这些领域的顶级会议上相当多的论文都与机器学习和数据挖掘技术有关。总的来看，引入机器学习和数据挖掘技术在计算机科学的众多分支领域中都是一个重要趋势。机器学习和数据挖掘技术还是很多交叉学科的重要支撑技术。例如，生物信息学是一个新兴的交叉学科，它试图利用信息科学技术来研究从DNA到基因、基因表达、蛋白质、基因电路、细胞、生理表现等一系列环节上的现象和规律。随着人类基因组计划的实施，以及基因药物的美好前景，生物信息学得到了蓬勃发展。实际上，从信息科学技术的角度来看，生物信息学的研究是一个从“数据”到“发现”的过程，这中间包括数据获取、数据管理、数据分析、仿真实验等环节，而“数据分析”这个环节正是机器学习和数据挖掘技术的舞台。正因为机器学习和数据挖掘技术的进展对计算机科学乃至整个科学技术领域都有重要意义，美国NASA-JPL实验室的科学家2001年9月在《Science》上专门撰文[3]指出，机器学习对科学研究的整个过程正起到越来越大的支持作用，并认为该领域将稳定而快速地发展，并将对科学技术的发展发挥更大的促进作用。NASA-JPL实验室的全名是美国航空航天局喷气推进实验室，位于加州理工学院，是美国尖端技术的一个重要基地，著名的“勇气”号和“机遇”号火星机器人正是在这个实验室完成的。从目前公开的信息来看，机器学习和数据挖掘技术在这两个火星机器人上有大量的应用。除了在科学研究中发挥重要作用，机器学习和数据挖掘技术和普通人的生活也息息相关。例如，在天气预报、地震预警、环境污染检测等方面，有效地利用机器学习和数据挖掘技术对卫星传递回来的大量数据进行分析，是提高预报、预警、检测准确性的重要途径；在商业营销中，对利用条形码技术获得的销售数据进行分析，不仅可以帮助商家优化进货、库存，还可以对用户行为进行分析以设计有针对性的营销策略；……。下面再举两个例子。公路交通事故是人类面临的昀大杀手之一，全世界每年有上百万人丧生车轮，仅我国每年就有约10万人死于车祸。美国一直在对自动驾驶车辆进行研究，因为自动驾驶车辆不仅在军事上有重要意义，还对减少因酒后、疲劳而引起的车祸有重要作用。2004年3月，在美国DARPA（国防部先进研究计划局）组织的自动驾驶车辆竞赛中，斯坦福大学的参赛车在完全无人控制的情况下，成功地在6小时53分钟内走完了132英里（约212公里）的路程，获得了冠军。比赛路段是在内华达州西南部的山区和沙漠中，路况相当复杂，有的地方路面只有几米宽，一边是山岩，另一边是百尺深沟，即使有丰富驾驶经验的司机，在这样的路段上行车也是一个巨大的挑战。这一结果显示出自动2驾驶车辆已经不再是一个梦想，可能在不久的将来就会走进普通人的生活。值得一提的是，斯坦福大学参赛队正是由一位机器学习专家所领导的，而获胜车辆也大量使用了机器学习和数据挖掘技术。Google、Yahoo、百度等互联网搜索引擎已经开始改变了很多人的生活方式，例如很多人已经习惯于在出行前通过网络搜索来了解旅游景点的背景知识、寻找合适的旅馆、饭店等。美国新闻周刊曾经对Google有个“一句话评论”：“它使得任何人离任何问题的答案之间的距离只有点击一下鼠标这么远”。现在很少有人不知道互联网搜索引擎的用处，但可能很多人并不了解，机器学习和数据挖掘技术正在支撑着这些搜索引擎。其实，互联网搜索引擎是通过分析互联网上的数据来找到用户所需要的信息，而这正是一个机器学习和数据挖掘任务。事实上，无论Google、Yahoo还是微软，其互联网搜索研究核心团队中都有相当大比例的人是机器学习和数据挖掘专家，而互联网搜索技术也正是机器学习和数据挖掘目前的热门研究话题之一。2雄关漫道机器学习是人工智能研究发展到一定阶段的必然产物。从20世纪50年代到70年代初，人工智能研究处于“推理期”，人们认为只要给机器赋予逻辑推理能力，机器就能具有智能。这一阶段的代表性工作主要有A.Newell和H.Simon的“逻辑理论家”程序以及此后的“通用问题求解”程序等，这些工作在当时取得了令人振奋的成果。例如，“逻辑理论家”程序在1952年证明了著名数学家罗素和怀特海的名著《数学原理》中的38条定理，在1963年证明了全部的52条定理，而且定理2.85甚至比罗素和怀特海证明得更巧妙。A.Newell和H.Simon因此获得了1975年图灵奖。然而，随着研究向前发展，人们逐渐认识到，仅具有逻辑推理能力是远远实现不了人工智能的。E.A.Feigenbaum等人认为，要使机器具有智能，就必须设法使机器拥有知识。在他们的倡导下，20世纪70年代中期开始，人工智能进入了“知识期”。在这一时期，大量专家系统问世，在很多领域做出了巨大贡献。E.A.Feigenbaum作为“知识工程”之父在1994年获得了图灵奖。但是，专家系统面临“知识工程瓶颈”，简单地说，就是由人来把知识总结出来再教给计算机是相当困难的。于是，一些学者想到，如果机器自己能够学习知识该多好！实际上，图灵在1950年提出图灵测试的文章中，就已经提到了机器学习的可能，而20世纪50年代其实已经开始有机器学习相关的研究工作，主要集中在基于神经网络的连接主义学习方面，代表性工作主要有F.Rosenblatt的感知机、B.Widrow的Adaline等。在20世纪6、70年代，多种学习技术得到了初步发展，例如以决策理论为基础的统计学习技术以及强化学习技术等，代表性工作主要有A.L.Samuel的跳棋程序以及N.J.Nilson的“学习机器”等，20多年后红极一时的统计学习理论的一些重要结果也是在这个时期取得的。在这一时期，基于逻辑或图结构表示的符号学习技术也开始出现，代表性工作有P.Winston的“结构学习系统”、R.S.Michalski等人的“基于逻辑的归纳学习系统”、E.B.Hunt等人的“概念学习系统”等。31980年夏天，在美国卡内基梅隆大学举行了第一届机器学习研讨会；同年，《策略分析与信息系统》连出三期机器学习专辑；1983年，Tioga出版社出版了R.S.Michalski、J.G.Carbonell和T.M.Mitchell主编的《机器学习：一种人工智能途径》[4]，书中汇集了20位学者撰写的16篇文章，对当时的机器学习研究工作进行了总结，产生了很大反响a；1986年，《MachineLearning》创刊；1989年，《ArtificialIntelligence》出版了机器学习专辑，刊发了一些当时比较活跃的研究工作，其内容后来出现在J.G.Carbonell主编、MIT出版社1990年出版的《机器学习：风范与方法》[5]一书中。总的来看，20世纪80年代是机器学习成为一个独立的学科领域并开始快速发展、各种机器学习技术百花齐放的时期。R.S.Michalski等人[4]中把机器学习研究划分成“从例子中学习”、“在问题求解和规划中学习”、“通过观察和发现学习”、“从指令中学习”等范畴；而E.A.Feigenbaum在著名的《人工智能手册》b中[6]，则把机器学习技术划分为四大类，即“机械学习”、“示教学习”、“类比学习”、“归纳学习”。机械学习也称为“死记硬背式学习”，就是把外界输入的信息全部记下来，在需要的时候原封不动地取出来使用，这实际上没有进行真正的学习；示教学习和类比学习实际上类似于R.S.Michalski等人所说的“从指令中学习”和“通过观察和发现学习”；归纳学习类似于“从例子中学习”，即从训练例中归纳出学习结果c。20世纪80年代以来，被研究得昀多、应用昀广的是“从例子中学习”（也就是广义的归纳学习），它涵盖了监督学习（例如分类、回归）、非监督学习（例如聚类）等众多内容。下面我们对这方面主流技术的演进做一个简单的回顾。在20世纪90年代中期之前，“从例子中学习”的一大主流技术是归纳逻辑程序设计（InductiveLogicProgramming），这实际上是机器学习和逻辑程序设计的交叉。它使用1阶逻辑来进行知识表示，通过修改和扩充逻辑表达式（例如Prolog表达式）来完成对数据的归纳。这一技术占据主流地位与整个人工智能领域的发展历程是分不开的。如前所述，人工智能在20世纪50年代到80年代经历了“推理期”和“知识期”，在“推理期”中人们基于逻辑知识表示、通过演绎技术获得了很多成果，而在知识期中人们基于逻辑知识表示、通过领域知识获取来实现专家系统，因此，逻辑知识表示很自然地受到青睐，而归纳逻辑程序设计技术也自然成为机器学习的一大主流。归纳逻辑程序设计技术的一大优点是它具有很强的知识表示能力，可以较容易地表示出复杂数据和复杂的数据关系。尤为重要的是，领域知识通常可以方便地写成逻辑表达式，因此，归纳逻辑程序设计技术不仅可以方便地利用领域知识指导学习，还可以通过学习对领域知识进行精化和增强，甚至可以从数据中学习出领域知识。事实上，机器学习在20世纪80年代正是被视为“解决知识工程瓶颈问题的关键”而走到人工智能主舞台的聚光灯下的，归纳逻辑程序设计的一些良好特性对此无疑居功至伟d。S.H.Muggleton主编的书[7]对90年代中期之前归纳逻辑程序设计方面的研aMorganKaufmann出版社后来分别于1986年和1990年出版了该书的续篇，编为第二卷和第三卷。b该书共4卷，分别由E.A.Feigenbaum与不同的学者合作编写而成。c“归纳学习”有狭义的解释和广义的解释。前者要求从训练数据中学得概念，因此也被称为“概念学习”或“概念形成”；后者则对学习结果是否是可理解的概念不做要求。d“归纳逻辑程序设计”这个名字其实是