博客思路
 
1.通过二叉排序树引出平衡二叉树
 
2.如何判断是不是一棵平衡二叉树
 
3.平衡因子
 
4.左旋  右旋   双旋
 
5.通过画图创建一棵二叉排序树
 
6.二叉排序树的代码思路和整体框架
 
 
 
1.二叉排序树
 
二叉排序树，又叫二叉查找树，它或者是一棵空树；或者是具有以下性质的二叉树：
 1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
 2. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
 3. 它的所有结点的左右子树也分别为二叉排序树。
 
讲平衡二叉树之前我们讲一下二叉排序树。
 
看看下面两张图
 
 
这两个都是二叉排序树吗？没错你看下上面的概念的话，发现两个都是二叉排序树。只是右边的树长的丑了一点，它是一棵右斜树。它们都是一样的关键字1，2，3，4，5，6，7，8，9 只是根结点取得不一样，排出来就长的不一样。
 
再来看看这两棵树的查找效率。我的天！这个斜树查找效率和链表的循序遍历效率都一模一样了。可见二叉排序树的查找效率是有点看运气的。想要建立一棵好看的二叉排序树，这个和快排有点像，知道一个数组所有的数字，每次取基准点，这里是取根，取越中间越好。如果每棵子二叉排序树都能取到尽量靠中间的数值当根结点时候，排出来的树越好看（也就是高度差低）。但是如果后面要继续对树进行插入删除，又改变了树的结构，是不是这棵树的长相就变得不可控了。查找效率也变得不可控。于是引出今天的平衡二叉树。
 
2.平衡二叉树
 
（AVL）平衡二叉树是一种二叉排序树，其中每个结点的左子树和右子树的高度差至多等于1。它是一种高度平衡的二叉排序树。意思是说，要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。
 
平衡二叉树是一种二叉排序树。也就是二叉排序树包含了平衡二叉排序树，其次它要满足后面的约束条件，就是每个结点的左子树和右子树的高度差不超过1
 
我先看几张图片判断一下哪些是平衡二叉树。
 
 
 
 
看完上面的图相信大家应该能判断出来什么树是平衡二叉树了
 
 
 
平衡因子
 
平衡因子就是在平衡二叉树结点的结构体引进的一个int 变量，用来记录该结点的（左子树整体高度 - 右子树整体高度）。平衡二叉树的平衡因子只能为（-1，0，1）。
 
画个图解释下
 
 
 
 
个人心得：下面到了重点部分了，其实我在学平衡二叉树也是从这里开始有些困惑，但是这时候先不要去考虑所有的问题，先去考虑下局部问题，那就是什么是左旋  右旋 双旋。  因为我们知道建立一棵平衡二叉树，关键是要降低整个树的高度差。所以不要被一些（左旋    右旋   双旋）名词吓到了。就是个调高度差的东西罢了。弄清楚了左旋 右旋  双旋
 
平衡二叉树的旋转问题
 
要学习平衡二叉树之前我们要先看一下左旋  右旋  双旋，我们知道当我们插入一个结点在平衡二叉树上时候，整个平衡二叉树可能左右子树的高度差可能发生了变化，而左旋  右旋  双旋目的就是为了降低整个树的高度差，使得它们左右子树的高度差不超过1。
 
左旋
 
先看一下图
 
 
 
 
下面是左旋转时候，新根带有左子树的
 
 
 
 
我大致要描述的文字在图里已经描述了我就不再描述了
 
看一下左旋代码
 
typedef struct BiNode
{
	int data;        //这里可以对data 类型进行宏定义，这里是方便理解
	int bf;           //平衡因子
	struct BiNode *lchild,*rchild;
}BiNode,*BiTree;



void L_Rotate(BiTree *p)
{
    BiTree L;                       //(*p) p的解引用还是一个指针，指向上图2结点
    L = (*P)->rchild;             //指针L指向上图的4结点   
    (*p)->rchild = L->lchild;      //让(*p) 也就是2结点右子树 = 4结点的左子树
    L->lchild = (*p);              //   让4结点的左子树  = 2结点；
    *p = L;                       //把4结点转化成新根
      
}
 
看完左旋我就不讲右旋了，真的是一样理解的。或者最后看总代码时候再理解把
 
 
 
双旋是什么鬼我们先把左旋和右旋解决不了的问题找出来先
 
 
 
这个便需要我们双旋，不要想那么复杂 。看完图片相信大家能找到问题所在了。现在就是要解决这个问题，我们要先找到
 
那个符号不统一的9结点，然后对它先进行右旋，在进行左旋。这就是双旋
 
 
这就是所谓的双旋。这里的符号统一我可能没描述清楚，是失衡结点，和要当新根结点符号统一就好了。我再画一张图。
 
 
 
 
说下当右子树失衡之后的调整的代码思路
 
当我们发现一棵树右边因为插入结点失衡了，要进行调整了
 
传进 T  是一个二级指针，指向一个失衡结点，这个失衡结点也就是从下往上看第一个平衡因子绝对值超过1的结点。因为是右子树平衡调整。我就知道要调整是这个失衡点的右子树。
 
1）定义 p = (*T)->rchild;  让它指向失衡结点的右子树。
 
2）利用switch p 的平衡因子的大小做出是左旋  还是双旋的操作
 
3）发现是p 的右子树高，证明可以直接左旋，左旋前要调整平衡因子大小。
 
调整平衡因子的逻辑我画个图这是推导（*T），p也可以推导
 
 
4）发现p的平衡因子 为LH     平衡因子符号不统一
 
这时候我们需要做的本身是先右旋再左旋但是我们要先调节它的平衡因子
 
5）于是多了一个switch(pl->bf)调整它的平衡因子的。这里我就不画图讲解了
 
6）右旋再左旋
 
#define LH   1
#define EH   0
#define RH  -1


