数据挖掘理论与方法

2.3.1　数据挖掘理论

数据挖掘诞生于1995年在加拿大首次召开的国际知识发现与数据挖掘学术会议［95］。数据挖掘虽然年轻且历史较短,但其发展极为迅速。数据挖掘最为常用和普遍接受的定义是:从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中的、人们事先不知道的、潜在有用的信息和知识的过程［58］。数据挖掘是可以针对大量业务数据进行抽取、转换和分析处理,从中挖掘出有价值的、隐含的、潜在的商业机遇［96］。目前数据挖掘应用在各行各业,如医疗、金融、物流、电子商务、互联网、物联网、智能交通、风险管理等。

数据挖掘是一门综合模式识别、数据库、机器学习、统计学、商业分析和人工智能等众多学科领域的新兴交叉学科,近年来发展十分迅速,并且引起了学术界、工业界及商界的广泛关注［97］。经过二十多年的研究和发展,数据挖掘领域产生了许多模型,其中以C4．5决策树、K－Means聚类、SVM支持向量机、Apriori关联规则挖掘方法、EM聚类方法、PageRank网页排名方法、AdaBoost迭代方法、k最近邻分类方法、NaiveBayes朴素贝叶斯方法和CART方法最为经典。这些经典的方法最终是在2006年ICDM的国际会议上,由145名与会者以公开投票的方式选出的十大经典方法［8］。

数据挖掘任务可分为描述和预测两大类［58］。描述性数据挖掘任务主要是描述和刻画数据库中数据的一般特性,如概念/类描述;预测性数据挖掘任务则是对将来的趋势和行为作出预测,如分类预测［58］。数据挖掘的六大任务简单介绍如下:

(1)概念/类描述:用概括性的、精练的方式对目标数据描述其相应的类和概念,其目的是对数据进行更好的浓缩,实现对目标数据的整体把握。

(2)关联规则:数据库中的数据之间可能存在某种潜在规律,关联规则挖掘则是找出数据库中数据间隐含的相互关联关系,探索其潜在的规律模式或兴趣。

(3)分类:各种分类方法从不同的角度对训练数据集(已标注了类别的数据)进行分析,找出训练数据集中存在的普遍规律,经过验证后将其用来对具有类似数据结构的未知数据的类别进行预测。

(4)聚类分析:在无监督学习的情况下,聚类不考虑类标号,将目标数据划分为类或簇,使得类或簇内部的相似性最大化,而类或簇间的相似性最小化。

(5)孤立点分析:与数据的一般行为或模型不一致的孤立点易被视为噪声而丢弃,但在某些特殊问题中,如发现金融欺诈行为,孤立点分析则尤为重要。

(6)演变分析:演变分析是用来描述和发现行为随时间变化的对象的演变规律或发展趋势,并且对其建模。

2.3.2　数据挖掘方法

数据挖掘经过二十多年的研究和发展,已经产生了许多方法和模型。在数据挖掘的六大任务类型中,最典型、最热点的还属聚类和分类。本小节主要介绍聚类方法和分类方法。

2．3．2．1　聚类方法

聚类是一种无监督学习技术,不需要先验知识,根据数据对象之间的相似性对数据进行分区。聚类方法可以处理各种类型的海量数据,以发现其隐藏的模式、未知的相关关系以及其他潜在有用的信息。现有的聚类方法已有近百种,可以把聚类方法分为通用聚类方法和特殊聚类方法。通用聚类方法可以分为参数的方法和非参数的方法。参数的方法试图去最小化一个代价函数或优化标准。非参数的方法即是基于数据相识度或者距离的方法。特殊聚类方法包括一些特殊数据情况和特殊要求下的聚类方法［98］。大体上,主要的聚类方法可以分为以下几类:基于划分的聚类方法、基于层次的聚类方法、基于密度的聚类方法、基于网格的聚类方法、基于模型的聚类方法［99］。

