数据挖掘分析的方法

1.广义知识挖掘

广义知识(Generalization)是指描述类别特征的概括性知识。众所周知,在源数据(如数据库)中存放的一般是细节性数据,而人们有时希望能从较高层次的视图上处理或观察这些数据,通过数据进行不同层次的泛化来寻找数据所蕴含的概念或逻辑,以适应数据分析的要求。数据挖掘的目的之一就是根据这些数据的微观特性发现有普遍性的、更高层次概念的中观和宏观的知识。因此,这类数据挖掘系统是对数据所蕴含的概念特征信息、汇总信息和比较信息等概括、精炼和抽象的过程。被挖掘出的广义知识,可以结合可视化技术,以直观的图表(如饼图、柱状图、曲线图、立方体等)形式展示给用户,也可以作为其他应用(如分类、预测)的基础知识。

2.关联知识挖掘

关联知识(Association)反映一个事件和其他事件之间的依赖或关联。数据库中的数据关联是现实世界中事物联系的表现。数据库作为一种结构化的数据组织形式,利用其依附的数据模型可能刻画了数据间的关联,如关系数据库的主键和外键。但是,数据之间的关联是复杂的,不仅是上面所说的依附在数据模型中的关联,大部分是隐藏的。关联知识挖掘的目的就是找出数据库中隐藏的关联信息。关联可分为简单关联、时序(Time Series)关联、因果关联、数量关联等,这些关联并不总是事先知道的,而是通过数据库中数据的关联分析获得的,因而对商业决策具有新价值。

3.类知识挖掘

类知识(Class)刻画了一类事物,这类事物具有某种意义上的共同特征,并明显和不同类事物相区别。和其他的文献相对应,这里的类知识是指数据挖掘的分类和聚类两类数据挖掘应用所对应的知识。

(1)分类方法有以下几种。

1)决策树。决策树方法,在许多的机器学习书或论文中可以找到,这类方法中的ID3算法是最典型的决策树分类算法,之后的改进算法包括ID4、ID5、C4.5、C5.0等。这些算法都是从机器学习角度研究和发展起来的,对于大训练样本集很难适应。这是决策树应用向数据挖掘方向发展必须面对和解决的关键问题。在这方面的尝试有很多,比较有代表性的研究有Agrawal等人提出的SLIQ、SPRINT算法,它们强调了决策树对大训练集的适应性。1998年,Michalski等对决策树与数据挖掘的结合方法和应用进行了归纳。另一个比较著名的研究是Gehrke等人提出了一个称为雨林(Rainforest)的在大型数据集中构建决策树的挖掘构架,并在1999年提出这个模型的改进算法BOAT。另外的一些研究,集中在针对数据挖掘特点所进行的高效决策树、裁剪决策树中规则的提取技术与算法等方面。

2)贝叶斯分类。贝叶斯分类(Bayesian Classification)来源于概率统计学,并且在机器学习中被很好地研究。近几年,作为数据挖掘的重要方法备受瞩目。朴素贝叶斯分类(Naïve Bayesian Classification)具有坚实的理论基础,和其他分类方法相比,其理论上具有较小的出错率。但是,由于受其对应用假设的准确性设定的限制,因此需要在提高和验证它的适应性等方面做进一步工作。Jone提出连续属性值的内核稠密估计的朴素贝叶斯分类方法,提高了基于普遍使用的高斯估计的准确性,Domingos等对于类条件独立性假设应用假设不成立时朴素贝叶斯分类的适应性进行了分析,贝叶斯信念网络(Bayesian Belief Network)是基于贝叶斯分类技术的学习框架,集中在贝叶斯信念网络本身架构以及它的推理算法研究上,其中比较有代表性的工作有Russell的布尔变量简单信念网、训练贝叶斯信念网络的梯度下降法、Buntine等建立的训练信念网络的基本操作以及Lauritzen等的具有蕴藏数据学习的信念网络及其推理算法EM等。

3)神经网络。神经网络作为一个相对独立的研究分支已经很早被提出,有许多著作和文献详细介绍了它的原理。由于神经网络需要较长的训练时间及其可解释性较差,为它的应用带来了困难。但是,由于神经网络具有高度的抗干扰能力和可以对未训练数据进行分类等优点,又使得它具有极大的诱惑力。因此,在数据挖掘中使用神经网络技术是一件有意义但仍需要艰苦探索的工作。在神经网络和数据挖掘技术的结合方面,一些利用神经网络挖掘知识的算法被提出,如Lu和Setiono等人提出的数据库中提取规则的方法、Widrow等系统介绍了神经网络在商业等方面的应用技术。

