BST树
 
  
        即二叉搜索树：
 
  
        1.所有非叶子结点至多拥有两个儿子（Left和Right）；
 
  
        2.所有结点存储一个关键字；
 
  
        3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；
 
  
        如：
 
  
        
 
  
 
 
  
         BST树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；
 
  
 否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入
 
  
 右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；
 
  
        如果BST树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树
 
  
 的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变BST树结构
 
  
 （插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；
 
  
        如：
 
  
       
 
  
 
 
  
    但BST树在经过多次插入与删除后，有可能导致不同的结构：
 
  
 
 
   
  
 
  
   右边也是一个BST树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的
 
  
树结构索引；所以，使用BST树还要考虑尽可能让BST树保持左图的结构，和避免右图的结构，也就
 
  
是所谓的“平衡”问题；      
 
  
       
AVL平衡二叉搜索树
 定义：平衡二叉树或为空树,或为如下性质的二叉排序树:
   （1）左右子树深度之差的绝对值不超过1;
   （2）左右子树仍然为平衡二叉树.
 平衡因子BF=左子树深度－右子树深度.
 平衡二叉树每个结点的平衡因子只能是1，0，-1。若其绝对值超过1，则该二叉排序树就是不平衡的。
 如图所示为平衡树和非平衡树示意图：
 
  

 
  

 
  
 
 
  
RBT 红黑树
 
  
AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；
 红黑是弱平衡的，用非严格的平衡来换取增删节点时候旋转次数的降低；
 所以简单说，搜索的次数远远大于插入和删除，那么选择AVL树，如果搜索，插入删除次数几乎差不多，应该选择RB树。
 
  
红黑树上每个结点内含五个域，color，key，left，right，p。如果相应的指针域没有，则设为NIL。
 一般的，红黑树，满足以下性质，即只有满足以下全部性质的树，我们才称之为红黑树：
 1）每个结点要么是红的，要么是黑的。
 2）根结点是黑的。
 3）每个叶结点，即空结点（NIL）是黑的。
 4）如果一个结点是红的，那么它的俩个儿子都是黑的。
 5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
 下图所示，即是一颗红黑树：
 
  



 
  

 
  

 
  
 
 
  
B-树
 
  
       是一种平衡多路搜索树（并不是二叉的）：
 
  
       1.定义任意非叶子结点最多只有M个儿子；且M>2；
 
  
       2.根结点的儿子数为[2, M]；
 
  
       3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
 
  
       4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
 
  
       5.非叶子结点的关键字个数=指向儿子的指针个数-1；
 
  
       6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
 
  
       7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的
 
  
子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
 
  
       8.所有叶子结点位于同一层；
 
  
       如：（M=3）
 
  
 
  
       B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果
 
  
命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为
 
  
空，或已经是叶子结点；
 
  
 B-树的特性：
 
  
       1.关键字集合分布在整颗树中；
 
  
       2.任何一个关键字出现且只出现在一个结点中；
 
  
       3.搜索有可能在非叶子结点结束；
 
  
       4.其搜索性能等价于在关键字全集内做一次二分查找；
 
  
       5.自动层次控制；
 
  
       由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少
 
  
利用率，其最底搜索性能为：
 
  
 
  
    
 
  
       其中，M为设定的非叶子结点最多子树个数，N为关键字总数；
 
  
       所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；
 
  
       由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占
 
  
M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并；
 
  
 
 
  
 
 
  
B+树
 
  
       B+树是B-树的变体，也是一种多路搜索树：
 
  
       1.其定义基本与B-树同，除了：
 
  
       2.非叶子结点的子树指针与关键字个数相同；
 
  
       3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树
 
  
（B-树是开区间）；
 
  
       5.为所有叶子结点增加一个链指针；
 
  
       6.所有关键字都在叶子结点出现；
 
  
       如：（M=3）
 
  
 
  
   B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在
 
  
非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；
 
  
       B+的特性：
 
  
       1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好
 
  
是有序的；
 
  
       2.不可能在非叶子结点命中；
 
  
       3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储
 
  
（关键字）数据的数据层；
 
  
       4.更适合文件索引系统；比如对已经建立索引的数据库记录，查找10<=id<=20，那么只要通过根节点搜索到id=10的叶节点，之后只要根据叶节点的链表找到第一个大于20的就行了，比B-树在查找10到20内的每一个时每次都从根节点出发查找提高了不少效率。
 
  
  
 
  
B*树
 
  
       是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；
 
  
 
  
   B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3
 
  
（代替B+树的1/2）；
 
  
       B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据
 
  
复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父
 
  
结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
 
  
       B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分
 
  
数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字
 
  
（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之
 
  
间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；
 
  
       所以，B*树分配新结点的概率比B+树要低，空间使用率更高；
 
  
  
 
  
小结
 
  
       B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于
 
  
走右结点；
 
  
       B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键
 
  
字范围的子结点；
 
  
       所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
 
  
       B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点
 
  
中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
 
  
       B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率
 
  
从1/2提高到2/3；
 
  

 
  
B+/B*Tree应用
 
  
 
  
 数据库索引–索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。
 
  
 
 
  
 
 
  
 数据库索引–表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键。
 
  
 
 
  
 
 
  
 倒排索引–也可以由B树及其变种实现但不一定非要B树及其变种实现，如lucene没有使用B树结构，因此lucene可以用二分搜索算法快速定位关键词。实现时，lucene将下面三列分别作为词典文件（Term Dictionary）、频率文件(frequencies)、位置文件 (positions)保存。其中词典文件不仅保存有每个关键词，还保留了指向频率文件和位置文件的指针，通过指针可以找到该关键字的频率信息和位置信息。 　　
 
  
 
 
  

   

     

      

     
     

      

       关键词            文章号[出现频率]              出现位置 　　
      
     

     

      

     
     

      

       guangzhou           
       1[
       2]                      
       3，
       6 　　
      
     

     

      

     
     

      

       he                  
       2[
       1]                      
       1 　　
      
     

     

      

     
     

      

       i                   
       1[
       1]                      
       4 　　
      
     

     

      

     
     

      

       live                
       1[
       2]                      
       2，
       5, 
      
     

     

      

     
     

      
                    
       2[
       1]                      
       2 　　
      
     

     

      

     
     

      

       shanghai            
       2[
       1]                      
       3 　　
      
     

     

      

     
     

      

       tom                 
       1[
       1]                      
       1
      
     
   

  

  

  
 参考文章 
  
