分类算法Java代码分析

Weak classifiers 包中含有用于分类和数值预测的大部分算法的实现 这个包 中最重要的是类是 Classifier 它定义了任何用于分类或数值预测的学习方案 的通用结构 Classifier 含有三个方法 buildClassfier classifyInstance distributionForInstance 学习算法用 Classifier 的子类代表 因此 自动继承这三个方法 每种方案都会根据构建分类器以及它对实例进行分类的具体方式对这三个方法 进行重新定义 首先先解释一下算法名字 很多人很奇怪为什么叫 IB1 IBK IB Instance Based 的缩写 但按 Jiawei Han 书上所写 KNN 其实是 Instance based learning 也被称 为 Lazing learning 中一种 他还讲解了基于案例的推理 Case based reasoning 算法其实是 KNN 但是作者论文的名字是 Instance based Learning Algorithms 我先介绍一下 IB1 IB1 就是只找一个邻居 我们还是先看 buildClassifier public void buildClassifier Instances instances throws Exception if instances classAttribute isNumeric throw new Exception IB1 Class is numeric 类别属性是数值型的话 报错 if instances checkForStringAttributes throw new UnsupportedAttributeTypeException IB1 Cannot handle string attributes 检查其他属性 如果是字符串 String 类型 报错 不能处理 Throw away training instances with missing class 缺失类别属性 的实例扔掉 m Train new Instances instances 0 instances numInstances m Train deleteWithMissingClass Instance 是一个类 Create empty instance with three attribute values m MinArray new double m Train numAttributes 定义一个数组 m MinArray 数据类型是 double 型 共有 m Train numAttributes 个数据 m MaxArray new double m Train numAttributes for int i 0 i m Train numAttributes i m MinArray i m MaxArray i Double NaN 还没有将真正的实例的属性存放在这两个数组里 Enumeration enu m Train enumerateInstances 列举出每个实例 的属性值 while enu hasMoreElements 以枚举的实例属性数量进行循环判 断 updateMinMax Instance enu nextElement 更新属性的最大最 小值 是的 KNN 也有 buildClassifier 听起来蛮奇怪的 第二个 if IB1 不能对 字符串属性进行学习 因为这种属性不好定义距离 比如 a 和 ab 是 0 5 还是 1 呢 然类别缺失的样本抛弃 m MinArray 和 m MaxArray 分别保存每一个属性 的最小值和最大值 最下面是对样本进行循环 找出最大值 最小值 updataMinMax 代码如下 private void updateMinMax Instance instance for int j 0 j m Train numAttributes j 有多少个属 性就循环多少次 if m Train attribute j isNumeric value 是要返回实 例的属性值 m MaxArray j instance value j else if instance value j m MaxArray j m MaxArray j instance value j 如果这个属性值大于之前定义的最大属性值 将其值赋给最大属性值 Double isNaN m MinArray j 判断是不是 m MinArray 和 m MaxArray 已经 赋值过了 else 如果可以更新 min 和更新 max 再看一下 classifyInstance 函数 public double classifyInstance Instance instance throws Exception 对待分类实例进行分类的过程 if m Train numInstances 0 throw new Exception No training instances 实例数量为 0 报错 double distance minDistance Double MAX VALUE 声明并且初始化 classValue 0 classValue 实例的类别属性 Returns an instance s class value in internal format updateMinMax instance Enumeration enu m Train enumerateInstances enumerateInstances Returns an enumeration 列举 枚举 of all the attributes while enu hasMoreElements Instance trainInstance Instance enu nextElement if trainInstance classIsMissing distance distance instance trainInstance distance 方法在后面有说明 if distance minDistance minDistance distance classValue trainInstance classValue classValue Returns an instance s class value in internal format 返回这个实例的类别属性 return classValue 因为要进化归范化 所以对这个待分类的样本再次调用 updateMinMax 然后对训练样本进行循环 用 distance 计算与每一个训 练样本和待分类样本的距离 如果比前面的距离小 则记录 最后返回与测试 样本距离最小的样本的类别值 private double distance Instance first Instance second double diff distance 0 声明并且初始化为 0 for int i 0 i m Train numAttributes i if i m Train classIndex classIndex Returns the class attribute s index continue if m Train attribute i isNominal If attribute is nominal if first isMissing i second isMissing i int first value i int second value i distance 1 else If attribute is numeric if first isMissing i second isMissing i if first isMissing i else if second isMissing i diff norm first value i i else diff norm second value i i if diff 0 Compute the number of attributes that contribute to each prediction m NumAttributesUsed 0 0 for int i 0 i 0 同样很简单 updateMinMax 如果超出窗口大小 循环删除超过窗口大小 的第一个样本 这里注意 IBk 没有实现 classifyInstance 它只实现了 distributionForInstances public double distributionForInstance Instance instance throws Exception if m Train numInstances 0 throw new Exception No training instances if m WindowSize 0 boolean deletedInstance false while m Train numInstances m WindowSize m Train delete 0 rebuild datastructure KDTree currently can t delete if deletedInstance true m NNSearch setInstances m Train Select k by cross validation if m kNNValid m NNSearch addInstanceInfo instance Instances neighbours m NNSearch kNearestNeighbours instance m kNN double distances m NNSearch getDistances double distribution makeDistribution neighbours distances return distribution 前面两个判断不讲了 crossValidate 马上讲 寻找 K 个邻居在我第 18 篇 里已经讲过了 现在我们看一下 makeDistribution 函数 protected double makeDistribution Instances neighbours double distances throws Exception double total 0 weight double distribution new double m NumClasses Set up a correction to the estimator if m ClassType Attribute NOMINAL for int i 0 i m NumClasses i distribution i 1 0 Math max 1 m Train numInstances total double m NumClasses Math max 1 m Train numInstances for int i 0 i 0 Utils normalize distribution total return distribution 第一行注释 Set up a correction 我感觉没什么必要 又不是 Bayes 还有除 0 错误 没什么可修正的 这里可以看见它实现了三种距离权重计算方法 倒 数 与 1 的差 另外就是固定权重 1 然后如果类别是离散值把对应的类值加 上权重 如果是连续值 就加上当前类别值剩权重 crossValidate 简单地说就是用蛮力找在到底用多少个邻居好 它对 m Train 中的样本进行循环 对每个样本找邻居 然后统计看寻找多少个邻居时最好 protected void crossValidate double performanceStats new double m kNNUpper double performanceStatsSq new double m kNNUpper for int i 0 i m kNNUpper i performanceStats i 0 performanceStatsSq i 0 m kNN m kNNUpper Instance instance Instances neighbours double origDistances convertedDistances for int i 0 i 0 j Update the performance stats convertedDistances new double origDistances length System arraycopy origDistances 0 convertedDistances 0 origDistances length double distribution makeDistribution neighbours convertedDistances double thisPrediction Utils maxIndex distribution if m Train classAttribute isNumeric thisPrediction distribution 0 double err thisPrediction instance classValue performanceStatsSq j err err Squared error performanceStats j Math abs err Absolute error else if thisPrediction instance classValue performanceStats j Classification error if j 1 neighbours pruneToK neighbours convertedDistances j Check through the performance stats and select the best k value or the lowest k if more than one best double searchStats performanceStats if m Train classAttribute isNumeric double bestPerformance Double NaN int bestK 1 for int i 0 i searchStats i bestPerformance searchStats i bestK i 1 m kNN bestK m kNNValid true m kNNUpper 是另一个设置最多有多少样本的参数 枚举每一个样本 instance 找它的邻居 neighbors 和距离 origDistances 接下来就是把从 0 到 m kNNUpper 个邻居的得到的方差 performanceStatsSq 和标准差 performanceStats 与以前得到的值累加 pruneToK 就是得到 j 个样本 如果 j 1 的距离不等于第 j 个 后面就比较好理解了 m MeanSquared 对连续类别 是选择用方差还是标准差进行选择 然后最出 m kNNUpper 看在多少邻居的时 候 分类误差最小 就认为是最好的邻居数 以前打算写一篇有关 OneR 的 weka 源代码介绍的 但考虑知道这个算法的人太 少 不想今天有人问这个算法 在这里我就把它补上 OneR 是一个很简单的算法 出自论文 Very simple classification rules perform well on most commonly used datasets 由于论文的风格过于奔放 并且很长 所以我也就没怎么看 基本思想就是对每一个属性都建一个单层的分类器 对这些分类器进行比较 谁分类效果好就作为最终的分类器 下面还是看 buildClassifier 的代码 删除了部分代码 首先判断是不是就 一个属性 一个属性意味着只有一个类别特征 如果是 那就用 ZeroR 算法 如果不知道为什么 看我上一篇 下面枚举每一个属性 在每一个属性上 产生一个 OneRRule 对象 r 下面判断这个 r 是比以前产生的正确的样本数多 如果是则替换 public void buildClassifier Instances instances throws Exception boolean noRule true only class build ZeroR model if data numAttributes 1 m ZeroR new weka classifiers rules ZeroR m ZeroR buildClassifier data return else m ZeroR null for each attribute Enumeration enu instances enumerateAttributes while enu hasMoreElements try OneRRule r newRule Attribute enu nextElement data if this attribute is the best so far replace the rule if noRule r m correct m rule m correct bbs m rule r bbs noRule false catch Exception ex 下面看一下刚才的 newRule 函数 初始化一个 missingValueCounts 数组 数组大小为类别集合的大小 如果当前这个类别是离散的调用 newNominalRule 如果是连续的调用 newNumericRule 下面的几行代码现在可 能还有点难理解 理解不了 看完下面的再转回来看 missingValueCounts 保 存的是对这个属性缺失值类别值的读数 而 maxIndex 函数返回的就是这个属性 缺失时最有时候的类别 Index 再下来 If 判断是否训练集中如果这个属性值缺 失的样本 那么 r m missingValueClass 1 如果有 r m correct 加上当这个属 性缺失情况下最多出现的类别值的出现次数 没办法就是这么难表达 public OneRRule newRule Attribute attr Instances data throws Exception OneRRule r create array to hold the missing value counts bbs int missingValueCounts new int data classAttribute numValues bbs if attr isNominal r newNominalRule attr data missingValueCounts bbs else bbs r newNumericRule attr data missingValueCounts r m missingValueClass Utils maxIndex missingValueCounts if missingValueCounts r m missingValueClass 0 r m missingValueClass 1 signal for no missing value class else r m correct missingValueCounts r m missingValueClass bbs return r 先看一下离散的情况 初始化一个二维数组 第一维属性的个数 第二维 类别值集合的大小 下面对样本进行枚举 如果当前样本该属性值是缺失的 那么 missingValuleCounts 在相应的类别值下标上记数 如果不是缺失的 那种 就在这个样本在该属性值的类别值下标上记数 说起来很糊涂 想通了很简单 接下面这段代码刚开始看的时候 我也糊涂了 其实也很简单 best 就是当 一个样本在该属性取值为 value 时 最有可能的类别值 m correct 就是对这种 情况的记数 即在全部样本中 当属性为 attr 时 属性值为 value 类别值是 value 这种情况一共出现了多少次 public OneRRule newNominalRule Attribute attr Instances data int missingValueCounts throws Exception create arrays to hold the counts int counts new int attr numValues data classAttribute numValues calculate the counts Enumeration enu data enumerateInstances while enu hasMoreElements Instance i Instance enu nextElement if i isMissing attr missingValueCounts int i classValue else counts int i value attr int i classValue OneRRule r new OneRRule data attr create a new rule bbs for int value 0 value 0 missingValueCounts int data instance lastInstance classValue bbs int i 0 int cl 0 index of next bucket to create int it while i lastInstance start a new bucket bbs for int j 0 j counts length j counts j 0 do fill it until it has enough of the majority class it int data instance i classValue counts it while counts it m minBucketSize while class remains the same keep on filling while i lastInstance bbs i while i lastInstance for int j 0 j counts it bbs it j if cl 0 can we coalesce with previous class if counts classifications cl 1 counts it it classifications cl 1 bbs if it classifications cl 1 bbs cl yes correct counts it classifications cl it if i lastInstance breakpoints cl data instance i 1 value attr data instance i value attr 2 bbs cl bbs if cl 0 bbs throw new Exception Only missing values in the training data OneRRule r new OneRRule data attr cl new rule with cl branches bbs r m correct correct for int v 0 v cl v r m classifications v classifications v bbs if v cl 1 r m breakpoints v breakpoints v return r 下面的 if 是判断是否两个段的类别值相同 如果相同就可以合并 coalesce 第一个 if 看起来比较怪 它其实是想判断是不是这一段里有多个最大值 而其 中一个就是上次的最大值 并且没有被认为是最大值 如果是 那么就用上次 的最大值来代替 下来的 correct 和 classification 没什么好讲的 下来一个 if 为什么是两个样 本值该属性值加起来除 2 是因为 i 已经加过了 这时做的是这一段结束值与下 一段的开始值以中间为界分开 最后一个 for 就是复制一下 不讲了 最后一个函数 classifyInstance 如果是 m ZeroR 分类器 说明只有一个类 别属性 下一个 if 如果是缺失值 那么就是 m rule 的 m missingValueClass 当然也可能有学习时没有缺失值 分类时有的情况 那么返回 0 如果是离散 值 直接返回在属性 m attr 值的上的类别值 如果是连续值 看它在哪个段上 返回该段上的类别值 public double classifyInstance Instance inst throws Exception bbs default model if m ZeroR null return m ZeroR classifyInstance inst bbs int v 0 if inst isMissing m rule m attr if m rule m missingValueClass 1 return m rule m missingValueClass else return 0 missing values occur in test but not training set bbs if m rule m attr isNominal bbs v int inst value m rule m attr else while v m rule m breakpoints v bbs bbs v return m rule m classifications v bbs 这次介绍一下 J48 的源码 分析 J48 的源码似乎真还是有用的 同学改造 J48 写过 VFDT 我自己用 J48 进行特征选择 当然很失败 J48 的 buildClassfier 函数 public void buildClassifier Instances instances throws Exception ModelSelection modSelection if m binarySplits modSelection new BinC45ModelSelection m minNumObj instances bbs else modSelection new C45ModelSelection m minNumObj instances if m reducedErrorPruning m root new C45PruneableClassifierTree modSelection bbs m unpruned m CF m subtreeRaising m noCleanup else m root new PruneableClassifierTree modSelection m unpruned bbs m numFolds m noCleanup m Seed m root buildClassifier instances bbs if m binarySplits bbs BinC45ModelSelection modSelection cleanup else C45ModelSelection modSelection cleanup bbs 在 NBTree 中已经介绍过了 ModelSelection 是决定决策树的模型类 前面两个 if 一个是判断连续属性是否只分出两个子结点 另一个判断是否最后剪枝 m root 是一个 ClassifierTree 对象 它调用 buildClassifier 函数 这里列出这个函数 public void buildClassifier Instances data throws Exception bbs can classifier tree handle the data getCapabilities testWithFail data bbs remove instances with missing class data new Instances data data deleteWithMissingClass buildTree data false bbs 有注释也没什么好说的 直接看最后一个函数 buildTree public void buildTree Instances data boolean keepData throws Exception Instances localInstances if keepData bbs m train data m test null m isLeaf false m isEmpty false m sons null m localModel m toSelectModel selectModel data if m localModel numSubsets 1 bbs localInstances m localModel split data data null m sons new ClassifierTree m localModel numSubsets for int i 0 i m sons length i m sons i getNewTree localInstances i localInstances i null else m isLeaf true if Utils eq data sumOfWeights 0 m isEmpty true data null bbs 这里的 selectModel 函数 如果看过 NBTree 一篇的读者应该不会太陌 生 selectModel 简单地说就是如果不符合分裂的条件就返回 NoSplit 如 果符合分裂的条件 则从 currentModel 数组中选出 bestModel 返回 这最要注意的是 selectModel 也不只是决定哪个属性分裂 其实到底如 何分裂已经在这个函数里算里出来了 我把 selectModel 拆开来讲解 bbs Check if all Instances belong to one class or if not bbs enough Instances to split bbs checkDistribution new Distribution data noSplitModel new NoSplit checkDistribution if Utils sm checkDistribution total 2 m minNoObj Utils eq checkDistribution total checkDistribution bbs perClass checkDistribution maxClass return noSplitModel bbs 2 m minNoObj 表示至有有这么多样本才可以分裂 原因很简单 因 为一个结点至少分出两个子结点 每个子结点至少有 m minNoObj 个样本 第 二个是或条件是表示是否这个结点上所有的样本都属于同一类别 也就是这个 结点总的权重是否等于这个最多类别的权重 Check if all attributes are nominal and have a lot of values if m allData null bbs Enumeration enu data enumerateAttributes bbs while enu hasMoreElements bbs attribute Attribute enu nextElement if attribute isNumeric Utils sm double attribute numValues 0 3 double m allData numInstances multiVal false bbs break 判断是否有很多不同的属性值 标准就是如果有一个属性的属性值小多于 总样本数 0 3 那么就是不是 multiVal currentModel new C45Split data numAttributes bbs sumOfWeights data sumOfWeights bbs For each attribute for i 0 i data numAttributes i Apart from class attribute bbs if i data classIndex Get models for current attribute currentModel i new C45Split i m minNoObj sumOfWeights bbs currentModel i buildClassifier data bbs Check if useful split for current attribute exists and check for enumerated attributes with a lot of values if currentModel i checkModel if m allData null if data attribute i isNumeric multiVal Utils sm double data attribute i numValues 0 3 double m allData numInstances averageInfoGain averageInfoGain currentModel i infoGain validModels else averageInfoGain averageInfoGain currentModel i infoGain validModels bbs else currentModel i null 里面重要的两句就是 Get models for current attribute currentModel i new C45Split i m minNoObj sumOfWeights currentModel i buildClassifier data bbs 其它的也没有什么 求一下 averageInfoGain 和 validModels checkModel 如果可以分出子结点则为真 这里是 C45Split 类的成员函数 buildClassfier 被调用 列出它的代码 public void buildClassifier Instances trainInstances throws Exception Initialize the remaining instance variables m numSubsets 0 m splitPoint Double MAX VALUE m infoGain 0 bbs m gainRatio 0 Different treatment for enumerated and numeric attributes if trainInstances attribute m attIndex isNominal m complexityIndex trainInstances attribute m attIndex numValues m index m complexityIndex handleEnumeratedAttribute trainInstances else m complexityIndex 2 m index 0 bbs trainInstances sort trainInstances attribute m attIndex handleNumericAttribute trainInstances bbs bbs 这里 handleEnumerateAttribute 和 handleNumericAttribute 是 决定到底是哪一个属性分裂 m attIndex 和分裂出几个子结点的函数 m numSubsets 这里的 m comlexity 就是指分可以分裂出多少子结点 如果是连续属性就是 2 再看一下 handleEnumeratedAttribute 函数 private void handleEnumeratedAttribute Instances trainInstances throws Exception bbs bbs Instance instance m distribution new Distribution m complexityIndex trainInstances numClasses Only Instances with known values are relevant Enumeration enu trainInstances enumerateInstances while enu hasMoreElements instance Instance enu nextElement if instance isMissing m attIndex m distribution add int instance value m attIndex bbs instance bbs Check if minimum number of Instances in at least two subsets if m distribution check m minNoObj m numSubsets m complexityIndex bbs m infoGain infoGainCrit splitCritValue m distribution bbs m sumOfWeights m gainRatio gainRatioCrit splitCritValue m distribution m sumOfWeights m infoGain bbs Current attribute is a numeric attribute bbs m distribution new Distribution 2 trainInstances numClasses Only Instances with known values are relevant Enumeration enu trainInstances enumerateInstances i 0 while enu hasMoreElements instance Instance enu nextElement if instance isMissing m attIndex break m distribution add 1 instance bbs i firstMiss i bbs 已经讲过了 如果是连续属性就分出两个子结点 也就是 Distribution 的第 一个参数 枚举所有样本 因为在调用 HandleNumericAttribute 之间已经对数据 集根据 m attIndex 排序过 所以缺失数据都在最后 也就是 firstMiss 是在 m attIndex 上有确定值的样本个数 1 在 while 循环中 把所有的样本都先放 到 bag 1 中 add 1 instance 还是列出来一下吧 public final void add int bagIndex Instance instance throws Exception int classIndex double weight bbs classIndex int instance classValue weight instance weight m perClassPerBag bagIndex classIndex m perClassPerBag bagIndex classIndex weight m perBag bagIndex m perBag bagIndex weight bbs m perClass classIndex m perClass classIndex weight totaL totaL weight 也就这个函数也就是根据参数 bagIndex 和样本的类别值 classIndex 三个 成员变量 m perBag m perClass m perClassPerBag 分别加上样本的权重 bbs Compute minimum number of Instances required in each subset minSplit 0 1 m distribution total double trainInstances numClasses bbs if Utils smOrEq minSplit m minNoObj minSplit m minNoObj else if Utils gr minSplit 25 bbs minSplit 25 bbs Enough Instances with known values if Utils sm double firstMiss 2 minSplit return 计算分最小分裂需要的样本数 这些涉及的值在 Quinlan 的论文中没有提 到 可能也没有太多的道理 就是如果样本数的 1 10 小于 m minNoObj 那么最 小分裂样本数就是 m minNoObj 如果大于 25 最小分裂样本数就是 25 如果 firstMiss 小于 2 minSplit 表示已经不可以再分裂了 为什么刚才已经 讲过了 bbs Compute values of criteria for all possible split indices bbs defaultEnt infoGainCrit oldEnt m distribution while next firstMiss if trainInstances instance next 1 value m attIndex 1e 5 trainInstances instanc