数据挖掘10大算法产生过程 1 三步鉴定流程 2 18种通过审核的候选算法 3 算法陈述 4 数据挖掘10大算法：一览 5 开放式讨论

除一人未参与外,其他获奖者均给出了算法的提名。 每个提名中均需同时给出以下信息： 1. 提名 (Nominations) 2006年9月在香港举办的国际会议ICDM会议上,邀请ACM KDD创新大奖 (Innovation Award)和 IEEE ICDM研究贡献奖(Research Contributions Award)的获奖 者们来参与数据挖掘10大算法的选举,每人提名10种他认为最重要的算法。 除一人未参与外,其他获奖者均给出了算法的提名。 每个提名中均需同时给出以下信息： - (a) 算法名称 - (b) 提名理由摘要 - (c) 算法的代表性论文 每个提名算法都应该被相关领域的研究者广泛引用和使用，每位提名者给出的同类 算法应该是数据挖掘重要应用领域的代表。 2. 审核 (Verification) 在2006年10月,通过Google Scholar对每个提名算法的引用情况进行了审核,从候选名 单中删除了低于50篇论文引用的算法 最终剩下18种提名算法通过了审核,它们分属10类数据挖掘主题 3. 投票 (Voting) 邀请更多的专业人士来从这些候选算法中投票选出10大算法，他们包括 - (a) KDD-06、ICDM ‘06和SDM ’06的程序委员会成员(Program Committee members) - (b) ACM KDD创新大奖和IEEE ICDM研究贡献奖的获奖者们 根据票数排名筛选出10大算法 (如果票数相同，则按字母顺序进行排名)

数据挖掘10大算法产生过程 1 三步鉴定流程 2 18种通过审核的候选算法 3 算法陈述 4 数据挖掘10大算法：一览 5 开放式讨论

统计学习(Statistical Learning) 18种通过审核的候选算法 分类(Classification) C4.5: Quinlan, J. R. 1993. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers Inc. CART: L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA, 1984. K Nearest Neighbours (kNN): Hastie, T. and Tibshirani, R. 1996. Discriminant Adaptive Nearest Neighbor Classification. IEEE Trans. Pattern Anal. Mach. Intell. (TPAMI). 18, 6 (Jun. 1996), 607-616. Naive Bayes Hand, D.J., Yu, K., 2001. Idiot's Bayes: Not So Stupid After All? Internat. Statist. Rev. 69, 385-398. 统计学习(Statistical Learning) SVM: Vapnik, V. N. 1995. The Nature of Statistical Learning Theory. Springer- Verlag New York, Inc. EM: McLachlan, G. and Peel, D. (2000). Finite Mixture Models. J. Wiley, New York. 关联分析(Association Analysis) Apriori: Rakesh Agrawal,Ramakrishnan Srikant. Fast Algorithms for Mining Association Rules. In VLDB '94. FP-Tree: Han, J., Pei, J., and Yin, Y. 2000. Mining frequent patterns without candidate generation. In SIGMOD '00. C4.5 CART kNN Naïve Bayes SVM EM Apriori FP-Tree

袋装与推进(Bagging and Boosting) 18种通过审核的候选算法 §链接挖掘(Link Mining) PageRank: Brin, S. and Page, L. 1998. The anatomy of a large-scale hypertextual Web search engine. In WWW-7, 1998. HITS: Kleinberg, J. M. 1998. Authoritative sources in a hyperlinked environment. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998. 聚类(Clustering) K-Means: MacQueen, J. B., Some methods for classification and analysis of multivariate observations, in Proc. 5th Berkeley Symp. Mathematical Statistics and Probability, 1967. BIRCH Zhang, T., Ramakrishnan, R., and Livny, M. 1996. BIRCH: an efficient data clustering method for very large databases. In SIGMOD '96. 袋装与推进(Bagging and Boosting) AdaBoost: Freund, Y. and Schapire, R. E. 1997. A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci. 55, 1 (Aug. 1997), 119-139. PageRank HITS K-Means BIRCH HITS算法和PageRank 算法可以说是搜索引擎链接分析的两个最基础且最重要的算法。从以上对两个算法的介绍可以看出，两者无论是在基本概念模型，还是计算思路及技术实现细节都有很大的不同，下面对两者之间的差异进行逐一说明。 HITS 算法是与用户输入的查询请求密切相关的，而PageRank 与查询请求无关。所以，HITS 算法可以单独作为相似性计算评价标准，而PageRank 必须结合内容相似性计算才可以用来对网页相关性进行评价。 HITS 算法因为与用户查询密切相关，所以必须在接收到用户查询后进行实时计算，计算效率较低；而PageRank 则可以在爬虫抓取完成后离线计算，在线直接使用计算结果，计算效率较高。 HITS 算法的计算对象数量较少，只需计算扩展集合内网页之间的链接关系；而PageRank 是全局性算法，对所有互联网页面节点进行处理。 从两者的计算效率和处理对象集合大小来比较，PageRank 更适合部署在服务器端，而HITS 算法更适合部署在客户端。 HITS 算法存在主题泛化问题，所以更适合处理具体的用户查询；而PageRank 算法在处理宽泛的用户查询时更有优势。 HITS 算法在计算时，对于每个页面需要计算两个分值，而PageRank 算法只需计算一个分值即可；在搜索引擎领域，更重视HITS 算法计算出的Authority 权值，但是在很多应用HITS 算法的其他领域，Hub 分值也有很重要的作用。 从链接反作弊的角度来说，PageRank 从机制上优于HITS 算法，而HITS 算法更易遭受链接作弊的影响。 HITS 算法结构不稳定，当对扩展网页集合内链接关系做出很小改变，则对最终排名有很大影响；而PageRank 算法相对HITS 而言表现稳定，其根本原因在于PageRank 计算时的远程跳转。   BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies）全称是：利用层次方法的平衡迭代规约和聚类。BIRCH算法是1996年由Tian Zhang提出来的，参考文献1。首先，BIRCH是一种聚类算法，它最大的特点是能利用有限的内存资源完成对大数据集的高质量的聚类，同时通过单遍扫描数据集能最小化I/O代价。           首先解释一下什么是聚类，从统计学的观点来看，聚类就是给定一个包含N个数据点的数据集和一个距离度量函数F（例如计算簇内每两个数据点之间的平均距离的函数），要求将这个数据集划分为K个簇（或者不给出数量K，由算法自动发现最佳的簇数量），最后的结果是找到一种对于数据集的最佳划分，使得距离度量函数F的值最小。从机器学习的角度来看，聚类是一种非监督的学习算法，通过将数据集聚成n个簇，使得簇内点之间距离最小化，簇之间的距离最大化。           BIRCH算法特点：           （1）BIRCH试图利用可用的资源来生成最好的聚类结果，给定有限的主存，一个重要的考虑是最小化I/O时间。           （2）BIRCH采用了一种多阶段聚类技术：数据集的单边扫描产生了一个基本的聚类，一或多遍的额外扫描可以进一步改进聚类质量。           （3）BIRCH是一种增量的聚类方法，因为它对每一个数据点的聚类的决策都是基于当前已经处理过的数据点，而不是基于全局的数据点。           （4）如果簇不是球形的，BIRCH不能很好的工作，因为它用了半径或直径的概念来控制聚类的边界。 AdaBoost