B-树和B+树的应用：数据搜索和数据库索引 http://blog.csdn.net/hguisu/article/details/7786014
 
  
 
  
 B树、B-树、B+树、B*树 http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html
 
 
 
 
            </div>

 
目录
 
1. 二叉树
1.1. 二叉树
1.2. 二叉查找树
1.3. 平衡二叉树
  
2. 红黑树
2.1. 红黑树
2.2. 红黑树和平衡二叉树
  
3. B树
3.1. B树
3.1. B+树
3.3. B*树
3.4. B树，B+树与B*树的比较
 


  
 
1. 二叉树
 
1.1. 二叉树
 
二叉树的递归定义为：
 
二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；
左子树和右子树又同样都是二叉树
  
  
 
1.2. 二叉查找树
 
对于树中每个节点：
 
左子树上所有结点的值均小于或等于它根结点的值。
右子树上所有结点的值均大于或等于它根结点的值。
左、右子树也分别为二叉查找树。
 
查找的时间复杂度
 
根结点出发，沿某一个路径朝叶子结点前进。因此查找中数据比较次数与树的形态密切相关。
当树中每个结点左右子树高度大致相同时，树高为log2(N)。查找的平均时间复杂度为O(log2(N))。
单支树结构，此时树高n。平均查找长度为(n+1)/2，时间复杂度为O(N)。
  
  
 
1.3. 平衡二叉树
 
在符合二叉查找树的条件下，满足任何节点的两个子树的高度最大差为1。
 
时间复杂度
 
查找
 
最坏的情况也是O(log2(N))
 
插入
 
插入结点操作最多只需要旋转1次
 
删除
 
每一次删除操作最多需要log2(N)次旋转
  
  
 
2. 红黑树
 
2.1. 红黑树
 
红黑树是一种自平衡二叉查找树。
 
 
红黑树特点：
 
 
每个节点不是红色就是黑色的；
 
 
根节点总是黑色的；
 
 
每个叶子节点都是黑色的空节点（NIL节点）。
 
 
每个红色节点的两个子节点都是黑色。也就是说从每个叶子到根的所有路径上不能有两个连续的红色节点。
 
 
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
 
 
时间复杂度
 
查找
 
最长路径长度不超过最短路径长度的2倍，查找时间复杂度在log2(N)左右，但在最坏情况下(最长路径是最短路径的2倍少1)，要比平衡二叉树差一些
 
插入
 
插入最多只需要两次旋转
 
删除
 
删除最多需要三次旋转
  
  
 
2.2. 红黑树和平衡二叉树
 
红黑树和平衡二叉树的搜索时间复杂度都是O(log2(N))
红黑树并不追求完全平衡 ，它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
平衡二叉树在删除时最多需要旋转log2(N)次。红黑树在插入或者删除时，任何的不平衡都会在三次旋转之内解决。
涉及到频繁的插入和删除操作，选择红黑树。涉及的插入和删除操作并不频繁，而是查找操作相对更频繁，那么就优先选择平衡二叉树进行实现。
  
  
 
3. B树
 
3.1. B树
 
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：
 
 
根结点至少有两个子女；
 
 
每个非根节点所包含的关键字：至少M/2-1（取上整），至多M-1个
 
 
指向儿子的=指针个数非叶子结点的关键字个数+1；
 
 
所有的叶子结点都位于同一层。
 
 

 B树的特性：
 
 
关键字集合分布在整颗树中；
 
 
任何一个关键字出现且只出现在一个结点中；
 
 
搜索有可能在非叶子结点结束；
 
 
其搜索性能等价于在关键字全集内做一次二分查找；
  
  
 
 
3.1. B+树
 
B+树是应文件系统所需而出的一种B树的变型树。
 
 
一棵m阶的B+树和m阶的B-树的差异在于：
 
 
有n棵子树的结点中含有n个关键字。每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。
 
 
所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针。且叶子结点本身依关键字的大小自小而大顺序链接
 
 
所有的非终端结点可以看成是索引部分，结点中仅含其子树（或根结点）中的最大（或最小）关键字。
 
 
B+的特性：
 
 
所有关键字都出现在叶子结点的链表中，且链表中的关键字恰好是有序的；
 
 
不可能在非叶子结点查找成功；
 
 
非叶子结点相当于是叶子结点的索引，叶子结点相当于是存储关键字的数据层。
  
  
 
 
3.3. B*树
 
是B+树的变体，在B+树的非根和非叶子结点增加指向兄弟的指针。
 
  
  
 
3.4. B树，B+树与B*树的比较
 
 
B树的优势是当要查找的值恰好处在一个非叶子节点时，查找到该节点就会成功并结束查询。而B+树由于非叶节点只是索引部分，这些节点中只含有其子树中的最大(或最小)关键字，当非终端节点上的关键字等于给点值时，查找并不终止，而是继续向下直到叶子节点。因此在B+树中，无论查找成功与否，都是走了一条从根到叶子节点的路径。基于频率的搜索可以选用B树，越频繁query的结点越往根上走。
 
 
B+树有一个最大的好处，方便扫库。B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了。
 
 
B+树支持区间查询，而B树不支持。这是数据库选用B+树的最主要原因。比如要查 5-10之间的，B+树找到5这个关键字对应存储的数据，再找到10的，然后串起来就行了，B树就非常麻烦。
 
 
B+树的分裂方式和B*树的分裂方式不同，B树分配新结点的概率比B+树要低，空间使用率更高；
 

（一）编程语言介绍
 
