数据挖掘算法详解

数据挖掘算法详解数据预处理：数据挖掘技术是面向大型数据集的，而且源数据库中的数据是动态变化的，数据存在噪声、不确定性、信息丢失、信息冗余、数据分布稀疏等问题这就要求我们必须对原始数据进行清洗，尽可能的保证数据的质量。另外，由于挖掘的实际需要，往往需要对原始数据进行一系列的转换和处理，从而得到我们真正需要的数据。此外,在实际情况中，为了提高建模速度，我们可能只需要部分数据参与建模，并指定一些必要的属性。所有这些在建模前对数据的处理操作,我们都称其为”数据预处理”。数据预处理的好坏在很大程度上决定了数据挖掘的质量。结点介绍：本系统提供的数据预处理方法主要有：过滤、抽样、公式、连接、联合、排序、字段过滤、替代规则、类型转换、装箱。过滤：通过对指定字段进行条件限制（大于、小于、等于、类似等条件），从而对数据进行筛选，过滤掉不需要的数据。抽样：通过各种抽样方法（随机抽样、按比例抽样、按指定数据量）抽取一部分数据。公式：公式和参数模型相对应。通过参数模型构造公式,通过公式操作可对由源数据构造新字段。联合：按照指定字段将两张表进行并集操作排序：按照指定字段进行排序操作连接：按照指定字段将两张表进行关联操作替代规则：缺失值处理方法，用某字段的最小值（最大值、均值等）替换该字段中的缺失值，或删除该行或该列。字段过滤：对数据进行汇总操作。类型转换：不同数据类型之间进行转换。主要有数值型转换为字符型，字符型转换为数值型，日期型转换为字符型。装箱：对数据进行离散化。可单独对不同数据类型的字段进行箱操作也可对不同数据类型字段的组合进行装箱操作。统计分析：本系统提供的统计分析方法有：相关分析、归纳分析和波动分析。相关分析：相关性度量是两个变量间线性关系强弱程度的一种测度。如果一个变量X恰好可表示成另一个变量的Y的线性函数，那么相关系数为1或•取1或-1依赖于两个变量是正相关或负相关。如果两变量间的线性相关系数为0，这意味着两变量无线性关系。一组变量之间的相关系数为计算回归及其它统计量提供了重要的信息。本系统提供了三种相关分析方法：线性相关分析、Spearman等级分析、Kendall等级分析。对应的相关系数分别是线性相关系数、Spearman相关系数、Kendall相关系数。线性相关系数：假设有一列数对(xl,yl).(x乙y2)、、(xn,yn)f则其相关系数为：r=(x-)(y-),这个系数是将x的均值和y的均值作为各自数据的中心，再计算x和y到中心的差距。线性相关系数刻画了变量之间线性联系的密切程度。Spearman相关系数:对一列数对(x1,y1)、(x2,y2)、x(xn,yn)f令所有xi在X样本11中的秩为ri,所有yi在Y样本中的秩为si,记r二，i,s二工si则Spearmannni=1i=1相关系数为：rs=I(r■)s(i_)Spearman相关系数是将x秩的均值r和y秩的均值s作为各自数据的中心，再计算X秩和V秩到中心的差距。Spearman相关系数适合研究一般分布的数据总体，且对有异常值的观测数据具有稳健性。Kendall相关系数：是由配对数和不配对数计算关联的测度，公式为：T=sgn(xi-xj)sgn(yi-yj)其中：T0二n(n-1)2,T1=/(t-1)2,T2=(u-1)2,ti,ui分别是X,Y的第i个结(tied,相等的秩)包含的观测值(元素)个数。n是总观测个数，1,当z>OLJsgn(z)二口0,当z二0-1,当z<00归纳分析：计算某字段的一些基本统计量(最小值、最大值、均值、标准差等)波动分析:主要分析目标字段随时间等序列字段的变化而变化的情况。线箱图：两个端边分别是下四分位数、上四分位数，中间两道线分别是中位数和均值，R1=Q3-Q1下截断点Q1-1.5R1,上截断点Q3+1.5R1,弱异常点：Q3+3RQ1-3R1雷达图：数据挖掘算法：重要属性算法：利用属性重要性算法计算各字段同目标字段之间的关联度大小,从而在保证模型准确度的前提下尽可能的指导去除不必要的字段，进而减小建模时的计算量，加快建模速度。最小描述长度方法（MDL）的基本思想：找出一个模型使得模型的算法复杂度以及与该模型相适应的训练数据的描述长度的和最小,是对模型复杂度和模型预测精度的一个折中。MDL倾向于选择最简单的模型。算法设置：抽样：为了提高速度可对数据进行抽样。装箱：即对数据进行离散化。分数值型装箱和字符型装箱。数值装箱有分位数和等间距装箱。设字段取值区间[mimmax],若装箱数为n，即将数据离散化为n个区间段,分位数装箱是指将数据分位n个区间段且每个区间段内的数据数量相等。等间距装箱是数据区间相等如：d=（min,max）/n,l段为：[min,min+d],n段J[min+（n-l）*d/max]o字符型装箱方法:topNf即字段被分为N+1类，出现频率最高的前N个为N类，其它的都归为N+1类。分类预测：分类的目的是构造一个分类函数或分类模型（分类器），该模型能把数据库中的数据项映射到某一个给定类别。分类可用于预测,预测的目的是从历史数据中自动推导出对给定数据的推广性描述，从而能够对未来数据进行预测。本系统提供了四种分类算法，主要是为了适应对不同数据进行分析，有时候同一组数据通过不同的模型的建模结果进行比较,寻找最优模型。其中分类回归树和C45决策树的建模结果都可以用树形展示并产生相应的规则集，可统称为决策树方法。决策树方法是应用最广泛的一种逻辑方法之一，它从一组无序、无规则的事例中推理出决策树表示形式的分类规则。决策树分类方法采用自顶向下的递归方式，在决策树的内部结点进行属性值的匕匕较并根据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结论。所以从决策树的根到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规则。（一般根据信息增益原则建树）决策树算法的一个最大优点是它在学习过程中不需要使用者了解很多背景知识。决策树是一个类似于流程图的数形结构，其中每个结点表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶结点代表类或类分布。数的最顶层是根结点。分类回归树：算法设置：抽样：算法：可设置树的最大深度，当训练数据字段个数、记录条数匕匕较多时，对应的树深度可能比较大，则相应的规则也匕匕较长，有时候有些长规则对分析数据不太重要，因此，可以通过设置树的最大深度对规则进行简化。剪枝：当判定树创建时，由于数据的噪声和孤立点，许多分枝反映的是训练数据中的异常。剪枝方法处理这种过分适应数据问题。通常，这种方法使用统计度量，剪去不可靠的分枝，这将导致较快的分类，提高树独立于测试数据正确分类的能力。分类回归树提供了两种剪枝方法，即叶子节点最小数和叶子节点最小百分比。C45决策树：采用信息增益原则，选择属性对节点进行划分的标准：划分属性应具有最高信自+阻X算法设置：抽样算法：提供了二叉树和多叉树展示方式。对于分类属性多叉树展示更直观减枝：叶子节点最少记录数：叶子节点的记录条数不能少于某个值减少误差法主要是按照簇数进行剪枝，如果簇数设置为3,随机选取2份做训练，用其余的一份数据来修正模型。（一般模型建议拆分为3份）按置信边界剪枝是对置信概率小于设走值的分枝进行剪枝。（分类最理想的情况是将不同属性值的全部分开，即取不同属性值的数据分属于不同的分支,置信概率越小，分支上取其它的值的记录数越少）（采用的是后减枝方法）支撑向量机分类：支撑向量机算法（SVM）是统计学习理论（Statisticallearningtheory,SLT）的一种成功实现，它建立在SLT的VC（Vapnik-chervonenkis）理论和结构风险最小化（StructuralriskminimizationzSRM）原理的基础上z根据有限样本信息在模型的复杂性（即对特定训练样本的学习精度）和学习能力（即无错误的识别任意样本的能力）之间寻求最佳折衷，以期获得更好的泛化能力。为了解决线性不可分问题（不能用直线进行分割的问题厂它采用非线性映射将低维空间的非线性分割问题转化成高维空间的线性分割问题。当支撑向量机算法用于分类问题时，其相应的方法被称为支撑向量机分类（SVMC）。相比通常的分类算法，SVMC不仅能够解决高维问题和非线性分类问题，而且具有极高的预测精度和泛化能力。支撑向量机分类流程，仅以取值为两种可能情况的分类问题为例子。（1）训练集T=((x1,y1),(xI,yI)｝丘(x,y)I,其中xiex=Rn,yie(l,-l),i=1,,I;(2)选择核函数K(x,x')和惩罚参数C,构造并求解最优问题mina1III玄2i=11yiyjaiqjK(xifxj)-Xqjj=ls.t.zi=1yiai=0I*0<ai<0zi=1,,1得最优解a*=(cd；,cd*)T；*(3)选择a的一个小于C的正分量a,并据此计算b二yj■刃iai*K(xi,yj)(4)求得决策函数f(x)二sgnQyiai*K(xifyj)+b*)算法设置:抽样i=1i=1算法：从低维空间向高维空间映射时需要选择映射函数，此映射函数称为核函数。本系统中支撑向量机分类可供选择的核函数有高斯核函数和线性核函数。线性核函数即直接通过线性变换映射到高维空间。高斯核函数：K(x,x')=exp(-x-x')/8)2。一方面，容忍因子越小，复杂因子越大效果越好。另一方面，容忍因子过小或复杂因子过大可能会导致模型的过拟合，从而降低模型的泛化能力。神经网络分类：神经网络近来越来越受到人们的关注，因为它为解决大复杂度问题提供了一种相对来说比较有效的简单方法。神经网络常用于两类问题:分类和回归。下图给出了一种最基本的神经网络结构。在结构上，可以把一个神经网络划分为输入层、输出层和隐含层。输入层的每个节点对应一个预测变量。输出层的节点对应目标变量，可有多个。在输入层和输出层之间是隐含层隐含层的层数和每层节点的个数决定了神经网络的复杂度。分类预测的主要流程分建模、测试、应用。对于训练数据选择分类算法进行建模，通过测试数据对模型进行评估，可根据需要对同一组训练数据选择多个模型进行建模和测试，从而选择最优模型。有时候还有选择验证数据集做应用检验模型对数据的适应性,对新数据做应用用于预测指导实践。测试评估指标：置信概率：预测正确的概率，如果目标字段的某一取值所占的比例为40%z则随机预测正确的概率为40%，而用决策树进行预测的正确概率可能是80%。正项目标值设置：用分类算法进行预测时更倾向于决策出的目标值，如在客户流失中，客户流失有两种取值，即流失和不流失，如果关注的是流失的客户，则将流失设为正项目标值，若关注的是不流失的客户则将正项目标值设为不流失。Lift图和ROC图都是相对于正项目标值讨论的。模型往往需要多个评估指标综合分析。用模型在整个数据集上的准确性来描述模型的性能常常意义不大。以客户响应模型为例，模型是用于发现哪些客户会对产品促销积极响应，那么分析的目标是找出这些客户的特征，并用于在今后的营销活动前锁定目标客户群。假定训练集大小为10万，其中响应的客户数为1万，未响应的客户数为9万。而通过分类建模，模型预测出了1万响应客户中的500人和9万非响应客户中的1000人为响应客户，而其它的都预测为非响应客户。那么模型在整个数据集上的准确性就等于(500+89000)/100000二89.5%。可以很明显地看出虽然准确性很高，但意义不大。因为建模的目的是关注响应客户的预测准确率，那么该指标就等于500/10000二5%。这个指标明显就低多了。最常见的做法是画出命中率（Hitrate）曲线，横坐标为给出的名单大小，纵坐标为在相应名单中响应客户所占的百分比，这条曲线一般是递减的。而且曲线越陡哨，模型的性能就越好，因为你只需给出一份较小的名单，就能让营销活动足够有效（因为抓到了尽可能多的目标客户）。当然，曲线的起点（纵坐标）越高，模型的性能就越好。只是在实践中，不必一味强求命中率一定要达到多少，需要关注的是它对营销活动的意义有多大。因为模型的命中率常常和你能拿到多少数据进行分析、数据的质量如何、数据中蕴含的规律性有多大等等有很大的关系。除了模型的命中率曲线图、召回率曲线图之外，一般还需要提供LIFT图来说明模型的性能。LIFT图和命中率图类似，只是纵坐标要除以基线响应率（即数据集的整体响应率，比如在上面我举的例子中，基线响应率为10000/100000=10%），这个指标就避免了当不同训练集基线响应率不同，单纯用命中率对模型的评估时造成的不公平。如果一个数据集中的基线响应率很高，而另一个数据集中的基线响应率很低，那么我们很容易地想到用前者建立模型时的命中率可能会更高一些，因为一方面响应客户的特征可能更明显，另一方面即便随机抓取名单，前者也会比后者抓到更多的响应客户。Lift图：命中率/基线响应率。命中率二响应名单中响应客户所占的百分比，基线响应率二响应记录/训练数据ROC图：以目标字段只有两种取值的情况为例进行解释，在分类预测中将关注的目标字段取值称为正项目标值，将不关注的目标字段取值称为负项目标值。例如在客户流失分析,决策者关注的是流失的客户，因此可以将流失设为正项目标值，将不流失设为负项目标值。如下混淆矩阵总体正确率二a+da+d+c+ddc+dba+baa+bcc+d正项目标值预测为正项目标值的概率TP二负向目标值预测为正项目标值的概率FP二负向目标值预测为负向目标值的概率TN二正项目标值预测为负向目标值的概率FN二正项目标值预测正确的概率P二应用回归预测：db+d支撑向量机回归：支撑向量机算法（SVM）是统计学习理论(Statisticallearningtheory,SLT)的一种成功实现，它建立在SLT的VC(Vapnik-chervonenkis)理论和结构风险最小化(StructuralriskminimizationzSRM)原理的基础上z根据有限样本信息在模型的复杂性(即对特定训练样本的学习精度)和学习能力(即无错误的识别任意样本的能力)之间寻求最佳折中，以期获得更好的泛化能力。为了解决线性不可分问题(不能用直线进行分割的问题厂它采用非线性映射将低维空间的非线性分割问题转化成高维空间的线性分割问题。当支撑向量机算法用于回归问题时，其相应的方法被称为支撑向量机回归(SVMR)。相比神经网络算法，其不存在局部最优的问题，且有较强的泛化能力。支撑向量机回归流程：(1)T={(x1,y1),(xl,yl)}G(xfy)L其中xiex=Rn,yie(l,-l),i=1,,I;(2)选择适当的正数£和C,选择适当的核函数K(x,x');(3)构造并求解最优问题min*2t1I**jI*iI*aeR(«I2i-ai)(a-ocj)K(xi,xj)+s八(a+ai)-Ayi(ai-ai)i=1i=1I(«i=1*i-ai)=0CI0<ai.ai*<i,=l,2,1*/得到最优解a=(al,al,,al,al)T(5)构造决策函数If(x)二Zi=1a(i-aiK)xi(x,+b)CI)中的aj或ak，若选到的是aj**其中b按下列方式计算：选择位于区间(0,则Ib=yi-》(ai-ai)(xixj)+ei=1**若选到的是akz则Ib=yi_》(ai-ai)x(ixj-)£i=1算法设置：抽样：算法：核函数类型有：线性核函数、多项式核函数、径向基核函数、Sigmoid核函数。其中：线性核函数即直接通过线性变换将数据映射到高维空间；多项式核函数:K(x,x')=((xx')+c)，其中c>0；径向基核函数K(x,x')=exp(-x-x*)/82)；Sigmoid核函数:K(xfx')=tanh(k(x,x')+v),其中k>0fv<0oSigmoid核函数不是正定核函数，但它在某些应用中非常有效。对测试评估指标应用神经网络回归：聚类："人以群分，物以类聚"。聚类就是将数据对象按照一定标准自动聚成两个或多个类或簇,划分的原则是使在同一个簇中的对象之间尽可能具有较小的差异，而在不同簇中的对象尽可能具有较大的差异。与分类不同的是，聚类分析中要划分的类是事先未知的，类的产生完全是数据驱动的，属于无指导学习。聚类是人类一项最基本的认知活动。聚类的用途非常广泛。在基因工程中，利用聚类寻找功能相似的基因；在地理信息系统中，利用聚类分析可以发掘具有相似特征的区域；在服务性行业，聚类分析可以帮助我们发掘特定的客户群，从而指导营销等。本系统提供了两种聚类方法，即OC聚类和EM聚类。OC聚类：OC聚类是一种基于密度的聚类分析方法。绝大多划分是基于对象之间的距离进行聚类，这样的方法只能发现球状的簇，而在发现任意形状的簇上遇到了困难。基于密度聚类的主要思想是：只要临近区域的密度(对象或数据点的数目)超过某个阈值，就继续聚类。即对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数据点。这样的方法可以用来过滤"噪声”孤立点数据，发现任意形状的簇。EM聚类(ExpectationMaximization,期望最大)：EM算法以另一种方式对K-平均方法进行了扩展。它不是把对象分配给一个确定的簇，而是根据对象与簇之间隶属关系发生的概率来分配对象。换句话说，在簇与簇之间没有严格的边界。因此新的平均值基于加权的度量值来计算。关联分析：关联分析反映一个事件和其它事件之间的依赖或关联。数据库中的数据关联是现实世界中事物联系的表现。数据库作为一种结构化的数据组织形式，利用其依附的数据模型可能刻画了数据间的关联(如关系数据库的主键和外键)。但是，数据之间的关联是