10种机器学习算法介绍培训课件(ppt-共68页).pptx

1、机器学习算法介绍基本概念分类监督式学习 多轮学习以达到目的：实现回归或分类非监督式学习 特定方法实现聚类。（由于目的性不明确，所以一般没有多轮）强化学习 不断学习，永无止境分类算法 适用因变量为离散变量回归算法 适用因变量为连续变量聚类和分类的差别聚类：无限种类别可能分类：有限种类别可能监督式学习工作机制这个算法由一个目标变量或结果变量（或因变量）组成。此变量由已知的一系列预示变量（自变量）预测而来。利用这一系列变量，我们生成一个将输入值映射到期望输出值的函数。这个训练过程会一直持续，直到模型在训练数据上获得期望的精确度。例子线性回归，决策树，SVM，K 近邻算法，逻辑回归 等非监督式学习工作

2、机制没有任何目标变量或结果变量要预测或估计。用在不同的组内聚类分析。例子关联算法，K 均值算法强化学习工作机制训练机器进行决策。机器被放在一个能让它通过反复试错来训练自己的环境中。机器从过去的经验中进行学习，并且尝试利用了解最透彻的知识作出精确的判断。例子马尔可夫决策过程十大机器学习算法1、线性回归2、逻辑回归3、决策树4、SVM5、朴素贝叶斯6、k-Means算法7、kNN算法8、Apriori算法9、最大期望算法（EM）10、PageRank监督式学习与非监督式学习的差别监督式学习方法，要求：事先明确知道各个类别的信息 所有待分类项都有一个类别与之对应如果不能满足上述两个条件（例如有海量数

3、据），则需适用聚类算法，即非监督式学习。监督式学习监督式学习非监督式学习非监督式学习线性回归 逻辑回归决策树 朴素贝叶斯SVM KNNK-meansAprioriEMPageRank线性回归适用场景 根据连续变量估计实际数值（房价、呼叫次数、总销售额等）。原理 可通过拟合最佳直线来建立自变量和因变量的关系。拟合结果是条直线 Y=a*X+b：其中Y是因变量，a是斜率，x是自变量，b是截距 最佳直线叫做回归线。系数 a 和 b 通过最小二乘法获得。Python代码from sklearn import linear_modelx_train=input_variables_values_train

4、ing_datasetsy_train=target_variables_values_training_datasetsx_test=input_variables_values_test_datasetslinear=linear_model.LinearRegression()linear.fit(x_train,y_train)linear.score(x_train,y_train)线性回归针对线性回归容易出现欠拟合的问题，采取局部加权线性回归。在该算法中，赋予预测点附近每一个点以一定的权值，在这上面基于波长函数来进行普通的线性回归.可以实现对临近点的精确拟合同时忽略那些距离较远的点

5、的贡献，即近点的权值大，远点的权值小，k为波长参数，控制了权值随距离下降的速度，越大下降的越快。线性回归针对数据的特征比样本点多的问题：一、岭回归二、前向逐步回归逻辑回归#Import Libraryfrom sklearn.linear_model import LogisticRegression#Assumed you have,X(predictor)and Y(target)for training data set and x_test(predictor)of test_dataset#Create logistic regression objectmodel=Logistic

6、Regression()#Train the model using the training sets and check scoremodel.fit(X,y)model.score(X,y)#Predict Outputpredicted=model.predict(x_test)逻辑回归基于最优化方法的最佳回归系数确定：梯度下降法-随机梯度下降法（根据梯度更新权重）牛顿法或拟牛顿法（最大熵模型）决策树使用场景 这个监督式学习算法通常被用于分类问题。它同时适用于分类变量和连续因变量。原理 在这个算法中，我们将总体分成两个或更多的同类群。这是根据最重要的属性或者自变量来分成尽可能不同的组别