编程语言（programminglanguage），是用来定义计算机程序的形式语言。它是一种被标准化的交流技巧，用来向计算机发出指令。一种计算机语言让程序员能够准确地定义计算机所需要使用的数据，并精确地定义在不同情况下所应当采取的行动。——百度百科
 
编程语言俗称“计算机语言”，种类非常的多，总的来说可以分成机器语言、汇编语言、高级语言三大类。电脑每做的一次动作，一个步骤，都是按照已经用计算机语言编好的程序来执行的，程序是计算机要执行的指令的集合，而程序全部都是用我们所掌握的语言来编写的。所以人们要控制计算机一定要通过计算机语言向计算机发出命令。
 目前通用的编程语言有两种形式：汇编语言和高级语言。
 
（二）几种主要的和常用的高级语言：
 
 
C语言
 
 
Java
 
 
C++
 
 
C#
 
 
JavaScript
 
 
 

  图 1：2018十大最热门编程语言排行榜 

2.1 C语言
 
C是迄今为止最常用的最古老的编程语言之一。C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。
 
尽管C语言提供了许多低级处理的功能，但仍然保持着良好跨平台的特性，以一个标准规格写出的C语言程序可在许多电脑平台上进行编译，甚至包含一些嵌入式处理器（单片机或称MCU）以及超级电脑等作业平台。
 
2.1.1 C语言特点
 
优点：
 
1、简洁紧凑、灵活方便
 C语言一共只有32个关键字，9种控制语句，程序书写形式自由，区分大小写。把高级语言的基本结构和语句与低级语言的实用性结合起来。C 语言可以像汇编语言一样对位、字节和地址进行操作，而这三者是计算机最基本的工作单元。
 
2、运算符丰富
 C语言的运算符包含的范围很广泛，共有34种运算符。C语言把括号、赋值、强制类型转换等都作为运算符处理。从而使C语言的运算类型极其丰富，表达式类型多样化。灵活使用各种运算符可以实现在其它高级语言中难以实现的运算。
 
3、数据类型丰富
 C语言的数据类型有：整型、实型、字符型、数组类型、指针类型、结构体类型、共用体类型等。能用来实现各种复杂的数据结构的运算。并引入了指针概念，使程序效率更高。
 
4、表达方式灵活实用
 C语言提供多种运算符和表达式值的方法，对问题的表达可通过多种途径获得，其程序设计更主动、灵活。它语法限制不太严格，程序设计自由度大，如对整型量与字符型数据及逻辑型数据可以通用等。
 
5、允许直接访问物理地址，对硬件进行操作
 由于C语言允许直接访问物理地址，可以直接对硬件进行操作，因此它既具有高级语言的功能，又具有低级语言的许多功能，能够像汇编语言一样对位（bit）、字节和地址进行操作，而这三者是计算机最基本的工作单元，可用来写系统软件。
 6、生成目标代码质量高，程序执行效率高
 C语言描述问题比汇编语言迅速，工作量小、可读性好，易于调试、修改和移植，而代码质量与汇编语言相当。C语言一般只比汇编程序生成的目标代码效率低10%～20%。
 
7、可移植性好
 C语言在不同机器上的C编译程序，86%的代码是公共的，所以C语言的编译程序便于移植。在一个环境上用C语言编写的程序，不改动或稍加改动，就可移植到另一个完全不同的环境中运行。
 
8、表达力强
 C语言有丰富的数据结构和运算符。包含了各种数据结构，如整型、数组类型、指针类型和联合类型等，用来实现各种数据结构的运算。C语言的运算符有34种，范围很宽，灵活使用各种运算符可以实现难度极大的运算。
 C语言能直接访问硬件的物理地址，能进行位（bit）操作。兼有高级语言和低级语言的许多优点。
 它既可用来编写系统软件，又可用来开发应用软件，已成为一种通用程序设计语言。
 另外C语言具有强大的图形功能，支持多种显示器和驱动器。且计算功能、逻辑判断功能强大。
 
缺点
 
1、 C语言的缺点主要表现在数据的封装性上，这一点使得C在数据的安全性上有很大缺陷，这也是C和C++的一大区别。
 2、 C语言的语法限制不太严格，对变量的类型约束不严格，影响程序的安全性，对数组下标越界不作检查等。从应用的角度，C语言比其他高级语言较难掌握。也就是说，对用C语言的人，要求对程序设计更熟练一些
 
2.2 Java
 
Java是一门面向对象编程语言，不仅吸收了C++语言的各种优点，还摒弃了C++里难以理解的多继承、指针等概念，因此Java语言具有功能强大和简单易用两个特征。Java语言作为静态面向对象编程语言的代表，极好地实现了面向对象理论，允许程序员以优雅的思维方式进行复杂的编程。Java具有简单性、面向对象、分布式、健壮性、安全性、平台独立与可移植性、多线程、动态性等特点。Java可以编写桌面应用程序、Web应用程序、分布式系统和嵌入式系统应用程序等
 
2.2.1 语言特点
 
Sun公司对Java的定义：Java是一种具有“简单、面向对象、分布式、解释型、健壮、安全、与体系结构无关、可移植、高性能、多线程和动态执行”等特点的语言。
 简单：简单而高效，Java系统（编译器和解释器）所占空间不到250KB。
 
面向对象：是纯面向对象的语言。
 
平台无关性与可移植性：可以在不同操作系统上运行。它既是编译型也是解释型语言。
 
稳定性和安全性：摒弃了C++中的不安全因素——指针数据类型。保证字节码文件加载的安全和访问系统资源的安全。
 
多线程并且是动态的：多线程使应用程序可以同时进行不同的操作和处理不同的时间。在执行过程中可以动态加载各类库，这一特点使之非常适合于网络运行，同时也非常有利于软件的开发，即使更新类库也不必重新编译使用这一类库的应用程序。
 
高性能：通常解释型语言的执行效率要低于直接执行机器码的速度，但Java的字节码转换成机器码非常简单和高效。
 