4)遗传算法。遗传算法是基于进化理论的机器学习方法,它采用遗传结合、遗传交叉变异以及自然选择等操作,实现规则的生成。有许多著作和文献详细介绍了它的原理,这里不再赘述。

5)类比学习和案例学习。最典型的类比学习(Analogy Learning)方法是k-最邻近分类(k-Nearest Neighbor)方法,它属于懒散学习法,与决策树等急切学习法相比,具有训练时间短、分类时间长的特点。k-最邻近方法可以用于分类和聚类中,基于案例的学习(Case-Based Learning)方法可以应用到数据挖掘的分类中。基于案例学习的分类技术的基本思想是,当一个新案例进行分类时,通过检查已有的训练案例找出相同的或最接近的案例,然后根据这些案例提出这个新案例的可能解。利用案例学习来进行数据挖掘的分类必须要解决案例的相似度、度量训练案例的选取以及利用相似案例生成新案例的组合解等关键问题,并且它们也正是目前研究的主要问题。

6)其他方法。如粗糙集和模糊集(Fuzzy Set)方法等。

另外需要强调的是,任何一种分类技术与算法都不是万能的,不同的商业问题需要用不同的方法去解决,即使对于同一个商业问题可能有多种分类算法。分类的效果一般和数据的特点有关。有些数据噪声大、有缺值、分布稀疏,有些属性是离散的,而有些是连续的,所以目前普遍认为不存在某种方法能适合所有特点的数据。因此,对于一个特定问题和一类特定数据,需要评估具体算法的适应性。

(2)聚类方法有以下几种。

1)基于划分的聚类方法。k-平均算法是统计学中的一个经典聚类方法,但是它只有在簇平均值被预先定义好的情况下才能使用,加之对噪声数据的敏感性等,使得对数据挖掘的适应性较差。因此,出现了一些改进算法。主要有Kaufman等人提出的k-中心点算法、PAM和Clare算法、Huang等人提出的k-模和k-原型方法、Bradley和Fayyad等建立的基于k-平均的可扩展聚类算法。其他的具代表性的方法有EM算法、Clarans算法等。基于划分的聚类方法得到了广泛研究和应用,但是对于大数据集的聚类仍需要进一步的研究和扩展。

2)基于层次的聚类方法。通过对源数据库中的数据进行层次分解,达到目标簇的逐步生成。有两种基本的方法,即凝聚(Agglomeration)和分裂(Division)。凝聚聚类是指由小到大开始,可能是每个元组为一组逐步合并,直到每个簇满足特征性条件。分裂聚类是指由大到小开始,可能为一组逐步分裂,直到每个簇满足特征性条件。Kaufman等人详细介绍了凝聚聚类和分裂聚类的基本方法,Zhang等人提出了利用CF树进行层次聚类的Birth算法,Guha等人提出了Cure算法、Rock算法,Karypis和Han等人提出了Chameleon算法。基于层次的聚类方法计算相对简单,但是操作后不易撤销,因而对于迭代中的重定义等问题仍需做进一步工作。

3)基于密度的聚类方法。基于密度的聚类方法是通过度量区域所包含的对象数目来形成最终目标的。如果一个区域的密度超过指定的值,那么它就需要进一步分解成更细的组,直至得到用户可以接受的结果。这种聚类方法相比基于划分的聚类方法,可以发现球形以外的任意形状的簇,而且可以很好地过滤孤立点(Outlier)数据,对大型数据集和空间数据库的适应性较好。比较有代表性的工作有1996年Ester等人提出的DBSCAN方法、1998年Hinneburg等人提出的基于密度分布函数的DENCLUE聚类算法、1999年Ankerst等人提出的OPTICS聚类排序方法。基于密度的聚类算法,大多还是把最终结果的决定权参数值交给用户决定,这些参数的设置以经验为主。而且对参数设定的敏感性较高,即较小的参数差别可能导致区别很大的结果。因此,这是这类方法有待进一步解决的问题。

4)基于网格的聚类方法。这种方法是把对象空间离散化成有限的网格单元,聚类工作在这种网格结构上进行。1997年,Wang等人提出的String方法是一个多层聚类技术。它把对象空间划分成多个级别的矩形单元,高层的矩形单元是多个低层矩形单元的综合,每个矩形单元的网格收集对应层次的统计信息值。该方法具有聚类速度快、支持并行处理和易于扩展等优点,受到广泛关注。另一些有代表性的研究包括Sheikholeslami等人提出的通过小波变换进行多分辨率聚类方法Wave Cluster、Agrawal等人提出的把基于网格和密度结合的高维数据聚类算法CLIQUE等。