1)基于层次的聚类方法

基于层次的聚类方法对给定的数据对象进行层次的分解。按照层次的形成方式,层次方法可以分为凝聚法和分裂法。凝聚法是建立在聚类间距离尺度的基础上的,最初把每个数据对象看成单独的组,然后把最邻近的组或对象合并、融合起来,重复直到最终只有一个或满足某个终止条件结束。分裂法与凝聚法相反,它首先将所有对象置于一个簇中,每次迭代,逐渐划分为越来越小的簇,直到最终每个对象自成一簇,或者达到某个终止条件结束。分裂的方法也有两种类型,即单分裂和多分裂。单分裂是指每次用数据的一个属性来分裂聚类,而多分裂的方法是对全部属性综合进行分析来分裂数据［98,100］。

2)基于划分的聚类方法

对于一个给定的具有n个数据对象的数据集,通常构建数据的k个划分,每个划分为一组,k≤n,同时满足以下两个条件:每个类中至少包含一个数据对象和每个数据对象必须属于且只属于一个类。在某些模糊聚类、可能性聚类中,后者可以放宽要求。划分的方法是一种参数的方法,其目的是将数据分为不同的子类。一般采用贪心启发式方法,最小化某个优化函数,通过迭代最终获取符合要求的划分。典型的划分聚类方法是k均值聚类方法［99,101］。

3)基于密度的聚类方法

基于密度的聚类方法,其思想是只要临近区域的密度超过某个阈值就继续聚类。也就是说,对给定类中的每个数据点,在一个给定范围的区域中必须至少包含某个数目的点。这类方法能克服基于距离的方法只能发现类圆形聚类的缺点,可发现任意形状的聚类,且对噪声数据不敏感。但其计算复杂度大,需要建立空间索引来降低计算量,且对数据维数的伸缩性较差［99,102］。

4)基于网格的聚类方法

基于网格的聚类方法,首先将样本所在的几何空间进行切割,形成不同粒度的网格。然后根据每个网格中样本的数量对数据进行划分聚类。由于网格化的方法并不是直接对数据对象做处理,而是采用了一个多分辨率的网格数据结构。它的计算复杂度和处理时间独立于样本对象的记录数目,只与量化空间中每一维度的单元数目有关［98,103］。

5)基于模型的聚类方法

基于模型的聚类方法为每个类假定了一个模型,认为数据是根据潜在的概率分布产生的,主要方法是寻找数据对给定模型的最佳拟合。在此基础上,基于模型的聚类方法致力于寻找特定的数学模型,使得这一模型能够拟合数据潜在的规律。基于模型的聚类通过构建反映数据点空间分布的密度函数来定位簇,主要包括基于统计学习的聚类和基于神经网络的聚类。它能够考虑“噪声”数据和离群点的影响,从而产生鲁棒的聚类方法［99,104］。

2．3．2．2　分类方法

所谓分类,是一种有监督学习方法,以待分析的目标问题为背景,采用一部分样本数据建立一个关于类别属性划分的分类方法,并利用该模型对同类问题中类别标记未知的样本进行学习和判断的过程。分类是一个两步过程:第一步,根据训练数据,建立分类函数或分类器。这是训练阶段,也叫学习步,是通过对数据分析或者从样本训练集“学习”中完成。训练集是由数据库元组以及相关联的类标号共同构成的。第二步,使用分类方法对数据进行分类。在使用分类方法之前,需要评估该分类器的预测准确率,在测试集上完成。该测试集是由检验元组和相关联的类标号组成的。目前已有许多种分类方法,具有一套完整的分类方法库,主要可分为以下几类:基于贝叶斯技术的分类方法、决策树分类方法、支持向量机分类方法、基于最近邻分类方法、神经网络分类方法等［99］。

1)基于贝叶斯技术的分类方法