分布式：物理上分布，逻辑上统一。其内容包括数据分布和操作分布两个方面。数据分布是指数据可以分散存放于网络上的不同主机中，以解决海量数据的存储问题；操作分布则是指把计算分布到不同主机上进行处理，这就如同许多人协同共同完成一项大而复杂的工作一样。
 
2.3 C++
 
C++是C语言的继承，它既可以进行C语言的过程化程序设计，又可以进行以抽象数据类型为特点的基于对象的程序设计，还可以进行以继承和多态为特点的面向对象的程序设计。
 
C++擅长面向对象程序设计的同时，还可以进行基于过程的程序设计，因而C++就适应的问题规模而论，大小由之。
 
2.3.1 语言特点
 
支持数据封装和数据隐藏
 
在C++中，类是支持数据封装的工具，对象则是数据封装的实现。C++通过建立用户定义类支持数据封装和数据隐藏。
 在面向对象的程序设计中，将数据和对该数据进行合法操作的函数封装在一起作为一个类的定义。对象被说明为具有一个给定类的变量。每个给定类的对象包含这个类所规定的若干私有成员、公有成员及保护成员。完好定义的类一旦建立，就可看成完全封装的实体，可以作为一个整体单元使用。类的实际内部工作隐藏起来，使用完好定义的类的用户不需要知道类是如何工作的，只要知道如何使用它即可。
 
支持继承和重用
 
在C++现有类的基础上可以声明新类型，这就是继承和重用的思想。通过继承和重用可以更有效地组织程序结构，明确类间关系，并且充分利用已有的类来完成更复杂、深入的开发。新定义的类为子类，成为派生类。它可以从父类那里继承所有非私有的属性和方法，作为自己的成员。
 
支持多态性
 
采用多态性为每个类指定表现行为。多态性形成由父类和它们的子类组成的一个树型结构。在这个树中的每个子类可以接收一个或多个具有相同名字的消息。当一个消息被这个树中一个类的一个对象接收时，这个对象动态地决定给予子类对象的消息的某种用法。多态性的这一特性允许使用高级抽象。
 继承性和多态性的组合，可以轻易地生成一系列虽然类似但独一无二的对象。由于继承性，这些对象共享许多相似的特征。由于多态性，一个对象可有独特的表现方式，而另一个对象有另一种表现方式。
 
2.4 C#
 
C#是微软公司发布的一种面向对象的、运行于.NET Framework之上的高级程序设计语言。C#看起来与Java有着惊人的相似；它包括了诸如单一继承、接口、与Java几乎同样的语法和编译成中间代码再运行的过程。但是C#与Java有着明显的不同，它借鉴了Delphi的一个特点，与COM（组件对象模型）是直接集成的，而且它是微软公司 .NET windows网络框架的主角。
 
C#是一种安全的、稳定的、简单的、优雅的，由C和C++衍生出来的面向对象的编程语言。它在继承C和C++强大功能的同时去掉了一些它们的复杂特性（例如没有宏以及不允许多重继承）。C#综合了VB简单的可视化操作和C++的高运行效率，以其强大的操作能力、优雅的语法风格、创新的语言特性和便捷的面向组件编程的支持成为.NET开发的首选语言。
 
2.4.1语言特点
 
简洁的语法
 
语法中的冗余是C++中的常见的问题，比如"const"和"#define"、各种各样的字符类型等等。C#对此进行了简化，只保留了常见的形式，而别的冗余形式从它的语法结构中被清除了出去。
 
精心地面向对象设计
 
C#具有面向对象的语言所应有的一切特性：封装、继承与多态性，这并不出奇。然而，通过精心地面向对象设计，从高级商业对象到系统级应用，C#建造广泛组件的绝对选择。
 
在C#的类型系统中，每种类型都可以看作一个对象。C#提供了一个叫做装箱(boxing)与拆箱(unboxing)的机制来完成这种操作，而不给使用者带来麻烦。C#只允许单继承，即一个类不会有多个基类，从而避免了类型定义的混乱。在后面的学习中你很快会发现，C#中没有了全局函数，没有了全局变量，也没有了全局常数。一切的一切，都必须封装在一个类之中。你的代码将具有更好的可读性，并且减少了发生命名冲突的可能。
 
与Web的紧密结合
 
由于有了Web服务框架的帮助，对程序员来说，网络服务看起来就象是C#的本地对象。程序员们能够利用他们已有的面向对象的知识与技巧开发Web服务。仅需要使用简单的C#语言结构，C#组件将能够方便地为Web服务，并允许它们通过Internet被运行在任何操作系统上的任何语言所调用。举个例子，XML已经成为网络中数据结构传递的标准，为了提高效率，C#允许直接将XML数据映射成为结构。这样就可以有效的处理各种数据。
 
完整的安全性与错误处理
 
语言的安全性与错误处理能力，是衡量一种语言是否优秀的重要依据。变量是类型安全的。C#中不能使用未初始化的变量，对象的成员变量由编译器负责将其置为零，当局部变量未经初始化而被使用时，编译器将做出提醒；C#不支持不安全的指向，不能将整数指向引用类型，例如对象，当进行下行指向时，C#将自动验证指向的有效性；C#中提供了边界检查与溢出检查功能。
 
灵活性与兼容性
 
在简化语法的同时，C#并没有失去灵活性。尽管它不是一种无限制语言，比如：它不能用来开发硬件驱动程序，在默认的状态下没有指针等等。如果需要，C#允许你将某些类或者类的某些方法声明为非安全的。这样一来，你将能够使用指针、结构和静态数组，并且调用这些非安全代码不会带来任何其它的问题。此外，它还提供了一个另外的东西（这样的称呼多少有些不敬）来模拟指针的功能–delegates，代表。再举一个例子：C#不支持类的多继承，但是通过对接口的继承，你将获得这一功能。
 
正是由于其灵活性，C#允许与C风格的需要传递指针型参数的API进行交互操作，DLL的任何入口点都可以在程序中进行访问。C#遵守.NET公用语言规范(Common Language Specification,CLS)，从而保证了C#组件与其它语言组件间的互操作性。元数据(Metadata)概念的引入既保证了兼容性，又实现了类型安全。
 