void RightBalance(BiTree *T)
{
    BiTree p,pl;
    p = (*T）->rchild;        //已经知道是右边高了才失衡，所以p指针直接指向它的右子树    
    
    switch (p->bf)         //这个是看要左旋还是  双旋，再调它的平衡因子            
    {
           case RH:             //p右子树高，证明平衡因子符号统一，直接左旋      
            (*T)->bf = p->bf = EH;     //看上图
            L_Rotate(T);            //左旋函数
            break;
            case LH:             //p左子树高，要双旋先调平衡因子  
             pl = p->lchild;
            switch(pl->bf)
            {
                case RH:
                (*T)->bf = LH;
                p->bf = EH;
                break;
                case EH:
                 (*T)->bf = p->bf = EH; 
                case LH:
                (*T)->bf = EH;
                p->bf = RH;
                break;
            }
            pl->bf = EH;              
            R_Rotate(&(*T)->rchild);    //把它的右子树先右旋，平衡因子符号统一
            L_Rotate(T);              //左旋
    }
}
 
左平衡我就不说了。一样的推导
 
 
 
看完前面再看现在的代码就轻松很多了自己看一下吧。
 
#include <iostream>
using namespace std;

#define  LH  1
#define  EH  0
#define  RH  -1
#define  ElemType  int
#define TRUE   1
#define FALSE   0

typedef struct BiNode
{
    ElemType data;
    int bf;
    struct BiNode  *lchild;
    struct  BiNode *rchild;
}BiNode,*BiTree;


void L_Rotate(BiTree *p)      //左旋
{
    BiTree R;                       
    R = (*p)->rchild;               
    (*p)->rchild = R->lchild;      
    R->lchild = (*p);              
    *p = R;                         
}


void R_Rotate(BiTree *p)    //右旋
{
    BiTree L;
    L = (*p)->lchild;
    (*p)->lchild = L->rchild;
    L->rchild = (*p);
    *p = L;
}


void RightBalance(BiTree *T)    //右平衡调整
{
    BiTree R,Rl;
    R = (*T)->rchild;        //已经知道是右边高了才失衡，所以R指针直接指向它的右子树    
    
    switch (R->bf)         //这个是看要左旋还是  双旋，再调它的平衡因子            
    {
           case RH:             //R右子树高，证明平衡因子符号统一，直接左旋      
            (*T)->bf = R->bf = EH;    
            L_Rotate(T);            //左旋函数
            break;
            case LH:             //R左子树高，要双旋先调平衡因子  
             Rl = R->lchild;
            switch(Rl->bf)    //调整平衡因子大小
            {
                case RH:
                (*T)->bf = LH;
                R->bf = EH;
                break;
                case EH:
                 (*T)->bf = R->bf = EH; 
                case LH:
                (*T)->bf = EH;
                R->bf = RH;
                break;
            }
            Rl->bf = EH;              
            R_Rotate(&(*T)->rchild);    //把它的右子树先右旋，平衡因子符号统一
            L_Rotate(T);              //左旋
    }
}


void LeftBalance(BiTree *T)
{
    BiTree L ,Lr;
    L = (*T)->lchild;

    switch(L->bf)
    {
        case LH:
        (*T)->bf = L->bf = EH;
        R_Rotate(T);
        break;
    
        case RH:
        Lr = L->rchild;
        switch(Lr->bf)
        {
            case LH: 
            (*T)->bf = RH;
            L->bf =EH;
            break;
            case EH: 
            (*T)->bf=L->bf = EH;
            break;
            case RH: 
            (*T)->bf = EH;
            L->bf = LH;
            break;
        }
        Lr->bf = EH;
        L_Rotate(&(*T)->lchild);
        R_Rotate(T);
    }
}


int InsertAVL(BiTree *T,ElemType val,int *taller)
{
    if(!*T)
    {
        *T = (BiTree)malloc(sizeof(BiNode));
        (*T)->data = val;
        *taller = TRUE;
    }
    else
    {
        if(val == (*T)->data)
        {
            *taller = FALSE;
            return FALSE;
        }
          
        if(val < (*T)->data)
        {
                if(!InsertAVL(&(*T)->lchild,val,taller))
                {
                    *taller = FALSE;
                    return FALSE;
                }
                
                if(*taller)
                {
                            switch((*T)->bf)
                            {
                     case LH:
                            LeftBalance(T);
                            *taller = FALSE;
                            break;
                     case EH:
                            (*T)->bf = LH;
                            *taller = TRUE;
                            break;
                     case RH:
                            (*T)->bf = EH; 
                            *taller = FALSE;
                            break;  
                            break;
                             }
      
               }
        }
        else
        {
                if(!InsertAVL(&(*T)->rchild,val,taller))
                {
                    return FALSE;    
                }

                if(*taller)
                {
                    switch((*T)->bf)
                    {
                             case LH:
                                   (*T)->bf = EH;
                                   *taller = FALSE;
                                    break;
                              case EH:
                                   (*T)->bf = EH;
                                    *taller = TRUE;
                                    break;
                             case RH:
                                   RightBalance(T);
                                    *taller = FALSE;
                                       break;  

                    }        

                }
                               
        }          
    }
    return TRUE;
}





 
我说一下带头节点的代码思路
 
1）在Insert(AVLTree *ptree,KeyType kx)
 
先看判断有没有头节点
 
有头节点在看有没有根，没根就把kx当根
 
while循环目的看是否存在kx，如果没有，就找到kx要插入的父节点，而且一定是插在叶子结点的
 
2）Insert_Item(AVLTree *ptree,AVLNode *pa,KeyType kx)
 
先创建一个结点，然后对其初始化，把data = kx
 
判断是kx所在的结点是pa的左孩子还是右孩子，两者建立好连接
 
然后对他们的平衡因子进行调整。引入tall。这部分得自己理解，不太好讲。自己领悟下就出来了。
 
#include<iostream>
#include<stack>
#include<queue>
using namespace std;

#define LH   1
#define EH   0
#define RH  -1


typedef int KeyType;
typedef struct AVLNode
{
	AVLNode *leftchild;
	AVLNode *parent;
	AVLNode *rightchild;
	int balance; // 0 1 -1;
	KeyType key;
}AVLNode;
typedef struct
{
	AVLNode *head;
	int cursize;
}AVLTree;


AVLNode * Buynode()
{
	AVLNode *s = (AVLNode*)malloc(sizeof(AVLNode));
	if(NULL == s) exit(1);
	memset(s,0,sizeof(AVLNode));
	return s;
}

void Freenode(AVLNode *p)
{
	free(p);
}

void Init_AVLTree(AVLTree *ptree)
{
	if(ptree == NULL) exit(1);
	ptree->head = Buynode();
	ptree->cursize = 0;
}

AVLNode * FindValue(AVLTree *ptree,KeyType kx)
{
	if(ptree == NULL || ptree->head == NULL)
		return NULL;
	AVLNode *p = ptree->head->parent;
	while(p != NULL && p->key != kx)
	{
		p = kx < p->key? p->leftchild:p->rightchild;
	}
	return p;
}

AVLNode *Search(AVLNode *ptr,KeyType kx)
{
	if(ptr == NULL || ptr->key == kx) 
		return ptr;
	else if(kx <ptr->key)
	{
		return Search(ptr->leftchild,kx);
	}else
	{
		return Search(ptr->rightchild,kx);
	}
}

AVLNode * SearchValue(AVLTree *ptree, KeyType kx)
{
	if(ptree == NULL || ptree->head == NULL)
		return NULL;
	else
		return Search(ptree->head->parent,kx);
}

void RotateRight(AVLTree *ptree,AVLNode *ptr)
{
	AVLNode *newroot = ptr->leftchild;
	newroot->parent = ptr->parent;
	ptr->leftchild = newroot->rightchild;
	if(newroot->rightchild != NULL)
	{
		newroot->rightchild->parent = ptr;
	}
	newroot->rightchild = ptr;
	if(ptree->head->parent == ptr) //root
	{
		ptree->head->parent = newroot;
	}
	else
	{
		if(ptr->parent->leftchild == ptr)
		{
			ptr->parent->leftchild = newroot;
		}
		else
		{
			ptr->parent->rightchild = newroot;
		}
	}
	ptr->parent = newroot;
}

void RotateLeft(AVLTree *ptree, AVLNode *ptr)
{
	AVLNode *newroot = ptr->rightchild;
	newroot->parent = ptr->parent; // 1
	ptr->rightchild = newroot->leftchild;
	if(newroot->leftchild != NULL)
	{
		newroot->leftchild->parent = ptr; //2
	}
	newroot->leftchild = ptr;
	if(ptr == ptree->head->parent) // root
	{
		ptree->head->parent = newroot;
	}
	else
	{
		if(ptr->parent->rightchild == ptr)
		{
			ptr->parent->rightchild = newroot;
		}
		else
		{
			ptr->parent->leftchild = newroot;
		}
	}
	ptr->parent = newroot;//3
}

void RightBalance(AVLTree *ptree,AVLNode *ptr)
{
	AVLNode *rightsub = ptr->rightchild, *leftsub= NULL;
	switch(rightsub->balance)
	{
	case EH: cout<<"right already balance"<<endl; break;
	case RH: 
		ptr->balance = EH;
		rightsub->balance = EH;
		RotateLeft(ptree,ptr);
		break;
	case LH:
		leftsub = rightsub->leftchild;
		switch(leftsub->balance)
		{
		case EH: 
			ptr->balance = EH;
			rightsub->balance = EH;
			break;
		case RH:
			ptr->balance = LH;
			rightsub->balance = EH;
			break;
		case LH:
			ptr->balance = EH;
			rightsub->balance = RH;
			break;
		}
		leftsub->balance = EH;
		RotateRight(ptree,rightsub);
		RotateLeft(ptree,ptr);
		break;
	}
}

void LeftBalance(AVLTree *ptree,AVLNode *ptr)               //整个树的左边失衡了要用这个函数进行调整
{
	AVLNode *leftsub = ptr->leftchild, *rightsub = NULL;      //ptr  是要作为新根的结点父结点
	switch(leftsub->balance)
	{
	case EH: cout<<"left already balance"<<endl; break;
	case LH:
		ptr->balance = EH;
		leftsub->balance = EH;
		RotateRight(ptree,ptr);
		break;
	case RH:
		rightsub = leftsub->rightchild;
		switch(rightsub->balance)     //这里看的是ptr ->rightchild  结点的平衡因子
		{
		case EH:                        //自己推导平衡因子的变化，这画图
			ptr->balance = EH;
			leftsub->balance = EH;
			break;
		case RH:                            
			ptr->balance = EH;
			leftsub->balance = LH;
			break;
		case LH:
			ptr->balance = RH;
			leftsub->balance = EH;
			break;
		}
		rightsub->balance = EH;
		RotateLeft(ptree,leftsub);
		RotateRight(ptree,ptr);
		break;
	}

}

void Insert_Item(AVLTree *ptree,AVLNode *pa,KeyType kx)
{
	AVLNode *s = Buynode();
	s->key = kx;
	s->parent = pa;
	s->balance = EH;       //新插入的结点是叶子结点，必是平衡
	if(s->key < pa->key)     //先判断是插在pa的左还是右,这里是插在pa左孩子结点上
	{
		pa->leftchild = s;          //pa左孩子 = 新插入的s结点
		if(s->key < ptree->head->leftchild->key)            //头的左孩子结点保存的是整个树的最小结点  头结点 != 根结点
		{
			ptree->head->leftchild = s;
		}
	}
	else
	{
		pa->rightchild = s;                               
		if(s->key > ptree->head->rightchild->key)
		{
			ptree->head->rightchild = s;
		}
	}
	
	AVLNode *_X = s;
	AVLNode *_Y = s->parent;
	int tall = 1;
	for(;tall == 1 && _Y != ptree->head; )
	{
		if(_Y->rightchild == _X)                   //依旧判断是左孩子还是右孩子
		{
			switch(_Y->balance)                  
			{
			case EH: _Y->balance = RH; break;          
			case LH: _Y->balance = EH; 
				tall = 0;
				break;
			case RH:
				RightBalance(ptree,_Y);
				tall = 0;
				break;
			}
		}
		else // _Y->leftchild == _X
		{
			switch(_Y->balance)
			{
			case EH: _Y->balance = LH; break;
			case RH: _Y->balance = EH; 
				tall = 0;
				break;
			case LH:
				LeftBalance(ptree,_Y);
				tall = 0;
				break;
			}
		}

		_X = _Y;
		_Y = _Y->parent;
	}	
}

bool Insert(AVLTree *ptree,KeyType kx)
{
	if(ptree == NULL || ptree->head == NULL)
		return false;
	if(ptree->head->parent == NULL)    //空树
	{
		AVLNode *s = Buynode();
		s->key = kx;
		s->parent = ptree->head;
		ptree->head->parent = s;
		ptree->head->leftchild = s;
		ptree->head->rightchild = s;
		ptree->cursize = 1;
		return true;
	}
	///
	AVLNode *pa = ptree->head; // 
	AVLNode *p = ptree->head->parent; // root;
	while(p != NULL && p->key != kx)    //判断是否存在该关键字kx  和找到要插入的位置
	{
		pa = p;
		p = kx < p->key? p->leftchild:p->rightchild;
	}
	if(p != NULL && p->key == kx) return false;   //找到关键字kx  推出
	
	Insert_Item(ptree,pa,kx);    //没找到插入kx , 此时pa 便是要插入的父结点
	ptree->cursize+=1;           //有效结点加1
	return true;
}


void showInorder(AVLNode *p)
{
	if(p != NULL)
	{
		showInorder(p->leftchild);
		cout<<p->key<<" ";
		cout<<p->balance<<" ";
		showInorder(p->rightchild);
	}
}
 
 
 
 
 
 

 
 
前言
 
 
     本文主要是针对即时战略游戏RTS的平衡设计的一些概念进行归类阐述。虽然题目是关于即时战略游戏RTS的，但是其中一些概念、思想也同样适合其它类型游戏：策略游戏STG、角色扮演类游戏RPG、战棋类游戏等。
 
     关于游戏平衡的文章会以三部分内容展开，前两篇《如何高效设计游戏——游戏平衡：RTS显性平衡与隐形平衡（上）》以及       《如何高效设计游戏——游戏平衡：RTS显性平衡与隐形平衡（下）》主要是介绍一些关于平衡设计的概念以及思想，属于内功修养，适合新手以及注重内在想要了解国外成熟模式的游戏设计者。最后一篇文章《如何高效设计游戏——策略游戏的平衡方法》则会着重介绍一些平衡策略游戏兵种的一些方法或者称之为技巧，给那些无从下手以及善于思考的游戏设计者一些参考。
 
     正如我之前博客预告中所提到的，游戏的平衡归类为两种：【显性平衡】与【隐形平衡】，这也让我想到了另外的两个词来形容：【具体】与【抽象】。在这片文章里我会更加详细的说明“什么是显性平衡”并会试着举一些例子。值得一提的是，本文所提到的一些概念不仅仅局限于策略游戏，适用于一般游戏的平衡设计。
 
    最后，还请各位尊重作者的劳动果实，切勿进行非法转载，改变原有转载格式、更换文章标题、变更作者等。如果喜欢请关注博客、微博支持。十分感谢！
 
 
 
显性平衡
 
 
     显性平衡既是一些表面上硬性的游戏机制设计。例如，利用显性平衡，我们可以设定某种单位无法攻击空中飞行单位。这种【显性平衡】设计相较于【抽象平衡】来说，更容易使玩家理解，降低学习成本。但完整的平衡也需要【抽象平衡】来维持。
 
     另一种角度来解释【显性平衡】与【隐性平衡】之间的区别是，【显性平衡】会给你一个明确的信息回馈，然而【隐形平衡】则不会那么直接体现出来。我们来假定一个游戏场景：【隐性的信息回馈】是指，当我们派一对步兵去攻击另一对步兵时，当把敌方步兵全部击杀时我方还能剩有一般数量的步兵。【明确的信息回馈】是指，当我们派一对步兵去攻击另一对弓箭手的时候，还没有近身时，全部步兵就已经被弓箭手放到了。
 
     PS：这里读者们可能没有完全理解。这里“明确回馈”与“隐性回馈”指的是占有优势或者劣势的程度。前者是占有绝对优势或者劣势，已经完全不用关心具体的细节了；后者则需要在优势或者劣势的程度上关注更多，例如结果的稳定性上、优势或者劣势的比例上、损失的程度上等。总结一句话就是，【显性平衡】是“静态的”“表面的”“硬性的”。【隐性平衡】是“动态的”“内部的”“细节的”“定量的”。
 
     一个游戏的设计应当尽可能的多关注于【显性平衡】设计，因为那是硬性的框架基础，一个好的框架支持可以靠内部细节做到优秀的产品。但是框架基础打的歪，再优秀的内部细节也无力回天。
 
 
 
兵种单位的【维度】
 
 
     这里【维度】指的是兵种的“存在的空间行动属性”不是指的量度。例如，一些陆地行走单位是属于一个存在维度（地面单位or维度），还有一些空中飞行单位则属于另一个存在维度（空中单位or维度）。值得注意的是单位的存在维度不等同于单位的攻击侦测维度。例如在某即时战略游戏中，有一种潜水艇单位，如果想要攻击它，必须先要去侦测这个单位，但是他们确确实实属于地面单位（能攻击地面单位的兵种都可以攻击这个潜水艇）。
 
     一个游戏到底有多少个维度，是要看游戏的设定本身，亦可以根据设计者的需要来随意改变。《最高指挥官》系列游戏的设定是有三个维度（地面、空中、水下），然而《魔兽争霸》系列则设定为2个维度。有些游戏例如《家园》、《黎明战争》等，设定为一个维度。
 
     维度设定对于【显性平衡】来说是一种很好的方法，它通常来说更容易被接受被理解。维度设定也会使得技能树的设计更加灵活，给予设计者更多的思路拓展。
 
     对于某些可以攻击多个维度，甚至不受维度限制的兵种来说，他们比其他兵种的价值更大。他们是“万能兵种”，并且通常会比单攻击维度的兵种训练花费更多。这些“万能兵种”有时候会被削弱防御力或者生命来进行游戏平衡设计。例如，在星际争霸中，神族的重骑兵对战虫族的小狗优势就很弱，考虑到重骑兵的造价是小狗的5倍之多。
 
 
 
攻击属性
 
 
     攻击属性是指例如“攻击速率”“攻击范围”“弹速”“伤害范围”之类的一些属性。这些可用【显性平衡】的方法来平衡战斗。
 
 
 
攻击速率
 
 
     攻击速率，或者射击速度是攻击属性中是属于一种比较容易表现平衡的类型。我们可以在两次攻击的间隙设定一个延时来控制速率，并且这个延时可以放置在一次攻击之后，或者一次攻击之前，亦或者前后动态随机安置。不过，如果你把这个延时安放在一次攻击之前对比之下会略微劣势于把这个延时安放在一次攻击之后。这是因为，一些特殊的情况如移除攻击范围或者反击将会使前者情况的攻击憋回去，并且放在攻击前面的延时也会留给敌人一个准备间隙。
 
     显然，延时的长度会决定于一个单位的攻击速度究竟有多块。假设我们只看每秒的伤害输出相同的情况，延时短（攻击速度快）的兵种可能会比延时长（攻击速度慢）的兵种弱。例如，假设两种兵种，每秒能够造成1000点伤害。其中一个兵种的攻击间隔为0.2秒，那么他能够1秒内攻击5次，每次造成200点伤害。而另一种兵种的攻击间隔为1秒，则这个兵种只需要在一秒内攻击一次就能够造成1000点伤害。一次全力的攻击可以使得地方单位毫无苟延的机会。然而，间隔时间短的攻击更擅长于对付比较弱的单位（因为每次攻击相比于高伤害攻击来说，不会造成额外的浪费），所以这种类型的单位会更泛用。
 
     PS：这里还想补充一点，在单位时间内伤害一定的情况下，高频率攻击对于低频率强力攻击的优势还更多的体现一点，如考虑到命中率的话，高频率会更加占优势，因为这会把这一秒的总伤害拆分成多次伤害，不至于MISS全部的伤害。
 
 
 
攻击范围
 
 
     攻击范围，由于玩家很直观的能够看得出一个兵种什么时候能够攻击什么时候不能攻击，所以无疑是另一种容易表现平衡的属性。攻击范围是一个性质非常强的平衡点，因为我们经常会发现攻击范围大的单位可以无伤地给对方造成巨大伤害。
 
 
 
弹速
 
 
     弹速，换个角度解释为“从发动攻击到受到攻击的延时”，也是一个可见的平衡量，只不过没有像“攻击速率”以及“攻击范围”那么明显而已，但显然的是，弹速快的攻击总比弹速慢的攻击好吧。值得注意的是弹速慢会造成一种“浪费”攻击机会的一种情况，就像当子弹还在空中“飘过”的时候，攻击目标早就撤离了攻击范围或者早就被灭掉了。
 
     PS：发生这种情况的前提是，游戏设计机制为“实时碰撞检测”
 
     对于某些实时碰撞检测的游戏来说，弹速对于游戏的影响还是很大的。虽然实时碰撞检测会使得游戏可玩性高一些，但是会受兵种移动速度以及微操作的影响，使得平衡工作更加困难。例如，《命令与征服 3》中的手榴弹兵投出的手榴弹缓慢且不会追踪，这就意味着只要你能很快意识到并且把你的兵移开就不会受到伤害。在星际争霸中的大部分攻击都是既定目标的，无论你如何闪躲都是徒劳的，或者这多多少少会让你感觉到缺少真实感。
 
 
 
命中
 
 
     命中是一个可以根据设计者想要的表现“可显”“可隐”的属性。在《帝国时代 II》中的弓箭手就是一个典型的“显性”例子，并且命中这一性质也被巧妙的设计在科技树中的一项科技中。通过提升这一科技“远程兵种攻击移动中的单位”来从“显性”模式中提升准确率。在《战争黎明》中，命中率这一概念则是通过“隐性”的方式来应用的。命中或者未命中是采用概率判断的形式。随机性固然是不错的想法，不过很难在表现上无法做出真实体验。更何况好多武器的攻击速度非常高，到后来命中率就会变成一个更多牵扯到伤害的一项属性，而并非游戏的战略趣味体验。
 
 
 
移动属性
 
 
     单位的移动属性同样也是一个符合“显性”标准的属性，并且可以用来直观的平衡对抗其他的兵种，最基本常用的手段就是修改兵种的移动速度了（一个效果很强的数值，慎调）。另外一些手段，你也可以设计是否允许这个兵种移动时可以攻击，是否需要转向目标方向才能攻击（其中还涉及到转向速度），是否可以越过障碍物（例如空中单位）等等。
 
     移动属性通常来说都会与视觉体验相联系的，所以你可能更加愿意修改兵种的移动属性，然后再用其他的属性来从全局角度来平衡这个兵种。但是几乎没有听说过某个游戏会放出修改兵种移动属性的补丁，大多的做法都是在造价上以及伤害上作调整。
 
 
 
隐性与反隐形
 
 
     这个标题从某种意义上可能会对读者造成一定程度的误导，因为这个技能在一些环境下可以说是无敌了，而并非平衡。这种类型的技能的厉害程度通常对玩家来说已是经显而易见了，因此如何反制才是一个大问题。换句话说，我们可能会经常遇到自己的兵被某种隐性单位一个一个的被杀死的这种情况而感到无计可施。
 
     值得注意的是，这些技能的实用性，往往是基于有没有或者怎样一种程度设计反制应对这些技能的措施。如何设计这个技能，更多的是一个如何平衡科技树的问题，而非兵种平衡问题。
 
     至此本章内容毕。
 
     欢迎各位提出一些观点、想法、建议等
 
 
 
 
 
 
 
 
前言
 
 
 
     再次强调，本为以“修心”为主，并不是某种意义上的“干货”，这也正是作者想为国内游戏设计者传达的理念。在国外游戏设计者眼中并没有什么数值策划这一概念，他们更注重的是如何从逻辑的角度来时游戏更加丰富，更加【平衡】，而不是国内游戏设计者眼中，做几个公式、几个函数算来算去就能达到想要的效果了。注意，公式也好，函数也好永远都是死的，如果不注重逻辑上的设计，游戏里的一切都是死的，都是“拉表格”“填表格”做出来的，根本就达不到“动态”的效果。这种硬派作风就相当于编码中的“硬编码（hard coding）”一样没有自己的灵魂，也无法应对游戏中的各种变化以及各种需求。
 
     其次需要强调的是，好多设计者习惯用什么“价值衡量”的办法来设计游戏平衡，所谓的“价值衡量”就是把游戏中涉及到的基本属性都通过某种方法映射成“权值”然后来做权值上的运算从而达到衡量这些属性的载体角色或者装备。我想说的是，这种属性的“价值衡量”方法非常不科学，甚至可以断言国家一级精算师恐怕也无法做好所谓的“价值衡量”，因为变量以及影响因素实在是太多了，根本无法准确地衡量各个阶段各个环境下的属性价值，除非在特定的环境限制特定的变量。
 
     在这一章节，将重点讲述什么是抽象的【隐性平衡】，以及“隐性平衡”是如何被运用到游戏中的。
 
 
 
何为【隐性平衡】
 
 
     之前也大概介绍过了，【隐性平衡】既是掀开哪华丽表面之后的，运作在内部的“齿轮”，对任何一个数值或者公式的修改都将影响一个单位兵种的战斗表现。例如，伤害值、生命值、防御值、命中率、护甲类型等等，皆为【隐性平衡】所控制的范畴。
 
     我们也可以假定一个1对1的战斗场景，在不考虑攻击速度的情况下，两个兵种互相“文斗”轮流做出一次攻击，在这种环境下，我们可以建立出纯净的环境足以安心建立隐性平衡。举个例子，一个步兵攻击一个骑兵造成的伤害可能不如一个枪兵对同样一个骑兵造成的伤害多。这本是基于“枪兵的攻击类型克制骑兵的护甲类型”这一【隐性平衡】而设定的。
 
 
 
伤害类型
 
 
     这部分是【隐性平衡】中最纯粹的形式。伤害类型的作用是用来抑制某单位兵种的能力并且与其他单位兵种相联系从而形成某种相生相克的效果。但是这会存在一个问题，就是玩家需要通过不断的游戏体验来加深这部分印象从而达到完全理解。一旦玩家熟悉了，玩家就会把这种规律当做常识来记住，这时我们就不易在这方面做修改了。例如，在《命令与征服3》中，所有的枪械单位总是克制“肉体”步兵单位的。
 
     在《星际争霸》中，设计者运用了一个相当简单的对应关系来设计攻击类型。其中有4种护甲类型以及3种伤害类型如下：
 
 l  普通攻击对任何护甲类型的单位造成100%伤害
 
 l  爆炸攻击对重型护甲单位造成100%伤害,中型护甲单位75%伤害,轻型护甲单位50%伤害
 
 l  震荡攻击对重型护甲单位造成25%伤害,中型护甲单位50%伤害,轻型护甲单位100%伤害
 
 l  神族的防护盾可以承担一切伤害类型
 
 换句话来说，三种攻击类型，其中一种主要针对小型或者有机单位，另一种则主要针对重甲单位或者建筑类型，最后一种则是泛用性。这种系统设定是可以满足大多数游戏的设计需求的，除非是那种有很多复杂的即死型武器的存在的游戏，如狙击手等（通常来说对重型或者建筑单位基本无效）。然而我们需要时刻注意的是，【显性平衡】永远要比【隐形平衡】更优先考虑，因为前者在设计上更容易得多，这也是为何显示“该目标无法攻击”总是比显示“对敌方造成0.0001点伤害”要好得多的原因。
 
 
 
命中率
 
 
     命中率是可以向【显性平衡】的那个方向去设计的，例如上一章节中曾经提到的《帝国时代2》在这点上就做的非常出色。然而命中率也可以朝着【隐性平衡】的方向去设计，我们称之为“命中的概率”。
 
     通常来说这种概率类型是决定你的兵种攻击的时候究竟可以造成多少伤害的。我们完全没必要把这个设定做很高深很玄乎以至于变成玩家完全无法理解的“数学题”，我们只要确保它能简单的显示到底“命中”还是“未命中”就可以了。在《战争黎明》中，命中率设定有时候会让玩家很难去辨认是否击中，其原因为：①“未命中”信息有时候会漂浮穿过单位兵种后面，②击中信息也有可能出现被兵种遮挡的现象（这些都有可能是渲染BUG造成的），③有些兵种攻击速率是在是太快了，以至于到底是命中还是未命中，怎么也看不清楚。
 
     就这点问题上，《魔兽争霸3》做的优化就显而易见了。
 
 
 
HP生命点数
 
 
     HP的概念已经深刻植入玩家的脑海里了，以至于无论你是否是一名真正的游戏玩家，你都会明确的指导HP代表什么，HP有什么作用。就算是对于某些非正式玩家或者休闲游戏玩家而言，着实不知HP的概念，他们也会很快的理解上手。然而HP这个属性还是归结到【隐性平衡】的设计中，因为大部分玩家都不会关心我到底扣了多少血这个【数】，甚至有些玩家根本不会记得每个兵种到底有多少血。
 
 
 
利用回馈将【隐性平衡】转为【显性平衡】
 
 
     对于【隐性平衡】来说，最大的问题就是玩家不能很直白的明白有些东西是如何运作的，是好还是坏。不过这些都可以用过适当的体验调整对一些【隐性平衡】的事件进行一些补偿。例如，发生暴击了，显示数值变一个颜色、大小甚至添加一些音效，回复生命或者吸血的时候也适当的做出一些醒目特征的调整等。试着让拥有相同护甲类型的单位拥有相同的外部特征（穿着、护甲类型的图标等）。试着把该兵种的体积与血量大小进行一些匹配等手段。
 
     曾经一款独立游戏，Afermath（2008，Gamesfaction），就试着用不同的颜色来代表不同类型的护甲与不同类型的攻击（红色类型的护甲可以抵御红色类型的攻击等）。像这样简单的设计，就可以给游戏带来巨大的体验改善（一个细微的用户界面UI设计可能会给你的游戏带来巨大的改变，这个改变可能是良性的也有可能是恶性的）。所以当你运用了大量的【隐性平衡】设计时，你可以参考本条内容。
 
  
 
                                                                                                                                                                 Einsphoton
 
                                                                                                                                                                  2013.01.04
 

在书上看了平衡二叉树的代码后，发现前人的智慧真是无限。但是因为一次性给出的最完美的代码让人有时候看不太懂...
 
后来经过仔细推敲，才慢慢发现了其中的奥秘。一开始并不知道关于平衡二叉树的平衡因子BF是怎么修改的，后来才发现关于平衡二叉树的最重要的一句话：在构建平衡二叉树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树，在保持二叉排序树特性的前提下，调整关系。
 
 
这句话意味着：只要破坏了平衡性，就马上修改使得二叉树重新平衡，意思就是只要修改了最小不平衡树就可以使得整个二叉树重新平衡.
 
 
下面借用书上的代码进行解释说明，说明在代码后面
 
 
[cpp] view plaincopy

	1. #include "stdio.h"      
	2. #include "stdlib.h"     
	3. #include "io.h"    
	4. #include "math.h"    
	5. #include "time.h"  
	6.   
	7. #define OK 1  
	8. #define ERROR 0  
	9. #define TRUE 1  
	10. #define FALSE 0  
	11. #define MAXSIZE 100 /* 存储空间初始分配量 */  
	12.   
	13. typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */   
	14.   
	15.   
	16. /* 二叉树的二叉链表结点结构定义 */  
	17. typedef  struct BiTNode /* 结点结构 */  
	18. {  
	19.     int data;   /* 结点数据 */  
	20.     int bf; /*  结点的平衡因子 */   
	21.     struct BiTNode *lchild, *rchild;    /* 左右孩子指针 */  
	22. } BiTNode, *BiTree;  
	23.   
	24.   
	25. /* 对以p为根的二叉排序树作右旋处理， */  
	26. /* 处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点 */  
	27. void R_Rotate(BiTree *P)  
	28. {   
	29.     BiTree L;  
	30.     L=(*P)->lchild; /*  L指向P的左子树根结点 */   
	31.     (*P)->lchild=L->rchild; /*  L的右子树挂接为P的左子树 */   
	32.     L->rchild=(*P);  
	33.     *P=L; /*  P指向新的根结点 */   
	34. }  
	35.   
	36. /* 对以P为根的二叉排序树作左旋处理， */  
	37. /* 处理之后P指向新的树根结点，即旋转处理之前的右子树的根结点0  */  
	38. void L_Rotate(BiTree *P)  
	39. {   
	40.     BiTree R;  
	41.     R=(*P)->rchild; /*  R指向P的右子树根结点 */   
	42.     (*P)->rchild=R->lchild; /* R的左子树挂接为P的右子树 */   
	43.     R->lchild=(*P);  
	44.     *P=R; /*  P指向新的根结点 */   
	45. }  
	46.   
	47. #define LH +1 /*  左高 */   
	48. #define EH 0  /*  等高 */   
	49. #define RH -1 /*  右高 */   
	50.   
	51. /*  对以指针T所指结点为根的二叉树作左平衡旋转处理 */  
	52. /*  本算法结束时，指针T指向新的根结点 */  
	53. void LeftBalance(BiTree *T)  
	54. {   
	55.     BiTree L,Lr;  
	56.     L=(*T)->lchild; /*  L指向T的左子树根结点 */   
	57.     switch(L->bf)  
	58.     { /*  检查T的左子树的平衡度，并作相应平衡处理 */   
	59.          case LH: /*  新结点插入在T的左孩子的左子树上，要作单右旋处理 */   
	60.             (*T)->bf=L->bf=EH;  
	61.             R_Rotate(T);  
	62.             break;  
	63.          case RH: /*  新结点插入在T的左孩子的右子树上，要作双旋处理 */   
	64.             Lr=L->rchild; /*  Lr指向T的左孩子的右子树根 */   
	65.             switch(Lr->bf)  
	66.             { /*  修改T及其左孩子的平衡因子 */   
	67.                 case LH: (*T)->bf=RH;  
	68.                          L->bf=EH;  
	69.                          break;  
	70.                 case EH: (*T)->bf=L->bf=EH;  
	71.                          break;  
	72.                 case RH: (*T)->bf=EH;  
	73.                          L->bf=LH;  
	74.                          break;  
	75.             }  
	76.             Lr->bf=EH;  
	77.             L_Rotate(&(*T)->lchild); /*  对T的左子树作左旋平衡处理 */   
	78.             R_Rotate(T); /*  对T作右旋平衡处理 */   
	79.     }  
	80. }  
	81.   
	82. /*  对以指针T所指结点为根的二叉树作右平衡旋转处理， */   
	83. /*  本算法结束时，指针T指向新的根结点 */   
	84. void RightBalance(BiTree *T)  
	85. {   
	86.     BiTree R,Rl;  
	87.     R=(*T)->rchild; /*  R指向T的右子树根结点 */   
	88.     switch(R->bf)  
	89.     { /*  检查T的右子树的平衡度，并作相应平衡处理 */   
	90.      case RH: /*  新结点插入在T的右孩子的右子树上，要作单左旋处理 */   
	91.               (*T)->bf=R->bf=EH;  
	92.               L_Rotate(T);  
	93.               break;  
	94.      case LH: /*  新结点插入在T的右孩子的左子树上，要作双旋处理 */   
	95.               Rl=R->lchild; /*  Rl指向T的右孩子的左子树根 */   
	96.               switch(Rl->bf)  
	97.               { /*  修改T及其右孩子的平衡因子 */   
	98.                 case RH: (*T)->bf=LH;  
	99.                          R->bf=EH;  
	100.                          break;  
	101.                 case EH: (*T)->bf=R->bf=EH;  
	102.                          break;  
	103.                 case LH: (*T)->bf=EH;  
	104.                          R->bf=RH;  
	105.                          break;  
	106.               }  
	107.               Rl->bf=EH;  
	108.               R_Rotate(&(*T)->rchild); /*  对T的右子树作右旋平衡处理 */   
	109.               L_Rotate(T); /*  对T作左旋平衡处理 */   
	110.     }  
	111. }  
	112.   
	113. /*  若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 */   
	114. /*  数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树 */   
	115. /*  失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。 */  
	116. Status InsertAVL(BiTree *T,int e,Status *taller)  
	117. {    
	118.     if(!*T)  
	119.     { /*  插入新结点，树“长高”，置taller为TRUE */   
	120.          *T=(BiTree)malloc(sizeof(BiTNode));  
	121.          (*T)->data=e; (*T)->lchild=(*T)->rchild=NULL; (*T)->bf=EH;  
	122.          *taller=TRUE;  
	123.     }  
	124.     else  
	125.     {  
	126.         if (e==(*T)->data)  
	127.         { /*  树中已存在和e有相同关键字的结点则不再插入 */   
	128.             *taller=FALSE; return FALSE;  
	129.         }  
	130.         if (e<(*T)->data)  
	131.         { /*  应继续在T的左子树中进行搜索 */   
	132.             if(!InsertAVL(&(*T)->lchild,e,taller)) /*  未插入 */   
	133.                 return FALSE;  
	134.             if(*taller) /*   已插入到T的左子树中且左子树“长高” */   
	135.                 switch((*T)->bf) /*  检查T的平衡度 */   
	136.                 {  
	137.                     case LH: /*  原本左子树比右子树高，需要作左平衡处理 */   
	138.                             LeftBalance(T); *taller=FALSE; break;  
	139.                     case EH: /*  原本左、右子树等高，现因左子树增高而使树增高 */   
	140.                             (*T)->bf=LH; *taller=TRUE; break;  
	141.                     case RH: /*  原本右子树比左子树高，现左、右子树等高 */    
	142.                             (*T)->bf=EH; *taller=FALSE; break;  
	143.                 }  
	144.         }  
	145.         else  
	146.         { /*  应继续在T的右子树中进行搜索 */   
	147.             if(!InsertAVL(&(*T)->rchild,e,taller)) /*  未插入 */   
	148.                 return FALSE;  
	149.             if(*taller) /*  已插入到T的右子树且右子树“长高” */   
	150.                 switch((*T)->bf) /*  检查T的平衡度 */   
	151.                 {  
	152.                     case LH: /*  原本左子树比右子树高，现左、右子树等高 */   
	153.                             (*T)->bf=EH; *taller=FALSE;  break;  
	154.                     case EH: /*  原本左、右子树等高，现因右子树增高而使树增高  */  
	155.                             (*T)->bf=RH; *taller=TRUE; break;  
	156.                     case RH: /*  原本右子树比左子树高，需要作右平衡处理 */   
	157.                             RightBalance(T); *taller=FALSE; break;  
	158.                 }  
	159.         }  
	160.     }  
	161.     return TRUE;  
	162. }  
	163.   
	164. int main(void)  
	165. {      
	166.     int i;  
	167.     int a[10]={3,2,1,4,5,6,7,10,9,8};  
	168.     BiTree T=NULL;  
	169.     Status taller;  
	170.     for(i=0;i<10;i++)  
	171.     {  
	172.         InsertAVL(&T,a[i],&taller);  
	173.     }  
	174.     printf("本样例建议断点跟踪查看平衡二叉树结构");  
	175.     return 0;  
	176. }  

1.关于insertAVL方法，需要说明的是，它用的是递归的思想，一层一层从下往父类修改平衡因子，而不用计算每个结点的BF，仅仅是根据左子树与右子树的高度差。因为是只要一破坏了平衡就修改，所以平衡因子的数只能是 -2、-1、0、1、2这几个数的取值。所以只要通过插入前的高度差与插入后的位置（左子树还是右子树）就可以确定现在的平衡因子。如果破坏了平衡性，就调用**Balance函数，调整平衡，并置taller为false，因为已经调整了平衡，高度并未发生改变，所以在这个结点以上的所有父亲都不用修改其平衡因子。 
 
 
 
 2.关于Balance方法，以leftBalance为例进行说明
 
 ①首先，之所以调用leftBalance是因为在插入前左子树的深度就比右子树的深度大一，现在插入的位置又是在左子树，所以左子树的深度比右子树的深度大于2，也就是最小不平衡树的顶点的平衡因子为2
 
 ②因为插入的是最小不平衡树的顶点T的左子树上L，所以需要比较顶点T 与 其左子树L 的平衡因子的符号，如果一致，就做简单的右旋转；如果不一致就先对其左子树做左旋转，再对最小不平衡树T做右旋转。——也就是说当左子树 L 的平衡因子为1时（LH）就进行简单的右旋转，为-1（RH）时就先对子树L做左旋转再对最小不平衡树T做右旋转
 
 ③关于先对左子树做左旋转，再对最小不平衡树做右旋转的平衡因子的改变。因为涉及对做子树L的左旋转，所以L的右子树Lr会受到影响,所以会根据Lr的平衡因子的不同而会有不同的改变
 
 
 
 
 a.当Lr 的平衡因子为LH(相当于1)时，T的平衡因子变为-1，L的平衡因子变为0
 
 
 
 
 
 
 b..当Lr的平衡因子为EH(相当于0）时，T的平衡因子变为0，L的平衡因子变为0
 
 
 
 
 c..当Lr的平衡因子RH(相当于-1)时，T的平衡因子变为0，L的平衡因子变为1
 
 
 
 
 
 
 
 
 
 
 可能会想：这只是特殊情况，其实并不是。因为每次旋转，受到影响的只有那么几个点，其他点的位置会改变，可是是以整体的方式变动，所以其他点的平衡因子并不会改变。rightBalance与leftBalance形成对称，所以就不画图啦
 

 

R语言解决数据不平衡问题
 
一、项目环境
 
开发工具：RStudio
R：3.5.2
相关包：dplyr、ROSE、DMwR
 
二、什么是数据不平衡？为什么要处理数据不平衡？
 
​ 首先我们要知道的第一个问题就是“什么是数据不平衡”，从字面意思上进行解释就是数据分布不均匀。在我们做有监督学习的时候，数据中有一个类的比例远大于其他类，或者有一个类的比值远小于其他类时，我们就可以认为这个数据存在数据不平衡问题。
 
​ 那么这样的一个问题会对我们后续的分析工作带来怎样的影响呢？我举个简单的例子，或许大家就明白了。假设我们现在需要训练一个模型来分辨人群中那个人是恐怖分子。那么现在给到我们1万个人员的数据，在做分析之前其实我们就很清楚，一群人中恐怖分子的比例肯定是要远小于普通人的比例的。那么假如在这1万个人中只有一个是恐怖分子，那么恐怖分子与正常人的比例就是 9999 : 1 。那么如果我们不进行任何处理就直接进行有监督学习的话，那么模型只需要将所有人数据都分类为正常人，模型的准确率就能达到99.99%。而这样的模型显然是没有意义的。因为基本上说有可能存在的恐怖分子的特征基本都被模型给忽略了，这也就说明了为什么要处理数据不平衡问题。
 
三、 常见的数据不平衡处理方法
 
以下是几种比较常见的处理数据不平衡的方法：
 
欠采样法（Undersampling）
过采样法（Oversampling）
人工数据合成法（Synthetic Data Generation)
代价敏感学习法（Cose Sensitive Learning）
 
 
 
【注】：本文主要以实现为主，因此不对上述方法进行过多的讲解。
 
 
感兴趣可以参考：https://mp.weixin.qq.com/s/m8M3I4vkOq44vguGAB5ccA
 
 
 
​ 在处理数据之前，我们先看一下需要处理的数据分布的情况。
 
load("C:/Users/User/Desktop/data.RData")

table(data$classification)

prop.table(table(data$classification))
 
 
 
> table(data$classification)
 
 
-8 1 2 3 4 5
 12 104 497 1158 4817 1410
 
 
> prop.table(table(data$classification))
 
 
-8 1 2 3 4 5
 0.001500375 0.013003251 0.062140535 0.144786197 0.602275569 0.176294074
 
 
1、 欠采样
 
######### 方法一 #########

library(ROSE)
# 由于是多分类问题，我们先提取数据中比例最大的类和比例最小的类
# 进行平衡（转化为二分类问题）
test <- data[which(data$classification == -8 | data$classification == 4),]

# 将分类结果转化为因子型（不然会报错）
test$classification <- as.factor(test$classification)

# 进行欠采样
# 其中 method = "under" 表示采用的方法为“欠采样”
# N = 40 表示最终整个数据集的数量
# seed 随机种子，为了保留对样本的追踪
under <- ovun.sample(classification ~ ., test, method = "under", N = 40, seed = 1)$data

# 查看结果
table(under$classification)
 
 
 
> table(under$classification)
 
 
4 -8
 28 12
 
 
 
######### 方法二 #########

library(dplyr)
# 由于是多分类问题，我们先提取数据中比例最大的类和比例最小的类
# 进行平衡（转化为二分类问题）
test <- data[which(data$classification == -8 | data$classification == 4),]

# 提取大比例类
test1 <- test[which(test$classification == 4),]

# 将大比例类的数量降为12个
down <- sample_n(test1, 12, replace = TRUE)

# 将欠采样后的类进行合并
down <- rbind(test[which(test$classification == -8), ],down)

table(down$classification)
 
 
 
> table(down$classification)
 
 
-8 4
 12 12
 
 
 
 
【注】：欠采样是无放回的采样。
 
 
2、 过采样
 
######### 方法一 #########
library(ROSE)

test <- data[which(data$classification == -8 | data$classification == 4),]

test$classification <- as.factor(test$classification)

# 实现上大致与欠采样相同，只有类型 method 改成了 "over"，同时没有限制总数量
under <- ovun.sample(classification ~ ., test, method = "over", seed = 1)$data

table(under$classification)
 
 
 
> table(under$classification)
 
 
4 -8
 4817 4785
 
 
 
######### 方法二 #########
library(dplyr)

test <- data[which(data$classification == -8 | data$classification == 4),]

# 提取小比例类
test1 <- test[which(test$classification == -8),]

# 将小比例类的数量降为4817个（与大比例类相同）
# 这里使用的过采样方法是随机复制小比例类中的数据，将其扩充到指定数量
down <- sample_n(test1, 4817, replace = TRUE)

down <- rbind(test[which(test$classification == 4), ],down)

table(down$classification)
 
 
 
> table(down$classification)
 
 
-8 4
 4817 4817
 
 
3、人工数据合成法（Synthetic Data Generation)
 