贝叶斯分类是一种基于统计学的分类方法,可以预测一个类成员关系的可能性,即给定样本属于一个特定类的概率。数据挖掘领域主要使用两种贝叶斯方法,即朴素贝叶斯方法和贝叶斯网络方法。朴素贝叶斯方法使用贝叶斯公式进行预测,把从训练样本中计算出的各个属性值与类别频率之比作为先验概率,并假定各个属性之间是相互独立的,然后利用贝叶斯公式及有关概率公式计算各实例的条件概率值,并选取其中概率值最大的类别作为预测值。此方法简单易行且精度较好。贝叶斯网络也叫贝叶斯信念网络,是一个带有概率注释的有向无环图,图中的每一个节点均表示一个随机变量,两节点间若存在着一条弧,则表示这两节点相对应的随机变量是概率相依的,反之则说明这两个随机变量是条件独立的。事实上,贝叶斯网络也是一种适合表示不确定性知识的方法［99,105］。

2)决策树分类方法

决策树分类方法是数据挖掘领域研究分类问题最常采用的方法,其原因归纳为以下三点:一是决策树构造的分类器易于理解;二是采用决策树分类,其速度快于其他分类方法;三是采用决策树分类方法得到的分类准确性通常优于其他方法［106］。绝大多数决策树分类方法分两步:第一步是树的生成,根据给定数据集进行建树,主要是对原数据源进行机器学习。第二步是根据建立好的决策树对数据进行分类学习。对于未知数据的样本,从决策树的根节点开始扫描,依次测试样本的属性值,直到到达对应的叶节点,那么数据所属于的类就是该叶节点代表的类。在数据量较大时,决策树方法能较快地构造出分类器:其树型结构可以很方便地转化为SQL语言形式,以便用来更有效地访问数据库［99,106,107］。

3)支持向量机分类方法

支持向量机是Vapnik在20世纪90年代中期提出来的一种分类方法,使用一种非线性映射,将原训练数据映射到较高的维,在新的维度上,搜索线性最佳分离超平面。支持向量机脱离了传统方法中降维的定式,建立在计算学习理论的结构风险最小化的原则之上,利用反转技术有目的地增加问题空间的维数,使得分类问题变得相对容易,也可以提高学习机的泛化能力。支持向量机的复杂度与实例集的维数无关,适合于两分类问题和线性不可分问题,因为它可将样本空间映射到一个高维空间,使原来线性不可分的情况在高维空间中得到解决。支持向量机可以用来分类和预测,且在很多领域得到广泛应用,如对象识别、语音识别、基准时间序列预测检验等［99,108,109］。

4)基于最近邻分类方法

基于最近邻分类方法的分类思想是:如果在一个样本的属性空间里,与这个样本相似的k个样本都属于同一个类,则这个样本也一定属于这个类。该方法仅使用与待分类样本最相似的样本所属的类别来判断待分类样本。k最近邻分类方法是基于类比学习,通过给定的检验元组与和它相似的训练元组进行比较来学习的。为了克服最近邻法错判率较高的缺陷,k最近邻分类方法不是仅选取一个最近邻进行分类,而是选取k个近邻,然后检查它们的类别,并归入比重最大的那一类。此外,由于k最近邻分类方法主要依据附近有限的样本,并不是依据类域的判断来确定样本所在类别的,故对于样本类域的交叉或重叠较多的待分样本集来说,k最近邻分类方法较其他方法更为适合［99,110］。

5)神经网络分类方法

神经网络是一组连接的输入输出单元,其中每个连接都与一个权重相关联,在学习阶段,通过调整这些权重,能够预测输入元组的正确类标号。由于单元之间的连接,神经网络学习又可称为连接着学习。神经网络可分为4种类型,即前向型、反馈型、随机型和自组织型。前向神经网络是数据挖掘中广为应用的一类网络,其原理和方法也是其他一些网络的基础。神经网络具有对噪声数据的承受能力,尤其是它对未经训练的数据具有很好的分类能力［99,106,111］。