2.5 JavaScript
 
JavaScript一种直译式脚本语言，是一种动态类型、弱类型、基于原型的语言，内置支持类型。它的解释器被称为JavaScript引擎，为浏览器的一部分，广泛用于客户端的脚本语言，最早是在HTML（标准通用标记语言下的一个应用）网页上使用，用来给HTML网页增加动态功能。
 
2.5.1 语言特点
 
JavaScript脚本语言具有以下特点:
 
(1)脚本语言 JavaScript是一种解释型的脚本语言,C、C++等语言先编译后执行,而JavaScript是在程序的运行过程中逐行进行解释。
 (2)基于对象 JavaScript是一种基于对象的脚本语言,它不仅可以创建对象,也能使用现有的对象。
 (3)简单 JavaScript语言中采用的是弱类型的变量类型,对使用的数据类型未做出严格的要求,是基于Java基本语句和控制的脚本语言,其设计简单紧凑。
 (4)动态性 JavaScript是一种采用事件驱动的脚本语言,它不需要经过Web服务器就可以对用户的输入做出响应。在访问一个网页时,鼠标在网页中进行鼠标点击或上下移、窗口移动等操作JavaScript都可直接对这些事件给出相应的响应。
 (5)跨平台性 JavaScript脚本语言不依赖于操作系统,仅需要浏览器的支持。因此一个JavaScript脚本在编写后可以带到任意机器上使用,前提上机器上的浏览器支 持JavaScript脚本语言,目前JavaScript已被大多数的浏览器所支持。
 
不同于服务器端脚本语言，例如PHP与ASP，JavaScript主要被作为客户端脚本语言在用户的浏览器上运行，不需要服务器的支持。所以在早期程序员比较青睐于JavaScript以减少对服务器的负担，而与此同时也带来另一个问题：安全性。
 
而随着服务器的强壮，虽然程序员更喜欢运行于服务端的脚本以保证安全，但JavaScript仍然以其跨平台、容易上手等优势大行其道。同时，有些特殊功能（如AJAX）必须依赖Javascript在客户端进行支持。随着引擎如V8和框架如Node.js的发展，及其事件驱动及异步IO等特性，JavaScript逐渐被用来编写服务器端程序。
 
2.5.2 日常用途
 
嵌入动态文本于HTML页面。
对浏览器事件做出响应。
读写HTML元素。
在数据被提交到服务器之前验证数据。
检测访客的浏览器信息。
控制cookies，包括创建和修改等。
基于Node.js技术进行服务器端编程。

 
 


 
向AI转型的程序员都关注了这个号👇👇👇
 
大数据挖掘DT机器学习  公众号： datayx
 


 
决策树 概述
 
决策树（Decision Tree）算法是一种基本的分类与回归方法，是最经常使用的数据挖掘算法之一。我们这章节只讨论用于分类的决策树。
 


 
决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是 if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。
 


 
决策树学习通常包括 3 个步骤：特征选择、决策树的生成和决策树的修剪。
 
决策树 场景
 
一个叫做 "二十个问题" 的游戏，游戏的规则很简单：参与游戏的一方在脑海中想某个事物，其他参与者向他提问，只允许提 20 个问题，问题的答案也只能用对或错回答。问问题的人通过推断分解，逐步缩小待猜测事物的范围，最后得到游戏的答案。
 
一个邮件分类系统，大致工作流程如下：
 


 

 


 


 
首先检测发送邮件域名地址。如果地址为 myEmployer.com, 则将其放在分类 
"无聊时需要阅读的邮件"中。
如果邮件不是来自这个域名，则检测邮件内容里是否包含单词 "曲棍球" , 
如果包含则将邮件归类到 "需要及时处理的朋友邮件", 
如果不包含则将邮件归类到 "无需阅读的垃圾邮件" 。
 


 
决策树的定义：
 


 
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性(features)，叶结点表示一个类(labels)。
 


 


 
用决策树对需要测试的实例进行分类：从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分配到叶结点的类中。
 
决策树 原理
 
决策树 须知概念
 
信息熵 & 信息增益
 
熵（entropy）： 熵指的是体系的混乱的程度，在不同的学科中也有引申出的更为具体的定义，是各领域十分重要的参量。
 
信息论（information theory）中的熵（香农熵）： 是一种信息的度量方式，表示信息的混乱程度，也就是说：信息越有序，信息熵越低。例如：火柴有序放在火柴盒里，熵值很低，相反，熵值很高。
 
信息增益（information gain）： 在划分数据集前后信息发生的变化称为信息增益。
 
决策树 工作原理
 
如何构造一个决策树?
我们使用 createBranch() 方法，如下所示：
 

 


 


 
决策树 开发流程
 


 
收集数据：可以使用任何方法。
 
准备数据：树构造算法 (这里使用的是ID3算法，只适用于标称型数据，这就是为什么数值型数据必须离散化。 还有其他的树构造算法，比如CART)
 
分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
 
训练算法：构造树的数据结构。
 
测试算法：使用训练好的树计算错误率。
 
使用算法：此步骤可以适用于任何监督学习任务，而使用决策树可以更好地理解数据的内在含义。
 


 
决策树 算法特点
 


 
优点：计算复杂度不高，输出结果易于理解，数据有缺失也能跑，可以处理不相关特征。
 
缺点：容易过拟合。
 
适用数据类型：数值型和标称型。
 


 
决策树 项目案例
 


 
项目案例1: 判定鱼类和非鱼类
 


 
项目概述
 


 
根据以下 2 个特征，将动物分成两类：鱼类和非鱼类。
 


 
特征：
 


 
    不浮出水面是否可以生存
    是否有脚蹼
 


 
开发流程
 


 
完整代码地址: https://github.com/apachecn/MachineLearning/blob/master/src/py2.x/ML/3.DecisionTree/DecisionTree.py
 


 
收集数据：可以使用任何方法
 
