精华内容
下载资源
问答
  • 1 基于贝叶斯决策理论的分类方法 优点:在数据较少情况下仍然有效,可以处理多类别问题。 缺点:对于输入数据准备方式比较敏感。 使用数据类型:标称型数据。 贝叶斯决策理论 我们现在用p1(x,y)表示数据点(x,...

    1 基于贝叶斯的决策理论的分类方法

    优点:在数据较少的情况下仍然有效,可以处理多类别问题。
    缺点:对于输入数据的准备方式比较敏感。
    使用数据类型:标称型数据。

    贝叶斯决策理论

    在这里插入图片描述
    我们现在用p1(x,y)表示数据点(x,y)属于类别1(图中用圆点表示的类别)的概率,用p2(x,y)表示数据点(x,y)属于类别2(图中用三角形表示的类别)的概率。对于一个新数据点,可以用下面的规则判定它的类别:

    • 如果p1(x,y)>p2(x,y),那么为类别1;
    • 如果p1(x,y)<p2(x,y),那么为类别2;

    也就是说,我们会选择高概率的类别。这就是贝叶斯决策的核心思想,即选择具有最高概率的决策。回到图4.1,如果图中的整个数据使用6个浮点数来表示,并且计算类别概率的Python代码只有两行,那么你会更倾向于使用哪种方法来对该数据点进行分类呢?

    • 使用kNN法,进行1000次距离计算;
    • 使用决策树,分别沿X轴、Y轴划分数据;
    • 计算数据点属于每个类别的概率,并进行比较。

    使用决策时不会非常成功;而和简单的概率计算相比,kNN计算量太大,因此,对于上述问题的最佳选择是使用概率比较的方法。

    2 条件概率

    假设x,a是两个事件,已知p(x|a),要求p(a|x),那么可以使用下面的计算方法:
    p(ax)=p(xa)p(a)p(x) p(a|x)=\frac{p(x|a)p(a)}{p(x)}

    p(a|x):x发生情况下,a发生的概率。
    p(x|a):a发生情况下,x发生的概率。
    p(x):x发生的概率。
    p(a):a发生的概率。

    3 使用条件概率来分类

    上面提到过按照贝叶斯决策理论计算要求计算两个概率p1(x,y)和p2(x,y):

    • 如果p1(x,y)>p2(x,y),那么为类别1;
    • 如果p1(x,y)<p2(x,y),那么为类别2;

    实际上,这两个准则并不是贝叶斯决策理论的全部内容,真正需要计算和比较的是p(c1x,y)p(c_1|x,y)p(c2x,y)p(c_2|x,y),这些符号所代表的意义是:给定某个x,y表示的数据点,那么该数据点来自类别c1c_1c2c_2的概率是多少呢? 具体的,可以应用贝叶斯准则得到:
    p(cix,y)=p(x,yci)p(ci)p(x,y) p(c_i|x,y)=\frac{p(x,y|c_i)p(c_i)}{p(x,y)}

    使用这些定义,可以定义贝叶斯分类准则为:

    • 如果p(c1x,y)&gt;p(c2x,y)p(c_1|x,y)&gt;p(c_2|x,y),那么属于类别为c1c_1
    • 如果p(c1x,y)&lt;p(c2x,y)p(c_1|x,y)&lt;p(c_2|x,y),那么属于类别为c2c_2

    使用贝叶斯准则,可以通过已知的三个概率值来计算未知的概率值。

    4 使用贝叶斯进行文档归类

    机器学习的一个重要应用就是文档的自动分类,在文档分类中,整个文档(如一封电子邮件)是实例,而电子邮件中的某些元素则构成特征。虽然电子邮件是一种会不断增加的文本,但我们同样可以对新闻报道、用户留言、政府公文等其他任意类型的文本进行分类。我们可以观察文档中出现的词,并把每个词的出现或者不出现作为一个特征。这样得到的特征树木就会跟词汇表中的词目一样多。朴素贝叶斯是上节介绍的贝叶斯分类器的一个扩展,是用于文档分类的常用算法。
    使用每个词作为特征并观察它们是否出现,这样得到的特征数目会有多少呢?据估计,仅在英语中,单词的总数就有500000之多,为了能进行英语阅读,估计需要掌握数千单词。

    朴素贝叶斯的一般过程

    1. 收集数据:可以使用任何方法。这里使用RSS源。
    2. 准备数据:需要数值型或者布尔型数据。
    3. 分析数据:有大量特征时,绘制特征作用不大,此时使用直方图比较好。
    4. 训练算法:计算不同的独立特征的条件概率 。
    5. 测试算法:计算错误率。
    6. 使用算法:一个常见的朴素贝叶斯应用是文档分类。可以在任意的分类场景中使用朴素贝叶斯分类器,不一定是文本。

    如果特征之间相互独立,那么样本数量就可以从N1000N^{1000}减少到1000×N{1000} \times N,所谓独立,指的是统计意义上的独立,即一个特征或者单词出现的可能性与它和其他单词相邻没有关系。朴素贝叶斯分类器的另一个假设是每个特征同等重要。其实这个假设也有问题,如果要判断留言板内容是否得当,不需要去看完1000个单词,而只需要10-20个特征就足以做出判断了。尽管有小瑕疵,但朴素贝叶斯的实际效果很好。

    5 使用Python进行文本分类

    要从文本中获取特征,必须对文本进行拆分。具体如何做呢?这里的特征是来自文本的词条,一个词条是字符的任意组合。可以吧词条想像成单词,也可以使用非单词词条,如URL,IP地址或者任意其他字符串。然后将每一个文本片段表示成一个词条向量,其中值为1表示词条出现在文档中,值为0表示词条未出现。
    对于在线留言板,建立两个类别:侮辱类和非侮辱类。使用1和0来表示。

    5.1 准备数据:从文本中构建词向量

    def loadDataSet():
        postingList = [['my','dog','has','flea','problems','help','please'],
                       ['maybe','not','take','him','to','dog','park','stupid'],
                       ['my','dalmation','is','so','cute','I','love','him',],
                       ['stop','posting','stupid','worthless','garbage'],
                       ['mr','licks','ate','my','steak','how','to','stop','him'],
                       ['quit','buying','worthless','dog','food','stupid']
                       ]
        classVec = [0,1,0,1,0,1]  # 1代表侮辱性文字,0代表正常言论
        return postingList, classVec
    
    def createVocalSet(dataSet):
        vocalSet = set([])         #创建一个空集
        for document in dataSet:
            vocalSet = vocalSet | set(document)  # 创建两个集合的并集
        return list(vocalSet)
        
    #词集模型,标记出现的词为1
    def setOfWords2Vec(vocalList,inputSet):       #创建一个其中所含元素都为0的向量
        returnVec = [0] * len(vocalList)
        for word in inputSet:
            if word in vocalList:
                returnVec[vocalList.index(word)] = 1
            else:
                print("the word: %s is not in my vocabulary!" % word)
        return returnVec
    

    第一个函数loadDataSet()创建了一些实验样本。该函数返回的第一个变量是进行词条切分后的文档集合。第二个变量是一个类别标签的集合。这里有两类,分别为侮辱性和非侮辱性。这些文本的标注由人工标注,这些标注信息用于训练程序以便自动检测侮辱性留言。
    第二个函数createVocalSet()会创建一个包含在所有文档中出现的不重复词的列表。此处使用了Python的set数据类型。将词条列表输给set构造函数,set就会返回一个不重复词表。首先,创建一个空集合 , 然后将每篇文档返回的新词集合添加到该集合中。操作符丨用于求两个集合的并集,这也是一个按位或(OR ) 操作符。在数学符号表示上,按位或操作与集合求并操作使用相同记号。
    第三个函数setOfWords2Vec(),该参数的输入参数为词汇表和某个文档,输出的是文档向量,向量的每一元素为1或0,分别表示词汇表中的单词在输入文档中是否出现。函数首先创建一个和词汇表等长的向量,并将其他元素设置为0。接着遍历文档中的所有单词,如果出现了词汇表中的单词,则将输出的文档向量中的对应值设为1。现在看一下这些函数的执行效果:

    if __name__=="__main__":
    #     '''
    #     steps:
    #     1st : create a original data, like txt ,email address,symbols etc. marking the bad message as zero and good message as one
    #     2nd :delete the same element in original data and form a new list as vocabulary list.
    #     3nd : compare the vocabulary list and original data, marking one once it appeared in vocabulary and marking zero once it didn't appeared
    #     '''
    	listOPosts,listClasses = loadDataSet()
           myVocabList = createVocalSet(listOPosts)
           print(myVocabList)
           label0 = setOfWords2Vec(myVocabList, listOPosts[0])
           print(label0)
           label1 = setOfWords2Vec(myVocabList, listOPosts[1])
           print(label1)
           result
    ['stupid', 'buying', 'love', 'licks', 'ate', 'park', 'stop', 'I', 'please', 'quit', 'maybe', 'worthless', 'dog', 'how', 'flea', 'has', 'not', 'mr', 'posting', 'problems', 'steak', 'dalmation', 'help', 'so', 'my', 'garbage', 'food', 'take', 'is', 'to', 'cute', 'him']
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
    [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1]
    

    5.2 训练算法:从词向量计算概率

    5.1节介绍了如何将一组单词转化为一组数字,接下来看看如何使用这些数字计算概率。现在已经知道了一个词是否出现在一篇文档中,也知道了该文档所属的类别。接下来要计算,给定一篇文档,判断它的类别。
    我们重写贝叶斯准则,将之前的x,y转换为w\vec{w}w\vec{w}表示一个向量,它由多个数值表示。在这个例子中,数值个数与词汇表中的词个数相同。
    p(ciw)=p(wci)p(ci)p(w)p(c_i|\vec{w})=\frac{p(\vec{w}|c_i)p(c_i)}{p(\vec{w})}
    我们将使用上面的公式,对每个类别进行计算(侮辱性和非侮辱性),然后比较这两个类别的概率值大小。如何计算呢?

    1. 首先可以通过类别i(侮辱性和非侮辱性留言)中文档书除以总的文档数来计算概率p(ci)p(c_i)
    2. 接下来计算p(wci)p(\vec{w}|c_i),这里要用到朴素贝叶斯假设。如果将w\vec{w}展开为一个个独立特征,那么就可以将上述概率写作p(w0,w1,w2,,wNci)p(w_0,w_1,w_2,\dots,w_N|c_i),这里假设所有词都相互独立,该假设也被称为条件独立性假设,它意味着可以使用p(w0ci)p(w1ci)p(w2ci)p(wNci)p(w_0|c_i)p(w_1|c_i)p(w_2|c_i)\dots p(w_N|c_i)来计算上述概率。极大简化了计算过程。

    编码实现:

    def trainNB0(trainMatrix, trainCategory):
        numTrainDocs = len(trainMatrix)
        print("numTrainDocs is",numTrainDocs)
        numWords = len(trainMatrix[0])
        print("numWords is", numWords)
        PAbusive = sum(trainCategory)/float(numTrainDocs)
        print("PAbusive is", PAbusive)
        #做一些修改,避免出现在计算条件概率的时候,因为其中一个值为0,导致所有的值为0
        p0Num = zeros(numWords)                     #1 初始化概率
        p1Num = zeros(numWords)
        p0Denom = 0.0
        p1Denom = 0.0
        for i in range(numTrainDocs):
            if trainCategory[i] == 1:
                p1Num += trainMatrix[i]             #2 向量相加
                p1Denom += sum(trainMatrix[i])
            else:
                p0Num += trainMatrix[i]
                p0Denom += sum(trainMatrix[i])
        #解决溢出问题,取对数运算
        p1Vect = p1Num / p1Denom                    #3 对每个元素做除法
        p0Vect = p0Num / p0Denom
        return p0Vect,p1Vect,PAbusive
    

    代码函数的输入参数为文档矩阵trainMatrix,以及由每篇文档类别标签构成的向量trainCategory。首先计算文档属于侮辱性文档(class=1)的概率,即p(1)。因为这是一个二分类问题,故p(0)=1p(1)p(0)=1-p(1)。对于多于两类的分类问题,则需要对代码进行修改。
    计算p(wic1)p(\vec{w_i}|c_1)p(wic0)p(\vec{w_i}|c_0),需要初始化程序中的分母和分子变量。由于w\vec{w}中元素众多,因此可以使用Numpy数组来快速计算这些值。上述程序中的分母变量是一个元素个数等于词汇表大小的Numpy数组,在for循环中,要遍历训练集trainMatrix中的所有文档。一旦某个词语(侮辱性或正常词语)在某一文档中出现,则该词对应的个数(p1Num或p0Num)就加1,而且在所有的文档中,该文档的总词数也相应加1,对于两个类别都要进行同样的计算处理。
    最后,对每个元素除以该类别中的总词数。利用NumPy可以很好的实现,用一个数组除以浮点数即可,接下来是代码的试验:

    if __name__=="__main__":
    trainMat = []
        for postinDoc in listOPosts:
            returnVec = setOfWords2Vec(myVocabList,postinDoc)
            print("Every returnVec is",returnVec)
            trainMat.append(setOfWords2Vec(myVocabList,postinDoc))
        print("trainMat is",trainMat)
    
        p0V,p1V,pAb = trainNB0(trainMat,listClasses)
        print("p0v is ",p0V)
        print("p1V is ",p1V)
        print("pAb is ",pAb)
    
    Result is as follows:
    trainMat is [[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1], [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1], [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1], [1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]]
    numTrainDocs is 6
    numWords is 32
    PAbusive is 0.5
    p0v is  [0.         0.04166667 0.04166667 0.04166667 0.04166667 0.04166667
     0.         0.         0.04166667 0.         0.04166667 0.04166667
     0.04166667 0.04166667 0.         0.04166667 0.04166667 0.04166667
     0.         0.         0.         0.04166667 0.04166667 0.04166667
     0.         0.08333333 0.04166667 0.04166667 0.         0.04166667
     0.125      0.        ]
    p1V is  [0.05263158 0.         0.         0.         0.10526316 0.
     0.05263158 0.05263158 0.         0.05263158 0.05263158 0.
     0.         0.         0.15789474 0.         0.05263158 0.
     0.10526316 0.05263158 0.05263158 0.         0.         0.
     0.05263158 0.05263158 0.         0.         0.05263158 0.
     0.         0.05263158]
    pAb is  0.5
    

    首先,我们发现文档属于侮辱类的概率为0.5是正确的,其他概率也基本是正确的。

    5.3 测试算法:根据现实情况修改分类器

    利用贝叶斯分类器对文档进行分类时,要计算多个概率的乘积以获得文档属于某个类别的概率。即计算p(w0ci)p(w1ci)p(w2ci)p(w_0|c_i)p(w_1|c_i)p(w_2|c_i),如果其中一个值为0,那么最后乘积也为0。为降低这种影响,可以将所以词的出现数初始化为1,并将分母初始化为2,修改trainNB0()中第四行和第五行,

        p0Num = ones(numWords)                    
        p1Num = ones(numWords)
        p0Denom = 2.0
        p1Denom = 2.0
    

    另一个遇到的问题是下溢,这是由于太多很小的数相乘造成的。一种解决办法是对乘积取自然对数。在代数中有ln(xy)=ln(x)+ln(y)ln(x\ast y)=ln(x)+ln(y),于是通过求对数可以避免下溢出或者浮点数舍入导致的错误。同时,采用自然对数进行处理不会有任何损失。给出函数f(x)f(x)ln(f(x))ln(f(x))的曲线。检查这两条曲线,就会发现它们在相同区域内同时增加或者减少,并且在相同点上取到极值。它们的取值虽然不同,但不影响最终结果。通过修改代码,可以实现这个过程:

        p1Vect = log(p1Num / p1Denom)                   
        p0Vect = log(p0Num / p0Denom)
    

    现在已经准备好了构建完整的分类器了。

    def classifyNB(vec2Classify,p0Vec,p1Vec,pClass1):
        p1 = sum(vec2Classify * p1Vec) + log(pClass1)
        p0 = sum(vec2Classify * p0Vec) + log(1-pClass1)
        if p1 > p0:
            return 1
        else:
            return 0
    
    def testingNB():
        listOPosts,listClasses = loadDataSet()
        myVocabList = createVocalSet(listOPosts)
        trainMat = []
        for postinDoc in listOPosts:
            returnVec = setOfWords2Vec(myVocabList, postinDoc)
            print("Every returnVec is", returnVec)
            trainMat.append(setOfWords2Vec(myVocabList, postinDoc))
        print("trainMat is", trainMat)
        p0V, p1V, pAb = trainNB0(array(trainMat), array(listClasses))
        testEntry = ['love','my','dalmation']
        thisDoc = array(setOfWords2Vec(myVocabList,testEntry))
        print(testEntry,'classified as: ',classifyNB(thisDoc,p0V,p1V,pAb))
        
    Result as follows:
        ['love', 'my', 'dalmation'] classified as:  0
    

    classifyNB有4个输入:要分类的向量vec2Classify,以及使用函数trainNB0()计算出来的p0V, p1V, pAb的概率。使用NumPy数组来计算两个向量相乘的结果。这里的相乘指的是向量中对应的元素相乘,即先将两个向量中的第一个元素相乘,然后在将第二个元素相乘,以此类推。接下来将词汇表中所有词的对应值相加,然后将该值加到类比的对数概率上。最后比较类别的概率返回大概率对应的类别标签。

    5.4 准备数据:文档词袋模型

    目前为止,我们将每个词的出现与否作为一个特征,这可以被描述为词集模型。如果一个词在文档中出现不止一次,这可能意味着包含该词是否出现在文档中所不能表达的某种信息,这种方法被称为词袋模型化。在词袋中,每个单词可以出现多次 ,而在词集中,每个词只能出现一次。为适应词袋模型,需要对函数稍加修改,修改后的函数称为bagOfWords2Vec()。代码如下:

    def bagOfWords2VecMN(vocalList,inputSet):
        returnVec = [0] * len(vocalList)
        for word in inputSet:
            if word in vocalList:
                returnVec[vocalList.index(word)] += 1
        return returnVec
    

    参考资料

    [1] Peter Harrington. 机器学习实战[M]. 北京:人民邮电出版社,2013:53-65.

    展开全文
  • 属于急切学习算法有:决策树、贝叶斯、基于规则的分类、后向传播分类、SVM和基于关联规则挖掘的分类等等。 懒惰学习:直至给定一个测试元组才开始构造泛化模型,也称为基于实例学习属于急切学习算法...

    1.急切学习与懒惰学习

    急切学习:在给定训练元组之后、接收到测试元组之前就构造好泛化(即分类)模型。

    属于急切学习的算法有:决策树、贝叶斯、基于规则的分类、后向传播分类、SVM和基于关联规则挖掘的分类等等。

    懒惰学习:直至给定一个测试元组才开始构造泛化模型,也称为基于实例的学习法。

    属于急切学习的算法有:KNN分类、基于案例的推理分类。

    2.KNN的优缺点

    优点:原理简单,实现起来比较方便。支持增量学习。能对超多边形的复杂决策空间建模。

    缺点:计算开销大,需要有效的存储技术和并行硬件的支撑。

    3.KNN算法原理

    基于类比学习,通过比较训练元组和测试元组的相似度来学习。

    将训练元组和测试元组看作是n维(若元组有n的属性)空间内的点,给定一条测试元组,搜索n维空间,找出与测试

    元组最相近的k个点(即训练元组),最后取这k个点中的多数类作为测试元组的类别。

    相近的度量方法:用空间内两个点的距离来度量。距离越大,表示两个点越不相似。

    距离的选择:可采用欧几里得距离、曼哈顿距离或其它距离度量。多采用欧几里得距离,简单!

    4.KNN算法中的细节处理

    • 数值属性规范化:将数值属性规范到0-1区间以便于计算,也可防止大数值型属性对分类的主导作用。

    可选的方法有:v' = (v - vmin)/ (vmax - vmin),当然也可以采用其它的规范化方法

    • 比较的属性是分类类型而不是数值类型的:同则差为0,异则差为1.

    有时候可以作更为精确的处理,比如黑色与白色的差肯定要大于灰色与白色的差。

    • 缺失值的处理:取最大的可能差,对于分类属性,如果属性A的一个或两个对应值丢失,则取差值为1;

    如果A是数值属性,若两个比较的元组A属性值均缺失,则取差值为1,若只有一个缺失,另一个值为v,

    则取差值为|1-v|和|0-v|中的最大值

    • 确定K的值:通过实验确定。进行若干次实验,取分类误差率最小的k值。
    • 对噪声数据或不相关属性的处理:对属性赋予相关性权重w,w越大说明属性对分类的影响越相关。对噪声数据可以将所在

    的元组直接cut掉。

    5.KNN算法流程

    • 准备数据,对数据进行预处理
    • 选用合适的数据结构存储训练数据和测试元组
    • 设定参数,如k
    • 维护一个大小为k的的按距离由大到小的优先级队列,用于存储最近邻训练元组
    • 随机从训练元组中选取k个元组作为初始的最近邻元组,分别计算测试元组到这k个元组的距离,将训练元组标号和距离存入优先级队列
    • 遍历训练元组集,计算当前训练元组与测试元组的距离,将所得距离L与优先级队列中的最大距离Lmax进行比较。若L>=Lmax,则舍弃该元组,遍历下一个元组。若L <Lmax,删除优先级队列中最大距离的元组,将当前训练元组存入优先级队列。
    • 遍历完毕,计算优先级队列中k个元组的多数类,并将其作为测试元组的类别。
    • 测试元组集测试完毕后计算误差率,继续设定不同的k值重新进行训练,最后取误差率最小的k值。

    6.KNN算法的改进策略

    • 将存储的训练元组预先排序并安排在搜索树中(如何排序有待研究)
    • 并行实现
    • 部分距离计算,取n个属性的“子集”计算出部分距离,若超过设定的阈值则停止对当前元组作进一步计算。转向下一个元组。
    • 剪枝或精简:删除证明是“无用的”元组。

    7.KNN算法java实现

    (待续,见下一篇博文)

    展开全文
  • Bayes 贝叶斯分类法是基于贝叶斯定定理统计学分类方法。...朴素贝叶斯分类法假定一个属性值在给定类影响独立于其他属性 —— 类条件独立性。 朴素贝叶斯优缺点 优点  所需估计参数少,
    转载地址:http://blog.csdn.net/china1000/article/details/48597469

    朴素贝叶斯

    贝叶斯分类法是基于贝叶斯定理的统计学分类方法。它通过预测一个给定的元组属于一个特定类的概率,来进行分类。朴素贝叶斯分类法假定一个属性值在给定类的影响独立于其他属性的 —— 类条件独立性。

    朴素贝叶斯的优缺点

    • 优点 
      1. 所需估计的参数少,对于缺失数据不敏感。
    • 缺点 
      1. 假设属性之间相互独立,这往往并不成立。(喜欢吃番茄、鸡蛋,却不喜欢吃番茄炒蛋)。
      2. 需要知道先验概率。
      3. 分类决策错误率。

    朴素贝叶斯的公式

    • 朴素贝叶斯求解: 
      P(C|F1,...,Fn)=p(C)p(F1,...,Fn|C)p(F1,...,Fn)=p(C)i=1np(Fi|C)

    Decision Tree

    决策树是一种简单但广泛使用的分类器,它通过训练数据构建决策树,对未知的数据进行分类。决策树的每个内部节点表示在一个属性上的测试,每个分枝代表该测试的一个输出,而每个树叶结点存放着一个类标号。 
    在决策树算法中,ID3基于信息增益作为属性选择的度量,C4.5基于信息增益比作为属性选择的度量,CART基于基尼指数作为属性选择的度量。

    决策树代码
    • 1

    决策树的优缺点

    • 优点 
      1. 不需要任何领域知识或参数假设。
      2. 适合高维数据。
      3. 简单易于理解。
      4. 短时间内处理大量数据,得到可行且效果较好的结果。
    • 缺点 
      1. 对于各类别样本数量不一致数据,信息增益偏向于那些具有更多数值的特征。
      2. 易于过拟合。
      3. 忽略属性之间的相关性。
      4. 不支持在线学习

    决策树公式

    • 熵: 
      Entropy(S)=pilogpi
    • 信息增益: 
      Entropy(S,A)=Entropy(S)vV(A)|Sv||S|Entropy(Sv)
    • 分裂信息: 
      SplitInfoR=j=1k|Dj||D|log2|Dj||D|
    • 增益比率: 
      GainRatio(R)=Gain(R)SplitInfoR(D)
    • 基尼指数: 
      Gini(S)=1imp2i

    SVM

    支持向量机把分类问题转化为寻找分类平面的问题,并通过最大化分类边界点距离分类平面的距离来实现分类。

    支持向量机的优缺点

    • 优点 
      1. 可以解决小样本下机器学习的问题。
      2. 提高泛化性能。
      3. 可以解决高维、非线性问题。超高维文本分类仍受欢迎。
      4. 避免神经网络结构选择和局部极小的问题。
    • 缺点 
      1. 缺失数据敏感。
      2. 内存消耗大,难以解释。
      3. 运行和调差略烦人。

    支持向量机的公式

    转自研究者July: SVM的求解,先导出12||w||2,继而引入拉格朗日函数,转化为单一因子对偶变量a的求解。如此求w.b与a的等价,而求a的解法即为SMO。把求分类函数f(x)=ωx+b的问题转化为求w,b的最优化问题,即凸二次规划问题,妙。 
    这里写图片描述 
    从上图我们可以看出,这条红色的线(超平面)把红色的点和蓝色的点分开了。超平面一边的点对应的y全部是-1,而另外一边全部是1。 
    接着我们可以令分类函数:f(x)=ωTx+b。显然x是超平面上的点时,f(x)=0。那么我们不妨要求所有满足f(x)<0的点,其对应的y等于-1,而f(x)>0则对应的y=1的数据点。(我盗用了很多图。。。) 
    这里写图片描述 
    回忆之前的目标函数:

    max1||ω||s.t.,yi(ωT+b)1,i=1,...,n
    这个问题等价于
    max1||ω||2s.t.,yi(ωT+b)1,i=1,...,n

    很显然这是一个凸优化的问题,更具体的,它是一个二次优化问题—目标函数是二次的,约束条件是线性的。这个问题可以用任何现成的QP(Quadratic Programming)优化包解决。但是因为这个问题的特殊性,我们还可以通过Lagrange Duality变换到对偶变量的优化问题,找到一种更加行之有效的方法求解。首先我们给每一个约束条件加上一个Lagrange mutiplier,我们可以将它们融合到目标函数中去。 L(ω,b,a)=12||ω||2ni=1α(yi(wTxi+b)1),然后我们令θ(ω)=maxai0L(ω,b,a)容易验证,当某个约束条件不满足时,例如yi(wTxi+b)<1,那么我们显然有θ(w)=。而当所有约束条件都满足时,则有θ(ω)=12||ω||2,亦即我们最初要最小化的量。那么我们现在的目标函数就变成了:minw,bθ(ω)=minω,bmaxai0L(ω,b,α)=p,并且我们有dp,因为最大值中最小的一个一定要大于最小值中最大的一个。总之p提供了一个第一个问题的最优值p的一个下界。在满足KKT条件时,二者相等,我们可以通过求解第二个问题来求解第一个问题。 
    先让L关于ω和b最小化,我们分别把L对w和b求偏导: 
    Lω=0ω=i=1nαiyixi

    Lb=0i=1nαiyi=0

    再带回L得到: 
    L(ω,b,a)=12i,j=1nαiαjyiyjxTixji,j=1nαiαjyiyjxTixjbi=1nαiyi+i=1nαi=i=1nαi12i,j=1nαiαjyiyjxTixj

    此时我们得到关于dual variable α的优化问题: 
    maxαni=1αi12ni,j=1αiαjyiyjxTixjs.t.,αi0,i=1,...,nni=1αiyi=0 
    这个问题存在高效的算法,不过求解过程就不在这里介绍了。对于一个数据点进行分类时,我们是把x带入到f(x)=wTx+b中,然后根据其正负号来进行类别划分的。把ω=ni=1αiyixi代入到f(x)=wTx+b,我们就可以得到f(x)=ni=1αiyi<xi,x>+b,这里的形式的有趣之处在于,对于新点x的检测,只需要计算它与训练数据点的内积即可。 
    为什么非支持向量的α等于零呢?因为对于非支持向量来说,L(ω,b,a)=12||ω||2ni=1α(yi(wTxi+b)1)中的,(yi(wTxi+b)1)是大于0的,而且αi又是非负的,为了满足最大化,αi必须等于0。悲剧的非支持向量就被无声的秒杀了。。。

    KNN

    K近邻的优缺点

    • 优点 
      1. 暂无
    • 缺点 
      1. 计算量太大
      2. 对于样本分类不均衡的问题,会产生误判。

    K近邻的公式

    Logistic Regression

    逻辑回归的优缺点

    • 优点 
      1. 速度快。
      2. 简单易于理解,直接看到各个特征的权重。
      3. 能容易地更新模型吸收新的数据。
      4. 如果想要一个概率框架,动态调整分类阀值。
    • 缺点 
      1. 特征处理复杂。需要归一化和较多的特征工程。

    逻辑回归的公式

    如果是连续的,那么就是多重线性回归;如果是二项分布,就是Logistic回归;如果是Poission分布,就是Poisson回归;如果是负二项分布,那么就是负二项分布。
    回归问题常见步骤是:寻找h函数;构造J函数;想办法使得J函数最小并求得回归参数。逻辑回归的h函数为:
    
    • 1
    • 2
    • 3

    hθ(x)=g(θTx)=11+eθTx 
    其中hθ(x)的值表示结果取1的概率。 
    这里写图片描述 
    那么对于输入x的分类结果对于类别1和类别0的概率分别为: 
    P(y=1|x;θ)=hθ(x) 
    P(y=0|x;θ)=1hθ(x) 
    那么对于构造损失函数J,它们基于最大似然估计推到得到的: 
    ni=1Cost(hθ(xi),yi)=1m[ni=1yiloghθ(xi)+(1yi)log(1hθ(xi))] 
    最小化上式,与最大化下式子类似: 
    P(y|x;θ)=(hθ(x))y(1hθ(x))1y 
    取似然函数: 
    l(θ)=logL(θ)=ni=1yi(loghθ(xi)+(1yi)log(1hθ(xi))) 
    使用梯度上升的方法,求解θ,同样如果把J(θ)取为 
    1ml(θ),这样通过梯度下降求解梯度最小值。 
    梯度下降法求最小值: 
    θj:=θjασσθiJ(θ) 
    代入后得到: 
    θj:=θjα1mmi=1(hθ(xi)yi)xji 
    然后θ的更新过程如下: 

    θj:=θjα1mxTE

    其中E=g(A)-y。 
    正则化Regularization: 
    正则化是在经验风线上增加一个正则化项或者惩罚项。正则化项一般是模型复杂度的单调递增函数,模型越复杂,正则化就越大。 
    J(θ)=12mi=1n(hθ(xi)yi)2+λj=1nθ2j

    λ是正则项系数。多分类时可以去样本被判定为分类概率最大的那个类。

    逻辑回归的问题

    • 过拟合问题 
      1. 减少feature个数
      2. 规格化

    神经网络

    神经网络的优缺点

    • 优点 
      1. 分类准确率高。
      2. 并行处理能力强。
      3. 分布式存储和学习能力强。
      4. 鲁棒性较强,不易受噪声影响。
    • 缺点 
      1. 需要大量参数(网络拓扑、阀值、阈值)。
      2. 结果难以解释。
      3. 训练时间过长。

    神经网络公式

    深度学习???

    Ensemble learning

    集成学习的思路是在对新的实例进行分类的时候,把多个单分类器的结果进行某种组合,来对最终的结果进行分类。 
    更好的数据往往打败更好的算法,设计好的特征大有脾益。并且如果你有一个庞大的数据集,使用某种特定的算法的性能可能并不要紧。大可以挨个分类器尝试,并且选取最好的一个。(可以多从易用性和性能考虑) 
    而且从Netfliex Prize的经验教训来看,尝试各类分类器、交叉验证、集成方法往往能取得更好的结果,一般的boosting>bagging>single classifier。集成学习的方法主要有一下三种: 
    1. 在样本上做文章,基分类器为同一个分类算法,主要有bagging和boosting。 
    2. 在分类算法上做文章,即用于训练基分类器的样本相同。基分类器的算法不同。 
    3. 在样本属性集上做文章,即在不同的属性上构建分类器,比较出名的是randomforest Tree的算法,这个有weka也有实现。 
    1998年Jerome Friedman & Trevor Hastie & Robert Tibshirani发表文章Additive Logistic Regression: a Statistical View of Boosting,中提到Bagging是一个纯粹的降低相关度的方法。如果树的节点具有很高的相关性,bagging就会有很好的效果。

    GBDT

    回归树类似决策树,使用叶子节点的平均值作为判定的结果。如果不是叶子节点,那么就继续向下寻找。GBDT几乎可用于所有的回归问题,亦可以适用于二分类问题。
    GBDT使用新生成的树来拟合之前的树拟合的残差。
    
    • 1
    • 2
    • 3

    Adaboost

    Adaboost目的就是从训练数据中学习一系列的弱分类器或基本分类器,然后将这些弱分类器组合成一个强分类器。
    Adaboost的算法流程如下,首先初始化训练数据的权值分布。每个训练样本最开始都被赋予相同的权重:1/N。计算Gm(x)在训练数据集上的误差率em就是被Gm(x)误分类样本的权值之和。计算Gm(x)的系数,am表示Gm(x)在最终分类器中的重要程度。
    
    • 1
    • 2
    • 3

    αm=12log1emem,在em<=1/2时,am>=0,且am随着em的减小而增大。 
    更新训练数据集的权值分布(目的:得到样本的新权值分布),用于下一轮迭代: 
    Dm+1=(wm+1,1,wm+1,2,...wm+1,i...,wm+1,N)
    wm+1,i=wmiZmexp(αmyiGm(xi)),i=1,2,...,N 
    使得被基本分类器Gm(x)误分类样本的权值增大,而被正确分类样本的权值减小。就这样,通过Zm=Ni=1wmiexp(αmyiGm(xi)),使得Dm+1成为一个概率分布。然后组合各个弱分类器f(x)=Mm=1αmGm(x),而得到的最终分类器G(x)=sign(f(x))=sign[Mm=1αmGm(x)]

    Random Forest

    随机森林指通过多颗决策树联合组成的预测模型,可以对样本或者特征取bagging。

    展开全文
  • kNN算法核心思想是如果一个样本在特征空间中k个最相邻样本中大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本特性。 kNN也被称为惰性算法,因为它是基于实例。...

    目录

    K最近邻法简介

    思想

    KNN算法的用途

    优点

    缺点

    改进策略

    K的取值

    实现


    K最近邻法简介

    思想

    近邻算法,又叫K最近邻(KNN,k-NearestNeighbor)分类算法。

    kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性。

    kNN也被称为惰性算法,因为它是基于实例的。kNN是无参数学习(这意味着它不会对底层数据的分布做出任何假设),它是基于实例(意味着我们的算法没有显式地学习模型。相反,它选择的是记忆训练实例)并在一个有监督的学习环境中使用。

    KNN算法的用途

    kNN算法在类别决策时,只与极少量的相邻样本有关。由于kNN主要依靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类别的交叉或重叠较多的待分样本集来说,kNN方法较其他方法更为合适。

    kNN算法还可用于回归,通过找出一个样本的k个最近邻居,将这些邻居的属性的平均值赋给该样本,就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值,如权值与距离成反比。

    优点

    1、简单,易于理解,易于实现,无需估计参数,无需训练。

    2、适合对稀有事件进行分类。

    3、特别适合于多分类问题(multi-modal,对象具有多个类别标签),kNN比SVM的表现要好。

    缺点

    1、计算量较大,对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。

    2、可理解性差,无法给出像决策树那样的规则。

    改进策略

    分类效率方面

    • 事先对样本属性进行约简,删除对分类结果影响较小的属性,快速的得出待分类样本的类别。
    • 较适用于样本容量大的类域的自动分类
    • 样本容量较小的类域采用这种算法比较容易产生误分。

    分类效果方面

    • 采用权值的方法(和样本距离小的邻居权值大)来改进。
    • 依照训练集合中各种分类的文件数量,选取不同数目的最近邻居,来参与分类。

    K的取值

    k值小意味着噪声会对结果产生较大的影响,而k值大则会使计算成本变高。

    k的取值很大程度上取决于你的实际情况,有些情况下最好是遍历每个可能的k值,然后根据实际来选择k值。


    实现

    API sklearn.neighbors.KNeighborsClassifier 

    闵科夫斯基距离介绍

    #导入相关库
    import numpy as np
    import pandas as pd
    import matplotlib.pyplot as plt
    #导入数据集
    dataset = pd.read_csv('./datasets/Social_Network_Ads.csv')
    X = dataset.iloc[ :,[2,3]].values
    y = dataset.iloc[ :,4].values
    #将数据集划分为训练集和测试集
    from sklearn.model_selection import train_test_split
    X_train, X_test, y_train, y_test = train_test_split(X,y,test_size = 0.25, random_state = 0)
    #特征缩放
    from sklearn.preprocessing import StandardScaler
    sc = StandardScaler()
    X_train = sc.fit_transform(X_train)
    X_test = sc.transform(X_test)
    
    #使用K-NN对训练集数据进行训练
    from sklearn.neighbors import KNeighborsClassifier
    #创建KNeighborsClassifier对象 
    #minkowski inequality闵科夫斯基不等式 p=2时为标准欧几里得度量
    classifier = KNeighborsClassifier(n_neighbors = 5, metric = 'minkowski', p = 2)  
    classifier.fit(X_train,y_train) #调用fit函数
    
    #对测试集进行预测
    y_pred = classifier.predict(X_test) #调用predict函数进行预测
    #生成混淆矩阵
    from sklearn.metrics import confusion_matrix
    cm = confusion_matrix(y_test,y_pred)
    print(cm)
    #[[64  4]
    #[ 3 29]]

     

     

    展开全文
  • 逻辑斯蒂回归(logistic distribution)适用于多类分类问题,它是对数线性模型,属于判别模型。 优点:计算代价不高,易于理解和实现。 缺点:容易欠拟合,分类精度可能不高。 模型 在讲逻辑斯蒂回归模型之前,我们先...
  • 概况: 提示:这里简述项目相关背景: 例如:项目场景:示例:通过蓝牙芯片(HC-05)与手机 APP 通信,每隔 5s 传输一批传感器数据(不是很大)在机器学习中,感知...感知机的学习算法具有简单而易于实现的优点,分为原始形
  • 随机森林特点

    2017-04-01 15:22:00
    在得到森林之后,当有一个新输入样本进入时候,就让森林中每一棵决策树分别进行一下判断,看看这个样本应该属于哪一类(对于分类算法),然后看看哪一类被选择最多,就预测这个样本为那一类。 二、优点 ...
  • K近邻是一种分类和回归算法,他输入特征向量,通过计算新数据与训练数据特征值之间距离,寻找K个距离最近邻居进行分类判断,若K=1,则直接分类给他距离最近数据那一类。 基本原理是概括为: 给定一...
  • 分类感知机--(1)

    2020-07-03 14:13:19
    感知机对应于输入空间(特征空间)中将实例划分为正负两类分高超平面,属于判别模型,感知机学习旨在求出将训练数据迸行线性划分分离超平面,为此,导入基于误分类的损失函数,利用梯度下降对损失函数进行极小...
  • 欧式距离:即计算每个特征之间距离,计算公式如下: 算法直观理解: 在已有样本中找到与当前样本距离最近k个样本,然后以者k个样本类别进行投票,看当前样本属于哪个类别。 算法评价 优点: 简单,易理解...
  • 给定一个训练数据集,对于新输入实例,在数据集中找到与该实例最邻近k个实例,这k个实例多数属于哪一类,就把该输入实例分为这个类。 优点:精度高、对异常值不敏感、无数据输入假定。 缺点:计算复杂度高、...
  • 属于急切学习算法有:决策树、贝叶斯、基于规则的分类、后向传播分类、SVM和基于关联规则挖掘的分类等等。懒惰学习:直至给定一个测试元组才开始构造泛化模型,也称为基于实例学习属于急切学习算法有:KNN...
  • 感知机的学习算法具有简单而易于实现的优点,分为原始形式和对偶形式。感知机预测是用学习得到的感知机模型对新的实例进行预测的,因此属于判别模型。感知机由Rosenblatt于1957年提出的,是神经网络和支持向量机的...
  • 属于急切学习算法有:决策树、贝叶斯、基于规则的分类、后向传播分类、SVM和基于关联规则挖掘的分类等等。   懒惰学习:直至给定一个测试元组才开始构造泛化模型,也称为基于实例学习属于急切学习算法有...
  • 调频连续波( frequency modulated contin - uous wave,FMCW)雷达是一种通过对连续波进行频率调制来获得距离与速度信息雷达体制系统,由于它具有无距离盲区、高分辨率和低发射功率等优点,近年来受到了人们广泛...
  • 调频连续波( frequency modulated contin - uous wave,FMCW)雷达是一种通过对连续波进行频率调制来获得距离与速度信息雷达体制系统,由于它具有无距离盲区、高分辨率和低发射功率等优点,近年来受到了人们广泛...
  • 调频连续波( frequency modulated contin - uous wave,FMCW)雷达是一种通过对连续波进行频率调制来获得距离与速度信息雷达体制系统,由于它具有无距离盲区、高分辨率和低发射功率等优点,近年来受到了人们广泛...
  • 1. 什么是感知机? ​ 感知机(perceptron)是二类分类的...感知机学习算法具有简答而易于实现的优点,分为原始形式和对偶形式,下文会一一给出。感知机预测是通过对训练数据的学习对新输入的实例进行分类。 定义1.1