转发：支持向量机&数据挖掘[综述,希望对搞这方面研究的朋友有点帮助

[Nirvana 发表于 2006-6-26 10:53:28]


文献综述
第一部分 引言

基于数据的机器学习是现代智能技术中的重要方面, 研究从观测数据(样本) 出发寻找规律, 利用这些规律对未来数据或无法观测的数据进行预测. 包括模式识别、神经网络等在内, 现有机器学习方法共同的重要理论基础之一是统计学. 传统统计学研究的是样本数目趋于无穷大时的渐近理论, 现有学习方法也多是基于此假设. 但在实际问题中, 样本数往往是有限的, 因此一些理论上很优秀的学习方法实际中表现却可能不尽人意.与传统统计学相比, 统计学习理论(Statistical Learning Theory，SLT) 是一种专门研究小样本情况下机器学习规律的理论. Vapnik 等人从六、七十年代开始致力于此方面研究, 到九十年代中期, 随着其理论的不断发展和成熟, 也由于神经网络等学习方法在理论上缺乏实质性进展, 统计学习理论开始受到越来越广泛的重视.统计学习理论是建立在一套较坚实的理论基础之上的, 为解决有限样本学习问题提供了一个统一的框架. 它能将很多现有方法纳入其中, 有望帮助解决许多原来难以解决的问题(比如神经网络结构选择问题、局部极小点问题等) ; 同时, 在这一理论基础上发展了一种新的通用学习方法——支持向量机(Support Vector Machine，SVM ) , 它已初步表现出很多优于已有方法的性能. 一些学者认为, SLT和SVM 正在成为继神经网络研究之后新的研究热点, 并将有力地推动机器学习理论和技术的发展
我国早在八十年代末就有学者注意到统计学习理论的基础成果, 但之后较少研究,目前只有少部分学者认识到这个重要的研究方向. 本文重点研究的多分类支持向量机至今还没有突破性进展。


第二部分 数据挖掘常用分类技术、算法


1、分类数据挖掘常用技术
　
分类作为数据挖掘中一项非常重要的任务,目前在商业上应用最多。分类的目的是学会一个分类函数或分类模型(也常常称作分类器),该模型能把数据库中的数据项映射到给定类别中的某一个，从而可以用于预测。目前，分类方法的研究成果较多，判别方法的好坏可以从三个方面进行：1）预测准确度（对非样本数据的判别准确度）；2）计算复杂度（方法实现时对时间和空间的复杂度）；3)模式的简洁度（在同样效果情况下，希望决策树小或规则少）。
近年来，对数据挖掘中分类算法的研究是该领域中一个热点，对不同分类方法都有许多对比研究成果。没有一个分类方法在对所有数据集上进行分类学习均是最优的。目前在数据挖掘软件中运用的最早也是最多的分类算法是神经网络，它具有对非线性数据快速建模的能力，通过对训练集的反复学习来调节自身的网络结构和连接权值，并对未知的数据进行分类和预测。但是，神经网络从某种意义上说是一种启发式的学习机，本身有很大经验的成分，为了克服传统神经网络方面不可避免的难题，Vapnik提出了一种新的神经网络――支持向量机，并随后提出了基于结构风险最小化思想的统计学习理论，正式奠定了SVM的理论基础，鉴于SVM扎实的理论基础

2、数据挖掘分类算法
（1）、判别分析
线性判别，KNN，Bayes判别，多元回归分析，Rocchio法，距离函数法，支持向量机，势函数法
（2）、机器学习
ID3决策树，AQ11算法，Rough Sets
（3）、神经网络
（4）、支持向量机



第三部分 支持向量机

1、支持向量机概述

V. Vapnik提出的支持向量机理论因其坚实的理论基础和诸多良好特性在近年获得了广泛的关注。已经有许多事实证明，作为支持向量机最基本思想之一的结构化风险最小化原则（Structural Risk Minimization, SRM ）要优于传统的经验风险最小化原则（Empirical Risk Minimization, ERM）。不同于ERM试图最小化训练集上的误差的做法，SRM试图最小化VC维的上界，从而使其学习机获得了更好的推广性能，这恰恰是统计学习理论最重要的目标之一。支持向量机的主要应用领域有模式识别、函数逼近和概率密度估计等等，本文的讨论重点是使用支持向量机进行多分类的问题。