准备数据：树构造算法（这里使用的是ID3算法，因此数值型数据必须离散化。）
 


 
分析数据：可以使用任何方法，构造树完成之后，我们可以将树画出来。
 
训练算法：构造树结构
 
测试算法：使用习得的决策树执行分类
 
使用算法：此步骤可以适用于任何监督学习任务，而使用决策树可以更好地理解数据的内在含义
 


 
    收集数据：可以使用任何方法
 

 
我们利用 createDataSet() 函数输入数据
 


 

 
使用算法：此步骤可以适用于任何监督学习任务，而使用决策树可以更好地理解数据的内在含义。
 


 


 

 


 
项目案例2: 使用决策树预测隐形眼镜类型
 


 
完整代码地址: https://github.com/apachecn/MachineLearning/blob/master/src/py2.x/ML/3.DecisionTree/DecisionTree.py
 


 
项目概述

 
隐形眼镜类型包括硬材质、软材质以及不适合佩戴隐形眼镜。我们需要使用决策树预测患者需要佩戴的隐形眼镜类型。
 


 
开发流程

 
收集数据: 提供的文本文件。
解析数据: 解析 tab 键分隔的数据行
分析数据: 快速检查数据，确保正确地解析数据内容，使用 createPlot() 函数绘制最终的树形图。
训练算法: 使用 createTree() 函数。
测试算法: 编写测试函数验证决策树可以正确分类给定的数据实例。
使用算法: 存储树的数据结构，以便下次使用时无需重新构造树。


 

  
收集数据：提供的文本文件
 
 


 
文本文件数据格式如下：
 

 


 

  
解析数据：解析 tab 键分隔的数据行
 
 
lecses = [inst.strip().split('\t') for inst in fr.readlines()]
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
 

  
分析数据：快速检查数据，确保正确地解析数据内容，使用 createPlot() 函数绘制最终的树形图。
 
 
>>> treePlotter.createPlot(lensesTree)
 

  
训练算法：使用 createTree() 函数
 
 


 


 

 
https://github.com/apachecn/AiLearning/blob/master/docs/3.%E5%86%B3%E7%AD%96%E6%A0%91.md
 


 


 
集成方法-随机森林和AdaBoost
 


 
集成方法: ensemble method（元算法: meta algorithm） 概述
 
概念：是对其他算法进行组合的一种形式。
通俗来说： 当做重要决定时，大家可能都会考虑吸取多个专家而不只是一个人的意见。 机器学习处理问题时又何尝不是如此？ 这就是集成方法背后的思想。
集成方法：
 
投票选举(bagging: 自举汇聚法 bootstrap aggregating): 是基于数据随机重抽样分类器构造的方法
再学习(boosting): 是基于所有分类器的加权求和的方法


 
集成方法 场景
 
目前 bagging 方法最流行的版本是: 随机森林(random forest)
选男友：美女选择择偶对象的时候，会问几个闺蜜的建议，最后选择一个综合得分最高的一个作为男朋友
 


 
目前 boosting 方法最流行的版本是: AdaBoost
追女友：3个帅哥追同一个美女，第1个帅哥失败->(传授经验：姓名、家庭情况) 第2个帅哥失败->(传授经验：兴趣爱好、性格特点) 第3个帅哥成功
 


 

  
bagging 和 boosting 区别是什么？
 
 
bagging 是一种与 boosting 很类似的技术, 所使用的多个分类器的类型（数据量和特征量）都是一致的。
bagging 是由不同的分类器（1.数据随机化 2.特征随机化）经过训练，综合得出的出现最多分类结果；boosting 是通过调整已有分类器错分的那些数据来获得新的分类器，得出目前最优的结果。
bagging 中的分类器权重是相等的；而 boosting 中的分类器加权求和，所以权重并不相等，每个权重代表的是其对应分类器在上一轮迭代中的成功度。


 
随机森林
 
随机森林 概述
 
随机森林指的是利用多棵树对样本进行训练并预测的一种分类器。
决策树相当于一个大师，通过自己在数据集中学到的知识用于新数据的分类。但是俗话说得好，一个诸葛亮，玩不过三个臭皮匠。随机森林就是希望构建多个臭皮匠，希望最终的分类效果能够超过单个大师的一种算法。


 
随机森林 原理
 
那随机森林具体如何构建呢？
有两个方面：

 
数据的随机性化
待选特征的随机化

 
使得随机森林中的决策树都能够彼此不同，提升系统的多样性，从而提升分类性能。
 

  
数据的随机化：使得随机森林中的决策树更普遍化一点，适合更多的场景。
 
 
（有放回的准确率在：70% 以上， 无放回的准确率在：60% 以上）
 
采取有放回的抽样方式 构造子数据集，保证不同子集之间的数量级一样（不同子集／同一子集 之间的元素可以重复）
利用子数据集来构建子决策树，将这个数据放到每个子决策树中，每个子决策树输出一个结果。
然后统计子决策树的投票结果，得到最终的分类 就是 随机森林的输出结果。
如下图，假设随机森林中有3棵子决策树，2棵子树的分类结果是A类，1棵子树的分类结果是B类，那么随机森林的分类结果就是A类。


 

 


 

  
待选特征的随机化
 
 
子树从所有的待选特征中随机选取一定的特征。
在选取的特征中选取最优的特征。
 


 
下图中，蓝色的方块代表所有可以被选择的特征，也就是目前的待选特征；黄色的方块是分裂特征。
 

左边是一棵决策树的特征选取过程，通过在待选特征中选取最优的分裂特征（别忘了前文提到的ID3算法，C4.5算法，CART算法等等），完成分裂。
右边是一个随机森林中的子树的特征选取过程。
 


 

 


 


 


 

  
随机森林 开发流程
 
 
收集数据：任何方法
准备数据：转换样本集
分析数据：任何方法
训练算法：通过数据随机化和特征随机化，进行多实例的分类评估
测试算法：计算错误率
使用算法：输入样本数据，然后运行 随机森林 算法判断输入数据分类属于哪个分类，
最后对计算出的分类执行后续处理
 

  
随机森林 算法特点

 
 
