分类算法Java代码分析

1、Weak.classifiers包中含有用于分类和数值预测的大部分算法的实现。这个包中最重要的是类是Classifier，它定义了任何用于分类或数值预测的学习方案的通用结构。Classifier含有三个方法，buildClassfier(),classifyInstance(),distributionForInstance().学习算法用Classifier的子类代表，因此，自动继承这三个方法。每种方案都会根据构建分类器以及它对实例进行分类的具体方式对这三个方法进行重新定义。首先先解释一下算法名字，很多人很奇怪为什么叫IB1,IBK，IB Instance-Based的缩写，但按Jiawei

2、 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().isNum

3、eric() 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 = ne

4、w Instances(instances, 0, instances.numInstances(); m_Train.deleteWithMissingClass(); /Instance是一个类，Create empty instance with three attribute values m_MinArray = new doublem_Train.numAttributes();/定义一个数组，m_MinArray ，数据类型是double型，共有m_Train.numAttributes()个数据。 m_MaxArray = new doublem_Train.numAttrib

5、utes(); for (int i = 0; i m_Train.numAttributes(); i+) m_MinArrayi = m_MaxArrayi = Double.NaN; /还没有将真正的实例的属性存放在这两个数组里 Enumeration enu = m_Train.enumerateInstances(); /列举出每个实例的属性值 while (enu.hasMoreElements() /以枚举的实例属性数量进行循环判断 updateMinMax(Instance) enu.nextElement(); /更新属性的最大最小值 是的，KNN也有buildClassif

6、ier，听起来蛮奇怪的。第二个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() & (!i

7、nstance.isMissing(j) /这个属性的第j个值是数值型，并且，实例不缺失这个属性值 if (Double.isNaN(m_MinArrayj) m_MinArrayj = instance.value(j); /value()是要返回实例的属性值。 m_MaxArrayj = instance.value(j); else if (instance.value(j) m_MaxArrayj) m_MaxArrayj = instance.value(j); /如果这个属性值大于之前定义的最大属性值，将其值赋给最大属性值。 Double.isNaN(m_MinArrayj)判断是

8、不是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,/声明并且

9、初始化 classValue = 0;/ classValue():实例的类别属性Returns an instances 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 = (Inst

10、ance) enu.nextElement(); if (!trainInstance.classIsMissing() distance = distance(instance, trainInstance); /distance方法在后面有说明 if (distance minDistance) minDistance = distance; classValue = trainInstance.classValue();/classValue()：Returns an instances class value in internal format，返回这个实例的类别属性 return

11、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() /

12、classIndex():Returns the class attributes 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.isMissin

13、g(i) if (first.isMissing(i) & second.isMissing(i) diff = 1; else if (second.isMissing(i) diff = norm(first.value(i), i); else diff = norm(second.value(i), i); if (diff 0) & (instances.numInstances() m_WindowSize) m_Train = new Instances(m_Train, m_Train.numInstances() - m_WindowSize, m_WindowSize);

14、/ Compute the number of attributes that contribute / to each prediction m_NumAttributesUsed = 0.0; for (int i = 0; i 0) & (m_Train.numInstances() m_WindowSize) while (m_Train.numInstances() m_WindowSize) m_Train.delete(0); 同样很简单，updateMinMax，如果超出窗口大小，循环删除超过窗口大小的第一个样本。 这里注意IBk没有实现classifyInstance，它只实

15、现了distributionForInstances: public double distributionForInstance(Instance instance) throws Exception if (m_Train.numInstances() = 0) throw new Exception(No training instances!); if (m_WindowSize 0) & (m_Train.numInstances() m_WindowSize) m_kNNValid = false; boolean deletedInstance = false; while (m

16、_Train.numInstances() m_WindowSize) m_Train.delete(0); /rebuild datastructure KDTree currently cant delete if (deletedInstance = true) m_NNSearch.setInstances(m_Train); / Select k by cross validation if (!m_kNNValid & (m_CrossValidate) & (m_kNNUpper = 1) crossValidate(); m_NNSearch.addInstanceInfo(i

17、nstance); 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 doub

18、le makeDistribution(Instances neighbours, double distances)throws Exception double total = 0, weight; double distribution = new doublem_NumClasses; / Set up a correction to the estimator if (m_ClassType = Attribute.NOMINAL) for (int i = 0; i m_NumClasses; i+) distributioni = 1.0 / Math.max(1, m_Trai

19、n.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。然后如果类别是离散值把对应的类值加上权重，如果是连续值，就加上当前类别值剩权

20、重。 crossValidate简单地说就是用蛮力找在到底用多少个邻居好，它对m_Train中的样本进行循环，对每个样本找邻居，然后统计看寻找多少个邻居时最好。 protected void crossValidate() double performanceStats = new doublem_kNNUpper; double performanceStatsSq = new doublem_kNNUpper; for (int i = 0; i m_kNNUpper; i+) performanceStatsi = 0; performanceStatsSqi = 0; m_kNN =

21、m_kNNUpper; Instance instance; Instances neighbours; double origDistances, convertedDistances; for (int i = 0; i = 0; j-) / Update the performance stats convertedDistances = new doubleorigDistances.length; System.arraycopy(origDistances, 0, convertedDistances, 0, origDistances.length); double distri

22、bution = makeDistribution(neighbours, convertedDistances); double thisPrediction = Utils.maxIndex(distribution); if (m_Train.classAttribute().isNumeric() thisPrediction = distribution0; double err = thisPrediction - instance.classValue(); performanceStatsSqj += err * err; / Squared error performance

23、Statsj += Math.abs(err); / Absolute error else if (thisPrediction != instance.classValue() performanceStatsj+; / 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

24、 one best) double searchStats = performanceStats; if (m_Train.classAttribute().isNumeric() & m_MeanSquared) searchStats = performanceStatsSq; double bestPerformance = Double.NaN; int bestK = 1; for (int i = 0; i searchStatsi) bestPerformance = searchStatsi; bestK = i + 1; m_kNN = bestK; m_kNNValid =

25、 true; m_kNNUpper是另一个设置最多有多少样本的参数，枚举每一个样本(instance)，找它的邻居(neighbors)，和距离(origDistances)。接下来就是把从0到m_kNNUpper个邻居的得到的方差(performanceStatsSq)和标准差(performanceStats)与以前得到的值累加。pruneToK就是得到j个样本(如果j+1的距离不等于第j个)，后面就比较好理解了， m_MeanSquared对连续类别是选择用方差还是标准差进行选择，然后最出m_kNNUpper看在多少邻居的时候，分类误差最小，就认为是最好的邻居数。以前打算写一篇有关One

26、R的weka源代码介绍的，但考虑知道这个算法的人太少，不想今天有人问这个算法，在这里我就把它补上。 OneR是一个很简单的算法，出自论文：Very simple classification rules perform well on most commonly used datasets，由于论文的风格过于奔放，并且很长，所以我也就没怎么看。基本思想就是对每一个属性都建一个单层的分类器，对这些分类器进行比较，谁分类效果好就作为最终的分类器。 下面还是看buildClassifier的代码（删除了部分代码），首先判断是不是就一个属性（一个属性意味着只有一个类别特征），如果是，那就用ZeroR算

27、法（如果不知道为什么，看我上一篇）。下面枚举每一个属性，在每一个属性上产生一个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.buildClassif

28、ier(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_corr

29、ect) bbs m_rule = r; bbs noRule = false; catch (Exception ex) 下面看一下刚才的newRule函数，初始化一个missingValueCounts数组，数组大小为类别集合的大小。如果当前这个类别是离散的调用newNominalRule，如果是连续的调用newNumericRule。下面的几行代码现在可能还有点难理解（理解不了，看完下面的再转回来看），missingValueCounts保存的是对这个属性缺失值类别值的读数，而maxIndex函数返回的就是这个属性缺失时最有时候的类别Index。再下来If判断是否训练集中如果这个属性值缺

30、失的样本，那么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 intdata.classAttribute().numValues(); bbs if

31、 (attr.isNominal() r = newNominalRule(attr, data, missingValueCounts); bbs else bbs r = newNumericRule(attr, data, missingValueCounts); r.m_missingValueClass = Utils.maxIndex(missingValueCounts); if (missingValueCountsr.m_missingValueClass = 0) r.m_missingValueClass = -1; / signal for no missing val

32、ue class else r.m_correct += missingValueCountsr.m_missingValueClass; bbs return r; 先看一下离散的情况，初始化一个二维数组，第一维属性的个数，第二维类别值集合的大小。下面对样本进行枚举，如果当前样本该属性值是缺失的，那么missingValuleCounts在相应的类别值下标上记数。如果不是缺失的，那种就在这个样本在该属性值的类别值下标上记数（说起来很糊涂，想通了很简单）。接下面这段代码刚开始看的时候，我也糊涂了，其实也很简单。best就是当一个样本在该属性取值为value时，最有可能的类别值。m_correct就是对这种情况的记数，即在全部样本中，当属性为attr时，属性值为value，类