十大经典数据挖掘算法（详细说明）

                                                       数据挖掘十大经典算法

 一、 C4.5  C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3 算法.   C4.5算法继承了ID3算法的长处。并在下面几方面对ID3算法进行了改进：  1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足。  2) 在树构造过程中进行剪枝；  3) 可以完毕对连续属性的离散化处理；  4) 可以对不完整数据进行处理。  C4.5算法有例如以下长处：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，须要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。

1、机器学习中。决策树是一个预測模型。他代表的是对象属性与对象值之间的一种映射关系。树中每一个节点表示某个对象，而每一个分叉路径则代表的某个可能的属性值，而每一个叶结点则 相应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出。若欲有复数输出，能够建立独立的决策树以处理不同输出。

  2、 从数据产生决策树的机器学习技术叫做决策树学习,  通俗说就是决策树。  3、决策树学习也是数据挖掘中一个普通的方法。在这里，每一个决策树都表述了一种树型结构，他由他的分支来对该类型的对象依靠属性进行分类。每一个决策树能够依靠对源数据库的切割 进行数据測试。

这个过程能够递归式的对树进行修剪。

当不能再进行切割或一个单独的类能够被应用于某一分支时。递归过程就完毕了。

另外。随机森林分类器将很多决策树结合起来 以提升分类的正确率。

决策树是怎样工作的？  1、决策树一般都是自上而下的来生成的。

  2、选择切割的方法有好几种，可是目的都是一致的：对目标类尝试进行最佳的切割。

  3、从根到叶子节点都有一条路径，这条路径就是一条―规则  4、决策树能够是二叉的，也能够是多叉的。  对每一个节点的衡量：  1)         通过该节点的记录数  2)         假设是叶子节点的话，分类的路径  3)         对叶子节点正确分类的比例。  有些规则的效果能够比其它的一些规则要好。

  因为ID3算法在实际应用中存在一些问题。于是Quilan提出了C4.5算法，严格上说C4.5仅仅能是ID3的一个改进算法。相信大家对ID3算法都非常.熟悉了，这里就不做介绍。  C4.5算法继承了ID3算法的长处，并在下面几方面对ID3算法进行了改进：  1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝。  3) 可以完毕对连续属性的离散化处理；  4) 可以对不完整数据进行处理。  C4.5算法有例如以下长处：产生的分类规则易于理解，准确率较高。

其缺点是：在构造树的过程中。须要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。

此外，C4.5仅仅适合于 可以驻留于内存的数据集。当训练集大得无法在内存容纳时程序无法执行。  来自搜索的其它内容：   C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法.  分类决策树算法是从大量事例中进行提取分类规则的自上而下的决策树. 决策树的各部分是:               根:    学习的事例集.               枝:    分类的判定条件.               叶:    分好的各个类. 

 ID3算法     1.概念提取算法CLS  1)      初始化參数C={E},E包含全部的样例,为根.  2)        IF      C中的任一元素e同属于同一个决策类则创建一个叶子                     节点YES终止.             ELSE      依启示式标准,选择特征Fi={V1,V2,V3,．．．Vn}并创建                         判定节点     划分C为互不相交的N个集合C1,C2,C3,．．．,Cn。  3)      对任一个Ci递归.      2.      ID3算法  1)      随机选择C的一个子集W    (窗体).  2)      调用CLS生成W的分类树DT(强调的启示式标准在后).  3)      顺序扫描C搜集DT的意外(即由DT无法确定的样例).  4)      组合W与已发现的意外,形成新的W.      5)      反复2)到4),直到无例外为止.     启示式标准:         仅仅跟本身与其子树有关,採取信息理论用熵来量度.         熵是选择事件时选择自由度的量度,其计算方法为                 P    =    freq(Cj,S)/|S|;         INFO(S)=    -    SUM(    P*LOG(P)    )    ;        SUM()函数是求j 从1到n和.         Gain(X)=Info(X)-Infox(X);         Infox(X)=SUM(    (|Ti|/|T|)*Info(X);  为保证生成的决策树最小,ID3 算法在生成子树时,选取使生成的子树的熵(即Gain(S))最小的 的特征来生成子树.       3、  ID3算法对数据的要求  1）.      全部属性必须为离散量.  2）.      全部的训练例的全部属性必须有一个明白的值.  3）.      同样的因素必须得到同样的结论且训练例必须唯一.        C4.5对ID3算法的改进:         1.      熵的改进,加上了子树的信息.               Split_Infox(X)=    -    SUM(      (|T|/|Ti|    )    *LOG(|Ti|/|T|)      );               Gain    ratio(X)=      Gain(X)/Split    Infox(X);          2.      在输入数据上的改进.           1)  因素属性的值能够是连续量,C4.5 对其排序并分成不同的集合后依照ID3 算法当作离散量进行处理,但结论属性的值必须是离散值.         2)    训练例的因素属性值能够是不确定的,以    ?    表示,但结论必须是确定的         3.      对已生成的决策树进行裁剪,减小生成树的规模.

二、数据挖掘十大经典算法(2) k-means  术语“k-means”最早是由James MacQueen在1967年提出的。这一观点能够追溯到1957年 Hugo Steinhaus所提出的想法。1957年。斯图亚特·劳埃德最先提出这一标准算法，当初是作为一门应用于脉码调制的技术,直到1982年，这一算法才在贝尔实验室被正式提出。1965年。 E.W.Forgy发表了一个本质上是同样的方法。1975年和1979年。Hartigan和Wong分别提出了一个更高效的版本号。

算法描写叙述 输入：簇的数目k；包括n个对象的数据集D。

输出：k个簇的集合。

方法：

从D中随意选择k个对象作为初始簇中心； repeat; 依据簇中对象的均值。将每一个对象指派到最相似的簇； 更新簇均值。即计算每一个簇中对象的均值； 计算准则函数； until准则函数不再发生变化。

算法的性能分析    1）长处 （1）k-平均算法是解决聚类问题的一种经典算法，算法简单、高速。 （2）对处理大数据集，该算法是相对可伸缩的和高效率的。由于它的复杂度大约是O（nkt），当中n是全部对象的数目，k是簇的数目,t是迭代的次数。

通常k