2、支持向量机相关讨论：
(1)SVM的优势：
由于支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度，Accuracy)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷，以期获得最好的推广能力(Generalizatin Ability)。支持向量机方法的几个主要优点是
可以解决小样本情况下的机器学习问题
可以提高泛化性能
可以解决高维问题
可以解决非线性问题
可以避免神经网络结构选择和局部极小点问题

(2)SVM的研究热点
目前，SVM算法在很多领域都有应用。例如，在模式识别方面，对于手写数字识别、语音识别、人脸图像识别、文章分类等问题，SVM算法在精度上已经超过传统的学习算法或与之不相上下。SVM主要有如下几个研究热点：
模式识别
回归估计
概率密度估计

(3)SVM的主要核函数
多项式核: (gamma*u’*v + coef0)^degree
径向基核（RBF）: exp(-gamma*u-v^2)
Sigmoid 核: tanh(gamma*u’*v + coef0)

(4)SVM的应用
文本分类，人脸识别
三维物体识别，遥感图像分析
函数逼近，时间序列预测
数据压缩，优化SVM算法
SVM改进方法（多分类扩展，用于多现实中的多分类问题）
SVM硬件实现

(5)SVM的难点
如何在非监督模式识别问题中应用统计学习理论（SLT）
如何用理论或实验的方法计算VC维
经验风险和实际风险之间的关系称之为推广性的界，但是当(h/n)>0.37时（h—VC维，n—样本数），推广性的界是松弛的，如何寻找一个更好地反映学习机器能力的参数和得到更紧的界
实现结构风险最小化（SRM）时，如何选择函数子集结构


第四部分 文献概述

1.Principles of Data Mining
出版社：机械工业出版社,中信出版社
作者：David Hand Heikki Mannila Padhraic Smyth
翻译：张银奎，廖丽，宋俊

本书讲的是数据挖掘的原理，而不仅仅是应用。介绍了常用的数据挖掘算法极其应用所依赖的基本原理；在数据挖掘算法中系统讨论了如何构建求解特定问题的不同算法，如何用算法和原理来解决现实中的问题本书也做了深入讨论。该书以统计学家的视角系统解析了数据挖掘技术所依赖的统计原理，应用面向组件的思想，把数据挖掘算法分解为既相互联系，又相对独立的几大组件：模型结构、评分函数、搜索方法、数据管理技术。全书既具有极强的理论性，又不脱离实践，对要求深入学习数据挖掘技术的人来讲很有帮助。



2.一种新的基于二叉树的SVM多类分类方法
源自：计算机应用
作者：孟媛媛,刘希玉
发表时间：2005年11月

本文对几种常用的支持向量机多类分类方法进行了分析和对比，分析其存在的问题和缺点。提出了一种基于二叉树的支持向量机多类分类方法(BT2SVM) ,通过先聚类后分类的思想构造最优二叉树结构，并将基于核的自组织映射引入进行聚类,以提高分类精度,取得了不错的效果。下面是本论文几个重点论述的方面：
支持向量机多分类方法的理论基础是：K分类问题( K > 2) 和两类分类问题之间存在一定的对应关系,如果一个分类问题K可分,则这K类中的任何两类间一定可分;反之,在一个K分类问题中, 如果已知任意两两可分,则通过一定的组合法则,可由两两可分来最终实现K类可分。
常用的支持向量机多分类方法有1-v-r(One-versus-the rest Method),1-v-1(One-versus-one Method), DDAG SVMs(Decision Directed Acyclic Graph, DDAG)决策导向非循环图。1-v-r,1-v-1由于其固有缺陷存在不可分区域 （如下图），而DDAG SVMs 的优点是推广误差只取决于类数k和结点上的类间间隙(Margin) ,而与输入空间的维数无关。