优点：几乎不需要输入准备、可实现隐式特征选择、训练速度非常快、其他模型很难超越、
很难建立一个糟糕的随机森林模型、大量优秀、免费以及开源的实现。
缺点：劣势在于模型大小、是个很难去解释的黑盒子。
适用数据范围：数值型和标称型
 


 
项目案例: 声纳信号分类
 
项目概述
 
这是 Gorman 和 Sejnowski 在研究使用神经网络的声纳信号分类中使用的数据集。任务是训练一个模型来区分声纳信号。
 


 
开发流程
 
收集数据：提供的文本文件
准备数据：转换样本集
分析数据：手工检查数据
训练算法：在数据上，利用 random_forest() 函数进行优化评估，返回模型的综合分类结果
测试算法：在采用自定义 n_folds 份随机重抽样 进行测试评估，得出综合的预测评分
使用算法：若你感兴趣可以构建完整的应用程序，从案例进行封装，也可以参考我们的代码
 

  
收集数据：提供的文本文件
 
 
样本数据：sonar-all-data.txt
 


 

  
使用算法：若你感兴趣可以构建完整的应用程序，从案例进行封装，也可以参考我们的代码
 
 


 
完整代码地址: https://github.com/apachecn/MachineLearning/blob/master/src/py2.x/ML/7.RandomForest/randomForest.py
 


 

 


 
AdaBoost
 
AdaBoost (adaptive boosting: 自适应 boosting) 概述
 
能否使用弱分类器和多个实例来构建一个强分类器？ 这是一个非常有趣的理论问题。
 


 
AdaBoost 原理
 

  
AdaBoost 工作原理
 
 


 

 


 

  
AdaBoost 开发流程
 
 
收集数据：可以使用任意方法
准备数据：依赖于所使用的弱分类器类型，本章使用的是单层决策树，这种分类器可以处理任
何数据类型。
    当然也可以使用任意分类器作为弱分类器，第2章到第6章中的任一分类器都可以充
当弱分类器。
    作为弱分类器，简单分类器的效果更好。
分析数据：可以使用任意方法。
训练算法：AdaBoost 的大部分时间都用在训练上，分类器将多次在同一数据集上
训练弱分类器。
测试算法：计算分类的错误率。
使用算法：通SVM一样，AdaBoost 预测两个类别中的一个。如果想把它应用到多个类别的
场景，那么就要像多类 SVM 中的做法一样对 AdaBoost 进行修改。
 

  
AdaBoost 算法特点
 
 
* 优点：泛化（由具体的、个别的扩大为一般的）错误率低，易编码，可以应用在大部分分
类器上，无参数调节。
* 缺点：对离群点敏感。
* 适用数据类型：数值型和标称型数据。
 


 
项目案例: 马疝病的预测

 

  
项目流程图
 
 


 

 


 
基于单层决策树构建弱分类器
 
单层决策树(decision stump, 也称决策树桩)是一种简单的决策树。
 


 
项目概述
 
预测患有疝气病的马的存活问题，这里的数据包括368个样本和28个特征，疝气病是描述马胃肠痛的术语，然而，这种病并不一定源自马的胃肠问题，其他问题也可能引发疝气病，该数据集中包含了医院检测马疝气病的一些指标，有的指标比较主观，有的指标难以测量，例如马的疼痛级别。另外，除了部分指标主观和难以测量之外，该数据还存在一个问题，数据集中有30%的值是缺失的。
 


 
完整代码地址: https://github.com/apachecn/MachineLearning/blob/master/src/py2.x/ML/7.AdaBoost/adaboost.py
 



 
开发流程

 
收集数据：提供的文本文件
准备数据：确保类别标签是+1和-1，而非1和0
分析数据：统计分析
训练算法：在数据上，利用 adaBoostTrainDS() 函数训练出一系列的分类器
测试算法：我们拥有两个数据集。在不采用随机抽样的方法下，我们就会对 AdaBoost 和 
Logistic 回归的结果进行完全对等的比较
使用算法：观察该例子上的错误率。不过，也可以构建一个 Web 网站，让驯马师输入马的
症状然后预测马是否会死去
 

  
收集数据：提供的文本文件

 
 
训练数据：horseColicTraining.txt
测试数据：horseColicTest.txt
 


 

 


 

  
分析数据：统计分析
 
 
过拟合(overfitting, 也称为过学习)
 
发现测试错误率在达到一个最小值之后有开始上升，这种现象称为过拟合。
 


 

 


 
通俗来说：就是把一些噪音数据也拟合进去的，如下图。
 

 
训练算法：在数据上，利用 adaBoostTrainDS() 函数训练出一系列的分类器。

 


 

 

 


 

 


 
要点补充
 


 

  
非均衡现象：
 
 
在分类器训练时，正例数目和反例数目不相等（相差很大）。或者发生在正负例分类错误的成本不同的时候。
 
判断马是否能继续生存(不可误杀)
过滤垃圾邮件(不可漏判)
不能放过传染病的人
不能随便认为别人犯罪
 
我们有多种方法来处理这个问题： 具体可参考此链接
 
https://machinelearningmastery.com/tactics-to-combat-imbalanced-classes-in-your-machine-learning-dataset/
 


 
再结合书中的方法，可以归为八大类：
 


 
1.能否收集到更多的数据？
 
这个措施往往被人们所忽略，被认为很蠢。但是更大的数据集更能体现样本的分布，多样性。
 


 
2.尝试使用其他的评价指标
 
Accuracy 或者error rate 不能用于非均衡的数据集。这会误导人。这时候可以尝试其他的评价指标。
 
Confusion Matrix 混淆矩阵：使用一个表格对分类器所预测的类别与其真实的类别的样本统计，分别为：TP、FN、FP与TN。
 
Precision：精确度
 
Recall： 召回率
 
F1 Score (or F-Score)： 精确度和召回率的加权平均
 