5)基于模型的聚类方法。这种方法为每个簇假定一个模型,寻找数据对给定模型的最佳拟和。目前研究主要集中在利用概率统计模型进行概念聚类和利用神经网络技术进行自组织聚类等方面,它需要解决的主要问题之一仍然是如何适用于大型数据库的聚类应用。

最近的研究倾向于利用多种技术的综合性聚类方法探索,以解决大型数据库或高维数据库等聚类挖掘问题。一些焦点问题也包括孤立点检测、一致性验证、异常情况处理等。

4.预测型知识挖掘

预测型知识(prediction)是指由历史的和当前的数据产生的并能推测未来数据趋势的知识。这类知识可以被认为是以时间为关键属性的关联知识,应用到以时间为关键属性的源数据挖掘中。从预测的主要功能上看,主要是对未来数据的概念分类和趋势输出。可以用于产生具有对未来数据进行归类的预测型知识,统计学中的回归方法等可以通过历史数据直接产生对未来数据预测的连续值,因而,这些预测型知识已经蕴藏在诸如趋势曲线等输出形式中。利用历史数据生成具有预测功能的知识挖掘工作归为分类问题,而把利用历史数据产生并输出连续趋势曲线等问题作为预测型知识挖掘的主要工作。分类型的知识也应该有两种基本用途:一是通过样本子集挖掘出的知识可能目的只是用于对现有源数据库的所有数据进行归类,以使现有的庞大源数据在概念或类别上被“物以类聚”;二是有些源数据尽管它们是已经发生的历史事件的记录,但是存在对未来有指导意义的规律性东西,如总是“老年人的癌症发病率高”。因此,这类分类知识也是预测型知识。

(1)趋势预测模式。主要是针对那些具有时序(time series)属性的数据,如股票价格等,或者是序列项目(sequence items)的数据,如年龄和薪水对照等、发现长期的趋势变化等。有许多来自于统计学的方法,经过改造可以用于数据挖掘中,如基于n阶移动平均值(moving average of ordern)、n阶加权移动平均值、最小二乘法、徒手法(freehand)等的回归预测技术。另一些研究较早的数据挖掘分支,如分类、关联规则等技术,也被应用到趋势预测中。

(2)周期分析模式。其主要是针对那些数据分布和时间依赖性很强的数据进行周期模式的挖掘,如服装在某季节或所有季节的销售周期。近年来,这方面的研究备受瞩目,除了传统的快速傅里叶变换等统计方法及其改造算法外,也从数据挖掘研究角度进行了有针对性的研究,如1999年Han等人提出的挖掘局部周期的最大自模式匹配集方法。

(3)序列模式。其主要是针对历史事件发生次序的分析形成预测模式来对未来行为进行预测,如预测“三年前购买计算机的客户有很大概率会买数字相机”。主要工作包括1998年Zaki等人提出的序列模式挖掘方法、2000年Han等人提出的称为Free Span的高效序列模式挖掘算法等。

(4)神经网络。在预测型知识挖掘中,神经网络也是很有用的模式结构,但是由于大量的时间序列是非平稳的,其特征参数和数据分布随着时间的推移而发生变化。因此,仅仅通过对某段历史数据的训练来建立单一的神经网络预测模型,还无法完成准确的预测任务。为此,人们提出了基于统计学等的再训练方法。当发现现存预测模型不再适用于当前数据时,对模型重新训练,获得新的权重参数,建立新的模型。

此外,也有许多系统借助并行算法的计算优势等进行时间序列预测。总之,数据挖掘的目标之一,就是自动在大型数据库中寻找预测型信息,并形成对应的知识模式或趋势输出来指导未来的行为。

5.特异型知识挖掘

特异型知识(exception)是源数据中所蕴含的极端特例,或明显区别于其他数据的知识描述,它揭示了事物偏离常规的异常规律。数据库中的数据常有一些异常记录,从数据库中检测出这些数据所蕴含的特异知识是很有意义的,如在站点发现那些区别于正常登录行为的用户特点,可以防止非法入侵。特异型知识可以和其他数据挖掘技术结合起来,在挖掘普通知识的同时进一步获得特异型知识,如分类中的反常实例、不满足普通规则的特例、观测结果与模型预测值的偏差、数据聚类外的离群值等。

6.数据仓库中的数据挖掘

