电影《无耻混蛋》里有一幕游戏，在德军小酒馆里有几个人在玩20问题游戏，游戏规则是一个设迷者在纸牌中抽出一个目标（可以是人，也可以是物），而猜谜者可以提问题，设迷者只能回答是或者不是，在几个问题（最多二十个问题）之后，猜谜者通过逐步缩小范围就准确的找到了答案。这就类似于决策树的工作原理。（图一）是一个判断邮件类别的工作方式，可以看出判别方法很简单，基本都是阈值判断，关键是如何构建决策树，也就是如何训练一个决策树。
（图一）
构建决策树的伪代码如下：
Check if every item in the dataset is inthe same class:
If so return the class label
Else
find the best feature to split the data
split the dataset
create a branch node
for each split
call createBranch and add the result to the branch node
return branch node
注意上面伪代码中一句说：find the best feature to split the data，那么如何find thebest feature?一般有个准则就是尽量使得分支之后节点的类别纯一些，也就是分的准确一些。如（图二）中所示，从海洋中捞取的5个动物，我们要判断他们是否是鱼，先用哪个特征？
（图二）
为了提高识别精度，我们是先用“能否在陆地存活”还是“是否有蹼”来判断？我们必须要有一个衡量准则，常用的有信息论、基尼纯度等，这里使用前者。我们的目标就是选择使得分割后数据集的标签信息增益最大的那个特征，信息增益就是原始数据集标签基熵减去分割后的数据集标签熵，换句话说，信息增益大就是熵变小，使得数据集更有序。熵的计算如（公式一）所示：
（公式一）
有了指导原则，那就进入代码实战阶段，先来看看熵的计算代码：
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet: #the the number of unique elements and their occurance
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1 #收集所有类别的数目，创建字典
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key])/numEntries
shannonEnt -= prob * log(prob,2) #log base 2 计算熵
return shannonEnt有了熵的计算代码，接下来看依照信息增益变大的原则选择特征的代码：
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis] #chop out axis used for splitting
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 #the last column is used for the labels
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0; bestFeature = -1
for i in range(numFeatures): #iterate over all the features
featList = [example[i] for example in dataSet]#create a list of all the examples of this feature
uniqueVals = set(featList) #get a set of unique values
newEntropy = 0.0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
infoGain = baseEntropy - newEntropy #calculate the info gain; ie reduction in entropy
if (infoGain > bestInfoGain): #compare this to the best gain so far #选择信息增益最大的代码在此
bestInfoGain = infoGain #if better than current best, set to best
bestFeature = i
return bestFeature #returns an integer
从最后一个if可以看出，选择使得信息增益最大的特征作为分割特征，现在有了特征分割准则，继续进入一下个环节，如何构建决策树，其实就是依照最上面的伪代码写下去，采用递归的思想依次分割下去，直到执行完成就构建了决策树。代码如下：
def majorityCnt(classList):
classCount={}
for vote in classList:
if vote not in classCount.keys(): classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
def createTree(dataSet,labels):
classList = [example[-1] for example in dataSet]
if classList.count(classList[0]) == len(classList):
return classList[0]#stop splitting when all of the classes are equal
if len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSet
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel:{}}
del(labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:] #copy all of labels, so trees don't mess up existing labels
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
return myTree 用图二的样本构建的决策树如（图三）所示：
（图三）
有了决策树，就可以用它做分类咯，分类代码如下：
def classify(inputTree,featLabels,testVec):
firstStr = inputTree.keys()[0]
secondDict = inputTree[firstStr]
featIndex = featLabels.index(firstStr)
key = testVec[featIndex]
valueOfFeat = secondDict[key]
if isinstance(valueOfFeat, dict):
classLabel = classify(valueOfFeat, featLabels, testVec)
else: classLabel = valueOfFeat
return classLabel最后给出序列化决策树（把决策树模型保存在硬盘上）的代码：
def storeTree(inputTree,filename):
import pickle
fw = open(filename,'w')
pickle.dump(inputTree,fw)
fw.close()
def grabTree(filename):
import pickle
fr = open(filename)
return pickle.load(fr)
一对多和上文讲的多对一两种映射关系，其实就是站在相反的角度考虑同样的事情。
一对多和多对一映射原理是一样的，都在多的一端加入一个外键指向一的一端。也就是说，在关系数据库的表中，他们的表及表字段都是一样的。
他们的不同在于维护的关系：
多对一维护的关系——多指向一的关系，如果维护了多指向一的关系，那么加载多的时候会把一加载上来。
一对多维护的关系——一指向多的关系，如果维护了一指向多的关系，那么加载多的时候，会把一加载上来。
现在假如要用一对多映射描述学生和班级的关系。
1、hibernate单向一对多关联映射（Classes----->Student）
实体Classes。一对多关系，加载时需要在一的一端（classes端）加载上来多的一端（Student），所以实体Classes中需包含实体Student的引用。
package com.lzq.hibernate;
import java.util.Set;
public class Classes {
private int id;
private String name;
private Set student;
此处省略getter和setter方法
} 实体Student
package com.lzq.hibernate;
public class Student {
private int id;
private String name;
此处省略getter和setter方法
}映射文件Classes.hbm.xml。一对多关系中，需要在多的一端维护关系，所以在Classes端加入“one-to-many”标签维护关系。
<?xml version="1.0"?>
<!DOCTYPE hibernate-mapping PUBLIC
"-//Hibernate/Hibernate Mapping DTD 3.0//EN"
"http://hibernate.sourceforge.net/hibernate-mapping-3.0.dtd">
<hibernate-mapping>
<class name="com.lzq.hibernate.Classes" table="t_classes">
<id name="id">
<generator class="native" />
</id>
<property name="name" />
<!-- 集合映射set-->
<set name="student">
<!-- 设置classesid外键为非空字段-->
<key column="classesid" not-null="true"/>
<one-to-many class="com.lzq.hibernate.Student"/>
</set>
</class>
</hibernate-mapping>映射文件Student.hbm.xml
<?xml version="1.0"?> <!DOCTYPE hibernate-mapping PUBLIC "-//Hibernate/Hibernate Mapping DTD 3.0//EN" "http://hibernate.sourceforge.net/hibernate-mapping-3.0.dtd"> <hibernate-mapping> <class name="com.lzq.hibernate.Student" table="t_student"> <id name="id"> <generator class="native" /> </id> <property name="name" /> </class> </hibernate-mapping>
尽管我们完成映射，但是这样映射还存在一定的问题，看下面的加载：
public void testOne2ManyAdd() throws Exception {
Session session=null;
Transaction tx=null;
try {
session=HibernateUtils.getSession();
tx=session.beginTransaction();
Student student1=new Student();
student1.setName("张三");
session.save(student1);
Classes classes=new Classes();
classes.setName("提高班");
Set students=new HashSet();
students.add(student1);
classes.setStudent(students);
session.save(classes);
tx.commit();
} catch (Exception e) {
e.printStackTrace();
HibernateUtils.closeSession(session);
}
}结果会抛PropertyValueException异常。原因很简单：我们在多的一端（Student）没有维护关系，也就是说，Student不知道自己是哪一个班的，所以我们在保存Student的时候关系字段classesid为null。这就限制了外键必须为允许非空，如果外键设置为“不能为空”，则无法进行保存。而我们这里对外键设置，所以才会抛出此异常。
那怎么解决该问题呢？当然，我们可以在Classes.hbm.xml配置中去掉“ not-null='true' ”，这样也可以保存，但是我们可以观察生成的SQL语句，此时进行了一条insert和update语句，显然，它实现插入了student信息，然后在更新的classesid字段。这种方式显然不友善。那么除了这种方式，还能不能用别的方式解决？
这应为此问题，才产生了双向的一对多的关联映射：
2、hibernate双向一对多关联映射（Classes<----->Student）
既然是双向一对多关联映射，那么一定要在多的一端（Student）加入一的一端（Classes）的引用，这样才能在多的一端（Student）进行存储和加载。
package com.lzq.hibernate;
public class Student {
private int id;
private String name;
private Classes classes;
此处省略getter/setter方法
}对应配置更改：
<?xml version="1.0"?>
<!DOCTYPE hibernate-mapping PUBLIC
"-//Hibernate/Hibernate Mapping DTD 3.0//EN"
"http://hibernate.sourceforge.net/hibernate-mapping-3.0.dtd">
<hibernate-mapping>
<class name="com.lzq.hibernate.Student" table="t_student">
<id name="id">
<generator class="native" />
</id>
<property name="name" />
<!-- 此处需要与classes端的配置的字段保持一致-->
<many-to-one name="classes" column="classesid" />
</class>
</hibernate-mapping>此外，既然双向一对多关联映射的产生是为了弥补单向一对多关联映射的缺陷，那么避免程序员编写程序仍然在一的一端（Classes）加载，我们可以采用反转技术，设置从Classes端加载失效：
<?xml version="1.0"?> <!DOCTYPE hibernate-mapping PUBLIC "-//Hibernate/Hibernate Mapping DTD 3.0//EN" "http://hibernate.sourceforge.net/hibernate-mapping-3.0.dtd"> <hibernate-mapping> <class name="com.lzq.hibernate.Classes" table="t_classes"> <id name="id"> <generator class="native" /> </id> <property name="name" /> <!--反转：设置从Classes端加入数据失效--> <set name="student" inverse="true"> <key column="classesid" /> <one-to-many class="com.lzq.hibernate.Student"/> </set> </class> </hibernate-mapping>
为什么多对一关联映射不存在单向一对多中的问题呢？如果你明白了上面所讲的，这个问题将很好回答。在多对一关联映射里面，由于关系是在多的一端进行维护的，加载的时候从多的一
未来机器智能化已然成为趋势，现在手机都能听懂英语和普通话，那我大中华几万种方言的被智能化也许也是趋势，我们的方言虽然和普通话相似，但是还是不一样的。这可能需要一个新的语法分析器来帮助我们。
我们的解释器模式就是描述了如何为简单的语言定义一个文法，如何在该语言中表示一个句子，以及如何解释这些句子。
但是解释一门自然语言是复杂的过程，我们以加减运算为例子来详细解释解释器模式。
类图和实例：抽象表达式角色(AbstractExpression): 声明一个抽象的解释操作,这个接口为所有具体表达式角色都要实现的.
终结符表达式角色(TerminalExpression): 实现与文法中的元素相关联的解释操作,通常一个解释器模式中只有一个终结符表达式,但有多个实例对应不同的终结符.
终结符就是语言中用到的基本元素,一般不能再被分解,如: x -> xa, 这里a是终结符，因为没有别的规则可以把a变成别的符号，不过x可以变成别的符号，所以x是非终结符.
非终结符表达式角色(NonterminalExpression): 文法中的每条规则对应于一个非终结表达式, 非终结表达式根据逻辑的复杂程度而增加,原则上每个文法规则都对应一个非终结符表达式.
环境角色(Context): 包含解释器之外的一些全局信息.
实例：
#include <iostream>
#include <map>
#include <string>
using namespace std;
class Context
{
private:
map<string, int> valueMap;
public:
void addValue(string key,int value)
{
valueMap.insert(std::pair<string,int>(key,value));
}
int getValue(string key)
{
return valueMap[key];
}
};
class AbstractExpression
{
public :
virtual int interpreter(Context context) = 0;
};
class AddNonterminalExpression : public AbstractExpression
{
private :
AbstractExpression *left;
AbstractExpression *right;
public:
AddNonterminalExpression(AbstractExpression *left, AbstractExpression *right)
{
this->left = left;
this->right = right;
}
int interpreter(Context context)
{
return this->left->interpreter(context) + this->right->interpreter(context);
}
};
class SubtractNonterminalExpression : public AbstractExpression
{
private :
AbstractExpression *left;
AbstractExpression *right;
public:
SubtractNonterminalExpression(AbstractExpression *left, AbstractExpression *right)
{
this->left = left;
this->right = right;
}
int interpreter(Context context)
{
return this->left->interpreter(context) - this->right->interpreter(context);
}
};
class TerminalExpression : public AbstractExpression
{
private :
int i;
public :
TerminalExpression(int i)
{
this->i = i;
}
int interpreter(Context context)
{
return this->i;
}
};
int main(){
//a-b+c
Context context;
context.addValue("a", 7);
context.addValue("b", 8);
context.addValue("c", 2);
SubtractNonterminalExpression *subtractValue = new SubtractNonterminalExpression(new TerminalExpression(
context.getValue("a")), new TerminalExpression(context.getValue("b")));
AddNonterminalExpression *addValue = new AddNonterminalExpression(subtractValue, new TerminalExpression(
context.getValue("c")));
cout<< addValue->interpreter(context);
return 0;
}
适用性：
在以下情况下可以考虑使用解释器模式：
(1) 可以将一个需要解释执行的语言中的句子表示为一个抽象语法树。
(2) 一些重复出现的问题可以用一种简单的语言来进行表达。
(3) 一个语言的文法较为简单。
(4) 执行效率不是关键问题。【注：高效的解释器通常不是通过直接解释抽象语法树来实现的，而是需要将它们转换成其他形式，使用解释器模式的执行效率并不高。】
优缺点： 优点： (1) 易于改变和扩展文法。由于在解释器模式中使用类来表示语言的文法规则，因此可以通过继承等机制来改变或扩展文法。(2) 每一条文法规则都可以表示为一个类，因此可以方便地实现一个简单的语言。
(3) 实现文法较为容易。在抽象语法树中每一个表达式节点类的实现方式都是相似的，这些类的代码编写都不会特别复杂，还可以通过一些工具自动生成节点类代码。
(4) 增加新的解释表达式较为方便。如果用户需要增加新的解释表达式只需要对应增加一个新的终结符表达式或非终结符表达式类，原有表达式类代码无须修改，符合“开闭原则”。
缺点： (1) 对于复杂文法难以维护。在解释器模式中，每一条规则至少需要定义一个类，因此如果一个语言包含太多文法规则，类的个数将会急剧增加，导致系统难以管理和维护，此时可以考虑使用语法分析程序等方式来取代解释器模式。(2) 执行效率较低。由于在解释器模式中使用了大量的循环和递归调用，因此在解释较为复杂的句子时其速度很慢，而且代码的调试过程也比较麻烦。
总论：尽量不要在重要模块中使用解释器模式，因为维护困难。在项目中，可以使用脚本语言来代替解释器模式。
LCL_data原创于CSDN.NET【http://blog.csdn.net/lcl_data/article/details/9259905】
其他设计模式请参考：我所理解的设计模式