weka開發(fā)[21]ibk(knn)源代碼分析

1、Weka開發(fā)21IBk(KNN)源代碼分析如果你沒有看上一篇IB1，請先看一下，因?yàn)橹貜?fù)的內(nèi)容我在這里不會(huì)介紹了。直接看buildClassifier，這里只列出在IB1中也沒有出現(xiàn)的代碼：trym_NumClasses=instances.numClasses();m_ClassType=instances.classAttribute().type();catch(Exceptionex)thrownewError("Thisshouldneverbereached");/Throwawayinitialinstancesuntilwithinthespecifiedw

2、indowsizeif(m_WindowSize>0)&&(instances.numInstances()>m_WindowSize)m_Train=newInstances(m_Train,m_Train.numInstances()-m_WindowSize,m_WindowSize);/Computethenumberofattributesthatcontribute/toeachpredictionm_NumAttributesUsed=0.0;for(inti=0;i<m_Train.numAttribut

3、es();i)if(i!=m_Train.classIndex()&&(m_Train.attribute(i).isNominal()|m_Train.attribute(i).isNumeric()m_NumAttributesUsed=1.0;/Invalidateanycurrentlycross-validationselectedkm_kNNValid=false;IB1中不關(guān)心m_NumClasses是因?yàn)樗驼乙粋€(gè)鄰居，當(dāng)然就一個(gè)值了。m_WindowSize是指用多少樣本用于分類，這里不是隨機(jī)選擇而是直接選前m_WindowSize個(gè)。這里下面

4、是看有多少屬性參與預(yù)測。KNN也是一個(gè)可以增量學(xué)習(xí)的分器量，下面看一下它的updateClassifier代碼：publicvoidupdateClassifier(Instanceinstance)throwsExceptionif(m_Train.equalHeaders(instance.dataset()=false)thrownewException("Incompatibleinstancetypes");if(instance.classIsMissing()return;if(!m_DontNormalize)updateMinMax(instance);m

5、_Train.add(instance);m_kNNValid=false;if(m_WindowSize>0)&&(m_Train.numInstances()>m_WindowSize)while(m_Train.numInstances()>m_WindowSize)m_Train.delete(0);updateMinMax，如果超出窗口大小，循環(huán)刪除超過窗口大小的第一個(gè)樣本。這里注意IBk沒有實(shí)現(xiàn)classifyInstance，它只實(shí)現(xiàn)了distributionForInstances:publicdoubl

6、edistributionForInstance(Instanceinstance)throwsExceptionif(m_Train.numInstances()=0)thrownewException("Notraininginstances!");if(m_WindowSize>0)&&(m_Train.numInstances()>m_WindowSize)m_kNNValid=false;booleandeletedInstance=false;while(m_Train.numInstances()&a

7、mp;gt;m_WindowSize)m_Train.delete(0);/rebuilddatastructureKDTreecurrentlycan'tdeleteif(deletedInstance=true)m_NNSearch.setInstances(m_Train);/Selectkbycrossvalidationif(!m_kNNValid&&(m_CrossValidate)&&(m_kNNUpper>=1)crossValidate();m_NNSearch.addInstanceInf

8、o(instance);Instancesneighbours=m_NNSearch.kNearestNeighbours(instance,m_kNN);doubledistances=m_NNSearch.getDistances();doubledistribution=makeDistribution(neighbours,distances);returndistribution;前面兩個(gè)判斷不講了，crossValidate()馬上講，尋找K個(gè)鄰居在我第18篇里已經(jīng)講過了，現(xiàn)在我們看一下makeDistribution函數(shù)。protecteddoublemakeDistributi

9、on(Instancesneighbours,doubledistances)throwsExceptiondoubletotal=0,weight;doubledistribution=newdoublem_NumClasses;/Setupacorrectiontotheestimatorif(m_ClassType=Attribute.NOMINAL)for(inti=0;i<m_NumClasses;i)distributioni=1.0/Math.max(1,m_Train.numInstances();total=(double)m_NumClasses/Math.m

10、ax(1,m_Train.numInstances();for(inti=0;i<neighbours.numInstances();i)/CollectclasscountsInstancecurrent=neighbours.instance(i);distancesi=distancesi*distancesi;distancesi=Math.sqrt(distancesi/m_NumAttributesUsed);switch(m_DistanceWeighting)caseWEIGHT_INVERSE:weight=1.0/(distancesi0.001);/toav

11、oiddivbyzerobreak;caseWEIGHT_SIMILARITY:weight=1.0-distancesi;break;default:/WEIGHT_NONE:weight=1.0;break;weight*=current.weight();tryswitch(m_ClassType)caseAttribute.NOMINAL:weight;distribution(int)current.classValue()=break;caseAttribute.NUMERIC:distribution0=current.classValue()*weight;break;catc

12、h(Exceptionex)thrownewError("Datahasnoclassattribute!");total=weight;/Normalisedistributionif(total>0)Utils.normalize(distribution,total);returndistribution;第一行注釋Setupacorrection，我感覺沒什么必要，又不是Bayes還有除0錯(cuò)誤，沒什么可修正的。這里可以看見它實(shí)現(xiàn)了三種距離權(quán)重計(jì)算方法，倒數(shù)，與1的差，另外就是固定權(quán)重1。然后如果類別是離散值把對應(yīng)的類值加上權(quán)重，如果是連續(xù)值，就加上當(dāng)前

13、類別值剩權(quán)重。crossValidate簡單地說就是用蠻力找在到底用多少個(gè)鄰居好，它對m_Train中的樣本進(jìn)行循環(huán)，對每個(gè)樣本找鄰居，然后統(tǒng)計(jì)看尋找多少個(gè)鄰居時(shí)最好。protectedvoidcrossValidate()doubleperformanceStats=newdoublem_kNNUpper;doubleperformanceStatsSq=newdoublem_kNNUpper;for(inti=0;i<m_kNNUpper;i)performanceStatsi=0;performanceStatsSqi=0;m_kNN=m_kNNUpper;Instance

14、instance;Instancesneighbours;doubleorigDistances,convertedDistances;for(inti=0;i<m_Train.numInstances();i)instance=m_Train.instance(i);neighbours=m_NNSearch.kNearestNeighbours(instance,m_kNN);origDistances=m_NNSearch.getDistances();for(intj=m_kNNUpper-1;j>=0;j-)convertedDistances=newdo

15、ubleorigDistances.length;System.arraycopy(origDistances,0,convertedDistances,0,origDistances.length);doubledistribution=makeDistribution(neighbours,convertedDistances);doublethisPrediction=Utils.maxIndex(distribution);if(m_Train.classAttribute().isNumeric()thisPrediction=distribution0;doubleerr=this

16、Prediction-instance.classValue();performanceStatsSqj=err*err;/SquarederrorperformanceStatsj=Math.abs(err);/Absoluteerrorelseif(thisPrediction!=instance.classValue()performanceStatsj;/Classificationerrorif(j>=1)neighbours=pruneToK(neighbours,convertedDistances,j);/Checkthroughtheperformancesta

17、tsandselectthebest/kvalue(orthelowestkifmorethanonebest)doublesearchStats=performanceStats;if(m_Train.classAttribute().isNumeric()&&m_MeanSquared)searchStats=performanceStatsSq;doublebestPerformance=Double.NaN;intbestK=1;for(inti=0;i<m_kNNUpper;i)if(Double.isNaN(bestPerformance)bestPerformance=searchStatsi;bestK=i1;m_kNN=bestK;m_kNNValid=true;m_kNNUp