数据仓库中的数据是按照主题来组织的。存储的数据可以从历史的观点提供信息。面对多数据源,经过清洗和转换后的数据仓库可以为数据挖掘提供理想的发现知识的环境。假如一个数据仓库模型具有多维数据模型或多维数据立方体模型支撑的话,那么基于多维数据立方体的操作算子可以达到高效率的计算和快速存取。虽然目前的一些数据仓库辅助工具可以帮助完成数据分析,但是发现蕴藏在数据内部的知识模式及其按知识工程方法来完成高层次的工作仍需要新技术。因此,研究数据仓库中的数据挖掘技术是必要的。

数据挖掘不仅伴随数据仓库而产生,而且随着应用的深入,产生了许多新的课题。如果把数据挖掘作为高级数据分析手段来看,那么它是伴随数据仓库技术提出并发展起来的。随着数据仓库技术的出现,出现了联机分析处理应用。OLAP尽管在许多方面和数据挖掘是有区别的,但是它们在应用目标上有很大的重合度,那就是它们都不满足于传统数据库的仅用于联机查询的简单应用,而是追求基于大型数据集的高级分析应用。客观地讲,数据挖掘更看中数据分析后所形成的知识表示模式,而OLAP更注重利用多维等高级数据模型实现数据的聚合。

7.Web数据源中的数据挖掘

面向Web的数据挖掘,比面向数据库和数据仓库的数据挖掘要复杂得多,因为它的数据是复杂的,有些是无结构的(如Web页),通常都是用长的句子或短语来表达文档类信息,有些可能是半结构的(如E-mail、HTML页),当然有些具有很好的结构(如电子表格)。揭开这些复合对象蕴含的一般性描述特征,成为数据挖掘的不可推卸的责任。

目前,Web挖掘的研究主要有3种流派,即Web结构挖掘(Web Structure Mining)、Web使用挖掘(Web Usage Mining)和Web内容挖掘(Web Content Mining)。

(1)Web结构挖掘。Web结构挖掘主要是指挖掘Web上的链接结构,它有广泛的应用价值。例如,通过Web页面间的链接信息可以识别出权威页面(Authoritative Page)、安全隐患(非法链接)等。1999年,Chakrabarti等人提出利用挖掘Web上的链接结构来识别权威页面的思想。1999年,Kleinberg等人提出了一个较有影响的称为HITS的算法。HITS算法使用HUB概念,HUB是指一系列的相关某一聚焦点(Focus)的Web页面收集。

(2)Web使用挖掘。Web使用挖掘主要是指对Web上的日志记录的挖掘。Web上的Log日志记录包括URL请求、IP地址以及时间等的访问信息。分析和发现Log日志中蕴藏的规律可以帮助我们识别潜在客户、跟踪服务质量以及侦探非法访问隐患等。发现得最早,对Web Log日志挖掘有较为系统化研究的是Tauscher和Greenberg两位,比较著名的原型系统有Zaiane和Han等研制的Web Log Mining。

(3)Web内容挖掘。实际上Web的链接结构也是Web的重要内容。除了链接信息外,Web的内容主要是包含文本、声音、图片等的文档信息。很显然,这些信息是深入理解站点的页面关联的关键所在。同时,这类挖掘也具有更大的挑战性。Web的内容是丰富的,而且构成成分是复杂的(无结构的、半结构的等),对内容的分析又离不开具体的词句等细节的、语义上的刻画。基于关键词的内容分析技术是研究较早的、最直观的方法,已经在文本挖掘(Text Mining)和Web搜索引擎(Search Engine)等相关领域得到广泛的研究和应用。目前对于Web内容挖掘技术更深入的研究是在页面的文档分类、多层次概念归纳等问题上。(www.xing528.com)

以下是最常用的机器学习算法,大部分数据问题都可以通过它们解决:线性回归(Linear Regression)、逻辑回归(Logistic Regression)、决策树(Decision Tree)、支持向量机(SVM)、朴素贝叶斯(Naive Bayes)、k-邻近算法(k-NN)、k-均值算法(k-Means)、随机森林(Random Forest)、降低维度算法(Dimensionality Reduction Algorithms)和Gradient Boosting和Adaboost算法等。

(1)线性回归。线性回归是利用连续性变量来估计实际数值。通过线性回归算法找出自变量和因变量间的最佳线性关系,图形上可以确定一条最佳直线。这条最佳直线就是回归线。

这个回归关系可以用下式来表示。

Y=aX+b

式中 Y——因变量;

a——斜率;

X——自变量;

b——截距。

(2)逻辑回归。逻辑回归其实是一个分类算法而不是回归算法。通常是利用已知的自变量来预测一个离散型因变量的值(像二进制值0/1、是/否、真/假)。简单来说,它就是通过拟合一个逻辑函数(Logic Function)来预测一个事件发生的概率。所以它预测的是一个概率值,自然,它的输出值应该在0～1。

