数据挖掘之经典算法
1 决策树算法
机器学习中，决策树是一个预测模型；它代表的是对象属性值与对象值之间的一种映射关系。树中每个节点表示某个对象，每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应具有上述属性值的子对象。决策树仅有单一输出；若需要多个输出，可以建立独立的决策树以处理不同输出。
从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。
决策树学习也是数据挖掘中一个普通的方法。在这里，每个决策树都表述了一种树型结构，它由它的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。当不能再进行分割或一个单独的类可以被应用于某一分支时，递归过程就完成了。另外，随机森林分类器将许多决策树结合起来以提升分类的正确率。
决策树同时也可以依靠计算条件概率来构造。决策树如果依靠数学的计算方法可以取得更加理想的效果。
1.1 决策树的工作原理
决策树一般都是自上而下的来生成的。
选择分割的方法有多种，但是目的都是一致的，即对目标类尝试进行最佳的分割。
从根节点到叶子节点都有一条路径，这条路径就是一条“规则”。
决策树可以是二叉的，也可以是多叉的。
对每个节点的衡量：
1) 通过该节点的记录数；
2) 如果是叶子节点的话，分类的路径；
3) 对叶子节点正确分类的比例。
有些规则的效果可以比其他的一些规则要好。
1.2 ID3算法
1.2.1 概念提取算法CLS
1) 初始化参数C={E}，E包括所有的例子，为根；
2) 如果C中的任一元素e同属于同一个决策类则创建一个叶子节点YES终止；否则依启发式标准，选择特征F i={V1, V2, V3,……, V n}并创建判定节点，划分C为互不相交的N个集合C1，C2，C3，……，C n；
3) 对任一个C i递归。
1.2.2 ID3算法
1) 随机选择C的一个子集W (窗口)；
2) 调用CLS生成W的分类树DT(强调的启发式标准在后)；
3) 顺序扫描C搜集DT的意外(即由DT无法确定的例子)；
4) 组合W与已发现的意外，形成新的W；
5) 重复2)到4)，直到无例外为止。
启发式标准：
只跟本身与其子树有关，采取信息理论用熵来量度。
熵是选择事件时选择自由度的量度，其计算方法为：P=freq(C j,S)/|S|；INFO(S)=-SUM(P*LOG(P))；SUM()函数是求j从1到n的和。Gain(X)=Info(X)-Infox(X)；Infox(X)=SUM( (|T i|/|T|)*Info(X)；
为保证生成的决策树最小，ID3算法在生成子树时，选取使生成的子树的熵(即Gain(S))最小的特征来生成子树。
ID3算法对数据的要求：
1) 所有属性必须为离散量；
2) 所有的训练例的所有属性必须有一个明确的值；
3) 相同的因素必须得到相同的结论且训练例必须唯一。
1.3 C4.5算法
由于ID3算法在实际应用中存在一些问题，于是Quilan提出了C4.5算法，严格上说C4.5只能是ID3的一个改进算法。
C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：
1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；
2) 在树构造过程中进行剪枝；
3) 能够完成对连续属性的离散化处理；
4) 能够对不完整数据进行处理。
C4.5算法有如下优点：
产生的分类规则易于理解，准确率较高。
C4.5算法有如下缺点：
在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。
分类决策树算法：
C4.5算法是机器学习算法中的一种分类决策树算法，其核心算法是ID3算法。
分类决策树算法是从大量事例中进行提取分类规则的自上而下的决策树。
决策树的各部分是：
根：学习的事例集；
枝：分类的判定条件；
叶：分好的各个类。
1.3.1 C4.5对ID3算法的改进
1) 熵的改进，加上了子树的信息。
Split_Infox(X)= -SUM( (|T|/|T i|)*LOG(|T i|/|T|))；
Gain ratio(X)= Gain(X)/Split_Infox(X);
2) 在输入数据上的改进
①因素属性的值可以是连续量，C4.5对其排序并分成不同的集合后按照ID3算法当作离散量进行处理，但结论属性的值必须是离散值。
②训练例的因素属性值可以是不确定的，以?表示，但结论必须是确定的。
3) 对已生成的决策树进行裁剪，减小生成树的规模。
2 The k-means algorithm（k平均算法）
k-means algorithm是一个聚类算法，把n个对象根据它们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。
假设有k个群组S i, i=1,2,...,k。μi是群组S i内所有元素x j的重心，或叫中心点。
k平均聚类发明于1956年，该算法最常见的形式是采用被称为劳埃德算法(Lloyd algorithm)的迭代式改进探索法。劳埃德算法首先把输入点分成k个初始化分组，可以是随机的或者使用一些启发式数据。然后计算每组的中心点，根据中心点的位置把对象分到离它最近的中心，重新确定分组。继续重复不断地计算中心并重新分组，直到收敛，即对象不再改变分组（中心点位置不再改变）。
劳埃德算法和k平均通常是紧密联系的，但是在实际应用中，劳埃德算法是解决k平均问题的启发式法则，对于某些起始点和重心的组合，劳埃德算法可能实际上收敛于错误的结果。（上面函数中存在的不同的最优解）
虽然存在变异，但是劳埃德算法仍旧保持流行，因为它在实际中收敛非常快。实际上，观察发现迭代次数远远少于点的数量。然而最近，David Arthur和Sergei Vassilvitskii提出存在特定的点集使得k平均算法花费超多项式时间达到收敛。
近似的k平均算法已经被设计用于原始数据子集的计算。
从算法的表现上来说，它并不保证一定得到全局最优解，最终解的质量很大程度上取决于初始化的分组。由于该算法的速度很快，因此常用的一种方法是多次运行k平均算法，选择最优解。
k平均算法的一个缺点是，分组的数目k是一个输入参数，不合适的k可能返回较差的结果。另外，算法还假设均方误差是计算群组分散度的最佳参数。
3 SVM（支持向量机）
支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。它是一种监督式学习的方法，它广泛的应用于统计分类以及回归分析中。
支持向量机属于一般化线性分类器。它们也可以被认为是提克洛夫规范化（Tikhonov Regularization）方法的一个特例。这种分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区。因此支持向量机也被称为最大边缘区分类器。
在统计计算中，最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variable）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。最大期望算法经过两个
步骤交替进行计算，第一步是计算期望（E），也就是将隐藏变量像能够观测到的一样包含在内从而计算最大似然的期望值；另外一步是最大化（M），也就是最大化在 E 步上找到的最大似然的期望值从而计算参数的最大似然估计。M 步上找到的参数然后用于另外一个E 步计算，这个过程不断交替进行。
Vapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。其原理也从线性可分说起，然后扩展到线性不可分的情况。甚至扩展到使用非线性函数中去，这种分类器被称为支持向量机(Support Vector Machine，简称SVM)。支持向量机的提出有很深的理论背景。支持向量机方法是在近年来提出的一种新方法，但是进展很快，已经被广泛应用在各个领域之中。
SVM的主要思想可以概括为两点：(1) 它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能；(2) 它基于结构风险最小化理论之上在特征空间中建构最优分割超平面，使得学习器得到全局最优化，并且在整个样本空间的期望风险以某个概率满足一定上界。
在学习这种方法时，首先要弄清楚这种方法考虑问题的特点，这就要从线性可分的最简单情况讨论起，在没有弄懂其原理之前，不要急于学习线性不可分等较复杂的情况，支持向量机在设计时，需要用到条件极值问题的求解，因此需用拉格朗日乘子理论，但对多数人来说，以前学到的或常用的是约束条件为等式表示的方式，但在此要用到以不等式作为必须满足的条件，此时只要了解拉格朗日理论的有关结论就行。
支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。van der Walt 和Barnard 将支持向量机和其他分类器进行了比较。
有很多个分类器(超平面）可以把数据分开，但是只有一个能够达到最大分割。
我们通常希望分类的过程是一个机器学习的过程。这些数据点并不需要是中的点，
而可以是任意(统计学符号)中或者(计算机科学符号) 的点。我们希望能够把这些点通过一个n-1维的超平面分开，通常这个被称为线性分类器。有很多分类器都符合这个要求，但是我们还希望找到分类最佳的平面，即使得属于两个不同类的数据点间隔最大的那个面，该面亦称为最大间隔超平面。如果我们能够找到这个面，那么这个分类器就称为最大间隔分类器。
设样本属于两个类，用该样本训练SVM得到的最大间隔超平面。在超平面上的样本点也称为支持向量。
SVM的优势：
由于支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度，Accuracy)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷，以期获得最好的推广能力(Generalizatin Ability)。支持向量机方法的几个主要优点是：
●可以解决小样本情况下的机器学习问题；
●可以提高泛化性能；
●可以解决高维问题；
●可以解决非线性问题；
●可以避免神经网络结构选择和局部极小点问题。
4 贝叶斯（Bayes）分类器
贝叶斯分类器的分类原理是通过某对象的先验概率，利用贝叶斯公式计算出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率的类作为该对象所属的类。目前研究较多的贝叶斯分类器主要有四种，分别是：Naive Bayes、TAN、BAN和GBN。
贝叶斯网络是一个带有概率注释的有向无环图，图中的每一个结点均表示一个随机变量，图中两结点间若存在着一条弧，则表示这两结点相对应的随机变量是概率相依的，反之则说明这两个随机变量是条件独立的。网络中任意一个结点X 均有一个相应的条件概率表(Conditional Probability Table，CPT)，用以表示结点X 在其父结点取各可能值时的条件概率。若结点X 无父结点，则X 的CPT 为其先验概率分布。贝叶斯网络的结构及各结点的CPT 定义了网络中各变量的概率分布。
贝叶斯分类器是用于分类的贝叶斯网络。该网络中应包含类结点C，其中C 的取值来自于类集合( c1 , c2 , ... , c m)，还包含一组结点X = ( X1 , X2 , ... , X n)，表示用于分类的特征。对于贝叶斯网络分类器，若某一待分类的样本D，其分类特征向量为x = ( x1 , x2 , ... , x n) ，则样本D 属于类别c i的概率为P( C = c i | X = x) = P( C = c i | X1 = x1 , X2 = x 2 , ... , X n = x n) ，( i = 1 ,2 , ... , m) 。
而由贝叶斯公式可得：P( C = c i | X = x) = P( X = x | C = c i) P( C = c i) / P( X = x)
其中，P( C = c i) 可由领域专家的经验得到，称为先验概率；而P( X = x | C = c i) 和P( X = x) 的计算则较困难；P( C = c i | X = x)称为后验概率。
应用贝叶斯网络分类器进行分类主要分成两阶段。第一阶段是贝叶斯网络分类器的学习，即从样本数据中构造分类器；第二阶段是贝叶斯网络分类器的推理，即计算类结点的条件概率，对分类数据进行分类。这两个阶段的时间复杂性均取决于特征值间的依赖程度，甚至可以是NP完全问题（世界七大数学难题之一），因而在实际应用中，往往需要对贝叶斯网络分类器进行简化。根据对特征值间不同关联程度的假设，可以得出各种贝叶斯分类器，Naive Bayes、TAN、BAN、GBN就是其中较典型、研究较深入的贝叶斯分类器。
4.1 朴素贝叶斯（Naive Bayes）分类器
分类是将一个未知样本分到几个预先已知类的过程。数据分类问题的解决是一个两步过程：第一步，建立模型，描述预先的数据集或概念集。通过分析由属性/特征描述的样本（或实例，对象等）来构造模型。假定每一个样本都有一个预先定义的类，由一个被称为类标签的属性确定。为建立模型而被分析的数据元组形成训练数据集，该步也称作有指导的学习。
4.1.1 决策树模型和朴素贝叶斯模型的比较
在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型（Naive Bayesian Model，NBC）。决策树模型通过构造树来解决分类问题。首先利用训练数据集来构造一棵决策树，一旦树建立起来，它就可为未知样本产生一个分类。在分类问题中使用决策树模型有很多的优点，决策树便于使用，而且高效；根据决策树可以很容易地构造出规则，而规则通常易于解释和理解；决策树可很好地扩展到大型数据库中，同时它的大小独立于数据库的大小；决策树模型的另外一大优点就是可以对有许多属性的数据集构造决策树。决策树模型也有一些缺点，比如处理缺失数据时的困难，过度拟合问题的出现，以及忽略数据集中属性之间的相关性等。
和决策树模型相比，朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好。
朴素贝叶斯模型：
V map=arg max{P( V j | a1,a2...a n)}
V j属于V集合，其中j=1,2,…,N，即共有N类；
V map是给定一个example，得到的最可能的目标值；
a1...an是这个example里面的属性/特征，共有n个特征。
Vmap为目标值，就是后面计算得出的概率最大的一个，所以用max 来表示，它意味着该example应该/最可能为得到最大后验概率的那个类，这与前面讲到的贝叶斯分类器是一致的。
将贝叶斯公式应用到P( V j | a1,a2...a n)中，可得到：
V map= arg max{P(a1,a2...a n | V j ) P( V j ) / P (a1,a2...a n)}
又因为朴素贝叶斯分类器默认a1...an他们互相独立的，所以P(a1,a2...an)对于结果没有影响（因为所有的概率都要除同一个东西之后再比较大小）。于是可得到：V map= arg max{P(a1,a2...a n | V j ) P( V j )}
然后，朴素贝叶斯分类器基于一个简单的假定：给定目标值时属性之间相互条件独立。换言之，该假定说明给定实例的目标值情况下，观察到联合的a1,a2...a n的概率正好是对每个单独属性的概率乘积：P(a1,a2...a n | V j ) = Πi P( a i| V j )。
因此，朴素贝叶斯分类器公式为：V nb =arg max{P( V j )Πi P ( a i | V j )}。
5 邻近算法（k-Nearest Neighbor algorithm，k最近邻算法）
下图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3（即实线圆内部），由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5（即虚线圆内），由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。
K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。
该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
6 回归树分类器
如果要选择在很大范围的情形下性能都好的、同时不需要应用开发者付出很多的努力并且易于被终端用户理解的分类技术的话，那么Brieman, Friedman, Olshen和Stone（1984）提出的分类树方法是一个强有力的竞争者。
6.1 分类树
在分类树下面有两个关键的思想。第一个是关于递归地划分自变量空间的想法；第二个想法是用验证数据进行剪枝。
6.2 递归划分
让我们用变量Y表示因变量（分类变量），用X1, X2, X3,...,X p表示自变量。通过递归的方式把关于变量X的p维空间划分为不重叠的矩形。首先，一个自变量被选择，比如X i 和X i的一个值x i，比方说选择x i把p维空间为两部分：一部分是p维的超矩形，其中包含的点都满足X i<=x i，另一个p维的超矩形包含的所有点满足X i>x i。接着，这两部分中的一个部分通过选择一个变量和该变量的划分值以相似的方式被划分。这导致了三个矩形区域。随着这个过程的持续，我们得到的矩形越来越小。这个想法是把整个X空间划分为矩形，
其中的每个小矩形都尽可能是同构的或“纯”的。“纯”的意思是（矩形）所包含的点都属于同一类。我们认为包含的点都只属于一个类（当然，这并不总是可能的，因为经常存在一些属于不同类的点，但这些点的自变量有完全相同的值）。
7 Adaboost分类器
Adaboost是adaptive boost的缩写，它是一种迭代算法。其核心思想是针对同一个训练集训练不同的分类器（弱分类器），然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器融合起来，作为最后的决策分类器。使用Adaboost分类器可以排除一些不必要的训练数据特征，并将重点放在关键的训练数据上。
该算法其实是一个弱分类算法的提升过程，这个过程通过不断的训练，可以提高对数据的分类能力。
整个过程如下所示：
●先通过对N个数据的训练样本的学习得到第一个弱分类器；
●将分错的样本和其他的新数据一起构成一个新的N个数据的训练样本，通过对这
个样本的学习得到第二个弱分类器；
●将1.和2.都分错了的样本加上其他的新样本构成另一个新的N个数据的训练样本，
通过对这个样本的学习得到第三个弱分类器；
●最终经过提升的强分类器，即某个数据被分为哪一类要通过，……的多数表决。
对于boosting算法，存在两个问题：
●如何调整训练集，使得在训练集上训练的弱分类器得以进行；
●如何将训练得到的各个弱分类器联合起来形成强分类器。
针对以上两个问题，adaboost算法进行了调整：
●使用加权后选取的训练数据代替随机选取的训练样本，这样将训练的焦点集中在比
较难分的训练数据样本上；
●将弱分类器联合起来，使用加权的投票机制代替平均投票机制。让分类效果好的弱
分类器具有较大的权重，而分类效果差的分类器具有较小的权重。
Adaboost算法是Freund和Schapire根据在线分配算法提出的，他们详细分析了Adaboost 算法错误率的上界，以及为了使强分类器达到要求的错误率，算法所需要的最多迭代次数等相关问题。与Boosting算法不同的是，adaboost算法不需要预先知道弱学习算法学习正确率的下限即弱分类器的误差，并且最后得到的强分类器的分类精度依赖于所有弱分类器的分类精度，这样可以深入挖掘弱分类器算法的能力。
Adaboost算法中不同的训练集是通过调整每个样本对应的权重来实现的。开始时，每个样本对应的权重是相同的，即其中n 为样本个数，在此样本分布下训练出一弱分类器。对于分类错误的样本，加大其对应的权重；而对于分类正确的样本，降低其权重，这样分错的样本就被突出出来，从而得到一个新的样本分布。在新的样本分布下，再次对弱分类器进行训练，得到弱分类器。依次类推，经过T次循环，得到T个弱分类器，把这T个弱分类器按一定的权重叠加（boost）起来，得到最终想要的强分类器。
8 人工神经网络（ANN, artificial neural network）
人工神经网络是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应。
人工神经网络研究的局限性：
● 研究受到脑科学研究成果的限制；
● 缺少一个完整、成熟的理论体系；
● 研究带有浓厚的策略和经验色彩；
● 与传统技术的接口不成熟。
一般而言, ANN 与经典计算方法相比并非优越, 只有当常规方法解决不了或效果不佳时ANN 方法才能显示出其优越性。尤其对问题的机理不甚了解或不能用数学模型表示的系统,如故障诊断、特征提取和预测等问题,ANN 往往是最有利的工具。另一方面, ANN 对处理大量原始数据而不能用规则或公式描述的问题, 表现出极大的灵活性和自适应性。
8.1 BP 网络
人工神经网络以其具有自学习、自组织、较好的容错性和优良的非线性逼近能力，受到众多领域学者的关注。在实际应用中，80%～90%的人工神经网络模型是采用误差反传算法或其变化形式的网络模型（简称BP 网络），目前主要应用于函数逼近、模式识别、分类和数据压缩或数据挖掘。
（1）BP 网络建模特点：
● 非线性映照能力：神经网络能以任意精度逼近任何非线性连续函数。在建模过程中
的许多问题正是具有高度的非线性。
● 并行分布处理方式：在神经网络中信息是分布储存和并行处理的，这使它具有很
强的容错性和很快的处理速度。
● 自学习和自适应能力：神经网络在训练时，能从输入、输出的数据中提取出规律
性的知识，记忆于网络的权值中，并具有泛化能力，即将这组权值应用于一般情形的能力。神经网络的学习也可以在线进行。
● 数据融合的能力：神经网络可以同时处理定量信息和定性信息，因此它可以利用传
统的工程技术（数值运算）和人工智能技术（符号处理）。
● 多变量系统：神经网络的输入和输出变量的数目是任意的，对单变量系统与多变量
系统提供了一种通用的描述方式，不必考虑各子系统间的解耦问题。
（2）样本数据的收集和整理分组：
采用BP 神经网络方法建模的首要和前提条件是有足够多典型性好和精度高的样本。而且，为监控训练（学习）过程使之不发生“过拟合”和评价建立的网络模型的性能和泛化能力，必须将收集到的数据随机分成训练样本、检验样本（10%以上）和测试样本（10%以上）3部分。此外，数据分组时还应尽可能考虑样本模式间的平衡。
由于传统的误差反传BP 算法较为成熟，且应用广泛，因此努力提高该方法的学习速度具有较高的实用价值。BP 算法中有几个常用的参数，包括学习率η，动量因子α，形状因子λ及收敛误差界值E 等。这些参数对训练速度的影响最为关键。
9 Fisher 分类器
图 生物神经元功能模型输
入输出神经网络基本模型
X 空间：
W T X-W 0 >0 X ∈ω1
-W T X-W 0 <0 X ∈ω2
映射到Y 空间：
Y = W T X-W 0 >0 X ∈ω1
Y = W T X-W 0 <0 X ∈ω2
把X 空间各点投影到Y 空间的一直线上，维数由2维降为一维。若适当选择W 的方向，可以使两类分开。于是问题便转化为从数学上寻找最好的投影方向，即寻找最好的变换向量W 的问题。
在X 空间上的均值为：2,111==∑=i x N X i N j j i
i 在Y 空间上的均值为：2,11111====∑∑==i X W x W N y N Y i T N j j T i N j j i i i i
投影样本类间的分离性用投影样本之差表示：|)(|||2121X X W Y Y T ?=?，要求类间的分离性越大越好。
投影样本类内离散度: ()()W S W X W x W Y y i T N j i T j T N j i j i i i =?=?=∑∑==12122
σ，其中，
∑=??=i
N x T i i i X x X x S 1))((。
投影样本总的离散度可用)(2212σσ+来表示，要求投影样本总的离散度越小越好。
W S W W S W W S W w T T T =+=+212212σσ，其中，S S S w 21+=称为类内散布矩阵。
Fisher 准则函数为：()22122
12
||)(σσ+?=Y Y W J ， 而W S W X W X W Y Y b T T T =?=?221221)()(，其中，()()212
1X X X X S T b ??=称
为类间散布矩阵。 所以，W
S W W S W W J w T b T =)(，对)(W J 求极值得()X X S W w 211?=?。这便是n 维X 空间向一维Y 空间的最好投影方向，它实际上是多维空间向一维空间的一种映射。
现在我们已把一个n 维的问题转化为一维的问题。于是只需在一维空间中设计 Fisher 分类器:
ω10∈?>=X W X W Y T
ω20∈?<=X W X W Y T
于是，问题归结为W 0的选择，常用的有以下三种： 1.2
210Y Y W +=; 2.2
121212102122N N X W N X W N N N Y N Y N W T T ++=++=; 3.()()()∑∑∑==?=?+??+=2211111211
22112
1120)(N j j N j j N j j Y y Y y
Y y
Y Y Y W 。 附录 数据挖掘中的十个算法
Top 10 algorithms in data mining
Abstract This paper presents the top 10 data mining algorithms identified by the IEEE International Conference on Data Mining (ICDM) in December 2006: C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART . These top 10 algorithms are among the most influential data mining algorithms in the research community.With each algorithm, we provide a description of the algorithm, discuss the impact of the algorithm, and reviewcurrent and further research on the algorithm. These 10 algorithms cover classification, X. clustering, statistical learning, association analysis, and link mining, which are all among the most important topics in data mining research and development.
概述 本文介绍有IEEE 2006年12月召开的国际会议确定的十个主要数据挖掘算法：C4.5（决策树），K-means （样本均值），SVM （支持向量机），Apriori （关联规则的一种），EM ，PageRank ，AdaBoost ，KNN ，Naive Bayes （贝叶斯）和CART 。这十个算法几乎在所有流行的数据挖掘研究中都有所包含。对于每一个算法，我们会首先描述算法，然后讨论起优缺点，总结当前应用和将来发展。这十个算法覆盖分类、聚类、统计学习、关联分析和关联挖掘，这些都是目前数据挖掘研究和开发的重要问题。 0 Introduction
0 简介
In an effort to identify some of the most influential algorithms that have been widely used in the data mining community, the IEEE International Conference on Data Mining (ICDM, https://www.doczj.com/doc/d73312220.html,/~icdm/) identified the top 10 algorithms in data mining for presentation at ICDM ’06 in Hong Kong.
为了确定最有影响力已广为广泛使用的数据挖掘算法的一些问题，IEEE国际会议（ICDM '06香港）确定的数据挖掘的数据挖掘算法的前10名。
As the first step in the identification process, in September 2006 we invited the ACMKDD Innovation Award and IEEE ICDM Research Contributions Award winners to each nominate up to 10 best-known algorithms in data mining. All except one in this distinguished set of award winners responded to our invitation. We asked each nomination to provide the following information: (a) the algorithm name, (b) a brief justification, and (c) a representative publication reference.We also advised that each nominated algorithm should have been widely cited and used by other researchers in the field, and the nominations from each nominator as a group should have a reasonable representation of the different areas in data mining.
首先2006年9月，我们邀请ACMKDD创新奖和IEEE ICDM研究贡献奖得主分别提名多达10个最知名的数据挖掘算法。此外的所有获奖者我们要求每名候选人提供下列资料：（1）的算法的名称，（b）一个简短的理由，以及（c）一名代表的出版物引用。我们还表示，每个提名的算法应该被广泛引用，并在该领域的其他研究人员使用，以及每个作为一个集团提名人的提名，应该有一个在数据挖掘不同领域合理的代表性。
After the nominations in Step 1, we verified each nomination for its citations on Google Scholar in late October 2006, and removed those nominations that did not have at least 50 citations. All remaining (18) nominations were then organized in 10 topics: association analysis, classification, clustering, statistical learning, bagging and boosting, sequential patterns, integrated mining, rough sets, linkmining, and graph mining. For some of these 18 algorithms such as k-means, the representative publication was not necessarily the original paper that introduced the algorithm, but a recent paper that highlights the importance of the technique. These representative publications are available at the ICDM website (https://www.doczj.com/doc/d73312220.html,/~icdm/algorithms/CandidateList.shtml).
In the third step of the identification process, we had a wider involvement of the research community. We invited the Program Committee members of KDD-06 (the 2006 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining), ICDM ’06 (the 2006 IEEE International Conference on Data Mining), and SDM ’06 (the 2006 SIAM International Conference on Data Mining), as well as the ACMKDD Innovation Award and IEEE ICDM Research Contributions Award winners to each vote for up to 10 well-known algorithms from the 18-algorithm candidate list. The voting results of this step were presented at the ICDM ’06 panel on Top 10 Algorithms in Data Mining. At the ICDM ’06 panel of December 21, 2006, we also took an open vote with all 145 attendees on the top 10 algorithms from the above 18-algorithm candidate list, and the top 10 algorithms from this open vote were the same as the voting results from the above third step. The 3-hour panel was organized as the last session of the ICDM ’06 conference, in parallel with 7 paper presentation sessions of the Web Intelligence (WI ’06) and Intelligent Agent Technology (IAT ’06) conferences at the same location, and attracting 145 participants to this panel clearly showed that the panel was a great success.
1 C4.5 and beyond
1.1 Introduction
Systems that construct classifiers are one of the commonly used tools in data mining. Such systems take as input a collection of cases, each belonging to one of a small number of classes and described by its values for a fixed set of attributes, and output a classifier that can
accurately predict the class to which a new case belongs.
These notes describe C4.5 [64], a descendant of CLS [41] and ID3 [62]. Like CLS and ID3, C4.5 generates classifiers expressed as decision trees, but it can also construct classifiers in more comprehensible ruleset form. We will outline the algorithms employed in C4.5, highlight some changes in its successor See5/C5.0, and conclude with a couple of open
research issues.
1.2 Decision trees
Given a set S of cases, C4.5 first grows an initial tree using the divide-and-conquer algorithm as follows:
? If all the cases in S belong to the same class or S is small, the tree is a leaf labeled with the most frequent class in S.
? Otherwise, choose a test based on a single attribute with two or more outcomes. Make this test the root of the tree with one branch for each outcome of the test, partition S into corresponding subsets S1, S2, . . . according to the outcome for each case, and apply the same procedure recursively to each subset.
There are usually many tests that could be chosen in this last step. C4.5 uses two heuristic criteria to rank possible tests: information gain, which minimizes the total entropy of the subsets {Si } (but is heavily biased towards tests with numerous outcomes), and the default gain ratio that divides information gain by the information provided by the test outcomes.
Attributes can be either numeric or nominal and this determines the format of the test outcomes. For a numeric attribute A they are {A ≤ h, A > h} where the threshold h is found by sor ting S on the values of A and choosing the split between successive values that maximizes the criterion above. An attribute A with discrete values has by default one outcome for each value, but an option allows the values to be grouped into two or more subsets with one outcome for each subset.
The initial tree is then pruned to avoid overfitting. The pruning algorithm is based on a pessimistic estimate of the error rate associated with a set of N cases, E of which do not belong to the most frequent class. Instead of E/N, C4.5 determines the upper limit of the binomial probability when E events have been observed in N trials, using a user-specified confidence whose default value is 0.25.
Pruning is carried out from the leaves to the root. The estimated error at a leaf with N cases and E errors is N times the pessimistic error rate as above. For a subtree, C4.5 adds the estimated errors of the branches and compares this to the estimated error if the subtree is replaced by a leaf; if the latter is no higher than the former, the subtree is pruned. Similarly, C4.5 checks the estimated error if the subtree is replaced by one of its branches and when this appears beneficial the tree is modified accordingly. The pruning process is completed in one pass through the tree.
C4.5’s tree-construction algorithm differs in several respects from CART [9], for instance:
? Tests in CART are always binary, but C4.5 allows two or more outcomes.
? CART uses the Gini diversity index to rank tests, whereas C4.5 uses information-based criteria.
? CART prunes trees using a cost-complexity model whose parameters are estimated by cross-validation; C4.5 uses a single-pass algorithm derived from binomial confidence limits.
? This brief discussion has not mentioned what happens when some of a case’s values are unknown. CART looks for surrogate tests that approximate the outcomes when the tested attribute has an unknown value, but C4.5 apportions the case probabilistically among the outcomes.
1.3 Ruleset classifiers
Complex decision trees can be difficult to understand, for instance because information about one class is usually distributed throughout the tree. C4.5 introduced an alternative formalism consisting of a list of rules of the form “if A and B and C and ... then class X”, where rules for each class are grouped together. A case is classified by finding the first rule whose conditions are satisfied by the case; if no rule is satisfied, the case is assigned to a default class.
C4.5 rulesets are formed from the initial (unpruned) decision tree. Each path from the root of the tree to a leaf becomes a prototype rule whose conditions are the outcomes along the path andwhose class is the label of the leaf. This rule is then simplified by determining the effect of discarding each condition in turn. Dropping a condition may increase the number N of cases covered by the rule, and also the number E of cases that do not belong to the class nominated by the rule, and may lower the pessimistic error rate determined as above. A hill-climbing algorithm is used to drop conditions until the lowest pessimistic error rate is found.
To complete the process, a subset of simplified rules is selected for each class in turn. These class subsets are ordered to minimize the error on the training cases and a default class is chosen. The final ruleset usually has far fewer rules than the number of leaves on the pruned decision tree.
The principal disadvantage of C4.5’s rulesets is the amount of CPU time and memory that they require. In one experiment, samples ranging from 10,000 to 100,000 cases were drawn from a large dataset. For decision trees, moving from 10 to 100K cases increased CPU time on a PC from 1.4 to 61 s, a factor of 44. The time required for rulesets, however, increased from 32 to 9,715 s, a factor of 300.
1.4 See5/C5.0
C4.5 was superseded in 1997 by a commercial system See5/C5.0 (or C5.0 for short). The changes encompass new capabilities as well as much-improved efficiency, and include:
? A variant of boosting [24], which constructs an ensemble of classifiers that are then voted to give a final classification. Boosting often leads to a dramatic improvement in predictive accuracy.
? New data types (e.g., dates), “not applicable” values, variable misclassification costs, and mechanisms to pre-filter attributes.
? Unordered rulesets—when a case is classified, all applicable rules are found and voted. This improves both the interpretability of rulesets and their predictive accuracy.
? Greatly improved scalability of both decision trees and (particularly) rulesets. Scalability is enhanced by multi-threading; C5.0 can take advantage of computers with multiple CPUs and/or cores.
More details are available from https://www.doczj.com/doc/d73312220.html,/see5-comparison.html.
1.5 Research issues
We have frequently heard colleagues express the view that decision trees are a “solved problem.” We do not agree with this proposition and will close with a couple of open research problems.
Stable trees. It is well known that the error rate of a tree on the cases fromwhich itwas constructed (the resubstitution error rate) is much lower than the error rate on unseen cases (the predictive error rate). For example, on a well-known letter recognition dataset with 20,000 cases, the resubstitution error rate for C4.5 is 4%, but the error rate from a leave-one-out (20,000-fold) cross-validation is 11.7%. As this demonstrates, leaving out a single case from 20,000 often affects the tree that is constructed!
Suppose now that we could develop a non-trivial tree-construction algorithm that was hardly ever affected by omitting a single case. For such stable trees, the resubstitution error rate should approximate the leave-one-out cross-validated error rate, suggesting that the tree is of the “right” size.
Decomposing complex trees. Ensemble classifiers, whether generated by boosting, bagging, weight randomization, or other techniques, usually offer improved predictive accuracy. Now, given a small number of decision trees, it is possible to generate a single (very complex) tree that is exactly equivalent to voting the original trees, but can we go the other way? That is, can a complex tree be broken down to a small collection of simple trees that, when voted together, give the same result as the complex tree? Such decomposition would be of great help in producing comprehensible decision trees.
Research on C4.5 was funded for many years by the Australian Research Council.
C4.5 is freely available for research and teaching, and source can be downloaded from https://www.doczj.com/doc/d73312220.html,/Personal/c4.5r8.tar.gz.
2 The k-means algorithm
2.1 The algorithm
The k-means algorithm is a simple iterative method to partition a given dataset into a userspecified number of clusters, k. This algorithm has been discovered by several researchers across different disciplines, most notably Lloyd (1957, 1982) [53], Forgey (1965), Friedman and Rubin (1967), and McQueen (1967). A detailed history of k-means alongwith descriptions of several variations are given in [43]. Gray and Neuhoff [34] provide a nice historical background for k-means placed in the larger context of hill-climbing algorithms. The algorithm
operates on a set of d-dimensional vectors, D = {xi | i = 1, . . . , N}, where xi ∈denotes the ith data point. The algorithm is initialized
by picking k points in as the initial k cluster representatives or “centroids”. Techniques for selecting these initial seeds include sampling at random from the dataset, setting them as the solution of clustering a small subset of the data or perturbing the global mean of the data k times. Then the algorithm iterates between two steps till convergence:
Step 1: Data Assignment. Each data point is assigned to its closest centroid, with ties broken arbitrarily. This results in a partitioning of the data.
Step 2: Relocation of “means”. Each cluster representative is relocated to the center (mean) of all data points assigned to it. If the data points come with a probability measure (weights), then the relocation is to the expectations (weighted mean) of the data partitions.
The algorithm convergeswhen the assignments (and hence the cj values) no longer change. The algorithm execution is visually depicted in Fig. 1. Note that each iteration needs N × k comparisons, which determines the time complexity of one iteration. The number of iterations required for convergence varies and may depend on N, but as a first cut, this algorithm can be considered linear in the dataset size.
One issue to resolve is how to quantify “closest” in the assignment step. The default measure of closeness is the Euclidean distance, in which case one can readily show that the non-negative cost function,
will decrease whenever there is a change in the assignment or the relocation steps, and hence convergence is guaranteed in a finite number of iterations. The greedy-descent nature of k-means on a non-convex cost also implies that the convergence is only to a local optimum, and indeed the algorithm is typically quite sensitive to the initial centroid locations. Figure 2-1 illustrates how a poorer result is obtained for the same dataset as in Fig. 1 for a different choice of the three initial centroids. The local minima problem can be countered to some extent by running the algorithm
Fig. 1 Changes in cluster representative locations (indicated by ‘+’ signs) and data assignments (indicated by color) during an execution of the k-means algorithm
Fig. 2 Effect of an inferior initialization on the k-means results
multiple times with different initial centroids, or by doing limited local search about the converged solution.
2.2 Limitations
In addition to being sensitive to initialization, the k-means algorithm suffers from several other problems. First, observe that
k-means is a limiting case of fitting data by a mixture of k Gaussians with identical, isotropic covariance matrices , when the soft assignments of data points to mixture components are hardened to allocate each data point solely to the most likely component. So, it will falter whenever the data is not well described by reasonably separated spherical balls, for example, if there are non-covex shaped clusters in the data. This problem may be alleviated by rescaling the data to “whiten” it before clustering, or by using a different distance measure that ismore appropriate for the dataset. For example, information-theoretic clustering uses theKL-divergence to measure the distance between two data points representing two discrete probability distributions. It has been recently shown that if one measures distance by selecting any member of a very large class of divergences called Bregman divergences during the assignment step and makes no other changes, the essential properties of k-means, including guaranteed convergence, linear separation boundaries and scalability, are retained [3]. This result makes k-means effective for a much larger class of datasets so long as an appropriate divergence is used.
k-means can be paired with another algorithm to describe non-convex clusters. One first clusters the data into a large number of groups using k-means. These groups are then agglomerated into larger clusters using single link hierarchical clustering, which can detect complex shapes. This approach also makes the solution less sensitive to initialization, and since the hierarchical method provides results at multiple resolutions, one does not need to pre-specify k either.
The cost of the optimal solution decreases with increasing k till it hits zero when the umber of clusters equals the number of distinct data-points. This makes it more difficult to (a) directly compare solutions with different numbers of clusters and (b) to find the optimum value of k. If the desired k is not known in advance, one will typically run k-means with different values of k, and then use a suitable criterion to select one of the results. For example, SAS uses the cube-clustering-criterion, while X-means adds a complexity term (which increases with k) to the original cost function (Eq. 1) and then identifies the k which minimizes this adjusted cost. Alternatively, one can progressively increase the number of clusters, in conjunction with a suitable stopping criterion. Bisecting k-means [73] achieves this by first putting all the data into a single cluster, and then recursively splitting the least compact cluster into two using 2-means. The celebrated LBG algorithm [34] used for vector quantization doubles the number of clusters till a suitable code-book size is obtained. Both these approaches thus alleviate the need to know k beforehand.
The algorithm is also sensitive to the presence of outliers, since “mean” is not a robust statistic. A preprocessing step to remove outliers can be helpful. Post-processing the results, for example to eliminate small clusters, or to merge close clusters into a large cluster, is also desirable. Ball and Hall’s ISODATA algorithm from 1967 effectively used both pre- and post-processing on k-means.
2.3 Generalizations and connections
As mentioned earlier, k-means is closely related to fitting a mixture of k isotropicGaussians to the data. Moreover, the generalization of the distance measure to all Bregman divergences is related to fitting the data with a mixture of k components from the exponential family of distributions. Another broad generalization is to view the “means” as probabilistic models instead of points in Rd . Here, in the assignment step, each data point is assigned to the most likely model to have generated it. In the “relocation” step, the model parameters are updated to best fit the assigned datasets. Such model-based k-means allow one to cater to more complex data, e.g. sequences described by Hidden Markov models.
One can also “kernelize” k-means [19]. Though boundaries between clusters are still linear in the implicit high-dimensional space, they can become non-linear when projected back to the original space, thus allowing kernel k-means to deal with more complex clusters. Dhillon et al. [19] have shown a close connection between kernel k-means and spectral clustering. The K-medoid algorithm is similar to k-means except that the centroids have to belong to the data set being clustered. Fuzzy c-means is also similar, except that it computes fuzzy membership functions for each clusters rather than a hard one.
Despite its drawbacks, k-means remains the most widely used partitional clustering algorithm in practice. The algorithm is simple, easily understandable and reasonably scalable, and can be easily modified to deal with streaming data. To deal with very large datasets, substantial effort has also gone into further speeding up k-means, most notably by using kd-trees or exploiting the triangular inequality to avoid comparing each data point with all the centroids during the assignment step. Continual improvements and generalizations of the basic algorithm have ensured its continued relevance and gradually increased its effectiveness as well.
3 Support vector machines
In today’s machine learning applications, support vector machines (SVM) [83] are considered amust try—it offers one of themost robust and accurate methods among all well-known algorithms. It has a sound theoretical foundation, requires only a dozen examples for training, and is insensitive to the number of dimensions. In addition, efficient methods for training SVM are also being developed at a fast pace.
In a two-class learning task, the aim of SVM is to find the best classification function to distinguish between members of the two classes in the training data. The metric for the concept of the “best” classification function can be realized geometrically. For a linearly separable dataset, a linear classification function corresponds to a separating hyperplane f (x) that passes through the middle of the two classes, separating the two. Once this function is determined, new data instance xn can be classified by simply testing the sign of the function f (xn); xn belongs to the positive class if f (xn) > 0.
Because there are many such linear hyperplanes, what SVM additionally guarantee is that the best such function is found by maximizing the margin between the two classes. Intuitively, the margin is defined as the amount of space, or separation between the two classes as defined by the hyperplane. Geometrically, the margin corresponds to the shortest distance between the closest data points to a point on the hyperplane. Having this geometric definition allows us to explore how to maximize the margin, so that even though there are an infinite number of hyperplanes, only a few qualify as the solution to SVM.
数据挖掘领域的十大经典算法原理及应用 国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. 不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。 1.C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法.C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1)用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。
C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 2. The k-means algorithm即K-Means算法 k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 3. Support vector machines 支持向量机，英文为Support Vector Machine，简称SV 机（论文中一般简称SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面
学习18大经典数据挖掘算法 本文所有涉及到的数据挖掘代码的都放在了github上了。 地址链接: https://https://www.doczj.com/doc/d73312220.html,/linyiqun/DataMiningAlgorithm 大概花了将近2个月的时间，自己把18大数据挖掘的经典算法进行了学习并且进行了代码实现，涉及到了决策分类，聚类，链接挖掘，关联挖掘，模式挖掘等等方面。也算是对数据挖掘领域的小小入门了吧。下面就做个小小的总结，后面都是我自己相应算法的博文链接，希望能够帮助大家学习。 1.C4.5算法。C4.5算法与ID3算法一样，都是数学分类算法，C4.5算法是ID3算法的一个改进。ID3算法采用信息增益进行决策判断，而C4.5采用的是增益率。 详细介绍链接：https://www.doczj.com/doc/d73312220.html,/androidlushangderen/article/details/42395865 2.CART算法。CART算法的全称是分类回归树算法，他是一个二元分类，采用的是类似于熵的基尼指数作为分类决策，形成决策树后之后还要进行剪枝，我自己在实现整个算法的时候采用的是代价复杂度算法， 详细介绍链接：https://www.doczj.com/doc/d73312220.html,/androidlushangderen/article/details/42558235 3.KNN(K最近邻)算法。给定一些已经训练好的数据，输入一个新的测试数据点，计算包含于此测试数据点的最近的点的分类情况，哪个分类的类型占多数，则此测试点的分类与此相同，所以在这里,有的时候可以复制不同的分类点不同的权重。近的点的权重大点，远的点自然就小点。 详细介绍链接：https://www.doczj.com/doc/d73312220.html,/androidlushangderen/article/details/42613011 4.Naive Bayes(朴素贝叶斯)算法。朴素贝叶斯算法是贝叶斯算法里面一种比较简单的分类算法，用到了一个比较重要的贝叶斯定理，用一句简单的话概括就是条件概率的相互转换推导。 详细介绍链接：https://www.doczj.com/doc/d73312220.html,/androidlushangderen/article/details/42680161 5.SVM(支持向量机)算法。支持向量机算法是一种对线性和非线性数据进行分类的方法，非线性数据进行分类的时候可以通过核函数转为线性的情况再处理。其中的一个关键的步骤是搜索最大边缘超平面。 详细介绍链接：https://www.doczj.com/doc/d73312220.html,/androidlushangderen/article/details/42780439 6.EM(期望最大化)算法。期望最大化算法，可以拆分为2个算法，1个E-Step期望化步骤,和1个M-Step最大化步骤。他是一种算法框架，在每次计算结果之后，逼近统计模型参数的最大似然或最大后验估计。
数据挖掘领域10大挑战性问题与十大经典算法 2010-04-21 20:05:51| 分类：技术编程| 标签：|字号大中小订阅 作为一个数据挖掘工作者，点可以唔知呢。 数据挖掘领域10大挑战性问题： 1.Developing a Unifying Theory of Data Mining 2.Scaling Up for High Dimensional Data/High Speed Streams 3.Mining Sequence Data and Time Series Data 4.Mining Complex Knowledge from Complex Data 5.Data Mining in a Network Setting 6.Distributed Data Mining and Mining Multi-agent Data 7.Data Mining for Biological and Environmental Problems 8.Data-Mining-Process Related Problems 9.Security, Privacy and Data Integrity 10.Dealing with Non-static, Unbalanced and Cost-sensitive Data 数据挖掘十大经典算法 国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. 不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。 1. C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 2. The k-means algorithm 即K-Means算法 k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 3. Support vector machines 支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。van der Walt 和Barnard 将支持向量机和其他分类器进行了比较。 4. The Apriori algorithm
数据挖掘十大经典算法 国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. 不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。 1. C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 2. The k-means algorithm 即K-Means算法 k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 3. Support vector machines 支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。van der Walt 和Barnard 将支持向量机和其他分类器进行了比较。 4. The Apriori algorithm Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。 5. 最大期望(EM)算法 在统计计算中，最大期望（EM，Expectation–Maximization）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。 6. PageRank PageRank是Google算法的重要内容。2001年9月被授予美国专利，专利人是Google创始人之一拉里?佩奇（Larry Page）。因此，PageRank里的page不是指网页，而是指佩奇，即这个
数据挖掘十大经典算法，你都知道哪些？ 当前时代大数据炙手可热，数据挖掘也是人人有所耳闻，但是关于数据挖掘更具体的算法，外行人了解的就少之甚少了。 数据挖掘主要分为分类算法，聚类算法和关联规则三大类，这三类基本上涵盖了目前商业市场对算法的所有需求。而这三类里又包含许多经典算法。而今天，小编就给大家介绍下数据挖掘中最经典的十大算法，希望它对你有所帮助。 一、分类决策树算法C4.5 C4.5，是机器学习算法中的一种分类决策树算法，它是决策树(决策树，就是做决策的节点间的组织方式像一棵倒栽树)核心算法ID3的改进算法，C4.5相比于ID3改进的地方有： 1、用信息增益率选择属性 ID3选择属性用的是子树的信息增益，这里可以用很多方法来定义信息，ID3使用的是熵（shang），一种不纯度度量准则，也就是熵的变化值，而 C4.5用的是信息增益率。区别就在于一个是信息增益，一个是信息增益率。 2、在树构造过程中进行剪枝，在构造决策树的时候，那些挂着几个元素的节点，不考虑最好，不然容易导致过拟。 3、能对非离散数据和不完整数据进行处理。 该算法适用于临床决策、生产制造、文档分析、生物信息学、空间数据建模等领域。 二、K平均算法
K平均算法（k-means algorithm）是一个聚类算法，把n个分类对象根据它们的属性分为k类（kn）。它与处理混合正态分布的最大期望算法相似，因为他们都试图找到数据中的自然聚类中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 从算法的表现上来说，它并不保证一定得到全局最优解，最终解的质量很大程度上取决于初始化的分组。由于该算法的速度很快，因此常用的一种方法是多次运行k平均算法，选择最优解。 k-Means 算法常用于图片分割、归类商品和分析客户。 三、支持向量机算法 支持向量机(Support Vector Machine)算法，简记为SVM，是一种监督式学习的方法，广泛用于统计分类以及回归分析中。 SVM的主要思想可以概括为两点： (1)它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分； (2)它基于结构风险最小化理论之上，在特征空间中建构最优分割超平面，使得学习器得到全局最优化，并且在整个样本空间的期望风险以某个概率满足一定上界。 四、The Apriori algorithm Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法，其核心是基于两阶段“频繁项集”思想的递推算法。其涉及到的关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支
数据挖掘的10大经典算法 国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. 不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。 1. C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在 构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 2. The k-means algorithm 即K-Means算法 k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 3. Support vector machines 支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。van der Walt 和 Barnard 将支持向量机和其他分类器进行了比较。 4. The Apriori algorithm
大数据常用的算法（分类、回归分析、聚类、关联规则） 在大数据时代，数据挖掘是最关键的工作。大数据的挖掘是从海量、不完全的、有噪声的、模糊的、随机的大型数据库中发现隐含在其中有价值的、潜在有用的信息和知识的过程，也是一种决策支持过程。其主要基于人工智能，机器学习，模式学习，统计学等。通过对大数据高度自动化地分析，做出归纳性的推理，从中挖掘出潜在的模式，可以帮助企业、商家、用户调整市场政策、减少风险、理性面对市场，并做出正确的决策。目前，在很多领域尤其是在商业领域如银行、电信、电商等，数据挖掘可以解决很多问题，包括市场营销策略制定、背景分析、企业管理危机等。大数据的挖掘常用的方法有分类、回归分析、聚类、关联规则、神经网络方法、Web 数据挖掘等。这些方法从不同的角度对数据进行挖掘。 (1)分类。分类是找出数据库中的一组数据对象的共同特点并按照分类模式将其划分为不同的类，其目的是通过分类模型，将数据库中的数据项映射到摸个给定的类别中。可以应用到涉及到应用分类、趋势预测中，如淘宝商铺将用户在一段时间内的购买情况划分成不同的类，根据情况向用户推荐关联类的商品，从而增加商铺的销售量。 (2)回归分析。回归分析反映了数据库中数据的属性值的特性，通过函数表达数据映射的关系来发现属性值之间的依赖关系。它可以应用到对数据序列的预测及相关关系的研究中去。在市场营销中，回归分析可以被应用到各个方面。如通过对本季度销售的回归分析，对下一季度的销售趋势作出预测并做出针对性的营销改变。 (3)聚类。聚类类似于分类，但与分类的目的不同，是针对数据的相似性和差异性将一组数据分为几个类别。属于同一类别的数据间的相似性很大，但不同类别之间数据的相似性很小，跨类的数据关联性很低。(4)关联规则。关联规则是隐藏在数据项之间的关联或相互关系，即可以根据一个数据项的出现推导出其他数据项的出现。关联规则的挖掘过程主要包括两个阶段：第一阶段为从海量原始数据中找出所有的高频项目组;第二极端为从这些高频项目组产生关联规则。关联规则挖掘技术已经被广泛应用于金融行业企业中用以预测客户的需求，各银行在自己的ATM 机上通过捆绑客户可能感兴趣的信息供用户了解并获取相应信
朴素贝叶斯： 有以下几个地方需要注意： 1. 如果给出的特征向量长度可能不同，这是需要归一化为通长度的向量（这里以文本分类为例），比如说是句子单词的话，则长度为整个词汇量的长度，对应位置是该单词出现的次数。 2. 计算公式如下： 其中一项条件概率可以通过朴素贝叶斯条件独立展开。要注意一点就是的计算方法，而由朴素贝叶斯的前提假设可知， = ，因此一般有两种，一种是在类别为ci的那些样本集中，找到wj出现次数的总和，然后除以该样本的总和；第二种方法是类别为ci的那些样本集中，找到wj出现次数的总和，然后除以该样本中所有特征出现次数的总和。 3. 如果中的某一项为0，则其联合概率的乘积也可能为0，即2中公式的分子为0，为了避免这种现象出现，一般情况下会将这一项初始化为1，当然为了保证概率相等，分母应对应初始化为2（这里因为是2类，所以加2，如果是k类就需要加k，术语上叫做laplace 光滑, 分母加k的原因是使之满足全概率公式）。 朴素贝叶斯的优点： 对小规模的数据表现很好，适合多分类任务，适合增量式训练。 缺点： 对输入数据的表达形式很敏感。 决策树： 决策树中很重要的一点就是选择一个属性进行分枝，因此要注意一下信息增益的计算公式，并深入理解它。 信息熵的计算公式如下:
其中的n代表有n个分类类别（比如假设是2类问题，那么n=2）。分别计算这2类样本在总样本中出现的概率p1和p2，这样就可以计算出未选中属性分枝前的信息熵。 现在选中一个属性xi用来进行分枝，此时分枝规则是：如果xi=vx的话，将样本分到树的一个分支；如果不相等则进入另一个分支。很显然，分支中的样本很有可能包括2个类别，分别计算这2个分支的熵H1和H2,计算出分枝后的总信息熵H’=p1*H1+p2*H2.，则此时的信息增益ΔH=H-H’。以信息增益为原则，把所有的属性都测试一边，选择一个使增益最大的属性作为本次分枝属性。 决策树的优点： 计算量简单，可解释性强，比较适合处理有缺失属性值的样本，能够处理不相关的特征； 缺点： 容易过拟合（后续出现了随机森林，减小了过拟合现象）； Logistic回归： Logistic是用来分类的，是一种线性分类器，需要注意的地方有： 1. logistic函数表达式为： 其导数形式为： 2. logsitc回归方法主要是用最大似然估计来学习的，所以单个样本的后验概率为： 到整个样本的后验概率：
数据挖掘十大算法 数据挖掘十大算法—K 近邻算法 k -近邻算法是基于实例的学习方法中最基本的，先介绍基于实例学习的相关概念。 一、基于实例的学习。 1、已知一系列的训练样例，很多学习方法为目标函数建立起明确的一般化描述；但与此不同，基于实例的学习方法只是简单地把训练样例存储起来。 从这些实例中泛化的工作被推迟到必须分类新的实例时。每当学习器遇到一个新的查询实例，它分析这个新实例与以前存储的实例的关系，并据此把一个目标函数值赋给新实例。 2、基于实例的方法可以为不同的待分类查询实例建立不同的目标函数逼近。事实上，很多技术只建立目标函数的局部逼近，将其应用于与新查询实例邻近的实例，而从不建立在整个实例空间上都表现良好的逼近。当目标函数很复杂，但它可用不太复杂的局部逼近描述时，这样做有显著的优势。 3、基于实例方法的不足： （1）分类新实例的开销可能很大。这是因为几乎所有的计算都发生在分类时，而不是在第一次遇到训练样例时。所以，如何有效地索引训练样例，以减少查询时所需计算是一个重要的实践问题。（2）当从存储器中检索相似的训练样例时，它们一般考虑实例的所有属性。如果目标概念仅依赖于很多属性中的几个时，那么真正最“相似”的实例之间很可能相距甚远。 二、k-近邻法基于实例的学习方法中最基本的是k -近邻算法。这个算法假定所有的实例对应于n 维欧氏空间?n 中的点。一个实例的最近邻是根据标准欧氏距离定义的。更精确地讲，把任意的实例x 表示为下面的特征向量：其中a r (x ) 表示实例x 的第r 个属性值。那么两个实例x i 和x j 间的距离定义为d (x i , x j ) ，其中： 说明： 1、在最近邻学习中，目标函数值可以为离散值也可以为实值。 2、我们先考虑学习以下形式的离散目标函数。其中V 是有限集合 {v 1，... v s }。下表给出了逼近离散目标函数的k-近邻算法。 3、正如下表中所指出的，这个算法的返回值f' (x q ) 为对f (x q ) 的估计，它就是距离x q 最近的k 个训练样例中最普遍的f 值。 4、如果我们选择k =1，那么“1-近邻算法”
数据挖掘经典案例 当前，市场竞争异常激烈，各商家企业为了能在竞争中占据优势，费劲心思。使用过OLAP技术的企业都知道，OLAP技术能给企业带来新的生机和活力。OLAP技术把企业大量的数据变成了客户需要的信息，把这些信息变成了价值，提高了企业的产值和效益，增强了客户自身的竞争实力。 “啤酒与尿布”的故事家喻户晓，在IT界里，几乎是数据挖掘的代名词，那么各商家企业受了多少启发，数据挖掘又给他们带来了多少价值呢？ 客户需求 客户面对大量的信息，用OLAP进行多维分析。如：一个网上书店，用OLAP技术可以浏览到什么时间，那个类别的客户买了多少书等信息，如果想动态的获得深层次的信息，比如：哪些书籍可以打包推荐，哪些书籍可以在销售中关联推出等等，就要用到数据挖掘技术了。 当客户在使用OLAＰ技术进行数据的多维分析的时候，联想到“啤酒与尿布”的故事，客户不禁会有疑问，能不能通过数据挖掘来对数据进行深层次的分析呢，能不能将数据挖掘和OLAP结合起来进行分析呢？ SQL Server 2005 数据挖掘： SQL Server 2005的Data Mining是SQL Server2005分析服务（Analysis Services）中的一部分。数据挖掘通常被称为“从大型数据库提取有效、可信和可行信息的过程”。换言之，数据挖掘派生数据中存在的模式和趋势。这些模式和趋势可以被收集在一起并定义为挖掘模型。挖掘模型可以应用于特定的业务方案，例如：预测销售额、向特定客户发送邮件、确定可能需要搭售的产品、查找客户将产品放入购物车的顺序序列。 Microsoft 决策树算法、Microsoft Naive Bayes 算法、Microsoft 聚类分析算法、Microsoft 神经网络算法 (SSAS)，可以预测离散属性，例如，预测目标邮件活动的收件人是否会购买某个产品。 Microsoft 决策树算法、Microsoft 时序算法可以预测连续属性，预测连续属性，例如，预测下一年的销量。 Microsoft 顺序分析和聚类分析算法预测顺序，例如，执行公司网站的点击流分析。 Microsoft 关联算法、Microsoft 决策树算法查找交易中的常见项的组，例如，使用市场篮分析来建议客户购买其他产品。 Microsoft 聚类分析算法、Microsoft 顺序分析和聚类分析算法，查找相似项的组，例如，将人口统计数据分割为组以便更好地理解属性之间的关系。 巅峰之旅之案例一：网上书店关联销售 提出问题 网上书店现在有了很强的市场和比较固定的大量的客户。为了促进网上书店的销售量的增长，各网上书店采取了各种方式，给客户提供更多更丰富的书籍，提供更优质服务，等方式吸引更多的读者。
国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. 不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。 1. C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。 2. The k-means algorithm 即K-Means算法 k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 3. Support vector machines 支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。它是一种監督式學習的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。van der Walt 和 Barnard 将支持向量机和其他分类器进行了
1、C4.5 机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。 决策树学习也是数据挖掘中一个普通的方法。在这里，每个决策树都表述了一种树型结构，他由他的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。当不能再进行分割或一个单独的类可以被应用于某一分支时，递归过程就完成了。另外，随机森林分类器将许多决策树结合起来以提升分类的正确率。决策树同时也可以依靠计算条件概率来构造。决策树如果依靠数学的计算方法可以取得更加理想的效果。决策树一般都是自上而下的来生成的。 选择分割的方法有好几种，但是目的都是一致的：对目标类尝试进行最佳的分割。从根到叶子节点都有一条路径，这条路径就是一条“规则”。决策树可以是二叉的，也可以是多叉的。对每个节点的衡量： 1)通过该节点的记录数 2)如果是叶子节点的话，分类的路径 3)对叶子节点正确分类的比例。 有些规则的效果可以比其他的一些规则要好。由于ID3算法在实际应用中存在一些问题，于是Quilan提出了C4.5算法，严格上说C4.5只能是ID3的一个改进算法。相信大家对ID3算法都很.熟悉了，这里就不做介绍。 C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。
Data Mining: What Is Data Mining ? https://www.doczj.com/doc/d73312220.html,/faculty/jason.frand/teacher/technologies/palace/datamining .htm Data Mining - An Introduction https://www.doczj.com/doc/d73312220.html,/library/weekly/aa100700a.htm?iam=excite_1&terms=data+m ining Data Mining - An Introduction Student Notes https://www.doczj.com/doc/d73312220.html,/tec/courses/datamining/stu_notes/dm_book_1.html Data Mining Overview https://www.doczj.com/doc/d73312220.html,/dm/index.php3 Data Mining - Award Winning Software https://www.doczj.com/doc/d73312220.html,/?source=goto Data Mining With MicroStrategy Best In Business Intelligence https://www.doczj.com/doc/d73312220.html,/Software/Mining.asp?CID=1818dm Data Mining, Web Mining and Knowledge Discovery Directory https://www.doczj.com/doc/d73312220.html,/ Data Miners Home Page https://www.doczj.com/doc/d73312220.html,/ Data Mining and Knowledge Discovery Journal https://www.doczj.com/doc/d73312220.html,/usama/datamine/ Data Mining and Knowledge Discovery Journal https://www.doczj.com/doc/d73312220.html,/issn/1384-5810
第五章 经典的机器学习案例 机器学习是一门成熟的学科，它所能解决的问题涵盖多种行业。本章介绍了四种经典的机器学习算法，它们所关心的重点在于机器学习是如何将统计学和数据挖掘连接起来的。通过学习本章，读者可以见识到机器学习的特殊魅力，并明白机器学习与其他学科的异同。使读者可以熟练地应用机器学习算法来解决实际问题是本章的目标。 5.1 机器学习综述 在正式开始了解机器学习之前，我们首先要搞清楚这样一个问题：世界上是不是所有的问题都可以使用一行一行清楚无误的代码解决？举个例子，倘若我们想让一个机器人完成出门去超市买菜并回家这一任务，我们能不能在程序里详详细细地把机器人所有可能遇到的情况以及对策都写下来，好让机器人一条一条按着执行？ 答案是“很难”。机器人在路上可能遭遇塑料袋儿、石头、跑动的儿童等障碍物，在超市可能遇到菜卖完了、菜篮挪动了位置等问题，把这些问题全部罗列出来是不太可能的，因此我们就难以使用硬性的、固定的程序来命令机器人完成这件事，我们需要的是一种灵活的、可以变化的程序。就像你去买菜时不用你妈告诉你路上看见有人打架要躲开，你就知道要躲开一样（即便你以前从来没有遇见过这种情况），我们希望机器人也可以根据经验学习到正确的做法，而不是必须依赖程序员一条一条地输入“IF……THEN……”。 美国人塞缪尔设计的下棋程序是另一个的经典机器学习算法。塞缪尔设计了一个可以依靠经验积累概率知识的下棋程序，一开始这个程序毫无章法，但四年以后，它就能够打败塞缪尔了，又过了三年，它战胜了美国的围棋冠军。这个下棋程序进步的方式和人类学习下棋的过程非常类似，如何让机器像人类一样学习，正是机器学习关心的事情。 不难想象，机器学习是一门多领域交叉的学科，它主要依赖统计学、概率论、逼近论等数学学科，同时也依赖算法复杂度、编译原理等计算机学科。通俗的说，机器学习首先将统计学得到的统计理论拿来进一步研究，然后改造成适合编译成程序的机器学习算法，最终才会应用到实际中。但机器学习和统计学仍有不同的地方，这种差异主要在于统计学关心理论是否完美，而机器学习关心实际效果是否良好。同时，机器学习侧重于归纳和总结，而不是演绎。 机器学习将统计学的研究理论改造成能够移植在机器上的算法，数据挖掘将机器学习的成果直接拿来使用。从这一意义上来说，机器学习是统计学和数据挖掘之间的桥梁。机器学习也是人工智能的核心，机器学习算法普遍应用于人工智能的各个领域。此外，机器学习和模式识别具有并列的关系，它们一个注重模仿人类的学习方式，一个注重模仿人类认识世界的方式。因此机器学习、数据挖掘、人工智能和模式识别等本来就属于一个不可分的整体，离开其他学科的支持，任何学科都难以独立生存下去。 本章介绍了语义搜索、顺序分析、文本分析和协同过滤这四种经典的机器学习算法，它们不仅理论完善，同时也具有广泛的应用。通过本章的学习，读者将看到机器学习在各行各业中的神奇作用以及广阔前景，并学会如何使用机器学习算法来解决实际问题。
学习笔记5：数据预处理与数据挖掘十大经典算法 前言在介绍了数据挖掘的一般流程、常用方法、应用功能和数据可视化之后，在本篇博文中，笔者想要分享一些在数据挖掘开始之前要做的一些事——数据预处理。在第二部分中，笔者整理了数据挖掘中的十大经典算法，与读者们共享。两部分分别从《数据挖掘中数据预处理的方法与技术》一文与网络中引用而来，作为自己和读者朋友们的学习笔记。在第三部分阶段小结中，笔者对近期的学习进行了阶段性的总结。 一、数据预处理现实中数据大多数都是不完整、不一致的，无法直接进行数据挖掘，或直接影响了挖掘结果。为了提高数据挖掘质量和数据挖掘效率，产生了数据预处理技术。对数据进行预处理，不但可以节约大量的空间和时间而且得到的挖掘结果能更好地起到决策和预测作用。数据预处理一般包括：数据清理，数据集成，数据变换，数据归约等方法。这些数据预处理技术根据数据挖掘项目的需要和原始数据的特点，在数据挖掘之前有选择的单独使用或综合使用，可大大提高数据挖掘模式的质量，降低实际挖掘所需要的时间。数据预处理技术整理如下：1、数据清理数据清理是数据预处理中最花费时间、最乏味的，但也是最重要的一步。该步骤可以有效地减少学习过程中可能出现相互矛盾的情
况。数据清理主要处理缺失数据，噪声数据，识别、删除孤立点。数据清理的基本方法有：（1）缺失数据处理：目前最常用的方法是使用最可能的值填充缺失值，比如可以用回归、贝叶斯形式化方法工具或判定树归纳等确定缺失值。这类方法依靠现有的数据信息来推测缺失值，使缺失值有更大的机会保持与其他属性之间的联系。还有其他一些方法来处理缺失值，如用一个全局常量替换缺失值、使用属性的平均值填充缺失值或将所有元组按某些属性分类，然后用同一类中属性的平均值填充缺失值。如果缺失值很多，这些方法可能误导挖掘结果。如果缺失值很少，可以忽略缺失数据。（2）噪声数据处理：噪声是一个测量变量中的随机错误或偏差，包括错误的值或偏离期望的孤立点值。目前最广泛的是应用数据平滑技术处理，具体包括：分箱技术，将存储的值分布到一些箱中，用箱中的数据值来局部平滑存储数据的值。具体可以采用按箱平均值平滑、按箱中值平滑和按箱边界平滑；回归方法，可以找到恰当的回归函数来平滑数据。线性回归要找出适合两个变量的“最佳”直线，使得一个变量能预测另一个。多线性回归涉及多个变量，数据要适合一个多维面；计算机检查和人工检查结合方法，可以通过计算机将被判定数据与已知的正常值比较，将差异程度大于某个阈值的模式输出到一个表中，然后人工审核表中的模式，识别出孤立点；聚类技术，将类似的值组织成群或“聚类”，落在
Apriori算法 一、Apriori算法简介：Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。Apriori（先验的，推测的）算法应用广泛，可用于消费市场价格分析，猜测顾客的消费习惯；网络安全领域中的入侵检测技术；可用在用于高校管理中，根据挖掘规则可以有效地辅助学校管理部门有针对性的开展贫困助学工作；也可用在移动通信领域中，指导运营商的业务运营和辅助业务提供商的决策制定。 二、挖掘步骤： 1.依据支持度找出所有频繁项集（频度） 2.依据置信度产生关联规则（强度） 三、基本概念 对于A->B ①支持度：P(A ∩B)，既有A又有B的概率 ②置信度： P(B|A)，在A发生的事件中同时发生B的概率p(AB)/P(A)例如购物篮分析：牛奶?面包 例子：[支持度：3%，置信度：40%] 支持度3%：意味着3%顾客同时购买牛奶和面包 置信度40%：意味着购买牛奶的顾客40%也购买面包 ③如果事件A中包含k个元素，那么称这个事件A为k项集事件A满足最小支持度阈值的事件称为频繁k项集。 ④同时满足最小支持度阈值和最小置信度阈值的规则称为强规则 四、实现步骤 Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法Apriori使用一种称作逐层搜索的迭代方法，“K-1项集”用于搜索“K项集”。 首先，找出频繁“1项集”的集合，该集合记作L1。L1用于找频繁“2项集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K项集”。找每个Lk都需要一次数据库扫描。 核心思想是：连接步和剪枝步。连接步是自连接，原则是保证前k-2项相同，并按照字典顺序连接。剪枝步，是使任一频繁项集的所有非空子集也必须是频繁的。反之，如果某 个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。 简单的讲，1、发现频繁项集，过程为（1）扫描（2）计数（3）比较（4）产生频繁项集（5）连接、剪枝，产生候选项集重复步骤（1）~（5）直到不能发现更大的频集 2、产生关联规则，过程为:根据前面提到的置信度的定义，关联规则的产生如下： （1）对于每个频繁项集L，产生L的所有非空子集； （2）对于L的每个非空子集S，如果 P（L）/P（S）≧min_conf 则输出规则“SàL-S” 注：L-S表示在项集L中除去S子集的项集
各种分类算法比较 最近在学习分类算法，顺便整理了各种分类算法的优缺点。 1决策树（Decision Trees）的优缺点 决策树的优点： 一、决策树易于理解和解释.人们在通过解释后都有能力去理解决策树所表达的意义。 二、对于决策树，数据的准备往往是简单或者是不必要的.其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。 三、能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一。 四、决策树是一个白盒模型。如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。 五、易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。 六、在相对短的时间内能够对大型数据源做出可行且效果良好的结果。 七、可以对有许多属性的数据集构造决策树。 八、决策树可很好地扩展到大型数据库中，同时它的大小独立于数据库的大小。 决策树的缺点： 一、对于那些各类别样本数量不一致的数据，在决策树当中,信息增益的结果偏向于那些具有更多数值的特征。 二、决策树处理缺失数据时的困难。 三、过度拟合问题的出现。
四、忽略数据集中属性之间的相关性。 2 人工神经网络的优缺点 人工神经网络的优点：分类的准确度高,并行分布处理能力强,分布存储及学习能力强，对噪声神经有较强的鲁棒性和容错能力，能充分逼近复杂的非线性关系，具备联想记忆的功能等。人工神经网络的缺点：神经网络需要大量的参数，如网络拓扑结构、权值和阈值的初始值；不能观察之间的学习过程，输出结果难以解释，会影响到结果的可信度和可接受程度；学习时间过长,甚至可能达不到学习的目的。 3 遗传算法的优缺点 遗传算法的优点： 一、与问题领域无关切快速随机的搜索能力。 二、搜索从群体出发，具有潜在的并行性，可以进行多个个体的同时比较，鲁棒性好。 三、搜索使用评价函数启发，过程简单。 四、使用概率机制进行迭代，具有随机性。 五、具有可扩展性，容易与其他算法结合。 遗传算法的缺点： 一、遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码, 二、另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验.没有能够及时利用网络的反馈信息,故算法的搜索速度比较慢，要得要较精确的解需要较多的训练时间。 三、算法对初始种群的选择有一定的依赖性，能够结合一些启发算法进行改进。