######### 方法一 #########

library(ROSE)
# 由于是多分类问题，我们先提取数据中比例最大的类和比例最小的类
# 进行平衡（转化为二分类问题）
test <- data[which(data$classification == -8 | data$classification == 4),]

# 将分类结果转化为因子型（不然会报错）
test$classification <- as.factor(test$classification)

# ROSE提供了ROSE()函数来合成人工数据
rose <- ROSE(classification ~ ., test, seed = 1)$data

# 查看结果
table(rose$classification)

 
 
 
> table(rose$classification)
 
 
4 -8
 2483 2346
 
 
 
######### 方法二 #########

library(DMwR)

test <- data[which(data$classification == -8 | data$classification == 4),]

test$classification <- as.factor(test$classification)

# perc.over: 如 perc.over = n，小比例类的个数变为 (n/100)a + a 个数据（a为小比例类原始数量）
# perc.under: 如 perc.under = m，大比例类的个数变为((nm)/100)a个
# 因此本次案例中，小比例类的个数变为(3500/100)*12 + 12 = 432个
# 大比例类的个数变为((3500*300)/100^2)*12 = 1260个
down <- SMOTE(classification ~ ., test, perc.over = 3500, perc.under = 300)

table(down$classification)
 
 
 
> table(down$classification)
 
 
-8 4
 432 1260
 
 
 
 
【注】：相较于前两种方法而言，人工合成法既不会像过采样容易导致过拟合问题，也不会出现欠采样大量丢失信息的问题。
 
 
4、代价敏感学习法（Cose Sensitive Learning）
 
 
 
【注】：还没想好怎么写。。。。。
 
 
三、 结语
 
​ 本文之所以都只拿两个分类在进行分析，是因为上面提到的用于解决数据不平衡问题的函数，基本上都是针对二分类问题的。当导入的数据中有大于两个分类时，函数就会报错。但是在实际分析的过程中，其实我们更经常遇到的时多分类问题，这是我们就需要将多分类问题转化为二分类问题，将各个分类两两进行比较才能更好的解决数据不平衡的问题。
 
 
很长一段时间没有在csdn中写文章了，事实上后面自己学习过程中的大部分文档都是在语雀中完成的，基本都是自己写自己看。不过后面打算弄个公众号来更新和分享自己写的笔记_(:з」∠)_ 。如果感兴趣的话也可以关注一下。不感兴趣就算了(っ╥╯﹏╰╥c)。
 
 然后写着个的另外一个原因就是，我可能会把一些文档搬运到自己的公众号，为了避免被说抄袭，所以说明一下。这样子_(:з」∠)_。