(3)决策树。它属于监督式学习,常用来解决分类问题。令人惊讶的是,它既可以运用于类别变量(Categorical Variables),也可以运用于连续变量。这个算法可以让我们把一个总体分为两个或多个群组。分组根据能够区分总体的最重要的特征变量/自变量进行。

(4)支持向量机。这是一个分类算法。在这个算法中将每一个数据作为一个点在一个n维空间上作图(n是特征数),每一个特征值就代表对应坐标值的大小。比如有两个特征,即一个人的身高和发长。可以将这两个变量在一个二维空间上作图,图上的每个点都有两个坐标值(这些坐标轴也叫做支持向量)。

(5)朴素贝叶斯。这个算法是建立在贝叶斯理论上的分类方法。它的假设条件是自变量之间相互独立。简言之,朴素贝叶斯假定某一特征的出现与其他特征无关。比如说,如果一个水果是红色的、圆状的,直径大概7cm左右,可能猜测它为苹果。即使这些特征之间存在一定关系,在朴素贝叶斯算法中都认为红色、圆状和直径在判断一个水果是苹果的可能性上是相互独立的。

朴素贝叶斯的模型易于建造,并且在分析大量数据问题时效率很高。虽然模型简单,但很多情况下工作的比非常复杂的分类方法还要好。

贝叶斯理论从先验概率P(c)、P(x)和条件概率P(x|c)中计算后验概率P(c|x)。算法如下。

P(c|x)是已知特征x而分类为c的后验概率。

P(c)是种类c的先验概率。

P(x|c)是种类c具有特征x的可能性。

P(x)是特征x的先验概率。

(6)k-NN(k-邻近算法)。这个算法既可以解决分类问题,也可以用于回归问题,但工业上用于分类的情况更多。k-NN先记录所有已知数据,再利用一个距离函数,找出已知数据中距离未知事件最近的k组数据,最后按照这k组数据里最常见的类别预测该事件。

距离函数可以是欧式距离、曼哈顿距离、闵氏距离(Minkowski Distance)和汉明距离(Hamming Distance)。前3种用于连续变量,汉明距离用于分类变量。如果k=1,那问题就简化为根据最近的数据分类。k值的选取时常是k-NN建模的关键。

(7)k-均值算法。这是一种解决聚类问题的非监督式学习算法。这个方法简单地利用了一定数量的集群(假设k个集群)对给定数据进行分类。同一集群内的数据点是同类的,不同集群的数据点不同类。

k均值算法划分集群的方法如下。

1)从每个集群中选取k个数据点作为质心(Centroids)。

2)将每一个数据点与距离自己最近的质心划分在同一集群,即生成k个新集群。

3)找出新集群的质心,这样就有了新的质心。

4)重复2)和3),直到结果收敛,即不再有新的质心出现。

确定k值的方法如下。

如果在每个集群中计算集群中所有点到质心的距离平方和,再将不同集群的距离平方和相加,就得到了这个集群方案的总平方和。

随着集群数量的增加,总平方和会减少。但是如果用总平方和对k作图,就会发现在某个k值之前总平方和急速减少,但在这个k值之后减少的幅度大大降低,这个值就是最佳的集群数。

(8)随机森林。随机森林是对决策树集合的一个特有名称。随机森林里有多个决策树(所以叫“森林”)。为了给一个新的观察值分类,根据它的特征,每一个决策树都会给出一个分类。随机森林算法选出投票最多的分类作为分类结果。

生成决策树的方法如下。

1)如果训练集中有N种类别,则重复地随机选取N个样本。这些样本将组成培养决策树的训练集。

2)如果有M个特征变量,那么选取数m≪M,从而在每个节点上随机选取m个特征变量来分割该节点。m在整个森林养成中保持不变。

3)每个决策树都最大程度上进行分割,没有剪枝。

(9)降低维度算法。在过去的4～5年里,可获取的数据几乎以指数形式增长。公司、政府机构、研究组织不仅有了更多的数据来源,也获得了更多维度的数据信息。

当数据有非常多的特征时,可建立更强大精准的模型,但它们也是建模中的一大难题。怎样才能从1000或2000个变量里找到最重要的变量呢?这种情况下,降维算法及其他算法,如决策树、随机森林、PCA、因子分析、相关矩阵和缺省值比例等,就能解决难题。

(10)Gradient Boosting和AdaBoost。Gradient Boosting和AdaBoost都是在有大量数据时提高预测准确度的Boosting算法。Boosting是一种集成学习方法。它通过有序结合多个较弱的分类器/估测器的估计结果来提高预测准确度。