或者使用
 


 
Kappa (Cohen's kappa)
 
ROC Curves
 

  
ROC 评估方法
 
 
ROC 曲线: 最佳的分类器应该尽可能地处于左上角
 


 


 

 


 
对不同的 ROC 曲线进行比较的一个指标是曲线下的面积(Area Unser the Curve, AUC).
AUC 给出的是分类器的平均性能值，当然它并不能完全代替对整条曲线的观察。
一个完美分类器的 AUC 为1，而随机猜测的 AUC 则为0.5。
 


 
3.尝试对样本重抽样

 
欠抽样(undersampling)或者过抽样(oversampling)
 
- 欠抽样: 意味着删除样例
- 过抽样: 意味着复制样例(重复使用)
 


 
对大类进行欠抽样
 
对小类进行过抽样
 
或者结合上述两种方法进行抽样
 
一些经验法则：
 
考虑样本（超过1万、十万甚至更多）进行欠采样，即删除部分样本；
考虑样本（不足1为甚至更少）进行过采样，即添加部分样本的副本；
考虑尝试随机采样与非随机采样两种采样方法；
考虑对各类别尝试不同的采样比例，不一定是1:1
考虑同时使用过采样与欠采样        
 


 
4.尝试产生人工生成的样本
 
一种简单的方法就是随机抽样小类样本的属性（特征）来组成新的样本即属性值随机采样。你可以根据经验进行抽样，可以使用其他方式比如朴素贝叶斯方法假设各属性之间互相独立进行采样，这样便可得到更多的数据，但是无法保证属性之间的非线性关系。
 


 
当然也有系统性的算法。最常用的SMOTE(Synthetic Minority Over-Sampling Technique)。 顾名思义，这是一种over sampling（过抽样）的方式。它是产生人为的样本而不是制造样本副本。这个算法是选取2个或者2个以上相似的样本（根据距离度量 distance measure），然后每次选择其中一个样本，并随机选择一定数量的邻居样本对选择的那个样本的一个属性增加噪声(每次只处理一个属性)。这样就构造了更多的新生数据。具体可以参见原始论文。
 
http://www.jair.org/papers/paper953.html
 


 
python实现可以查阅UnbalancedDataset
 
https://github.com/scikit-learn-contrib/imbalanced-learn
 


 
5.尝试不同的算法

 
强烈建议不要在每个问题上使用你最喜欢的算法。虽然这个算法带来较好的效果，但是它也会蒙蔽你观察数据内蕴含的其他的信息。至少你得在同一个问题上试试各种算法。具体可以参阅Why you should be Spot-Checking Algorithms on your Machine Learning Problems
 


 
https://machinelearningmastery.com/why-you-should-be-spot-checking-algorithms-on-your-machine-learning-problems/
 


 
比如说，决策树经常在非均衡数据集上表现良好。创建分类树时候使用基于类变量的划分规则强制使类别表达出来。如果有疑惑，可以尝试一些流行的决策树，比如, C4.5, C5.0, CART 和 Random Forrest。
 


 


 
6.尝试使用惩罚的模型

 
你可以使用同种算法但是以不同的角度对待这个问题。
 
惩罚的模型就是对于不同的分类错误给予不同的代价（惩罚）。比如对于错分的小类给予更高的代价。这种方式会使模型偏差，更加关注小类。
 
通常来说这种代价/惩罚或者比重在学习中算法是特定的。比如使用代价函数来实现：
 


 

  
代价函数
 
 
基于代价函数的分类器决策控制：TP*(-5)+FN*1+FP*50+TN*0
 


 

 
这种方式叫做 cost sensitive learning，Weka 中相应的框架可以实现叫CostSensitiveClassifier
 


 
http://weka.sourceforge.net/doc.dev/weka/classifiers/meta/CostSensitiveClassifier.html
 


 
如果当你只能使用特定算法而且无法重抽样，或者模型效果不行，这时候使用惩罚（penalization）是可行的方法。这提供另外一种方式来“平衡”类别。但是设定惩罚函数/代价函数是比较复杂的。最好还是尝试不同的代价函数组合来得到最优效果。
 


 
7.尝试使用不同的角度

 
其实有很多研究关于非均衡数据。他们有自己的算法，度量，术语。
 
从它们的角度看看你的问题，思考你的问题，说不定会有新的想法。
 
两个领域您可以考虑： anomaly detection(异常值检测) 和 change detection（变化趋势检测）。
 


 
Anomaly dectection 就是检测稀有事件。 比如通过机器震动来识别机器谷中或者根据一系列系统的调用来检测恶意操作。与常规操作相比，这些事件是罕见的。
 


 
把小类想成异常类这种转变可能会帮助你想到新办法来分类数据样本。
 
change detection 变化趋势检测类似于异常值检测。但是他不是寻找异常值而是寻找变化或区别。比如通过使用模式或者银行交易记录来观察用户行为转变。
 


 
这些两种转变可能会给你新的方式去思考你的问题和新的技术去尝试。    
 


 
8.尝试去创新
 
仔细思考你的问题然后想想看如何将这问题细分为几个更切实际的小问题。
 
比如：
 


 
将你的大类分解成多个较小的类；
 
使用One Class分类器（看待成异常点检测）；
 
对数据集进行抽样成多个数据集，使用集成方式，训练多个分类器，然后联合这些分类器进行分类；
 


 
这只是一个例子。更多的可以参阅In classification, how do you handle an unbalanced training set? 和Classification when 80% of my training set is of one class
 


 
http://www.quora.com/In-classification-how-do-you-handle-an-unbalanced-training-set
 


 
https://github.com/apachecn/AiLearning/blob/master/docs/7.%E9%9B%86%E6%88%90%E6%96%B9%E6%B3%95-%E9%9A%8F%E6%9C%BA%E6%A3%AE%E6%9E%97%E5%92%8CAdaBoost.md
 


 


 


 

 
阅读过本文的人还看了以下：
 


 


 


 



 


 
不断更新资源
 
深度学习、机器学习、数据分析、python
 
 搜索公众号添加： datayx  
 

 
长按图片，识别二维码，点关注