§序列模式(Sequential Patterns) 18种通过审核的候选算法 §序列模式(Sequential Patterns) GSP: Srikant, R. and Agrawal, R. 1996. Mining Sequential Patterns: Generalizations and Performance Improvements. In Proceedings of the 5th International Conference on Extending Database Technology, 1996. PrefixSpan: J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayaland M-C. Hsu. PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth. In ICDE '01. 集成挖掘(Integrated Mining) CBA: Liu, B., Hsu, W. and Ma, Y. M. Integrating classification and association rule mining. KDD-98. 粗糙集(Rough Sets) Finding reduct: Zdzislaw Pawlak, Rough Sets: Theoretical Aspects of Reasoning about Data, KluwerAcademic Publishers, Norwell, MA, 1992 图挖掘(Graph Mining) gSpan: Yan, X. and Han, J. 2002. gSpan: Graph-Based Substructure Pattern Mining. In ICDM '02. GSP PrefixSpan CBA AprioriAll算法属于Apriori类算法，其基本思想为首先遍历序列数据库生成候选序列并利用Apriori性质进行剪枝得到频繁序列。每次遍历都是通过连接上次得到的频繁序列生成新的长度加1的候选序列，然后扫描每个候选序列验证其是否为频繁序列。 GSP（generalized sequential pattern）算法是AprioriAll算法的扩展算法，其算法的执行过程和AprioriAll类似，最大的不同在于GSP引入了时间约束、滑动时间窗和分类层次技术，增加了扫描的约束条件，有效地减少了需要扫描的候选序列的数量。此外GSP利用哈希树来存储候选序列，减少了需要扫描的序列数量。 FreeSpan算法是基于模式投影的序列挖掘算法，其基本思想：利用当前挖掘的频繁序列集将序列数据库递归地投影到一组更小的投影数据库上，分别在每个投影数据库上增长子序列。这一过程对数据和待检验的频繁模式集都进行了分割，并且每一次检验限制在与其相符合的更小投影数据库中。 PrefixSpan是FreeSpan的改进算法，即通过前缀投影挖掘序列模式。其基本思想：投影时不考虑所有可能出现的频繁子序列，只检查前缀序列，然后把相应的后缀投影成投影数据库。每个投影数据库中，只检查局部频繁模式，在整个过程中不需要生成候选序列。 CBA算法作为分类算法，他的分类情况也就是给定一些预先知道的属性，然后叫你判断出他的决策属性是哪个值。判断的依据就是Apriori算法挖掘出的频繁项，如果一个项集中包含预先知道的属性，同时也包含分类属性值，然后我们计算此频繁项能否导出已知属性值推出决策属性值的关联规则，如果满足规则的最小置信度的要求，那么可以把频繁项中的决策属性值作为最后的分类结果。具体的算法细节如下： 1、输入数据记录，就是一条条的属性值。 2、对属性值做数字的替换(按照列从上往下寻找属性值)，就类似于Apriori中的一条条事务记录。 3、根据这个转化后的事务记录，进行Apriori算法计算，挖掘出频繁项集。 4、输入查询的属性值，找出符合条件的频繁项集(需要包含查询属性和分类决策属性)，如果能够推导出这样的关联规则，就算分类成功，输出分类结果 算法原理 说实话，gSpan算法在我最近学习的算法之中属于非常难的那种，因为要想实现他，必须要明白他的原理，而这就要花很多时间去明白算法的一些定义，比如dfs编码，最右路径这样的概念。所以，我们应该先知道算法整体的一个结构。 1、遍历所有的图，计算出所有的边和点的频度。 2、将频度与最小支持度数做比较，移除不频繁的边和点。 3、重新将剩下的点和边按照频度进行排序，将他们的排名号给边和点进行重新标号。 4、再次计算每条边的频度，计算完后，然后初始化每条边，并且进行此边的subMining()挖掘过程。 subMining的过程 1、根据graphCode重新恢复当前的子图 2、判断当前的编码是否为最小dfs编码，如果是加入到结果集中，继续在此基础上尝试添加可能的边，进行继续挖掘 3、如果不是最小编码，则此子图的挖掘过程结束。 DFS编码 gSpan算法对图的边进行编码，采用E(v0,v1,A,B,a)的方式，v0,v1代表的标识，你可以看做就是点的id,A,B可以作为点的标号，a为之间的边的标号，而一个图就是由这样的边构成的，G{e1, e2, e3,.....}，而dfs编码的方式就是比里面的五元组的元素，我这里采用的规则是，从左往右依次比较大小，如果谁先小于另一方，谁就算小，图的比较算法同样如此，具体的规则可以见我后面代码中的注释。但是这个规则并不是完全一致的，至少在我看的相关论文中有不一样的描述存在。 生成subGraph 生成子图的进行下一次挖掘的过程也是gSpan算法中的一个难点，首先你要对原图进行编码，找到与挖掘子图一致的编码，找到之后，在图的最右路径上寻找可以扩展的边，在最右路径上扩展的情况分为2种，1种为在最右节点上进行扩展，1种为在最右路径的点上进行扩展。2种情况都需要做一定的判断。 算法的技巧 算法在实现时，用的技巧比较多，有些也很不好理解，比如在dfs编码或找子边的过程中，用到了图id对于Edge中的五元组id的映射，这个会一开始没想到，还有怎么去描述一个图通过一定的数据结构。 算法的实现 此算法是借鉴了网上其他版本的实现，我是在看懂了人家代码的基础上，自己对其中的某些部分作了修改之后的。由于代码比较多，下面给出核心代码，全部代码在这里。 GSpanTool.java: [java] view plain copy package DataMining_GSpan;      import java.io.BufferedReader;   import java.io.File;   import java.io.FileReader;   import java.io.IOException;   import java.text.MessageFormat;   import java.util.ArrayList;   import java.util.HashMap;   import java.util.Map;   /**   * gSpan频繁子图挖掘算法工具类   *    * @author lyq   */   public class GSpanTool {       // 文件数据类型       public final String INPUT_NEW_GRAPH = "t";       public final String INPUT_VERTICE = "v";       public final String INPUT_EDGE = "e";       // Label标号的最大数量，包括点标号和边标号       public final int LABEL_MAX = 100;       // 测试数据文件地址       private String filePath;       // 最小支持度率       private double minSupportRate;       // 最小支持度数，通过图总数与最小支持度率的乘积计算所得       private int minSupportCount;       // 初始所有图的数据       private ArrayList<GraphData> totalGraphDatas;       // 所有的图结构数据       private ArrayList<Graph> totalGraphs;       // 挖掘出的频繁子图       private ArrayList<Graph> resultGraphs;       // 边的频度统计       private EdgeFrequency ef;       // 节点的频度       private int[] freqNodeLabel;       // 边的频度       private int[] freqEdgeLabel;       // 重新标号之后的点的标号数       private int newNodeLabelNum = 0;       // 重新标号后的边的标号数       private int newEdgeLabelNum = 0;       public GSpanTool(String filePath, double minSupportRate) {           this.filePath = filePath;           this.minSupportRate = minSupportRate;           readDataFile();       }       /**       * 从文件中读取数据       */       private void readDataFile() {           File file = new File(filePath);           ArrayList<String[]> dataArray = new ArrayList<String[]>();           try {               BufferedReader in = new BufferedReader(new FileReader(file));               String str;               String[] tempArray;               while ((str = in.readLine()) != null) {                   tempArray = str.split(" ");                   dataArray.add(tempArray);               }               in.close();           } catch (IOException e) {               e.getStackTrace();           }           calFrequentAndRemove(dataArray);        * 统计边和点的频度，并移除不频繁的点边，以标号作为统计的变量       *        * @param dataArray       *            原始数据      private void calFrequentAndRemove(ArrayList<String[]> dataArray) {           int tempCount = 0;           freqNodeLabel = new int[LABEL_MAX];           freqEdgeLabel = new int[LABEL_MAX];           // 做初始化操作           for (int i = 0; i < LABEL_MAX; i++) {               // 代表标号为i的节点目前的数量为0               freqNodeLabel[i] = 0;               freqEdgeLabel[i] = 0;           GraphData gd = null;           totalGraphDatas = new ArrayList<>();           for (String[] array : dataArray) {               if (array[0].equals(INPUT_NEW_GRAPH)) {                   if (gd != null) {                       totalGraphDatas.add(gd);                   }                   // 新建图                   gd = new GraphData();               } else if (array[0].equals(INPUT_VERTICE)) {                   // 每个图中的每种图只统计一次                   if (!gd.getNodeLabels().contains(Integer.parseInt(array[2]))) {                       tempCount = freqNodeLabel[Integer.parseInt(array[2])];                       tempCount++;                       freqNodeLabel[Integer.parseInt(array[2])] = tempCount;                   gd.getNodeLabels().add(Integer.parseInt(array[2]));                   gd.getNodeVisibles().add(true);               } else if (array[0].equals(INPUT_EDGE)) {                   if (!gd.getEdgeLabels().contains(Integer.parseInt(array[3]))) {                       tempCount = freqEdgeLabel[Integer.parseInt(array[3])];                       freqEdgeLabel[Integer.parseInt(array[3])] = tempCount;                   int i = Integer.parseInt(array[1]);                   int j = Integer.parseInt(array[2]);                   gd.getEdgeLabels().add(Integer.parseInt(array[3]));                   gd.getEdgeX().add(i);                   gd.getEdgeY().add(j);                   gd.getEdgeVisibles().add(true);           // 把最后一块gd数据加入           totalGraphDatas.add(gd);           minSupportCount = (int) (minSupportRate * totalGraphDatas.size());           for (GraphData g : totalGraphDatas) {               g.removeInFreqNodeAndEdge(freqNodeLabel, freqEdgeLabel,                       minSupportCount);        * 根据标号频繁度进行排序并且重新标号      private void sortAndReLabel() {           int label1 = 0;           int label2 = 0;           int temp = 0;           // 点排序名次           int[] rankNodeLabels = new int[LABEL_MAX];           // 边排序名次           int[] rankEdgeLabels = new int[LABEL_MAX];           // 标号对应排名           int[] nodeLabel2Rank = new int[LABEL_MAX];           int[] edgeLabel2Rank = new int[LABEL_MAX];               // 表示排名第i位的标号为i，[i]中的i表示排名               rankNodeLabels[i] = i;               rankEdgeLabels[i] = i;           for (int i = 0; i < freqNodeLabel.length - 1; i++) {               int k = 0;               label1 = rankNodeLabels[i];               temp = label1;               for (int j = i + 1; j < freqNodeLabel.length; j++) {                   label2 = rankNodeLabels[j];                   if (freqNodeLabel[temp] < freqNodeLabel[label2]) {                       // 进行标号的互换                       temp = label2;                       k = j;               if (temp != label1) {                   // 进行i，k排名下的标号对调                   temp = rankNodeLabels[k];                   rankNodeLabels[k] = rankNodeLabels[i];                   rankNodeLabels[i] = temp;           // 对边同样进行排序           for (int i = 0; i < freqEdgeLabel.length - 1; i++) {               label1 = rankEdgeLabels[i];               for (int j = i + 1; j < freqEdgeLabel.length; j++) {                   label2 = rankEdgeLabels[j];                   if (freqEdgeLabel[temp] < freqEdgeLabel[label2]) {                   temp = rankEdgeLabels[k];                   rankEdgeLabels[k] = rankEdgeLabels[i];                   rankEdgeLabels[i] = temp;           // 将排名对标号转为标号对排名           for (int i = 0; i < rankNodeLabels.length; i++) {               nodeLabel2Rank[rankNodeLabels[i]] = i;           for (int i = 0; i < rankEdgeLabels.length; i++) {               edgeLabel2Rank[rankEdgeLabels[i]] = i;           for (GraphData gd : totalGraphDatas) {               gd.reLabelByRank(nodeLabel2Rank, edgeLabel2Rank);           // 根据排名找出小于支持度值的最大排名值               if (freqNodeLabel[rankNodeLabels[i]] > minSupportCount) {                   newNodeLabelNum = i;               if (freqEdgeLabel[rankEdgeLabels[i]] > minSupportCount) {                   newEdgeLabelNum = i;           //排名号比数量少1，所以要加回来           newNodeLabelNum++;           newEdgeLabelNum++;        * 进行频繁子图的挖掘      public void freqGraphMining() {           long startTime =  System.currentTimeMillis();           long endTime = 0;           Graph g;           sortAndReLabel();           resultGraphs = new ArrayList<>();           totalGraphs = new ArrayList<>();           // 通过图数据构造图结构               g = new Graph();               g = g.constructGraph(gd);               totalGraphs.add(g);           // 根据新的点边的标号数初始化边频繁度对象           ef = new EdgeFrequency(newNodeLabelNum, newEdgeLabelNum);           for (int i = 0; i < newNodeLabelNum; i++) {               for (int j = 0; j < newEdgeLabelNum; j++) {                   for (int k = 0; k < newNodeLabelNum; k++) {                       for (Graph tempG : totalGraphs) {                           if (tempG.hasEdge(i, j, k)) {                               ef.edgeFreqCount[i][j][k]++;                           }                       }           Edge edge;           GraphCode gc;                       if (ef.edgeFreqCount[i][j][k] >= minSupportCount) {                           gc = new GraphCode();                           edge = new Edge(0, 1, i, j, k);                           gc.getEdgeSeq().add(edge);                           // 将含有此边的图id加入到gc中                           for (int y = 0; y < totalGraphs.size(); y++) {                               if (totalGraphs.get(y).hasEdge(i, j, k)) {                                   gc.getGs().add(y);                               }                           // 对某条满足阈值的边进行挖掘                           subMining(gc, 2);                      endTime = System.currentTimeMillis();           System.out.println("算法执行时间"+ (endTime-startTime) + "ms");           printResultGraphInfo();        * @param gc       *            图编码       * @param next       *            图所含的点的个数      public void subMining(GraphCode gc, int next) {           Edge e;           Graph graph = new Graph();           int id1;           int id2;           for(int i=0; i<next; i++){               graph.nodeLabels.add(-1);               graph.edgeLabels.add(new ArrayList<Integer>());               graph.edgeNexts.add(new ArrayList<Integer>());           // 首先根据图编码中的边五元组构造图           for (int i = 0; i < gc.getEdgeSeq().size(); i++) {               e = gc.getEdgeSeq().get(i);               id1 = e.ix;               id2 = e.iy;               graph.nodeLabels.set(id1, e.x);               graph.nodeLabels.set(id2, e.y);               graph.edgeLabels.get(id1).add(e.a);               graph.edgeLabels.get(id2).add(e.a);               graph.edgeNexts.get(id1).add(id2);               graph.edgeNexts.get(id2).add(id1);           DFSCodeTraveler dTraveler = new DFSCodeTraveler(gc.getEdgeSeq(), graph);           dTraveler.traveler();           if (!dTraveler.isMin) {               return;           // 如果当前是最小编码则将此图加入到结果集中           resultGraphs.add(graph);           Edge e1;           ArrayList<Integer> gIds;           SubChildTraveler sct;           ArrayList<Edge> edgeArray;           // 添加潜在的孩子边，每条孩子边所属的图id           HashMap<Edge, ArrayList<Integer>> edge2GId = new HashMap<>();           for (int i = 0; i < gc.gs.size(); i++) {               int id = gc.gs.get(i);               // 在此结构的条件下，在多加一条边构成子图继续挖掘               sct = new SubChildTraveler(gc.edgeSeq, totalGraphs.get(id));               sct.traveler();               edgeArray = sct.getResultChildEdge();               // 做边id的更新               for (Edge e2 : edgeArray) {                   if (!edge2GId.containsKey(e2)) {                       gIds = new ArrayList<>();                   } else {                       gIds = edge2GId.get(e2);                   gIds.add(id);                   edge2GId.put(e2, gIds);           for (Map.Entry entry : edge2GId.entrySet()) {               e1 = (Edge) entry.getKey();               gIds = (ArrayList<Integer>) entry.getValue();               // 如果此边的频度大于最小支持度值，则继续挖掘               if (gIds.size() < minSupportCount) {                   continue;               GraphCode nGc = new GraphCode();               nGc.edgeSeq.addAll(gc.edgeSeq);               // 在当前图中新加入一条边，构成新的子图进行挖掘               nGc.edgeSeq.add(e1);               nGc.gs.addAll(gIds);               if (e1.iy == next) {                   // 如果边的点id设置是为当前最大值的时候，则开始寻找下一个点                   subMining(nGc, next + 1);               } else {                   // 如果此点已经存在，则next值不变                   subMining(nGc, next);               * 输出频繁子图结果信息      public void printResultGraphInfo(){           System.out.println(MessageFormat.format("挖掘出的频繁子图的个数为：{0}个", resultGraphs.size()));   }   这个算法在后来的实现时，渐渐的发现此算法的难度大大超出我预先的设想，不仅仅是其中的抽象性，还在于测试的复杂性，对于测试数据的捏造，如果用的是真实数据测的话，数据量太大，自己造数据拿捏的也不是很准确。我最后也只是自己伪造了一个图的数据，挖掘了其中的一条边的情况。大致的走了一个过程。代码并不算是完整的，仅供学习。 算法的缺点 在后来实现完算法之后，我对于其中的小的过程进行了分析，发现这个算法在2个深度优先遍历的过程中还存在问题，就是DFS判断是否最小编码和对原图进行寻找相应编码，的时候，都只是限于Edge中边是连续的情况，如果不连续了，会出现判断出错的情况，因为在最右路径上添加边，就是会出现在前面的点中多扩展一条边，就不会是连续的。而在上面的代码中是无法处理这样的情况的，个人的解决办法是用栈的方式，将节点压入栈中实现最好。 算法的体会 这个算法花了很多的时间，关关理解这个算法就已经不容易了，经常需要我在脑海中去刻画这样的图形和遍历的一些情况，带给我的挑战还是非常的大吧。 算法的特点 此算法与FP-Tree算法类似，在挖掘的过程中也是没有产生候选集的，采用深度优先的挖掘方式，一步一步进行挖掘。gSpan算法可以进行对于化学分子的结构挖掘。 阅读全文 Finding reduct gSpan

十大经典算法 1. C4.5（ID3算法 ） 2. The k-means algorithm 即K-Means算法 3. Support vector machines 4. The Apriori algorithm 5. 最大期望(EM)算法 6. PageRank 7. AdaBoost 8. kNN: k-nearest neighbor classification 9. Naive Bayes 10. CART: 分类与回归树

决策树基础 女孩家长 安排相亲 女孩 不厌其烦 提出决策树 父母筛选 候选男士

决策树基础 实例 No. 头痛 肌肉痛 体温 患流感 1 是(1) 正常(0) N(0) 2 高(1) Y(1) 3 很高(2) 4 否(0) 5 6 N(1) 7

生活工作中的决策 （做？不做？） 总是优先选取最具有决定性意义的 辅助条件进行判定 如—打不打室外羽毛球？ 刮风是最具有决定意义的因素

主要内容 决策树基本概念 决策树算法 决策树研究问题 主要参考文献

决策树 决策树基本概念 关于分类问题 分类（Classification）任务就是通过学习获得一个目标函数 （Target Function）f, 将每个属性集x映射到一个预先定义好的类 标号y。 分类任务的输入数据是纪录的集合，每条记录也称为实例 或者样例。用元组(X,y)表示，其中，X 是属性集合，y是一个 特殊的属性，指出样例的类标号（也称为分类属性或者目标属性）

决策树分类的步骤 建立模型 训练样本(training samples) 测试样本(testing samples) 评估模型 数据库 13 2019/2/23

决策树 决策树基本概念 解决分类问题的一般方法 通过以上对分类问题一般方法的描述，可以看出分类问题 一般包括两个步骤： 1、模型构建（归纳） 通过对训练集合的归纳，建立分类模型。 2、预测应用（推论） 根据建立的分类模型，对测试集合进行测试。

决策树 决策树基本概念 解决分类问题的一般方法 训练集（类标号已知） 学习算法 学习模型 归纳 模型 检验集（类标号未知） 应用模型 推论 TID A1 A2 A3 类 1 Y 100 L N 2 125 S 3 400 4 415 M 学习模型 归纳 模型 检验集（类标号未知） 应用模型 TID A1 A2 A3 类 1 Y 100 L ？ 2 N 125 S 3 400 4 415 M 推论

决策树 决策树基本概念 决策树 决策树是一种典型的分类方法，首先对数据进行处理，利用 归纳算法生成可读的规则和决策树，然后使用决策对新数据进行 分析。本质上决策树是通过一系列规则对数据进行分类的过程。

决策树 决策树基本概念 决策树的优点 1、推理过程容易理解，决策推理过程可以表示成If Then形式； 2、推理过程完全依赖于属性变量的取值特点； 3、可自动忽略目标变量没有贡献的属性变量，也为判断属性 变量的重要性，减少变量的数目提供参考。

决策树 决策树基本概念 关于归纳学习(1) 决策树技术发现数据模式和规则的核心是归纳算法。 归纳是从特殊到一般的过程。归纳推理从若干个事实中表 征出的特征、特性和属性中，通过比较、总结、概括而得出一 个规律性的结论。 归纳推理试图从对象的一部分或整体的特定的观察中获得 一个完备且正确的描述。即从特殊事实到普遍性规律的结论。 归纳对于认识的发展和完善具有重要的意义。人类知识的增长 主要来源于归纳学习。

决策树 决策树基本概念 关于归纳学习(2) 归纳学习的过程就是寻找一般化描述的过程。这种一般性 描述能够解释给定的输入数据，并可以用来预测新的数据。 锐角三角形内角和等于180度； 钝角三角形内角和等于180度； 三角形内角和 直角三角形内角和等于180度； 等于180度 已知三角形ABC，A角等于76度， B角等于89度，则其C角等于15度

决策树 决策树基本概念 关于归纳学习(3) 归纳学习由于依赖于检验数据，因此又称为检验学习。归纳学习存在一个基本的假设： 任一假设如果能够在足够大的训练样本集中很好的逼近目标函数，则它也能在未见样本中很好地逼近目标函数。该假定是归纳学习的有效性的前提条件。

主要内容 决策树基本概念 决策树算法 决策树研究问题 主要参考文献

决策树 决策树算法 与决策树相关的重要算法 CLS, ID3，C4.5，CART 1、Hunt,Marin和Stone 于1966年研制的CLS学习系统，用于学习单个概 念。 2、1979年, J.R. Quinlan 给出ID3算法，并在1983年和1986年对ID3 进行了总结和简化，使其成为决策树学习算法的典型。 3、Schlimmer 和Fisher 于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。 4、1988年，Utgoff 在ID4基础上提出了ID5学习算法，进一步提高了效率。 1993年，Quinlan 进一步发展了ID3算法，改进成C4.5算法。 5、另一类决策树算法为CART，与C4.5不同的是，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例。

决策树基础 女孩家长 安排相亲 女孩 不厌其烦 提出决策树 父母筛选 候选男士

决策树基础 有向无环 二叉/多叉树 父节点：没有子节点的节点 内部节点：有父节点、子节点的节点 叶节点：有父节点没有子节点的节点 父节点 有向无环 二叉/多叉树 父节点：没有子节点的节点 内部节点：有父节点、子节点的节点 叶节点：有父节点没有子节点的节点 父节点 内部节点 分割属性+判断规则 叶节点 类别标识

决策树基础 叶节点 （类别标识） 父节点 内部节点 （分割属性+判断规则）

决策树基础 训练集：数据的集合，用于生成树（模型） 测试集：用于测试树（模型）的性能 决策树作用： 通过训练集 算法指导下 生成决策树 新数据进行划分 否则是“三拍”决策 训练集 算法 新数据 决策树 三拍决策为： 　　一、拍脑袋决策 　　“拍脑袋”决策是不少领导干部都有的毛病。不下基层了解，不搞实地调查，不用数据说话，遇事只凭脑袋“灵光一闪”，政策即出，看似胸有成竹运筹帷幄，实则纸上谈兵，犯下和古人赵括一样的错误。 　　二、拍胸脯保证 　　“拍脑袋”决策一出，紧跟的自然就是“拍胸脯”保证。政策即出，如有人问到：“如何保证政策行之有效？”决策本身就来之无凭，没有实地调查，也无细致审计，“拍脑袋”者自然说不出个所以然。既然亏了“道理”，那就只能用“豪气”来撑撑场面，于是“胸脯”拍得震天响，凭着代表政府的威望来获取群众的信任和支持。 　　三、拍屁股走人 　　“拍脑袋”而出的决策，运作起来与预期目的相去甚远，而群众也不可能指望一个“拍胸脯”保证的干部在事后主动承担起相应的责任。于是，“拍屁股”走人几乎就成了“拍脑袋”和“拍胸脯”之后的必然结果。政策既出，自然要投入大量人力物力，而运作之后却又达不到预期的目的，到最后既浪费了国家资源，又寒了老百姓的心，后果之严重，可见一斑。 决策

三 拍 决 策 决策树基础 决策树怎么做？谁是父节点？ 实例 谁是下一层子节点？为什么是它？ 头-肌肉-体温 头-体温-肌肉 肌肉-头-体温 No. 头痛 肌肉痛 体温 患流感 1 是(1) 正常(0) N(0) 2 高(1) Y(1) 3 很高(2) 4 否(0) 5 6 N(1) 7 头-肌肉-体温 头-体温-肌肉 肌肉-头-体温 肌肉-体温-头 体温-头-肌肉 体温-肌肉-头 三 拍 决 策

决策树 决策树算法 决策树的用途 假定公司收集了左表数据，那么对于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？ 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 买 60 老 低 是 132 32 63 1 假定公司收集了左表数据，那么对于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？ 即：你能预测这位客人是属于“买”计算机的那一类，还是属于“不买”计算机的那一类？ 又：你需要多少有关这位客人的信息才能回答这个问题？

决策树 决策树算法 谁在买计算机？ 决策树的用途 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 60 老 低 是 132 32 63 1 谁在买计算机？ 年龄？ 青 老 中 学生？ 买 信誉？ 否 是 优 良 不买 买 不买 买

决策树 决策树算法 谁在买计算机？ 决策树的用途 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 60 老 低 是 132 32 63 1 谁在买计算机？ 年龄？ 青 老 中 学生？ 买 信誉？ 否 是 优 良 不买 买 不买 买

决策树 决策树算法 决策树的表示 决策树的基本组成部分：决策结点、分支和叶子。 决策树中最上面的结点称为根结点。 是整个决策树的开始。每个分支是一 个新的决策结点，或者是树的叶子。 每个决策结点代表一个问题或者决策. 通常对应待分类对象的属性。 每个叶结点代表一种可能的分类结果 年龄？ 青 老 中 学生？ 买 信誉？ 否 是 优 良 不买 买 不买 买 在沿着决策树从上到下的遍历过程中，在每个结点都有一个 测试。对每个结点上问题的不同测试输出导致不同的分枝，最后 会达到一个叶子结点。这一过程就是利用决策树进行分类的过程， 利用若干个变量来判断属性的类别

决策树 决策树算法 CLS（Concept Learning System）算法 CLS算法是早期的决策树学习算法。它是许多决策树学习算法 的基础。 CLS基本思想 从一棵空决策树开始，选择某一属性（分类属性）作为测试 属性。该测试属性对应决策树中的决策结点。根据该属性的值的 不同，可将训练样本分成相应的子集，如果该子集为空，或该子 集中的样本属于同一个类，则该子集为叶结点，否则该子集对应 于决策树的内部结点，即测试结点，需要选择一个新的分类属性 对该子集进行划分，直到所有的子集都为空或者属于同一类。

决策树 决策树算法 CLS算法 人员 眼睛颜色 头发颜色 所属人种 1 黑色 黄种人 2 蓝色 金色 白种人 3 灰色 4 红色 5 6 混血 7 8

决策树 决策树算法 CLS算法-决策树的构建 眼睛颜色 黑色 兰色 灰色 [1，6] [2，4，8] [3，5，7] 不属于同一类，非叶结点 人员 眼睛颜色 头发颜色 所属人种 1 黑色 黄种人 2 蓝色 金色 白种人 3 灰色 4 红色 5 6 混血 7 8 黑色 兰色 灰色 [1，6] [2，4，8] [3，5，7] 不属于同一类，非叶结点

决策树 决策树算法 CLS算法 眼睛颜色 黑色 兰色 灰色 头发颜色 头发颜色 头发颜色 黑色 金色 黑色 金色 金色 红色 黑色 红色 混血[7] 金色 黑色 金色 金色 红色 黑色 红色 黄种人[1] 混血[6] 白种人[2] 白种人[4] 混血[8] 白种人[3] 白种人[5]

决策树 决策树算法 CLS算法 1 生成一颗空决策树和一张训练样本属性集; 2 若训练样本集T 中所有的样本都属于同一类, 3 根据某种策略从训练样本属性表中选择属性 A 作为测试属性, 生成测试结点A 4 若A的取值为v1,v2,…,vm, 则根据A 的取值的 不同,将T 划分成 m个子集T1,T2,…,Tm; 5 从训练样本属性表中删除属性A; 6 转步骤2, 对每个子集递归调用CLS;

决策树 决策树算法 CLS算法问题 在步骤3中，根据某种策略从训练样本属性表中选择属性A作为测试属性。没有规定采用何种测试属性。实践表明，测试属性集的组成以及测试属性的先后对决策树的学习具有举足轻重的影响。 举例加以说明，下表为调查学生膳食结构和缺钙情况的关系，其中1表示包含食物，0表示不包含

决策树 决策树算法 CLS算法问题 学生膳食结构和缺钙调查表 学生 鸡肉 猪肉 牛肉 羊肉 鱼肉 鸡蛋 青菜 番茄 牛奶 健康情况 1 不缺钙 2 3 缺钙 4 5 6 7 8 9 10

决策树 决策树算法 CLS算法问题 采用不同的测试属性及其先后顺序将会生成不同的决策树 鸡肉 猪肉 猪肉 牛肉 牛肉 牛肉 不缺钙（2） 是 否 猪肉 猪肉 否 是 是 否 牛肉 牛肉 牛肉 不缺钙（2） 是 否 是 否 是 否 缺钙（3，6） 不缺钙（4） 不缺钙（10） 缺钙（5） 不缺钙（1） 鱼肉 否 是 缺钙（5） 不缺钙（7，9）

决策树 决策树算法 CLS算法问题 在上例中，显然生成的两种决策树的复杂性和分类意义相差 牛奶 不缺钙 （1，2，4， 7，9，10） 缺钙 （3，5，6，8） 在上例中，显然生成的两种决策树的复杂性和分类意义相差 很大由此可见，选择测试属性是决策树学习算法中需要研究的重 要课题。

决策树 决策树算法 ID3 ID3算法主要针对属性选择问题。是决策树学习方法中最 具影响和最为典型的算法。 该方法使用信息增益度选择测试属性。 当获取信息时，将不确定的内容转为确定的内容，因此信 息伴着不确定性。 从直觉上讲，小概率事件比大概率事件包含的信息量大。 如果某件事情是“百年一见”则肯定比“习以为常”的事件包含的 信息量大。 如何度量信息量的大小？

决策树基础 选哪个？？ 决策树基础 信息论基础 Next One! ID3算法 C4.5算法 怎么生成好的？

香农的信息论 的概念，解决了对信息的量化问题。 信息量的大小，由其所消除的 不确定性大小来衡量！ 例 你已经确知的东西，别人告诉你， 1948 年，香农提出了“信息熵”(shāng) 的概念，解决了对信息的量化问题。 信息量的大小，由其所消除的 不确定性大小来衡量！  例 你已经确知的东西，别人告诉你， 你会觉得信息量不大。 信息论之父 C. E. Shannon

信息的定量描述 衡量信息多少的物理量称为信息量。 若概率很大，受信者事先已有所估计，则该消息信息量就很小； 若概率很小，受信者感觉很突然，该消息所含信息量就很大。 在一个口袋中，有100个球，其中1个是红球，另外99个是绿球，现在你随意抓一个球。先知告诉你将抓到的是绿球，你会觉得惊讶吗？但如果先知告诉你将抓到的是红球，则你觉得他的确是有神算能力。 如果某个人告诉你明天将下雨，你会觉得很惊讶吗？如果某个人告诉你明天天上将会掉下一只乌龟来，则又如何？ 44

信息量的定义 根据客观事实和人们的习惯概念，函数f(p)应满足以下条件： f(p)应是概率p的严格单调递减函数，即当p1>p2， f(p1)<f(p2)； 当p=1时，f(p)=0； 当p=0时，f(p)=∞； 两个独立事件的联合信息量应等于它们分别的信息量之和。

对信息量的 认识理解 信息量的定义 信息量单位 若一个消息x出现的概率为p，则这一消息所含的信息量为 其中，对数的底大于1 信息量单位 以2为底时，单位为 bit（binary unit，比特） 以e为底时，单位为 nat（natural unit，奈特） 以10为底时，单位为 hart（Hartley，哈特）

抛一枚均匀硬币，出现正面与反面的信息量是多少？ 解：出现正面与反面的概率均为0. 5，它们的信息量是 I(正)= -lbp(正)= -lb0.5=1b I(反)= -lbp(反)= -lb0.5=1b

抛一枚畸形硬币，出现正面与反面的概率分别是1/4，3/4，出现正面与反面时的信息量是多少？ 解：出现正面与反面的概率分别是1/4，3/4，它们的信息量是 I(正)= -lbp(正)= -lb1/4=2b I(反)= -lbp(反)= -lb3/4=0.415b

信源含有的信息量是信源发出的所有可能消息的平均不确定性，香农把信源所含有的信息量称为信息熵，是指每个符号所含信息量的统计平均值。m种符号的平均信息量为

抛一枚均匀硬币的信息熵是多少？ 解：出现正面与反面的概率均为0. 5，信息熵是

抛一枚畸形硬币，出现正面与反面的概率分别是1/4，3/4，出现正面与反面时的信息量是多少？ 解：出现正面与反面的概率分别是1/4，3/4，信息熵是

例：气象预报

条件自信息量 在事件yj出现的条件下，随机事件xi发生的条件概率为p(xi | yj) ，则它的条件自信息量定义为条件概率对数的负值： 53

条件熵 在给定yj条件下，xi的条件自信息量为I(xi| yj), X集合的条件熵H(X|yj)为 在给定Y(即各个yj )条件下,X集合的条件熵H(X|Y) 条件熵H(X|Y)表示已知Y后，X的不确定度 54

是否进行垒球活动 活　动 进行 取消 活　动 进行 取消 　天　气 雨 晴 晴 阴 雨 阴 雨

H(活动) = - (9/14)*log (9/14) - (5/14)*log (5/14) = 0.94 活动的熵 活　动 进行 取消 活动有2个属性值，进行，取消。其熵为： H(活动) = - (9/14)*log (9/14) - (5/14)*log (5/14) = 0.94

活 动 天 气 已知户外的天气情况下活动的条件熵 户外有三个属性值，晴，阴和雨。其熵分别为： 进行 取消 晴 阴 雨 活　动 已知户外的天气情况下活动的条件熵 进行 取消 　天　气 晴 阴 雨 户外有三个属性值，晴，阴和雨。其熵分别为： H(活动|户外=晴) = - (2/5)*log2(2/5) - (3/5)*log2(3/5) = 0.971 H(活动|户外=阴) = - (4/4)*log2(4/4) = 0 H(活动|户外=雨) = - (3/5)*log2(3/5)- (2/5)*log2(2/5) = 0.971

已知户外时活动的条件熵 晴 阴 雨 H(活动|户外)=5/14*H(活动|户外=晴)+4/14*H(活动|户外=阴) +5/14* H(活动|户外=雨) = (5/14)*0.971 + (4/14)*0 +(5/14)*0.971 = 0.693

平均互信息 I(活动;户外) = H(活动) - H(活动|户外) = 0.94- 0.693 = 0.246

是否适合打垒球的决策表 天气 温度 湿度 风速 活动 晴 炎热 高 弱 取消 强 阴 进行 雨 适中 寒冷 正常

H(活动) = - (9/14)*lb (9/14) - (5/14)*lb (5/14) = 0.94 活动的熵 天气 温度 湿度 风速 活动 阴 炎热 高 弱 进行 雨 适中 寒冷 正常 强 晴 取消 H(活动) = - (9/14)*lb (9/14) - (5/14)*lb (5/14) = 0.94

已知天气时活动的条件熵 温度 湿度 风速 天气 活动 寒冷 正常 弱 晴 进行 适中 强 炎热 高 取消 阴 雨 H(活动|天气)=5/14*H(活动|天气=晴)+4/14*H(活动|天气=阴) +5/14* H(活动|天气=雨) = (5/14)*0.971 + (4/14)*0 +(5/14)*0.971 = 0.693

已知温度时活动的条件熵 H(活动|温度) = 0.911 天气 湿度 风速 温度 活动 阴 高 弱 炎热 进行 正常 晴 取消 强 雨 适中 寒冷 H(活动|温度) = 0.911

已知湿度时活动的条件熵 H(活动|湿度) = 0.789 天气 温度 风速 湿度 活动 阴 炎热 弱 高 进行 雨 适中 强 晴 取消 寒冷 正常 H(活动|湿度) = 0.789

已知风速时活动的条件熵 H(活动|风速) = 0.892 天气 温度 湿度 风速 活动 阴 寒冷 正常 强 进行 晴 适中 高 炎热 取消 雨 弱 H(活动|风速) = 0.892

各互信息量 I(活动;天气) = H(活动) - H(活动|天气) = 0.94- 0.693 = 0.246

晴 阴 雨 温度 湿度 风速 活动 寒冷 正常 弱 进行 适中 强 炎热 高 取消 温度 湿度 风速 活动 炎热 高 弱 进行 寒冷 正常 天气 温度 湿度 风速 活动 晴 炎热 高 弱 取消 强 阴 进行 雨 适中 寒冷 正常 天气 温度 湿度 风速 活动 晴 寒冷 正常 弱 进行 适中 强 炎热 高 取消 阴 雨 温度 湿度 风速 活动 炎热 高 弱 进行 寒冷 正常 强 适中 阴 温度 湿度 风速 活动 适中 高 弱 进行 寒冷 正常 强 取消 雨

ID3算法生成的决策树

决策规则（产生式规则） 天气=阴⇒进行 天气=晴∧湿度=正常⇒进行 天气=晴∧湿度=高⇒取消 天气=雨∧风速=强⇒取消 天气=雨∧风速=弱⇒进行

决策树 决策树算法 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 买 60 老 低 是 132 63 1

决策树 决策树算法 第1步计算决策属性的熵 决策属性“买计算机？”。该属性分 两类：买/不买 S1(买)=641 S2（不买）= 383 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 买 60 老 低 是 132 32 63 1 决策属性“买计算机？”。该属性分 两类：买/不买 S1(买)=641 S2（不买）= 383 S=S1+S2=1024 P1=641/1024=0.6260 P2=383/1024=0.3740 I(S1,S2)=I(641,383) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9537

决策树 决策树算法 第2步计算条件属性的熵 条件属性共有4个。分别是年龄、 收入、学生、信誉。 分别计算不同属性的信息增益。 计数 年龄 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 买 60 老 低 是 132 32 63 1 条件属性共有4个。分别是年龄、 收入、学生、信誉。 分别计算不同属性的信息增益。

决策树 决策树算法 第2-1步计算年龄的熵 年龄共分三个组： 青年、中年、老年 青年买与不买比例为128/256 S1(买)=128 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 买 60 老 低 是 132 32 63 1 年龄共分三个组： 青年、中年、老年 青年买与不买比例为128/256 S1(买)=128 S2（不买）= 256 S=S1+S2=384 P1=128/384 P2=256/384 I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183

决策树 决策树算法 第2-2步计算年龄的熵 年龄共分三个组： 青年、中年、老年 中年买与不买比例为256/0 S1(买)=256 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 买 60 老 低 是 132 32 63 1 第2-2步计算年龄的熵 年龄共分三个组： 青年、中年、老年 中年买与不买比例为256/0 S1(买)=256 S2（不买）= 0 S=S1+S2=256 P1=256/256 P2=0/256 I(S1,S2)=I(256，0) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0

决策树 决策树算法 第2-3步计算年龄的熵 年龄共分三个组： 青年、中年、老年 老年买与不买比例为125/127 S1(买)=125 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 买 60 老 低 是 132 32 63 1 第2-3步计算年龄的熵 年龄共分三个组： 青年、中年、老年 老年买与不买比例为125/127 S1(买)=125 S2（不买）=127 S=S1+S2=252 P1=125/252 P2=127/252 I(S1,S2)=I(125，127) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9157

决策树 决策树算法 第2-4步计算年龄的熵 年龄共分三个组： 青年、中年、老年 所占比例 青年组 384/1025=0.375 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 买 60 老 低 是 132 32 63 1 第2-4步计算年龄的熵 年龄共分三个组： 青年、中年、老年 所占比例 青年组 384/1025=0.375 中年组 256/1024=0.25 老年组 384/1024=0.375 计算年龄的平均信息期望 E（年龄）=0.375*0.9183+ 0.25*0+ 0.375*0.9157 =0.6877 G（年龄信息增益） =0.9537-0.6877 =0.2660 （1）

决策树 决策树算法 第3步计算收入的熵 收入共分三个组： 高、中、低 E（收入）=0.9361 收入信息增益=0.9537-0.9361 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 买 60 老 低 是 132 32 63 1 收入共分三个组： 高、中、低 E（收入）=0.9361 收入信息增益=0.9537-0.9361 =0.0176 (2)

决策树 决策树算法 第4步计算学生的熵 学生共分二个组： 学生、非学生 E（学生）=0.7811 年龄信息增益=0.9537-0.7811 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 买 60 老 低 是 132 32 63 1 学生共分二个组： 学生、非学生 E（学生）=0.7811 年龄信息增益=0.9537-0.7811 =0.1726 （3）

决策树 决策树算法 第5步计算信誉的熵 信誉分二个组： 良好，优秀 E（信誉）= 0.9048 信誉信息增益=0.9537-0.9048 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 买 60 老 低 是 132 32 63 1 信誉分二个组： 良好，优秀 E（信誉）= 0.9048 信誉信息增益=0.9537-0.9048 =0.0453 （4）

决策树 决策树算法 第6步计算选择节点 年龄信息增益=0.9537-0.6877 =0.2660 （1） 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 买 60 老 低 是 132 32 63 1 年龄信息增益=0.9537-0.6877 =0.2660 （1） 收入信息增益=0.9537-0.9361 =0.0176 （2） 年龄信息增益=0.9537-0.7811 =0.1726 （3） 信誉信息增益=0.9537-0.9048 =0.0453 （4）

决策树 决策树算法 年龄 青年 老年 中年 买/ 不买 买/ 不买 买 叶子 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 低 是 买 中年 买/ 不买 买/ 不买 买 叶子

决策树 决策树算法 青年买与不买比例为128/256 S1(买)=128 S2（不买）= 256 S=S1+S2=384 P1=128/384 P2=256/384 I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 低 是 买

决策树 决策树算法 注意 如果选择收入作为节点 分高、中、低 I(0,128)=0 比例: 128/384=0.3333 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 低 是 买 I(0,128)=0 比例: 128/384=0.3333 I(64,128)=0.9183 比例: 192/384=0.5 I(64,0)=0 比例: 64/384=0.1667 平均信息期望（加权总和）： E(收入）= 0.3333 * 0 + 0.5 * 0.9183 + 0.1667 * 0 = 0.4592 Gain(收入) = I(128, 256) - E(收入)=0.9183 – 0.4592 = 0.4591 注意

决策树 决策树算法 年龄 青年 老年 中年 学生 信誉 买 叶子 否 是 优 良 不买 买 买 买/ 不买 叶子 叶子 叶子 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 买 60 老 低 是 132 32 63 1 年龄 青年 老年 中年 学生 信誉 买 叶子 否 是 优 良 不买 买 买 买/ 不买 叶子 叶子 叶子

决策树 决策树算法 ID3 决策树建立算法 1 决定分类属性； 2 对目前的数据表，建立一个节点N 标出所属的类 4 如果数据表中没有其他属性可以考虑，则N也是树叶，按照少 数服从多数的原则在树叶上标出所属类别 5 否则，根据平均信息期望值E或GAIN值选出一个最佳属性作 为节点N的测试属性 6 节点属性选定后，对于该属性中的每个值： 从N生成一个分支，并将数据表中与该分支有关的数据收集形 成分支节点的数据表，在表中删除节点属性那一栏 如果分支数据表非空，则运用以上算法从该节点建立子树。

决策树 决策树算法 原始表 决策树的数据准备 姓名 年龄 收入 学生 信誉 电话 地址 邮编 买计算机 张三 23 4000 是 良 281-322-0328 2714 Ave. M 77388 买 李四 34 2800 否 优 713-239-7830 5606 Holly Cr 78766 王二 70 1900 281-242-3222 2000 Bell Blvd. 70244 不买 赵五 18 900 281-550-0544 100 Main Street 刘兰 2500 713-239-7430 606 Holly Ct 78566 杨俊 27 8900 281-355-7990 233 Rice Blvd. 70388 张毅 38 9500 281-556-0544 399 Sugar Rd. 78244 。。。 。。

决策树 决策树算法 决策树的数据准备 整理后的数据表 Data cleaning 删除/减少noise， 补填missing values Data transformation 数据标准化（data normalization） 数据归纳（generalize data to higher-level concepts using concept hierarchies） 例如：年龄归纳为老、中、青三类 控制每个属性的可能值不超过七种 （最好不超过五种） Relevance analysis 对于与问题无关的属性：删 对于属性的可能值大于七种 又不能归纳的属性：删 计数 年龄 收入 学生 信誉 归类：买计算机？ 64 青 高 否 良 不买 优 128 中 买 60 老 低 是 。。。

决策树 决策树算法 决策树的数据准备 处理连续属性值 决策树算法比较适合处理离散数值的属性。实际应用中 属性是连续的或者离散的情况都比较常见。 在应用连续属性值时，在一个树结点可以将属性Ai的值 划分为几个区间。然后信息增益的计算就可以采用和离散值 处理一样的方法。原则上可以将Ai的属性划分为任意数目的 空间。C4.5中采用的是二元分割（Binary Split）。需要找出 一个合适的分割阈值。 参考C4.5算法 Top 10 algorithms in data mining Knowledge Information System 2008 14:1–37

决策树 决策树算法 ID3算法小结 ID3算法是一种经典的决策树学习算法，由Quinlan于1979年 点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值 变为最小的属性，以构造一颗熵值下降最快的决策树，到叶子节 点处的熵值为0。此时，每个叶子节点对应的实例集中的实例属于 同一类。

分类器评价标准 预测准确度 计算复杂度 模型描述的简洁度：产生式规则

准确度分析 一般采用召回率r(Recall)和精准率p(Precision)这两个指标衡量分类器的准确度。—个好的分类器应同时具有较高的召回率和精准率，当然这两个指标一般情况下是互斥的，有时要根据需要在这两个指标间作某种权衡和妥协。

召回率r(Recall)和精准率p(Precision) 为了定义这两个指标，引入分类中常用的两个基本概念，Relevant和Retrieved。 Relevant：真正属于某类的集合 Retrieved：判断属于某类的集合 召回率反映了分类器正确分类的对象在真正归入该类的对象中所占的比率，而精准率反映了分类器正确分类的对象在系统归入该类的对象中所占的比率。 Relevant Retrieved Relevant∩Retrieved Relevant Retrieved Relevant∩Retrieved

F1 召回率和精准率反映了分类质量的两个不同侧面，两者必须综合考虑，不可偏废，因此，可引入一种新的评价指标F1，该指标综合了这两种因素，其公式如下：

构造分类器的主要步骤 将现有的已知类别的数据划分为训练集和测试集两部分。 构造分类算法对训练集进行学习，得到一个分类模型，它可以以分类规则、决策树或数学公式等形式给出。 使用分类模型对测试集进行检测，如果符合测试要求（如分类精度），则进行④；否则，返回②。 应用得到的分类模型对未知类别的数据进行分类。

练习：决策树在犯罪分析中的应用 有无固定 职业 家庭经济 状况 年龄 文化程度 有无特长 社会关系 犯罪 记录 违法 家庭 和睦 次数 是否 经常 赌博 犯罪程度 无 差 30-40 初中 否 有 4 是 严重 中 20-30 中专 较轻 <20 高中 1 >40 2 6 大专 3 好 5 小学

犯罪潜在风险决策树 22

应用案例：在农业中的应用 97 2019/2/23

第一步：属性离散化 98 2019/2/23

第二步：概化（泛化） 99 2019/2/23

第三步：计算各属性的期望信息 =(17/30)*LOG((17/30),2)+(10/30)*LOG((10/30),2)+(3/30)*LOG((3/30),2) 100 2019/2/23

计算各属性的信息增益 101 2019/2/23

第四步：决策树 102 2019/2/23

案例2：银行违约率 103 2019/2/23

104 2019/2/23

案例3 对电信客户的流失率分析 条件属性 类别属性 数据仓库 客户是否流失 105 2019/2/23

案例4：在银行中的应用 106 2019/2/23

决策树 决策树算法 ID3算法实际应用-在电信行业应用实例（1） 通过ID3算法来实现客户流失的预警分析，找出客户流失的 特征，以帮助电信公司有针对性地改善客户关系，避免客户流失 利用决策树方法进行数据挖掘，一般有如下步骤：数据预处 理、决策树挖掘操作，模式评估和应用。 电信运营商的客户流失有三方面的含义：一是指客户从一个 电信运营商转网到其他电信运营商，这是流失分析的重点。二是 指客户月平均消费量降低，从高价值客户成为低价值客户。三、 指客户自然流失和被动流失。 在客户流失分析中有两个核心变量：财务原因／非财务原因、 主动流失／被动流失。 客户流失可以相应分为四种类型：其中非财务原因主动流失 的客户往往是高价值的客户。他们会正常支付服务费用，并容易 对市场活动有所响应。这种客户是电信企业真正需要保住的客户。

决策树 决策树算法 ID3算法实际应用-在电信行业应用实例（2） 数据预处理 数据挖掘的处理对象是大量的数据，这些数据一般存储在数 据库系统中（该用户相关数据存储在其CRM中），是长期积累的 结果。但往往不适合直接挖掘，需要做数据的预处理工作，一般 包括数据的选择(选择相关的数据)、净化(消除冗余数据)、转换、 归约等。数据预处理工作准备是否充分，对于挖掘算法的效率乃 至正确性都有关键性的影响。 该公司经过多年的电脑化管理，已有大量的客户个人基本信息 (文中简称为客户信息表)。在客户信息表中，有很多属性，如姓名 用户号码、用户标识、用户身份证号码(转化为年龄)、在网时间 （竣工时间）、地址、职业、用户类别、客户流失（用户状态） 等等，数据准备时必须除掉表中一些不必要的属性，一般可采用面 向属性的归纳等方法去掉不相关或弱相关属性。

决策树 决策树算法 ID3算法实际应用-在电信行业应用实例（3） 属性删除：将有大量不同取值且无概化操作符的属性或者可用其 它属性来代替它的较高层概念的那些属性删除。比如客户信息表 中的用户标识、身份证号码等，它们的取值太多且无法在该取值 域内找到概化操作符，应将其删除，得到表1。 表1 客户信息表 年龄 学历 职业 缴费方式 在网时长 费用变化率 客户流失 58 大学 公务员 托收 13 10% NO 47 高中 工人 营业厅缴费 9 42% 26 研究生 充值卡 2 63% YES 28 5 2.91% 32 初中 3 2.3% 42 无业人员 100% 68

决策树 决策树算法 ID3算法实际应用-在电信行业应用实例（4） 属性概化：用属性概化阈值控制技术沿属性概念分层上卷或下钻 进行概化。文化程度分为3类：W1初中以下(含初中)，W2高中(含 中专)，W3大学(专科、本科及以上)；职业类别：按工作性质来分 共分3类：Z1一Z3； 缴费方式：托收：T1,营业厅缴费：T2,充值卡：T3。 连续型属性概化为区间值：表中年龄、费用变化率和在网时间为 连续型数据，由于建立决策树时，用离散型数据进行处理速度最 快，因此对连续型数据进行离散化处理，根据专家经验和实际计 算信息增益，在“在网时长”属性中，通过检测每个划分，得到在 阈值为5年时信息增益最大，从而确定最好的划分是在5年处，则 这个属性的范围就变为｛<=5,>5：H1,H2｝。而在“年龄”属性中， 信息增益有两个锋值，分别在40和50处，因而该属性的范围变为 {<=40,>40-<=50,>50}即变为{青年，中年，老年：N1,N2,N3}；费 用变化率：指（（当月话费－近3个月的平均话费）/近3个月的平 均话费）×％>0，F1:<＝30%，F2：30%-99%, F3:＝100%变为 ｛F1,F2,F3｝。

决策树 决策树算法 ID3算法实际应用-在电信行业应用实例（5） 表2 转化后的客户信息表 年龄 学历 职业 缴费方式 开户时间 费用变化率 表2 转化后的客户信息表 年龄 学历 职业 缴费方式 开户时间 费用变化率 客户流失 N3 W3 Z1 T1 H2 F1 NO N2 W2 Z2 T2 F2 N1 T3 H1 YES W1 Z3 F3

决策树 决策树算法 ID3算法实际应用-在电信行业应用实例（6） YES NO 年 龄 职 业 缴费方式 YSES 在网时长 F1 F2 F3 N1 N2 N3 T1 T2 T3 Z1 Z2 Z3 H1 H2 费用变化率 在图中，NO表示客户不流失，YES表示客户流失。从图可以看出，客户费用变化率 为100%的客户肯定已经流失；而费用变化率低于30%的客户；即每月资费相对稳定的客 户一般不会流失，费用变化率在30%～99%的客户有可能流失，其中年龄在40～50岁之间 的客户流失的可能性非常大，而年龄低于40岁的客户，用充值卡缴费的客户和在网时间较 短的客户容易流失；年龄较大的客户，则工人容易流失。

CART是1984年由Breiman, Friedman, Olshen, Stone提出的一个决策树算法 Gini系数是Breiman于1984年提出来的，主要用在CART(Classfication and Regression Tree)算法中 CART(Classification And Regression Tree)算法采用一种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生成的的每个非叶子节点都有两个分支。因此，CART算法生成的决策树是结构简洁的二叉树。

基尼指标 在CART算法中, 基尼不纯度表示一个随机选中的样本在子集中被分错的可能性。 基尼不纯度为这个样本被选中的概率乘以它被分错的概率。 假设y的可能取值为{1, 2, ..., m},令fi是样本被赋予i的概率，则基尼指数可以通过如下计算： 基尼指标 最大值：(1 - 1/nc)，记录在所有类中等分布 最小值：0，所有记录属于同一个类

Gini指标 (Gini index) Gini指标 用来度量数据集的不纯度： Gini越小，数据越纯 CART中计算Gini指标考虑每个属性上的二元划分，根据训练数据集S中的属性F将S分成的S1和S2，则给定划分的Gini指标如下公式所示： 最小化Gini指标

选择最佳分割点 数值型变量： 对记录的值从小到大排序，计算每个值作为临界点产生的子节点的异质性统计量。能够使异质性减小程度最大的临界值便是最佳的划分点。 分类型变量： 列出划分为两个子集的所有可能组合，计算每种组合下生成子节点的异质性。同样，找到使异质性减小程度最大的组合作为最佳划分点。 最好的划分就是使得GINI最小的划分。 对于连续值处理引进“分裂点”的思想

一递归划分自变量空间 Num 有房者 婚姻状况 年收入 拖欠贷款者 1 2 3 4 5 6 7 8 9 10 是 否 单身 已婚 离异 125K 100K 70K 120K 95K 60K 220K 85K 75K 90K

Gini(t1)=1-(3/3)²-(0/3)²=0 Gini(t2)=1-(4/7)²-(3/7)²=0.4849 有房 无房 否 3 4 是 Gini(t1)=1-(3/3)²-(0/3)²=0 Gini(t2)=1-(4/7)²-(3/7)²=0.4849 Gini=0.3×0+0.7×0.4898=0.343

对离散值如{x,y,z}，则在该属性上的划分有三种情况({{x,y},{z}},{{x,z},y},{{y,z},x})，空集和全集的划分除外

单身或已婚 离异 否 6 1 是 2 Gini(t1)=1-(6/8)²-(2/8)²=0.375 Gini(t2)=1-(1/2)²-(1/2)²=0.5 Gini=8/10×0.375+2/10×0.5=0.4 单身或离异 已婚 否 3 4 是 Gini(t1)=1-(3/6)²-(3/6)²=0.5 Gini(t2)=1-(4/4)²-(0/4)²=0 Gini=6/10×0.5+4/10×0=0.3 离异或已婚 单身 否 5 2 是 1 Gini(t1)=1-(5/6)²-(1/6)²=0.2778 Gini(t2)=1-(2/4)²-(2/4)²=0.5 Gini=6/10×0.2778+4/10×0.5=0.3667

对于连续值处理引进“分裂点”的思想，假设样本集中某个属性共n个连续值， 则有n-1个分裂点，每个“分裂点”为相邻两个连续值的均值 (a[i] + a[i+1]) / 2。 60 70 75 85 90 95 100 120 125 220 65 72 80 87 92 97 110 122 172 ≤ > 3 1 2 6 5 4 0.400 0.375 0.343 0.417 0.300 是 否 Gini

决策树 有房者 是 否 拖欠贷款者=否 拖欠贷款者=否 拖欠贷款者=是 有房者 是 否 有房者 婚姻状况 拖欠贷款者=否 是 否 单身 离异 已婚 婚姻状况 拖欠贷款者=否 年收入 拖欠贷款者=否 单身 离异 已婚 <97K ≥97K 拖欠贷款者=是 拖欠贷款者=否 拖欠贷款者=是 拖欠贷款者=否

课堂练习：AllElectronics顾客数据库类标记的训练样本

Gini指标 CART 为了找出数据集的分裂准则，需要计算每个属性的 指标。 有三个属性值 子集有 个分别是 由于集合 和 为了找出数据集的分裂准则，需要计算每个属性的 指标。 以属性 为例。 有三个属性值 子集有 个分别是 和 由于集合 和 不代表任何分裂，基于属性 的二元 CART 划分，存在 种划分数据集的方法。

Gini指标 CART 如果按照 的二元分裂，将 划分成 和 ，则给定该划分的 考虑属性 的子集 。 基于该划分计算出的 指标值为： 如果按照 的二元分裂，将 划分成 和 ，则给定该划分的 指标为： 对于连续值属性，必须考虑每个可能的分裂点。取排序好的每对相邻值的中点取做可能的分裂点 。 被分成 和 数据集 中满足 的样本共10个， 考虑属性 的子集 。 其余4个样本被划分到 中。 被分到 中， CART 基于该划分计算出的 指标值为：

Gini指标 类似地，对其余子集分裂的 指标值是： 和 属性 的最好二元划分在 。 因为它最小化 指标。 0.458(子集{ }和{ }) 类似地，对其余子集分裂的 指标值是： 0.458(子集{ }和{ }) 0.450(子集{ }和{ }) 。 属性 的最好二元划分在 因为它最小化 指标。 和

CART生成二叉树 CART 同样的办法，评估节点 ， 得到 (或 ) 为 的最好分裂. 属性 和 都是二元的， 同样的办法，评估节点 ， 得到 (或 ) 为 的最好分裂. 指标值为0.357； 属性 和 都是二元的， 分别具有 指标值0.367和0.429. 比较可知，属性 和分裂子集 产生最小 CART 指标，因此被选作根节点，产生两个分支。

CART生成二叉树 yes no 对分裂后的子集，递归调用上述流程，即可完成建树。 是 否 对分裂后的子集，递归调用上述流程，即可完成建树。 用训练集来评估该二叉树，14个样本中能正确分类12个，正确率85.71%。

2019/2/23 129 129