Python基于hadoop的大规模并行数据分析系统原型设计(9)
数据挖掘模块基于Hadoop平台，课题使用Mrjob的python框架，在使用Mrjob框架中主要使用框架提供的三个函数：mapper、combiner、reducer来完成MapReduce操作。所以将数据挖掘算法并行化后分解成map、reduce、steps三个模块来对应Mrjob框架的并行操作。由此抽象得到数据挖掘算法的KDD类图：
图4-1分布式挖掘算法类图
系统所实现的以及将来将实现的数据挖掘算法都继承此基类，并覆盖实现类中的三个方法来完成分布式算法的构造。
为了实现系统的扩展性和文护性，系统基于数据挖掘算法的特点，引入了工厂方法的设计模式，此模块中使用工厂方法设计模式的详细设计类图如下：
图4-2 课题数据挖掘模块-工厂方法模式类图
工厂方法的设计模型是使用封装和委托的典型模式。使用工厂方法时，在系统需要添加数据挖掘算法的时候，不需要对基类以及实现的相关功能进行大量修改，只需要增加相应的算法实现类和具体的工厂类就可以完成扩展，大大提高了系统的可扩展性。其中：
工厂方法封装了创建新对象，将New语句与逻辑实现代码尽心分离，大大减少了代码间相干性，使用工厂返回类的实例化对象。
在对象的使用过程中，不必要关心实现的逻辑，只需要关心使用的工厂和使用个构造接口。
对于不同算法的逻辑先封装再分派，减少耦合，再以后系统拓展增加新的算法或者改善已有算法时，只需要修改自身的逻辑，减少文护的工作量，减少了系统的风险。
数据挖掘算法原理和实现
ID3算法原理
本课题实现了分布式化决策树算法中的ID3算法。决策树是一种用来分类的树型结构，将数据的属性字段作为结点，将数据的分类结果作为叶结点。决策树是基于信息论原理对数据进行分析挖掘归纳产生的。决策树的根结点是数据中最能决定分类结果的属性。ID3算法是构造决策树的经典算法。
ID3也是基于信息论原理，使用信息增益作为判定的指标。当某个属性的信息增益是最高时，该属性将作为基础结点并根据属性的不同结果建立树的分枝，在每个分枝中递归这个步骤。通过这样的算法可以保证决策树的分枝数量将达到最小，最大程度的降低决策树的冗余。
由于ID3是以个递归的过程，所以只需要处理好单个结点的选择，便可以进行整棵决策树的构建。熵是作为度量属性信息量大小的指标，如果存在n个相同概率的信息，那么每个信息的概率为1/n，信息量为log2(n)。
假设Pi为属性信息的概率分布，则信息量大小熵为：
I(U)=-∑_i▒〖P(U_i)log_2〖P(u_i)〗 〗
假设被选中的属性具有n个不同的值{a1,…,an}，可以用属性的值将结果集分成n个子集合，由该属性划分成子集的条件熵为：
I(U/V)=-∑_n▒〖P(V_n)∑_i▒〖P(U_i/V_j)log_2〖P(U_i/V_j)〗 〗〗
由该属性的条件熵值和熵值可以得到该属性的对应的信息增益值为：
I(U)- I(U/V)
ID3算法是采用自上而下、采用分而治之并基于贪心算法的思想进行递归的方式来构造决策树，而递归的结束条件是某个属性的结果均为相同的类别或者无属性继续划分，便将该属性当做叶子节点。基于以上思想，将ID3算法划分成以下主要步骤：
遍历数据，确定还未构成节点的属性。
根据熵的定义公式计算各节点的信息增益值。
选择最大的信息增益值属性，构造成相应的节点。
根据构造的节点生成相应的分枝结构。
重新处理数据。以便算法再次遍历。
判断是否符合递归结束条件，若符合结束条件，则决策树构造完成；若不符合则进行循环1-6步骤。