7、。回归树预测值为叶节点目标变量的加权均值 分类树某叶节点预测的分类值应是造成错判损失最小的分类值。细说决策树（1）混乱度判断熵 熵：E=sum(-p(I)*log(p(I)，I=1:N（N类结果，如客户是否流失）所有样本都属于一个类别I（最整齐），那么熵为0，如果样本完全随机，那么熵为1 信息增益 信息增益：原样本的熵-sum（区分后的各部分熵），增益越大表示区分的方法越好 Gain(Sample,Action)=E(sample)-sum(|Sample(v)|/Sample*E(Sample(v)除了熵以外，还有GINI不纯度，错误率两种计算混乱度的方法，定义不同但效果类似。细说决策树（2

8、）建构树生成树（1）从根节点t=1开始，从所有可能候选S集合中搜索使不纯性降低最大的划分S；（2）使用划分S将节点1（t=1）划分成两个节点t=2和t=3；（3）在t=2和t=3上分别重复划分搜索过程终止树（1）节点达到完全纯性；（2）树的深度达到用户指定的深度；（3）节点中样本的个数少于用户指定的个数；（4）异质性指标下降的最大幅度小于用户指定的幅度。细说决策树（3）剪枝prune当分类回归树划分得太细时，会对噪声数据产生过拟合作用。因此我们要通过剪枝来解决。剪枝又分为前剪枝和后剪枝：前剪枝：在构造树的过程中就知道那些节点需要减掉，及早的停止树增长。后剪枝：在构造出完整树之后再按照一定方法进

9、行剪枝，方法有：代价复杂性剪枝、最小误差剪枝、悲观误差剪枝等等。决策树代码 def createTree(dataSet,labels):classList=example-1 for example in dataSet#将最后一行的数据放到classList中 if classList.count(classList0)=len(classList):return classList0 if len(dataSet0)=1:#这里为什么是1呢？就是说特征数为1的时候 return majorityCnt(classList)bestFeat=chooseBestFeatureToSplit

10、(dataSet)print(bestFeat)bestFeatLabel=labelsbestFeat#运行结果no surfacing myTree=bestFeatLabel:#运行结果no surfacing:del(labelsbestFeat)featValues=examplebestFeat for example in dataSet#第0个特征值 uniqueVals=set(featValues)for value in uniqueVals:subLabels=labels:myTreebestFeatLabelvalue=createTree(splitDataSet

11、 (dataSet,bestFeat,value),subLabels)return myTree Python代码支持向量机适用场景 这是一种统计分类及回归分析方法算法 支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面，分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。支持向量机支持向量机优缺点优点：(1)非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射；(2)对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核

12、心；(3)支持向量是SVM的训练结果,在SVM分类决策中起决定性作用。因此，模型需要存储空间小，算法鲁棒性（Robust）强。缺点：(1)SVM算法对大规模训练样本难以实施(2)用SVM解决多分类问题存在困难经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。朴素贝叶斯#Import Libraryfrom sklearn.naive_bayes import GaussianNB#Assumed you have,X(predictor)and Y(target)for training data set and x_test(predictor)

13、of test_dataset#Create SVM classification object model=GaussianNB()#there is other distribution for multinomial classes like Bernoulli Naive Bayes,Refer link#Train the model using the training sets and check scoremodel.fit(X,y)#Predict Outputpredicted=model.predict(x_test)朴素贝叶斯算法 对于给出的待分类项，求解在此项出现的条

14、件下各个类别出现的概率，哪个最大，就认为此待分类项属于哪个类别。自变量：x=a1,a2,.,an 因变量：假设我们的结论有True/False两种 根据样本可得到p(a1|T),p(a2|T),.,p(an|T),p(a1|F),p(a2|F),.,p(an|F)我们想比较p(T|x)和p(F|x)，则根据贝叶斯定理：p(T|x)=p(p(x|Tx|T)*p(T)/p(x)=p(a1|T)p(a1|T)*p(a2|T)p(a2|T)*.*p(p(an|Tan|T)*p(T)/p(x)p(T|x)*p(x)=p(p(x|Tx|T)*p(T)=p(a1|T)p(a1|T)*p(a2|T)p(a2|

15、T)*.*p(p(an|Tan|T)*p(T)p(F|x)*p(x)=p(p(x|Fx|F)*p(T)=p(a1|F)p(a1|F)*p(a2|F)p(a2|F)*.*p(p(an|Fan|F)*p(F)由此得出x情况下T的概率和F的概率。KNN（K最邻近算法）适用场景 该算法可用于分类问题和回归问题。然而，在业界内，K最近邻算法更常用于分类问题。原理 K最近邻算法是一个简单的算法。它储存所有的案例，通过周围k个案例中的大多数情况划分新的案例。根据一个距离函数，新案例会被分配到它的 K 个近邻中最普遍的类别中去。这些距离函数可以是欧式距离、曼哈顿距离、明式距离或者是汉明距离。前三个距离函数用于

16、连续函数，第四个函数（汉明函数）则被用于分类变量。KNN（K最邻近算法）实现流程（1）计算已知类别数据集中的点与当前点之间的距离（2）按照距离递增次序排序（3）选取与当前点距离最近的k个点（4）确定前k个点所在类别的出现频率（5）返回前k个点出现频率最高的类别作为当前点的预测分类Python代码#Import Libraryfrom sklearn.neighbors import KNeighborsClassifier#Assumed you have,X(predictor)and Y(target)for training data set and x_test(predictor)o

17、f test_dataset#Create KNeighbors classifier object model KNeighborsClassifier(n_neighbors=6)#default value for n_neighbors is 5#Train the model using the training sets and check scoremodel.fit(X,y)#Predict Outputpredicted=model.predict(x_test)KNN（K最邻近算法）补充说明 KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些

18、邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成反比。K均值算法使用场景 K均值算法是一种非监督式学习算法，它能解决聚类问题。使用 K均值算法来将一个数据归入一定数量的集群（假设有 k 个集群）的过程是简单的。一个集群内的数据点是均匀齐次的，并且异于别的集群。算法 1、从D中随机取k个元素，作为k个簇的各自的中心。2、分别计算剩下的元素到k个簇中心的相异度，将这些元素分别划归到相异度最低的簇。3、根据聚类结果，重新计算k个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均数。4、将D中全部

19、元素按照新的中心重新聚类。5、重复第4步，直到聚类结果不再变化。6、将结果输出。K均值算法如何确定K值 K 均值算法涉及到集群，每个集群有自己的质心。一个集群内的质心和各数据点之间距离的平方和形成了这个集群的平方值之和。同时，当所有集群的平方值之和加起来的时候，就组成了集群方案的平方值之和。我们知道，当集群的数量增加时，所有集群平方和之和会持续下降。但是，如果你将结果用图表来表示，你会看到距离的平方总和快速减少。到某个值 k 之后，减少的速度就大大下降了。在此，我们可以找到集群数量的最优值。工作流程#k-means 聚类算法 def kMeans(dataSet,k,distMeans=dis

20、tEclud,createCent=randCent):m=shape(dataSet)0 clusterAssment=mat(zeros(m,2)centroids=createCent(dataSet,k)clusterChanged=True while clusterChanged:clusterChanged=False;for i in range(m):minDist=inf;minIndex=-1;for j in range(k):distJI=distMeans(centroidsj,:,dataSeti,:)if distJI minDist:minDist=distJ

21、I;minIndex=j if clusterAssmenti,0!=minIndex:clusterChanged=True;clusterAssmenti,:=minIndex,minDist*2 print centroids for cent in range(k):ptsInClust=dataSetnonzero(clusterAssment:,0.A=cent)0 centroidscent,:=mean(ptsInClust,axis=0)return centroids,clusterAssment 创建k个点作为起始质心，可以随机选择(位于数据边界内)当任意一个点的簇分配结

22、果发生改变时 对数据集中的每一个点对每个质心 计算质心与数据点之间的距离将数据点分配到距其最近的簇对每个簇，计算簇中所有点的均值并将均值作为质心 Pyhton代码K-MEANS性能分析优点（1）是解决聚类问题的一种经典算法，简单、快速。（2）当结果簇是密集的，而簇与簇之间区别明显时,它的效果较好。缺点（1）在簇的平均值被定义的情况下才能使用，这对于处理符号属性的数据不适用。（2）要求用户必须事先给出要生成的簇的数目k。（3）对初值敏感，对于不同的初始值，可能会导致不同的聚类结果。（4）不适合于发现非凸面形状的簇，或者大小差别很大的簇。（5）对于噪声和孤立点数据敏感，少量的该类数据能够对平均值产

23、生极大影响。K-MEANS性能分析改进：（1）对于离群点和孤立点敏感：离群点检测的LOF算法，通过去除离群点后再聚类，可以减少离群点和孤立点对于聚类效果的影响。（2）k值选择：开始设定k值，每跑一次K-means，根据k个聚类的距离情况，合并距离最近的类，不断重复，最终得到合适数目的聚类数。可以通过一个评判值E来确定聚类数得到一个合适的位置停下来，而不继续合并聚类中心。（3）初始聚类中心的选择：选择批次距离尽可能远的K个点（首先随机选择一个点作为第一个初始类簇中心点，然后选择距离该点最远的那个点作为第二个初始类簇中心点，然后再选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点，以此类

24、推，直至选出K个初始类簇中心点。）（4）只能发现球状簇：如果数据集中有不规则的数据，往往通过基于密度的聚类算法更加适合，比如DESCAN算法K-MEANS补充相异度 相异度就是两个东西差别有多大（例如用什么来说明人类与章鱼的相异度明显大于人类与黑猩猩的相异度）欧式距离，曼哈顿距离，闵科夫斯基距离什么叫聚类 所谓聚类问题，就是给定一个元素集合D，其中每个元素具有n个可观察属性，使用某种算法将D划分成k个子集，要求每个子集内部的元素之间相异度尽可能低，而不同子集的元素相异度尽可能高。其中每个子集叫做一个簇。AdaBoost算法原理（1）针对同一个训练集训练不同的分类器（弱分类器），然后把这些弱分类

25、器集合起来，构成一个更强的最终分类器（强分类器）。（2）算法本身是通过改变数据分布来实现的，根据每次训练集中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。（3）将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器融合起来，作为最终的决策分类器Python代码#Import Libraryfrom sklearn.ensemble import GradientBoostingClassifier#Assumed you have,X(predictor)and Y(target)for training data set and x_test(p

26、redictor)of test_dataset#Create Gradient Boosting Classifier objectmodel=GradientBoostingClassifier(n_estimators=100,learning_rate=1.0,max_depth=1,random_state=0)model.fit(X,y)predicted=model.predict(x_test)AdaBoost工作流程：将最小错误率minError设为无穷大对数据集中的每一个特征（第一层循环）：对每个步长（第二层循环）：对每个不等号（第三层循环）：建立一棵单层决策树并利用加权数

27、据集进行测试 如果错误率低于minError，将当前单层决策树设为最佳单层决策树返回最佳单层决策树构建弱分类器对每次迭代：找到最佳的单层决策树 将最佳单层决策树加入到单层决策树数组 计算alpha,计算新的权重向量D 更新累计类别估计值 如果错误率小于minError，则退出循环构建强分类器优点：（1）AdaBoost是一种有很高精度的分类器（2）可以使用各种方法构建弱分类器（3）弱分类器构造特别简单，不用做特征筛选（4）不会过拟合缺点：（1）执行效果依赖于弱分类器的选择，迭代次数和 弱分类器的数目不太好设定（2）训练时间过长（3）容易受到噪声干扰，数据不平衡导致分类精度下降。Apriori原

28、理（1）寻找所有不低于最小支持度的项集（频繁项集）；（2）使用频繁项集生成规则。PS：支持度：数据集中包含该项集的记录所占的比例；频繁项集：支持度大于最小支持度的项集。对数据集中的每条交易记录tran和每个候选项集can：检查一下can是否是tran的子集：如果是，则增加can的计数值 对每个候选项集：如果其支持度不低于最小值，则保留该项集返回所有频繁项集列表生成候选项集工作流程发现关联规则当集合中项的个数大于0时：构建一个k个项组成的候选项集的列表 检查数据以确认每个项集都是频繁的 保留频繁项集并构建k+1项组成的候选项集的列表强化学习-马尔科夫决策过程原理 系统的下个状态不仅和当前的状态有

29、关，也和当前采取的动作有关，而与更早之前的状态和动作无关。定义：马尔科夫决策流程：一个马尔科夫决策过程由一个五元组构成（S,A,Psa,R）马尔科夫决策模型已经处于某个状态s时，我们会以一定的策略来选择下一个动作a执行，然后转换到另一个状态ss。我们将这个动作的选择过程称为策略(policy)每一个policy起始就是一个状态到动作的映射函数:SA。给定也就是给定了a=(s),也就是说，知道了就知道了每个状态下一步应该执行的动作。数据挖掘以对消费者的建模为例，举一些场景下的常用算法对应：划分消费者群体：聚类，分类；购物篮分析：相关，聚类；购买额预测：回归，时间序列；满意度调查：回归，聚类，分类

30、；数据挖掘主要模型：分类、聚类、预测及关联数据挖掘主要模型：分类、聚类、预测及关联一、非线性拟合二、货运量预测目标：预测货运量方法：基于广义回归神经网络（GRNN）输入量：根据货运量影响因素的分析，分别取GDP、工业总产值、铁路运输线路长度、复线里程比重、公路运输线路长度、等级公路比重、铁路货车数量和民用载货汽车数量8项指标因素作为网络输入输出量：以货运总量、铁路货运量和公路货运量3项指标因素作为网络输出。二、货运量预测结果：GRNN神经网络三项流量预测的误差为16342.6947 6360.723 16945.2494三、财政收入影响因素与预测模型目标：预测未来财政收入方法：Adaptive

31、-Lasso、神经网络 (1)获取某市财政收入以及各类收入相关数据 (2)完成数据预处理，建立Adaptive-Lasso变量选择模型 (3)建立人工神经网络预测模型 (4)将得到的预测值代入构建好的人工神经网络模型中，从而得到财政收入以及各类别收入的预测值。输入值：社会从业人数（x1），在岗职工工资总额（x2），社会消费品零售总额（x3），城镇居民人均可支配收入（x4），城镇居民人均消费性支出（x5），年末总人口（x6），全社会固定资产投资额（x7），地区生产总值（x8），第一产业产值（x9），税收（x10），居民消费价格指数（x11），第三产业与第二产业产值比（x12），居民消费水平（x1

32、3）。输出值：财政收入总值三、财政收入影响因素与预测模型三、财政收入影响因素与预测模型1、Adaptive-Lasso变量选择模型 通过相关系数，将无关变量从输入值中删除，综上所述，影响财政收入的关键因素是社会从业人数、在岗职工工资、社会消费品零售总额、城镇居民人均可支配收入、城镇居民人均消费性支出以及全社会固定资产投资额。将输入值和输出值分为训练集和测试集，代入三层的 BP神经网络，预测未来的财政收入。三、财政收入影响因素与预测模型四、时间序列预测法交通流量预测概念：时间序列预测法就是通过编制和分析时间序列，根据时间序列所反映出来的发展过程、方向和趋势，进行类推或延伸，借以预测下一段时间或以

33、后若干年内可能达到的水平。其内容包括：收集与整理某种社会现象的历史资料；对这些资料进行检查鉴别，排成数列；分析时间数列，从中寻找该社会现象随时间变化而变化的规律，得出一定的模式；以此模式去预测该社会现象将来的情况。常用时间序列预测问题，比较常用的方法包括：多元线性回归预测、AR模型预测、ARMA模型预测、指数平滑预测、小波神经网络、RNN等四、时间序列预测法交通流量预测步骤：（1）采集4天的交通流浪数据，每隔15分钟记录一次，一共记录384个时间点的数据 （2）用3天共288个数据训练小波神经网络 （3）用训练好的小波神经网络预测第4天的交通流量。一、数据探索 数据质量分析 数据质量分析的主要

34、任务是检查原始数据中是否存在脏数据，脏数据一般是指不符合要求，以及不能直接进行相应分析的数据，主要包括：缺失值，异常值，重复数据及含有特殊符号（如#、￥、%）的数据等。（1）缺失值分析 数据的缺失主要包括记录的缺失和记录中某个字段信息的缺失 原因：数据无法获取；数据遗漏；属性值不存在 影响：丢失信息；增加不确定性，难把握规律；分析：使用简单的统计分析，可以得到含有缺失值的属性的个数，以及每个属性的未缺失数、缺失率等一、数据探索二、数据预处理 数据预处理的主要内容包括数据清洗、数据集成、数据变换和数据规约。数据预处理一方面是要提高数据的质量，另一方面是要让数据更好地适应特定的挖掘技术或工具。2.

35、1 数据清洗 数据清洗主要是删除原始数据集中的无关数据、重复数据，平滑噪声数据，筛选掉与挖掘主题无关的数据，处理缺失值、异常值等。清洗内容主要包括:缺失数据处理、相似重复对象检测、异常数据处理、逻辑错误检测和不一致数据等二、数据预处理（1）缺失数据处理 处理缺失值的方法可以分为3类：删除记录、数据插补和不处理。（1）删除数据：主要针对缺失值数量较少、且删除数据对整体数据几乎没有影响；也可以根据数据缺失挖掘信息.文献1利用5组医疗数据集测试了缺失数据对于病情阳性概率的影响，以及对分类结果精确度的影响，并通过knn、判别分析和朴素贝叶斯3种方法在数据缺失不同比例的情况下，对分类结果进行了分析比较；

36、（2）数据插补：属性间的关联性在缺失值估计过程中非常重要，在数据挖掘方法中，关键是挖掘属性间的关系。数据插补的目的在于估计正确的替代值。文献2提出了基于不完备数据聚类的缺失数据填补方法，针对分类变量不完备数据集定义约束容差集合差异度，从集合的角度判断不完备数据对象的总体相异程度，并以不完备数据聚类的结果对基础进行缺失数据的填补。文献3提出一种基于进化算法的自适应聚类方法,该方法的基本思想是将聚类问题转化成一个全局优化问题,利用聚类方法填充缺失值。文献4针对缺失数据问题，提出了多元回归方法，弥补一元回归方法的不足。1 Juhola M,Laurikkala J.Missing values:ho

37、w many can they be to preserve classification reliability J/OL.Artificial Intelligence Review,2011.(2011-08-01)2012-12-28.2武森,冯小东,单志广.基于不完备数据聚类的缺失数据填补方法J.计算机学报,2012,35(8):1726-1738.3 Silva J A,Hruschka E R.An evolutionary algorithm for missing values substitution in classification tasksC Proceedings

38、 of the HAIS09.Salamanca:Springer,2009:195-202.4 Zhang Shichao,Jin Zhi,Zhu Xiaofeng,et al.Missing data analysis:a kernel-based multi-imputation ap-proachCProceedings of Transactions on Comput-ational Science III.Berlin,Heidelberg:Springer,2009:122-142.(2)相似重复对象检测 文献5：邻近排序算法(SNM)是重复记录检测的常用方法，该方法基于排序比

39、较的思想 文献6：多趟排序；文献7：优先队列排序 文献8：提出了基于N-gram的重复记录检测方法,并给出了改进的优先权队列算法以准确地 聚类相似重复记录。文献9：用依赖图的概念,计算数据表中的关键属性,根据关键属性值将记录集划分为小记录集,在每个小记录集中进行相似重复记录检测。文献10：针对非结构化数据的重复检测，介绍了复杂数据实体识别的概念和应用,分别就XML数据、图数据和复杂网络上实体识别技术进行了讨论。5张建中,方 正,熊 拥 军,等.对 基 于 S N M数 据 清 洗 算 法 的 优 化 J .中 南 大 学 学 报:自 然 科 学版,2010,41(6):2240-2245.6M

40、onge A E,Elkan C P.Efficient domain-independentdetection of approximately duplicate database recordsC Proceedings of the ACM-SIGMOD Workshop on Research Issues in Knowledge Discovery and Data Mining.Tucson,Arizona:s.n.1997.7Hernndez M A,Stolfo S J.Real-world data is dirty:data cleansing and the merg

41、e/purge problemJ.Data Mining and Knowledge Discovery,1998,2(1):9-37.8邱越峰,田增平,季文,等.一种高效的检测相似重复记录的方法J.计算机学报,2001,24(1):69-77.9庞雄文,姚占林,李拥军.大数据量的高效重复记录检测方法J.华中科技大学学报:自然科学版,2010,38(2):8-11.10王宏志,樊文飞.复杂数据上的实体识别技术研究J.计算机学报,2011,34(10):1843-1852.二、数据预处理补充：基于N-gram的重复记录检测方法：给每个记录赋一个N-gram值,以该值为键来对数据中的记录进行排序。

42、在一赋值时必须尽可能地使相似程度越高的记录的一价帅值越接近,以保证通过对值排序之后它们将被聚 到邻近的区域。所谓记录的田值是根据记录的内容并参照全局统计信息而计算出的一个表示记录特征的整数值。基本近邻排序算法(SNM)：（1）创建排序关键字；（2）排序，尽可能的使潜在的可能的重复记录调整到一个邻近的区域内；（3）合并，在排序后的数据集上滑动一个固定大小的窗口,重复比较，将数据合并。二、数据预处理(3)异常数据处理 异常数据的探测主要有基于统计学、基于距离和基于偏离3类方法。文献11：采用数据审计的方法实现异常数据的自动化检测，称为数据质量挖掘，由2步构成：(1)采用数理统计方法对数据分布进行概

43、化描述,自动获得数据的总体分布特征;(2)针对特定的数据质量问题进行挖掘以发现数据异常。文献12:将数据按距离划分为不同的层,在每一层统计数据特征,再根据定义的距离计算各数据点和中心距离的远近来判断异常是否存在。（聚类）文献13：基于关联方法，将置信度和支持度很低的点视为异常点。11 Hipp J,Guntzer U,Grimmer U.Data quality mining:making a virtue of necessity C Proceedings of Workshop on Research Issues in Data Mining and Knowledge Discove

44、ry.Santa Barbara:s.n.,2001.12 Dasu T,Johnson T.Hunting of the snark:finding data glitches using data mining methods C Proceedings of the 1999 Conference of Information Quality.Cam-bridge:s.n.,1999.13 Kimball,R.Dealing with dirty Data.DBMS,vol.9,NO.10,September 1996,pp.55二、数据预处理(3)异常数据处理 在很多情况下，要先分析异

45、常值出现的可能原因，再判断异常值是否应该舍弃，如果是正确的数据，可以直接在具有异常值的数据集上进行挖掘建模。二、数据预处理2.2 数据集成 数据挖掘需要的数据往往分布在不同的数据源中，数据集成就是将多个数据源合并存放在一个一致的数据存储（如数据库）中的过程。（1）实体识别实体识别是指从不同数据源识别出现实世界的实体，任务是统一不同数据源的矛盾之处，例如：同名异义；异名同义；单位不统一。（2）冗余属性识别数据集成往往导致数据冗余，例如：同一属性多次出现；同一属性命名不一致导致重复。仔细整合不同源数据能减少甚至避免数据冗余与不一致，对于冗余属性要先分析，检测到后再将其删除。二、数据预处理2.2 数

46、据集成 目前,常用的消除数据不一致的方法有排序、融合和基于规则3种方法。文献14：使用了邻近排序的方法,根据定义的关键码对数据集进行排序,使可匹配的记录在位置上临近,并检测数据中的不一致。文献15：从不同的特征评估每个数值,通过线性组合各特征值得到整体评估值,再根据评估值确定正确值。14 Hernndez M A,Stolfo S J.Real-world data is dirty:data cleansing and the merge/purge problemJ.Data Mining and Knowledge Discovery,1998,2(1):9-37.15 Morto A,

47、Anokhin P,Acar A C.Utility-based resolu-tion of data inconsistencies C Proceedings of the 2004 International Workshop on Information Quality in Information Systems.New York:ACM,2004:35-43.二、数据预处理2.3 数据变换（1）简单函数变换简单函数变换是对原始数据进行某些数据函数变换，常用的变换包括平方、开方、取对数、差分运算等。简单的函数变换常用来将不具有正态分布的数据变换成具有正态分布的数据。在时间序列分析中

48、，有时简单的对数变换或者差分运算就可以将非平稳序列转换成平稳序列。比如个人年收入的取值范围为10000元到10亿元，这是一个很大的区间，使用对数变换对其进行压缩是常用的一种变换处理方法。二、数据预处理二、数据预处理（3）连续属性离散化 一些数据挖掘算法，特别是某些分类算法，要求数据是分类属性形式。这样，常常需要将连续属性变换成分类属性，即连续属性离散化。连续属性的离散化就是在数据的取值范围内设定若干个离散的划分点，将取值范围划分为一些离散化的区间，最后用不同的符号或者整数值代表落在每个子区间中的数据值。常用的离散化法有等宽法、等频法和聚类。等宽法：将属性的值域分成具有相同宽度的区间等频法：将相

49、同数量的记录放进每个区间聚类分析：将连续属性的值用聚类算法进行聚类，然后再将聚类得到的簇进行处理，合并到一个簇的连续属性值并做同一标记。二、数据预处理（4）小波变换 小波变换具有多分辨率的特点，在时域和频域都具有表征信号局部特征的能力，通过伸缩和平移等运算过程对信号进行多尺度聚焦分析，提供了一种非平稳信号的时频分析手段，可以由粗及细地逐步观察信号，从中提取有用信息。小波变换可以把非平稳信号分解为表达不同层次、不同频带信息的数据序列，及小波系数。选取适当的小波系数，即完成了信号的特征提取。二、数据预处理2.4 数据规约 数据规约产生更小但保持原数据完整性的新数据集，数据规约的意义在于：降低无效、

50、错误数据对建模的影响，提高建模的准确性；少量且具代表性的数据将大幅缩减数据挖掘所需的时间；降低储存数据的成本。（1）属性规约 属性规约的目标是通过合并、删除属性维数等方法寻找出最小的属性子集并确保新数据子集的概率分布尽可能地接近原来数据集的概率分布。属性规约常用方法：合并属性、逐步向前选择、逐步向后删除、决策树归纳、主成分分析。二、数据预处理（2）数值规约 数值规约指通过选择替代的、较小的数据来减少数据量，包括有参方法和无参方法两类。有参方法是使用一个模型来评估数据，只需存放参数，而不需要存放实际数据，例如回归和对数线性模型。无参数方法就需要存放实际数据，例如直方图、聚类、抽样（采样）。聚类：