精华内容
下载资源
问答
  • 机器学习之KNN最邻近分类算法

    万次阅读 多人点赞 2018-09-15 13:13:33
    KNN(K-Nearest Neighbor)最邻近分类算法是数据挖掘分类(classification)技术中最简单的算法之一,其指导思想是”近朱者赤,近墨者黑“,即由你的邻居来推断出你的类别。 KNN最邻近分类算法的实现原理:为了...

    前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到教程

    KNN算法简介

    KNN(K-Nearest Neighbor)最邻近分类算法是数据挖掘分类(classification)技术中最简单的算法之一,其指导思想是”近朱者赤,近墨者黑“,即由你的邻居来推断出你的类别。

    KNN最邻近分类算法的实现原理:为了判断未知样本的类别,以所有已知类别的样本作为参照,计算未知样本与所有已知样本的距离,从中选取与未知样本距离最近的K个已知样本,根据少数服从多数的投票法则(majority-voting),将未知样本与K个最邻近样本中所属类别占比较多的归为一类。

              以上就是KNN算法在分类任务中的基本原理,实际上K这个字母的含义就是要选取的最邻近样本实例的个数,在 scikit-learn 中 KNN算法的 K 值是通过 n_neighbors 参数来调节的,默认值是 5。

              如下图所示,如何判断绿色圆应该属于哪一类,是属于红色三角形还是属于蓝色四方形?如果K=3,由于红色三角形所占比例为2/3,绿色圆将被判定为属于红色三角形那个类,如果K=5,由于蓝色四方形比例为3/5,因此绿色圆将被判定为属于蓝色四方形类。

    由于KNN最邻近分类算法在分类决策时只依据最邻近的一个或者几个样本的类别来决定待分类样本所属的类别,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。

               KNN算法的关键:

               (1) 样本的所有特征都要做可比较的量化

               若是样本特征中存在非数值的类型,必须采取手段将其量化为数值。例如样本特征中包含颜色,可通过将颜色转换为灰度值来实现距离计算。

               (2) 样本特征要做归一化处理

               样本有多个参数,每一个参数都有自己的定义域和取值范围,他们对距离计算的影响不一样,如取值较大的影响力会盖过取值较小的参数。所以样本参数必须做一些 scale 处理,最简单的方式就是所有特征的数值都采取归一化处置。

               (3) 需要一个距离函数以计算两个样本之间的距离

               通常使用的距离函数有:欧氏距离、余弦距离、汉明距离、曼哈顿距离等,一般选欧氏距离作为距离度量,但是这是只适用于连续变量。在文本分类这种非连续变量情况下,汉明距离可以用来作为度量。通常情况下,如果运用一些特殊的算法来计算度量的话,K近邻分类精度可显著提高,如运用大边缘最近邻法或者近邻成分分析法。

    以计算二维空间中的A(x1,y1)、B(x2,y2)两点之间的距离为例,欧氏距离和曼哈顿距离的计算方法如下图所示:

    (4) 确定K的值

               K值选的太大易引起欠拟合,太小容易过拟合,需交叉验证确定K值。

    KNN算法的优点:

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

               2. 适合对稀有事件进行分类;

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

    KNN算法的缺点:

               KNN算法在分类时有个主要的不足是,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数,如下图所示。该算法只计算最近的邻居样本,某一类的样本数量很大,那么或者这类样本并不接近目标样本,或者这类样本很靠近目标样本。无论怎样,数量并不能影响运行结果。可以采用权值的方法(和该样本距离小的邻居权值大)来改进。

    该方法的另一个不足之处是计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。

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

    KNN算法实现

    要自己动手实现KNN算法其实不难,主要有以下三个步骤:

               算距离:给定待分类样本,计算它与已分类样本中的每个样本的距离;

               找邻居:圈定与待分类样本距离最近的K个已分类样本,作为待分类样本的近邻;

               做分类:根据这K个近邻中的大部分样本所属的类别来决定待分类样本该属于哪个分类;

    以下是使用Python实现KNN算法的简单示例:

    import math
    import csv
    import operator
    import random
    import numpy as np
    from sklearn.datasets import make_blobs
    
    #Python version 3.6.5
    
    # 生成样本数据集 samples(样本数量) features(特征向量的维度) centers(类别个数)
    def createDataSet(samples=100, features=2, centers=2):
        return make_blobs(n_samples=samples, n_features=features, centers=centers, cluster_std=1.0, random_state=8)
    
    # 加载鸢尾花卉数据集 filename(数据集文件存放路径)
    def loadIrisDataset(filename):
        with open(filename, 'rt') as csvfile:
            lines = csv.reader(csvfile)
            dataset = list(lines)
            for x in range(len(dataset)):
                for y in range(4):
                    dataset[x][y] = float(dataset[x][y])
            return dataset
        
    # 拆分数据集 dataset(要拆分的数据集) split(训练集所占比例) trainingSet(训练集) testSet(测试集)
    def splitDataSet(dataSet, split, trainingSet=[], testSet=[]):
        for x in range(len(dataSet)):
            if random.random() <= split:
                trainingSet.append(dataSet[x])
            else:
                testSet.append(dataSet[x])
    # 计算欧氏距离 
    def euclideanDistance(instance1, instance2, length):
        distance = 0
        for x in range(length):
            distance += pow((instance1[x] - instance2[x]), 2)
        return math.sqrt(distance)
    
    # 选取距离最近的K个实例
    def getNeighbors(trainingSet, testInstance, k):
        distances = []
        length = len(testInstance) - 1
        for x in range(len(trainingSet)):
            dist = euclideanDistance(testInstance, trainingSet[x], length)
            distances.append((trainingSet[x], dist))
        distances.sort(key=operator.itemgetter(1))
        
        neighbors = []
        for x in range(k):
            neighbors.append(distances[x][0])
        return neighbors
    
    #  获取距离最近的K个实例中占比例较大的分类
    def getResponse(neighbors):
        classVotes = {}
        for x in range(len(neighbors)):
            response = neighbors[x][-1]
            if response in classVotes:
                classVotes[response] += 1
            else:
                classVotes[response] = 1
        sortedVotes = sorted(classVotes.items(), key=operator.itemgetter(1), reverse=True)
        return sortedVotes[0][0]
    
    # 计算准确率
    def getAccuracy(testSet, predictions):
        correct = 0
        for x in range(len(testSet)):
            if testSet[x][-1] == predictions[x]:
                correct += 1
        return (correct / float(len(testSet))) * 100.0
    
    
    def main():
        # 使用自定义创建的数据集进行分类
        # x,y = createDataSet(features=2)
        # dataSet= np.c_[x,y]
        
        # 使用鸢尾花卉数据集进行分类
        dataSet = loadIrisDataset(r'C:\DevTolls\eclipse-pureh2b\python\DeepLearning\KNN\iris_dataset.txt')
            
        print(dataSet)
        trainingSet = []
        testSet = []
        splitDataSet(dataSet, 0.75, trainingSet, testSet)
        print('Train set:' + repr(len(trainingSet)))
        print('Test set:' + repr(len(testSet)))
        predictions = []
        k = 7
        for x in range(len(testSet)):
            neighbors = getNeighbors(trainingSet, testSet[x], k)
            result = getResponse(neighbors)
            predictions.append(result)
            print('>predicted=' + repr(result) + ',actual=' + repr(testSet[x][-1]))
        accuracy = getAccuracy(testSet, predictions)
        print('Accuracy: ' + repr(accuracy) + '%')
    main()
        
    

    尾花卉数据文件百度网盘下载链接:https://pan.baidu.com/s/10vI5p_QuM7esc-jkar2zdQ 密码:4und

    KNN算法应用

    使用KNN算法处理简单分类任务

    在scikit-learn中,内置了若干个玩具数据集(Toy Datasets),还有一些API让我们可以自己动手生成一些数据集。接下来我们将使用scikit-learn的make_blobs函数来生成一个样本数量为200,分类数量为2的数据集,并使用KNN算法来对其进行分类。

    # 导入画图工具
    import matplotlib.pyplot as plt
    # 导入数组工具
    import numpy as np
    # 导入数据集生成器
    from sklearn.datasets import make_blobs
    # 导入KNN 分类器
    from sklearn.neighbors import KNeighborsClassifier
    # 导入数据集拆分工具
    from sklearn.model_selection import train_test_split
    
    # 生成样本数为200,分类数为2的数据集
    data=make_blobs(n_samples=200, n_features=2,centers=2, cluster_std=1.0, random_state=8)
    X,Y=data
    
    # 将生成的数据集进行可视化
    # plt.scatter(X[:,0], X[:,1],s=80, c=Y,  cmap=plt.cm.spring, edgecolors='k')
    # plt.show()
    
    clf = KNeighborsClassifier()
    clf.fit(X,Y)
    
    # 绘制图形
    x_min,x_max=X[:,0].min()-1,X[:,0].max()+1
    y_min,y_max=X[:,1].min()-1,X[:,1].max()+1
    xx,yy=np.meshgrid(np.arange(x_min,x_max,.02),np.arange(y_min,y_max,.02))
    z=clf.predict(np.c_[xx.ravel(),yy.ravel()])
    
    z=z.reshape(xx.shape)
    plt.pcolormesh(xx,yy,z,cmap=plt.cm.Pastel1)
    plt.scatter(X[:,0], X[:,1],s=80, c=Y,  cmap=plt.cm.spring, edgecolors='k')
    plt.xlim(xx.min(),xx.max())
    plt.ylim(yy.min(),yy.max())
    plt.title("Classifier:KNN")
    
    # 把待分类的数据点用五星表示出来
    plt.scatter(6.75,4.82,marker='*',c='red',s=200)
    
    # 对待分类的数据点的分类进行判断
    res = clf.predict([[6.75,4.82]])
    plt.text(6.9,4.5,'Classification flag: '+str(res))
    
    plt.show()

     程序执行后得到结果如下图所示:

    使用KNN算法处理多元分类任务

    接下来,我们再使用scikit-learn的make_blobs函数来生成一个样本数量为500,分类数量为5的数据集,并使用KNN算法来对其进行分类。

    # 导入画图工具
    import matplotlib.pyplot as plt
    # 导入数组工具
    import numpy as np
    # 导入数据集生成器
    from sklearn.datasets import make_blobs
    # 导入KNN 分类器
    from sklearn.neighbors import KNeighborsClassifier
    # 导入数据集拆分工具
    from sklearn.model_selection import train_test_split
    
    # 生成样本数为500,分类数为5的数据集
    data=make_blobs(n_samples=500, n_features=2,centers=5, cluster_std=1.0, random_state=8)
    X,Y=data
    
    # 将生成的数据集进行可视化
    # plt.scatter(X[:,0], X[:,1],s=80, c=Y,  cmap=plt.cm.spring, edgecolors='k')
    # plt.show()
    
    clf = KNeighborsClassifier()
    clf.fit(X,Y)
    
    # 绘制图形
    x_min,x_max=X[:,0].min()-1,X[:,0].max()+1
    y_min,y_max=X[:,1].min()-1,X[:,1].max()+1
    xx,yy=np.meshgrid(np.arange(x_min,x_max,.02),np.arange(y_min,y_max,.02))
    z=clf.predict(np.c_[xx.ravel(),yy.ravel()])
    
    z=z.reshape(xx.shape)
    plt.pcolormesh(xx,yy,z,cmap=plt.cm.Pastel1)
    plt.scatter(X[:,0], X[:,1],s=80, c=Y,  cmap=plt.cm.spring, edgecolors='k')
    plt.xlim(xx.min(),xx.max())
    plt.ylim(yy.min(),yy.max())
    plt.title("Classifier:KNN")
    
    # 把待分类的数据点用五星表示出来
    plt.scatter(0,5,marker='*',c='red',s=200)
    
    # 对待分类的数据点的分类进行判断
    res = clf.predict([[0,5]])
    plt.text(0.2,4.6,'Classification flag: '+str(res))
    plt.text(3.75,-13,'Model accuracy: {:.2f}'.format(clf.score(X, Y)))
    
    plt.show()

     程序执行后得到结果如下图所示:

    使用KNN算法进行回归分析

    这里我们使用scikit-learn的make_regression生成数据集来进行实验,演示KNN算法在回归分析中的表现。

    # 导入画图工具
    import matplotlib.pyplot as plt
    # 导入数组工具
    import numpy as np
    
    # 导入用于回归分析的KNN模型
    from sklearn.neighbors import KNeighborsRegressor
    # 导入数据集拆分工具
    from sklearn.model_selection import train_test_split
    # 导入数据集生成器
    from sklearn.datasets.samples_generator import make_regression
    from docutils.utils.math.math2html import LineWriter
    
    # 生成样本数为200,分类数为2的数据集
    X,Y=make_regression(n_samples=100,n_features=1,n_informative=1,noise=50,random_state=8)
    
    # 将生成的数据集进行可视化
    # plt.scatter(X,Y,s=80, c='orange',  cmap=plt.cm.spring, edgecolors='k')
    # plt.show()
    reg = KNeighborsRegressor(n_neighbors=5)
    
    reg.fit(X,Y)
    
    # 将预测结果用图像进行可视化
    z = np.linspace(-3,3,200).reshape(-1,1)
    plt.scatter(X,Y,c='orange',edgecolor='k')
    plt.plot(z,reg.predict(z),c='k',Linewidth=3)
    #
    plt.title("KNN Regressor")
    
    plt.show()

      程序执行后得到结果如下图所示:

    KNN算法项目实战----酒的分类

    from sklearn.datasets.base import load_wine
    from sklearn.model_selection import train_test_split
    from sklearn.neighbors import KNeighborsClassifier
    import numpy as np
    
    # 从 sklearn的datasets模块载入数据集加载酒的数据集
    wineDataSet=load_wine()
    print(wineDataSet)
    print("红酒数据集中的键:\n{}".format(wineDataSet.keys()))
    print("数据概况:\n{}".format(wineDataSet['data'].shape))
    print(wineDataSet['DESCR'])
    
    # 将数据集拆分为训练数据集和测试数据集
    X_train,X_test,y_train,y_test=train_test_split(wineDataSet['data'],wineDataSet['target'],random_state=0)
    print("X_train shape:{}".format(X_train.shape))
    print("X_test shape:{}".format(X_test.shape))
    print("y_train shape:{}".format(y_train.shape))
    print("y_test shape:{}".format(y_test.shape))
    
    knn = KNeighborsClassifier(n_neighbors=1)
    knn.fit(X_train,y_train)
    print(knn)
    
    # 评估模型的准确率
    print('测试数据集得分:{:.2f}'.format(knn.score(X_test,y_test)))
    
    # 使用建好的模型对新酒进行分类预测
    X_new = np.array([[13.2,2.77,2.51,18.5,96.6,1.04,2.55,0.57,1.47,6.2,1.05,3.33,820]])
    prediction = knn.predict(X_new)
    print("预测新酒的分类为:{}".format(wineDataSet['target_names'][prediction]))

     执行程序后打印如下结果:

    X_train shape:(133, 13)
    X_test shape:(45, 13)
    y_train shape:(133,)
    y_test shape:(45,)
    KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
               metric_params=None, n_jobs=1, n_neighbors=1, p=2,
               weights='uniform')
    测试数据集得分:0.76
    预测新酒的分类为:['class_2']

    参考书籍:《深入浅出 Python 机器学习》 作者:段小手

    展开全文
  • 带你搞懂朴素贝叶斯分类算法

    万次阅读 多人点赞 2017-04-14 16:19:33
    贝叶斯分类是一类分类算法的总称,这类算法均以贝叶斯定理为基础,故统称为贝叶斯分类。而朴素朴素贝叶斯分类是贝叶斯分类中最简单,也是常见的一种分类方法。这篇文章我尽可能用直白的话语总结一下我们学习会上讲到...

    最新人工智能论文:http://paperreading.club

    带你搞懂朴素贝叶斯分类算

    贝叶斯分类是一类分类算法的总称,这类算法均以贝叶斯定理为基础,故统称为贝叶斯分类。而朴素朴素贝叶斯分类是贝叶斯分类中最简单,也是常见的一种分类方法。这篇文章我尽可能用直白的话语总结一下我们学习会上讲到的朴素贝叶斯分类算法,希望有利于他人理解。

     

    1  分类问题综述

     对于分类问题,其实谁都不会陌生,日常生活中我们每天都进行着分类过程。例如,当你看到一个人,你的脑子下意识判断他是学生还是社会上的人;你可能经常会走在路上对身旁的朋友说“这个人一看就很有钱”之类的话,其实这就是一种分类操作。

     

    既然是贝叶斯分类算法,那么分类的数学描述又是什么呢?

     

    从数学角度来说,分类问题可做如下定义:已知集合,确定映射规则y = f(x),使得任意有且仅有一个,使得成立。

     

    其中C叫做类别集合,其中每一个元素是一个类别,而I叫做项集合(特征集合),其中每一个元素是一个待分类项,f叫做分类器。分类算法的任务就是构造分类器f。

     

    分类算法的内容是要求给定特征,让我们得出类别,这也是所有分类问题的关键。那么如何由指定特征,得到我们最终的类别,也是我们下面要讲的,每一个不同的分类算法,对应着不同的核心思想。

     

    本篇文章,我会用一个具体实例,对朴素贝叶斯算法几乎所有的重要知识点进行讲解。

     

    2  朴素贝叶斯分类

    那么既然是朴素贝叶斯分类算法,它的核心算法又是什么呢?

    是下面这个贝叶斯公式:

     

     

    换个表达形式就会明朗很多,如下:

     

     

    我们最终求的p(类别|特征)即可!就相当于完成了我们的任务。

     

    3  例题分析

    下面我先给出例子问题。

     

    给定数据如下:

     

     

    现在给我们的问题是,如果一对男女朋友,男生想女生求婚,男生的四个特点分别是不帅,性格不好,身高矮,不上进,请你判断一下女生是还是不嫁

     

    这是一个典型的分类问题,转为数学问题就是比较p(嫁|(不帅、性格不好、身高矮、不上进))与p(不嫁|(不帅、性格不好、身高矮、不上进))的概率,谁的概率大,我就能给出嫁或者不嫁的答案!

    这里我们联系到朴素贝叶斯公式:

     

     

    我们需要求p(嫁|(不帅、性格不好、身高矮、不上进),这是我们不知道的,但是通过朴素贝叶斯公式可以转化为好求的三个量.

     

    p(不帅、性格不好、身高矮、不上进|嫁)、p(不帅、性格不好、身高矮、不上进)、p(嫁)(至于为什么能求,后面会讲,那么就太好了,将待求的量转化为其它可求的值,这就相当于解决了我们的问题!

     

    4  朴素贝叶斯算法的朴素一词解释

    那么这三个量是如何求得?

     

    是根据已知训练数据统计得来,下面详细给出该例子的求解过程。

    回忆一下我们要求的公式如下:

     

     

    那么我只要求得p(不帅、性格不好、身高矮、不上进|嫁)、p(不帅、性格不好、身高矮、不上进)、p(嫁)即可,好的,下面我分别求出这几个概率,最后一比,就得到最终结果。

     

    p(不帅、性格不好、身高矮、不上进|嫁) = p(不帅|嫁)*p(性格不好|嫁)*p(身高矮|嫁)*p(不上进|嫁),那么我就要分别统计后面几个概率,也就得到了左边的概率!

     

    等等,为什么这个成立呢?学过概率论的同学可能有感觉了,这个等式成立的条件需要特征之间相互独立吧!

     

    对的!这也就是为什么朴素贝叶斯分类有朴素一词的来源,朴素贝叶斯算法是假设各个特征之间相互独立,那么这个等式就成立了!

     

    但是为什么需要假设特征之间相互独立呢?

     

     

    1、我们这么想,假如没有这个假设,那么我们对右边这些概率的估计其实是不可做的,这么说,我们这个例子有4个特征,其中帅包括{帅,不帅},性格包括{不好,好,爆好},身高包括{高,矮,中},上进包括{不上进,上进},那么四个特征的联合概率分布总共是4维空间,总个数为2*3*3*2=36个。

     

    36个,计算机扫描统计还可以,但是现实生活中,往往有非常多的特征,每一个特征的取值也是非常之多,那么通过统计来估计后面概率的值,变得几乎不可做,这也是为什么需要假设特征之间独立的原因。

     

    2、假如我们没有假设特征之间相互独立,那么我们统计的时候,就需要在整个特征空间中去找,比如统计p(不帅、性格不好、身高矮、不上进|嫁),

     

    我们就需要在嫁的条件下,去找四种特征全满足分别是不帅,性格不好,身高矮,不上进的人的个数,这样的话,由于数据的稀疏性,很容易统计到0的情况。 这样是不合适的。

     

    根据上面俩个原因,朴素贝叶斯法对条件概率分布做了条件独立性的假设,由于这是一个较强的假设,朴素贝叶斯也由此得名!这一假设使得朴素贝叶斯法变得简单,但有时会牺牲一定的分类准确率。

     

    好的,上面我解释了为什么可以拆成分开连乘形式。那么下面我们就开始求解!

     

    我们将上面公式整理一下如下:

     

     

    下面我将一个一个的进行统计计算(在数据量很大的时候,根据中心极限定理,频率是等于概率的,这里只是一个例子,所以我就进行统计即可)。

     

    p(嫁)=?

    首先我们整理训练数据中,嫁的样本数如下:

     

    则 p(嫁) = 6/12(总样本数) = 1/2

     

    p(不帅|嫁)=?统计满足样本数如下:

     

    则p(不帅|嫁) = 3/6 = 1/2 在嫁的条件下,看不帅有多少

     

    p(性格不好|嫁)= ?统计满足样本数如下:

     

    则p(性格不好|嫁)= 1/6

     

    p(矮|嫁) = ?统计满足样本数如下:

     

    则p(矮|嫁) = 1/6

     

    p(不上进|嫁) = ?统计满足样本数如下:

     

    则p(不上进|嫁) = 1/6

     

    下面开始求分母,p(不帅),p(性格不好),p(矮),p(不上进)

    统计样本如下:

     

     

    不帅统计如上红色所示,占4个,那么p(不帅) = 4/12 = 1/3

     

     

    性格不好统计如上红色所示,占4个,那么p(性格不好) = 4/12 = 1/3

     

     

    身高矮统计如上红色所示,占7个,那么p(身高矮) = 7/12

     

     

    不上进统计如上红色所示,占4个,那么p(不上进) = 4/12 = 1/3

     

    到这里,要求p(不帅、性格不好、身高矮、不上进|嫁)的所需项全部求出来了,下面我带入进去即可,

     

    = (1/2*1/6*1/6*1/6*1/2)/(1/3*1/3*7/12*1/3)

     

    下面我们根据同样的方法来求p(不嫁|不帅,性格不好,身高矮,不上进),完全一样的做法,为了方便理解,我这里也走一遍帮助理解。首先公式如下:

     

     

    下面我也一个一个来进行统计计算,这里与上面公式中,分母是一样的,于是我们分母不需要重新统计计算!

     

    p(不嫁)=?根据统计计算如下(红色为满足条件):

     

     

    则p(不嫁)=6/12 = 1/2

     

    p(不帅|不嫁) = ?统计满足条件的样本如下(红色为满足条件):

     

     

    则p(不帅|不嫁) = 1/6

     

    p(性格不好|不嫁) = ?据统计计算如下(红色为满足条件):


    则p(性格不好|不嫁) =3/6 = 1/2

     

    p(矮|不嫁) = ?据统计计算如下(红色为满足条件):

     

    则p(矮|不嫁) = 6/6 = 1

     

    p(不上进|不嫁) = ?据统计计算如下(红色为满足条件):

    则p(不上进|不嫁) = 3/6 = 1/2

     

    那么根据公式:

     

    p (不嫁|不帅、性格不好、身高矮、不上进) = ((1/6*1/2*1*1/2)*1/2)/(1/3*1/3*7/12*1/3)

    很显然(1/6*1/2*1*1/2) > (1/2*1/6*1/6*1/6*1/2)

     

    于是有p (不嫁|不帅、性格不好、身高矮、不上进)>p (嫁|不帅、性格不好、身高矮、不上进)

     

    所以我们根据朴素贝叶斯算法可以给这个女生答案,是不嫁!!!!

     

    5  朴素贝叶斯分类的优缺点

    优点:

    (1) 算法逻辑简单,易于实现(算法思路很简单,只要使用贝叶斯公式转化医学即可!

    (2)分类过程中时空开销小(假设特征相互独立,只会涉及到二维存储

     

    缺点:

     

    理论上,朴素贝叶斯模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此,这是因为朴素贝叶斯模型假设属性之间相互独立,这个假设在实际应用中往往是不成立的,在属性个数比较多或者属性之间相关性较大时,分类效果不好。

     

    而在属性相关性较小时,朴素贝叶斯性能最为良好。对于这一点,有半朴素贝叶斯之类的算法通过考虑部分关联性适度改进。

     

    整个例子详细的讲解了朴素贝叶斯算法的分类过程,希望对大家的理解有帮助~

     

    参考:李航博士《统计学习方法》

    算法杂货铺--分类算法之朴素贝叶斯分类(Naive Bayesian classification)

     

    致谢:德川,皓宇,继豪,施琦


    原文地址:https://mp.weixin.qq.com/s?__biz=MzI4MDYzNzg4Mw==&mid=2247483819&idx=1&sn=7f1859c0a00248a4c658fa65f846f341&chksm=ebb4397fdcc3b06933816770b928355eb9119c4c80a1148b92a42dc3c08de5098fd6f278e61e#rd

    展开全文
  • 数据挖掘算法——常用分类算法总结

    万次阅读 多人点赞 2019-06-17 10:55:22
    常用分类算法总结分类算法总结NBC算法LR算法SVM算法ID3算法C4.5 算法C5.0算法KNN 算法ANN 算法 分类算法总结 分类是在一群已经知道类别标号的样本中,训练一种分类器,让其能够对某种未知的样本进行分类。分类算法...

    分类算法

    分类是在一群已经知道类别标号的样本中,训练一种分类器,让其能够对某种未知的样本进行分类。分类算法属于一种有监督的学习。分类算法的分类过程就是建立一种分类模型来描述预定的数据集或概念集,通过分析由属性描述的数据库元组来构造模型。分类的目的就是使用分类对新的数据集进行划分,其主要涉及分类规则的准确性、过拟合、矛盾划分的取舍等。分类算法分类效果如图所示。

    常用的分类算法包括:NBC(Naive Bayesian Classifier,朴素贝叶斯分类)算法、LR(Logistic Regress,逻辑回归)算法、ID3(Iterative Dichotomiser 3 迭代二叉树3 代)决策树算法、C4.5 决策树算法、C5.0 决策树算法、SVM(Support Vector Machine,支持向量机)算法、KNN(K-Nearest Neighbor,K 最近邻近)算法、ANN(Artificial Neural Network,人工神经网络)算法等。

    NBC算法

    NBC 模型发源于古典数学理论,有着坚实的数学基础。该算法是基于条件独立性假设的一种算法,当条件独立性假设成立时,利用贝叶斯公式计算出其后验概率,即该对象属于某一类的概率,选择具有最大后验概率的类作为该对象所属的类。
    NBC算法的优点

    1. NBC算法逻辑简单,易于实现;
    2. NBC算法所需估计的参数很少;
    3. NBC 算法对缺失数据不太敏感;
    4. NBC 算法具有较小的误差分类率;
    5. NBC 算法性能稳定,健壮性比较好;

    NBC算法的缺点
    1.在属性个数比较多或者属性之间相关性较大时,NBC 模型的分类效果相对较差;
    2.算法是基于条件独立性假设的,在实际应用中很难成立,故会影响分类效果

    LR算法

    LR 回归是当前业界比较常用的机器学习方法,用于估计某种事物的可能性。它与多元线性回归同属一个家族,即广义线性模型。简单来说多元线性回归是直接将特征值和其对应的概率进行相乘得到一个结果,逻辑回归则是在这样的结果上加上一个逻辑函数。在此选择LR 作为回归分析模型的代表进行介绍。
    LR算法的优点
    1.对数据中小噪声的鲁棒性好;
    2.LR 算法已被广泛应用于工业问题中;
    3.多重共线性并不是问题,它可结合正则化来解决。

    LR算法的缺点
    1.对于非线性特征,需要转换
    2.当特征空间很大时,LR的性能并不是太好

    SVM算法

    SVM 算法是建立在统计学习理论基础上的机器学习方法,为十大数据挖掘算法之一。通过学习算法,SVM 可以自动寻找出对分类有较好区分能力的支持向量,由此构造出的分类器可以最大化类与类的间隔,因而有较好的适应能力和较高的分准率。SVM 算法的目的在于寻找一个超平面H,该超平面可以将训练集中的数据分开,且与类域边界的沿垂直于该超平面方向的距离最大,故SVM 法亦被称为最大边缘算法。

    SVM算法的优点
    1.SVM 模型有很高的分准率;
    2. SVM 模型有很高的泛化性能;
    3. SVM 模型能很好地解决高维问题;
    4. SVM 模型对小样本情况下的机器学习问题效果好。

    SVM算法的缺点
    1.SVM 模型对缺失数据敏感;
    2.对非线性问题没有通用解决方案,得谨慎选择核函数来处理。

    ID3算法

    ID3 算法是一种基于决策树的分类算法,该算法是以信息论为基础,以信息熵和信息增益为衡量标准,从而实现对数据的归纳分类。信息增益用于度量某个属性对样本集合分类的好坏程度。ID3 算法的时间复杂度为O(n*|D|*log|D|)。

    ID3算法的优点

    1. ID3 算法建立的决策树规模比较小;
    2. 查询速度快。

    ID3算法的缺点
    1.不适合处理连续数据;
    2.难以处理海量数据集;
    3.建树时偏选属性值较大的进行分离,而有时属性值较大的不一定能反应更多的数据信息。

    C4.5 算法

    C4.5 算法是ID3 算法的修订版,采用信息增益率来加以改进,选取有最大增益率的分割变量作为准则,避免ID3 算法过度的适配问题。

    C4.5算法优点
    1.C4.5 继承了ID3 优点;
    2.在树构造过程中进行剪枝;
    3.能对不完整数据进行处理;
    4.能够完成对连续属性的离散化处理;
    5.产生的分类规则易于理解,准确率较高;
    6.用增益率来选择属性,克服了用增益选择属性时偏向选择取值多的属性。

    C4.5 算法缺点
    1.构造树时,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效;
    2.只适合于能驻留于内存的数据集,当训练集达到内存无法容纳时程序无法运行。

    C4.5 用于遥感分类过程中,首先依据通常的方式建立第一个模型。随后建立的第二个模型聚焦于被第一个模型错误分类的记录。以此类推,最后应用整个模型集对样本进行分类,使用加权投票过程把分散的预测合并成综合预测。Boosting 技术对于噪声不大的数据,通常通过建立的多模型来减少错误分类的影响,提高分类精度。

    C5.0算法

    C5.0 算法是 Quinlan 在C4.5 算法的基础上改进而来的产生决策树的一种更新的算法,它除了包括C4.5 的全部功能外,还引入许多新的技术,其中最重要的技术是提升(Boosting)技术,目的是为了进一步提高决策树对样本的识别率。同时C5.0 的算法复杂度要更低,使用更简单,适应性更强,因此具有更高的使用价值。

    C5.0算法的优点
    1.C5.0 模型能同时处理连续和离散的数据
    2.C5.0 模型估计
    模型通常不需要很长的训练时间;
    3.C5.0 引入Boosting 技术以提高分类的效率和精度;
    4.C5.0 模型易于理解,模型推出的规则有非常直观的解释;
    5.C5.0 模型在面对数据遗漏和特征很多的问题时非常稳健。

    C5.0算法的缺点
    目标字段必须为分类字段。

    美国地质调查局(USGS)在进行土地覆盖分类项目过程中研发了支持决策树分类的软件。软件分类模块主要是针对庞大数据量的数据集进行数据挖掘,找出特征,然后建立规则集进行决策分类。在分类模块中采用C5.0 模型来完成决策树分类、形成分类文件,实现遥感影像的分类。

    KNN 算法

    KNN 算法是Cover 和Hart 于1968 年提出的理论上比较成熟的方法,为十大挖掘算法之一。该算法的思路非常简单直观:如果一个样本在特征空间中的k 个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

    KNN算法的优点
    1.KNN 算法简单、有效;
    2.KNN 算法适用于样本容量比较大的类域的自动分类;
    3.由于KNN 方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN 方法较其他方法更为适合。

    KNN算法的缺点
    1.KNN 算法计算量较大;
    2.KNN 算法需要事先确定K 值;
    3.KNN 算法输出的可解释不强;
    4. KNN 算法对样本容量较小的类域很容易产生误分。

    ANN 算法

    人工神经网络(ANN)算法就是一组连续的输入/输出单元,其中每个连接都与一个权相关。在学习阶段,通过调整神经网络的权,使得能够预测样本的正确类标号来学习。

    ANN算法的优点
    1.能处理数值型及分类型的属性;
    2.分类的准确度高,分布并行处理能力强;
    3.对包含大量噪声数据的数据集有较强的鲁棒性和容错能力。

    ANN算法的缺点
    1.不能观察之间的学习过程;
    2.学习时间过长,甚至可能达不到学习的目的;
    3.对于非数值型数据需要做大量数据预处理工作;
    4.输出结果难以解释,会影响到结果的可信度和可接受程度;
    5.神经网络需要大量的参数,如网络拓扑结构、权值和阈值的初始值。

    小结:

    算法名称 收敛时间 是否过度拟合 是否过渡拟合缺失数据敏感度 训练数据量
    NBC 存在 不敏感 无要求
    LR 存在 敏感 无要求
    SVM 一般 存在 敏感 小数据量
    ID3 存在 不敏感 小数据集
    C4.5 存在 不敏感 小数据集
    C5.0 不存在 不敏感 大数据集
    ANN 存在 敏感 大数据集
    KNN 存在 敏感 数据量多

    创建了一个技术闲聊群:有兴趣可加我微信,拉你一起讨论杂七杂八的技术,虽然大家都不怎么活跃!
    加好友备注:你的博客名 && 随便给我的任意文章点个赞或留言
    在这里插入图片描述

    展开全文
  • 从决策树学习谈到贝叶斯分类算法、EM、HMM

    万次阅读 多人点赞 2012-05-17 21:06:53
    第一篇:从决策树学习谈到贝叶斯分类算法、EM、HMM (Machine Learning & Data Mining交流群:8986884)引言 最近在面试中,除了基础 & 算法 & 项目之外,经常被问到或被要求介绍和描述下自己所知道...

            从决策树学习谈到贝叶斯分类算法、EM、HMM




    引言

        最近在面试中,除了基础 &  算法 & 项目之外,经常被问到或被要求介绍和描述下自己所知道的几种分类或聚类算法(当然,这完全不代表你将来的面试中会遇到此类问题,只是因为我的简历上写了句:熟悉常见的聚类 & 分类算法而已),而我向来恨对一个东西只知其皮毛而不得深入,故写一个有关数据挖掘十大算法的系列文章以作为自己备试之用,甚至以备将来常常回顾思考。行文杂乱,但侥幸若能对读者起到一点帮助,则幸甚至哉。

        本文借鉴和参考了两本书,一本是Tom M.Mitchhell所著的机器学习,一本是数据挖掘导论,这两本书皆分别是机器学习 & 数据挖掘领域的开山 or 杠鼎之作,读者有继续深入下去的兴趣的话,不妨在阅读本文之后,课后细细研读这两本书。除此之外,还参考了网上不少牛人的作品(文末已注明参考文献或链接),在此,皆一一表示感谢(从本质上来讲,本文更像是一篇读书 & 备忘笔记)。

        说白了,一年多以前,我在本blog内写过一篇文章,叫做:数据挖掘领域十大经典算法初探(题外话:最初有个出版社的朋友便是因此文找到的我,尽管现在看来,我离出书日期仍是遥遥无期)。现在,我抽取其中几个最值得一写的几个算法每一个都写一遍,以期对其有个大致通透的了解。

        OK,暂称本系列为Top 10 Algorithms in Data Mining,若全系列任何一篇文章若有任何错误,漏洞,或不妥之处,还请读者们一定要随时不吝赐教 & 指正,谢谢各位。


    分类与聚类,监督学习与无监督学习

        在讲具体的分类和聚类算法之前,有必要讲一下什么是分类,什么是聚类,以及都包含哪些具体算法或问题。

    • Classification (分类),对于一个 classifier ,通常需要你告诉它“这个东西被分为某某类”这样一些例子,理想情况下,一个 classifier 会从它得到的训练集中进行“学习”,从而具备对未知数据进行分类的能力,这种提供训练数据的过程通常叫做 supervised learning (监督学习),
    • 而Clustering(聚类),简单地说就是把相似的东西分到一组,聚类的时候,我们并不关心某一类是什么,我们需要实现的目标只是把相似的东西聚到一起,因此,一个聚类算法通常只需要知道如何计算相似 度就可以开始工作了,因此 clustering 通常并不需要使用训练数据进行学习,这在 Machine Learning 中被称作 unsupervised learning (无监督学习).

      常见的分类与聚类算法

        所谓分类分类,简单来说,就是根据文本的特征或属性,划分到已有的类别中。如在自然语言处理NLP中,我们经常提到的文本分类便就是一个分类问题,一般的模式分类方法都可用于文本分类研究。常用的分类算法包括:决策树分类法,朴素的贝叶斯分类算法(native Bayesian classifier)、基于支持向量机(SVM)的分类器,神经网络法,k-最近邻法(k-nearest neighbor,kNN),模糊分类法等等(所有这些分类算法日后在本blog内都会一一陆续阐述)。

        分类作为一种监督学习方法,要求必须事先明确知道各个类别的信息,并且断言所有待分类项都有一个类别与之对应。但是很多时候上述条件得不到满足,尤其是在处理海量数据的时候,如果通过预处理使得数据满足分类算法的要求,则代价非常大,这时候可以考虑使用聚类算法。

        而K均值(K-means clustering)聚类则是最典型的聚类算法(当然,除此之外,还有很多诸如属于划分法K-MEDOIDS算法、CLARANS算法;属于层次法的BIRCH算法、CURE算法、CHAMELEON算法等;基于密度的方法:DBSCAN算法、OPTICS算法、DENCLUE算法等;基于网格的方法:STING算法、CLIQUE算法、WAVE-CLUSTER算法;基于模型的方法,本系列后续会介绍其中几种)。

      监督学习与无监督学习

        机器学习发展到现在,一般划分为 监督学习(supervised learning),半监督学习(semi-supervised learning)以及无监督学习(unsupervised learning)三类。举个具体的对应例子,则是比如说,在NLP词义消岐中,也分为监督的消岐方法,和无监督的消岐方法。在有监督的消岐方法中,训练数据是已知的,即每个词的语义分类是被标注了的;而在无监督的消岐方法中,训练数据是未经标注的

        上面所介绍的常见的分类算法属于监督学习,聚类则属于无监督学习(反过来说,监督学习属于分类算法则不准确,因为监督学习只是说我们给样本sample同时打上了标签(label),然后同时利用样本和标签进行相应的学习任务,而不是仅仅局限于分类任务。常见的其他监督问题,比如相似性学习,特征学习等等也是监督的,但是不是分类)。

        再举个例子,正如人们通过已知病例学习诊断技术那样,计算机要通过学习才能具有识别各种事物和现象的能力。用来进行学习的材料就是与被识别对象属于同类的有限数量样本。监督学习中在给予计算机学习样本的同时,还告诉计算各个样本所属的类别。若所给的学习样本不带有类别信息,就是无监督学习(浅显点说:同样是学习训练,监督学习中,给的样例比如是已经标注了如心脏病的,肝炎的;而无监督学习中,就是给你一大堆的样例,没有标明是何种病例的)。

        而在支持向量机导论一书给监督学习下的定义是:当样例是输入/输出对给出时,称为监督学习,有关输入/输出函数关系的样例称为训练数据。而在无监督学习中,其数据不包含输出值,学习的任务是理解数据产生的过程。


    第一部分、决策树学习

    1.1、什么是决策树

        咱们直接切入正题。所谓决策树,顾名思义,是一种树,一种依托于策略抉择而建立起来的树。

        机器学习中,决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出,若欲有复数输出,可以建立独立的决策树以处理不同输出。
        从数据产生决策树的机器学习技术叫做决策树学习, 通俗点说就是决策树,说白了,这是一种依托于分类、训练上的预测树,根据已知预测、归类未来。

        来理论的太过抽象,下面举两个浅显易懂的例子:

    第一个例子

        套用俗语,决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友,于是有了下面的对话:

          女儿:多大年纪了?
          母亲:26。
          女儿:长的帅不帅?
          母亲:挺帅的。
          女儿:收入高不?
          母亲:不算很高,中等情况。
          女儿:是公务员不?
          母亲:是,在税务局上班呢。
          女儿:那好,我去见见。

          这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别:见和不见。假设这个女孩对男人的要求是:30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员,那么这个可以用下图表示女孩的决策逻辑:

        也就是说,决策树的简单策略就是,好比公司招聘面试过程中筛选一个人的简历,如果你的条件相当好比如说某985/211重点大学博士毕业,那么二话不说,直接叫过来面试,如果非重点大学毕业,但实际项目经验丰富,那么也要考虑叫过来面试一下,即所谓具体情况具体分析、决策。但每一个未知的选项都是可以归类到已有的分类类别中的。

    第二个例子

        此例子来自Tom M.Mitchell著的机器学习一书:

        小王的目的是通过下周天气预报寻找什么时候人们会打高尔夫,他了解到人们决定是否打球的原因最主要取决于天气情况。而天气状况有晴,云和雨;气温用华氏温度表示;相对湿度用百分比;还有有无风。如此,我们便可以构造一棵决策树,如下(根据天气这个分类决策这天是否合适打网球):

        上述决策树对应于以下表达式:

    (Outlook=Sunny ^Humidity<=70)V (Outlook = Overcast)V (Outlook=Rain ^ Wind=Weak)

    1.2、ID3算法

    1.2.1、决策树学习之ID3算法

        ID3算法是决策树算法的一种。想了解什么是ID3算法之前,我们得先明白一个概念:奥卡姆剃刀。

    • 奥卡姆剃刀(Occam's Razor, Ockham's Razor),又称“奥坎的剃刀”,是由14世纪逻辑学家、圣方济各会修士奥卡姆的威廉(William of Occam,约1285年至1349年)提出,他在《箴言书注》2卷15题说“切勿浪费较多东西,去做‘用较少的东西,同样可以做好的事情’。简单点说,便是:be simple

         ID3算法(Iterative Dichotomiser 3 迭代二叉树3代)是一个由Ross Quinlan发明的用于决策树的算法。这个算法便是建立在上述所介绍的奥卡姆剃刀的基础上:越是小型的决策树越优于大的决策树(be simple简单理论)。尽管如此,该算法也不是总是生成最小的树形结构,而是一个启发式算法。

        OK,从信息论知识中我们知道,期望信息越小,信息增益越大,从而纯度越高。ID3算法的核心思想就是以信息增益度量属性选择,选择分裂后信息增益(很快,由下文你就会知道信息增益又是怎么一回事)最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。

         所以,ID3的思想便是:

    1. 自顶向下的贪婪搜索遍历可能的决策树空间构造决策树(此方法是ID3算法和C4.5算法的基础);
    2. 从“哪一个属性将在树的根节点被测试”开始;
    3. 使用统计测试来确定每一个实例属性单独分类训练样例的能力,分类能力最好的属性作为树的根结点测试(如何定义或者评判一个属性是分类能力最好的呢?这便是下文将要介绍的信息增益,or 信息增益率)。
    4. 然后为根结点属性的每个可能值产生一个分支,并把训练样例排列到适当的分支(也就是说,样例的该属性值对应的分支)之下。
    5. 重复这个过程,用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。

    这形成了对合格决策树的贪婪搜索,也就是算法从不回溯重新考虑以前的选择。

        下图所示即是用于学习布尔函数的ID3算法概要:


    1.2.2、哪个属性是最佳的分类属性

    1、信息增益的度量标准:
        上文中,我们提到:“ID3算法的核心思想就是以信息增益度量属性选择,选择分裂后信息增益(很快,由下文你就会知道信息增益又是怎么一回事)最大的属性进行分裂。”接下来,咱们就来看看这个信息增益是个什么概念(当然,在了解信息增益之前,你必须先理解:信息增益的度量标准:熵)。
        上述的ID3算法的核心问题是选取在树的每个结点要测试的属性。我们希望选择的是最有利于分类实例的属性,信息增益(Information Gain)是用来衡量给定的属性区分训练样例的能力,而ID3算法在增长树的每一步使用信息增益从候选属性中选择属性。

        为了精确地定义信息增益,我们先定义信息论中广泛使用的一个度量标准,称为entropy),它刻画了任意样例集的纯度(purity)。给定包含关于某个目标概念的正反样例的样例集S,那么S相对这个布尔型分类的熵为:

        上述公式中,p+代表正样例,比如在本文开头第二个例子中p+则意味着去打羽毛球,而p-则代表反样例,不去打球(在有关熵的所有计算中我们定义0log0为0)。

        如果写代码实现熵的计算,则如下所示:

    //根据具体属性和值来计算熵  
    double ComputeEntropy(vector <vector <string> > remain_state, string attribute, string value,bool ifparent){  
        vector<int> count (2,0);  
        unsigned int i,j;  
        bool done_flag = false;//哨兵值  
        for(j = 1; j < MAXLEN; j++){  
            if(done_flag) break;  
            if(!attribute_row[j].compare(attribute)){  
                for(i = 1; i < remain_state.size(); i++){  
                    if((!ifparent&&!remain_state[i][j].compare(value)) || ifparent){//ifparent记录是否算父节点  
                        if(!remain_state[i][MAXLEN - 1].compare(yes)){  
                            count[0]++;  
                        }  
                        else count[1]++;  
                    }  
                }  
                done_flag = true;  
            }  
        }  
        if(count[0] == 0 || count[1] == 0 ) return 0;//全部是正实例或者负实例  
        //具体计算熵 根据[+count[0],-count[1]],log2为底通过换底公式换成自然数底数  
        double sum = count[0] + count[1];  
        double entropy = -count[0]/sum*log(count[0]/sum)/log(2.0) - count[1]/sum*log(count[1]/sum)/log(2.0);  
        return entropy;  
    }  

        举例来说,假设S是一个关于布尔概念的有14个样例的集合,它包括9个正例和5个反例(我们采用记号[9+,5-]来概括这样的数据样例),那么S相对于这个布尔样例的熵为:

    Entropy([9+,5-])=-(9/14)log2(9/14)-(5/14)log2(5/14)=0.940。

        So,根据上述这个公式,我们可以得到:S的所有成员属于同一类,Entropy(S)=0; S的正反样例数量相等,Entropy(S)=1;S的正反样例数量不等,熵介于0,1之间,如下图所示:


        信息论中对熵的一种解释,熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数。更一般地,如果目标属性具有c个不同的值,那么S相对于c个状态的分类的熵定义为:

         Pi为子集合中不同性(而二元分类即正样例和负样例)的样例的比例。

    2、信息增益度量期望的熵降低

    信息增益Gain(S,A)定义

        已经有了熵作为衡量训练样例集合纯度的标准,现在可以定义属性分类训练数据的效力的度量标准。这个标准被称为“信息增益(information gain)”。简单的说,一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低(或者说,样本按照某属性划分时造成熵减少的期望)。更精确地讲,一个属性A相对样例集合S的信息增益Gain(S,A)被定义为:

        其中 Values(A)是属性A所有可能值的集合,是S中属性A的值为v的子集。换句话来讲,Gain(S,A)是由于给定属性A的值而得到的关于目标函数值的信息。当对S的一个任意成员的目标值编码时,Gain(S,A)的值是在知道属性A的值后可以节省的二进制位数。

        接下来,有必要提醒读者一下:关于下面这两个概念 or 公式,



        第一个Entropy(S)是熵定义,第二个则是信息增益Gain(S,A)的定义,而Gain(S,A)由第一个Entropy(S)计算出,记住了。

        下面,举个例子,假定S是一套有关天气的训练样例,描述它的属性包括可能是具有Weak和Strong两个值的Wind。像前面一样,假定S包含14个样例,[9+5-]。在这14个样例中,假定正例中的6个和反例中的2个有Wind =Weak其他的有Wind=Strong。由于按照属性Wind分类14个样例得到的信息增益可以计算如下。


        运用在本文开头举得第二个根据天气情况是否决定打羽毛球的例子上,得到的最佳分类属性如下图所示:


         在上图中,计算了两个不同属性:湿度(humidity)和风力(wind)的信息增益,最终humidity这种分类的信息增益0.151>wind增益的0.048。说白了,就是在星期六上午是否适合打网球的问题诀策中,采取humidity较wind作为分类属性更佳,决策树由此而来。

    //计算信息增益,DFS构建决策树  
    //current_node为当前的节点  
    //remain_state为剩余待分类的样例  
    //remian_attribute为剩余还没有考虑的属性  
    //返回根结点指针  
    Node * BulidDecisionTreeDFS(Node * p, vector <vector <string> > remain_state, vector <string> remain_attribute){  
        //if(remain_state.size() > 0){  
            //printv(remain_state);  
        //}  
        if (p == NULL)  
            p = new Node();  
        //先看搜索到树叶的情况  
        if (AllTheSameLabel(remain_state, yes)){  
            p->attribute = yes;  
            return p;  
        }  
        if (AllTheSameLabel(remain_state, no)){  
            p->attribute = no;  
            return p;  
        }  
        if(remain_attribute.size() == 0){//所有的属性均已经考虑完了,还没有分尽  
            string label = MostCommonLabel(remain_state);  
            p->attribute = label;  
            return p;  
        }  
      
        double max_gain = 0, temp_gain;  
        vector <string>::iterator max_it;  
        vector <string>::iterator it1;  
        for(it1 = remain_attribute.begin(); it1 < remain_attribute.end(); it1++){  
            temp_gain = ComputeGain(remain_state, (*it1));  
            if(temp_gain > max_gain) {  
                max_gain = temp_gain;  
                max_it = it1;  
            }  
        }  
        //下面根据max_it指向的属性来划分当前样例,更新样例集和属性集  
        vector <string> new_attribute;  
        vector <vector <string> > new_state;  
        for(vector <string>::iterator it2 = remain_attribute.begin(); it2 < remain_attribute.end(); it2++){  
            if((*it2).compare(*max_it)) new_attribute.push_back(*it2);  
        }  
        //确定了最佳划分属性,注意保存  
        p->attribute = *max_it;  
        vector <string> values = map_attribute_values[*max_it];  
        int attribue_num = FindAttriNumByName(*max_it);  
        new_state.push_back(attribute_row);  
        for(vector <string>::iterator it3 = values.begin(); it3 < values.end(); it3++){  
            for(unsigned int i = 1; i < remain_state.size(); i++){  
                if(!remain_state[i][attribue_num].compare(*it3)){  
                    new_state.push_back(remain_state[i]);  
                }  
            }  
            Node * new_node = new Node();  
            new_node->arrived_value = *it3;  
            if(new_state.size() == 0){//表示当前没有这个分支的样例,当前的new_node为叶子节点  
                new_node->attribute = MostCommonLabel(remain_state);  
            }  
            else   
                BulidDecisionTreeDFS(new_node, new_state, new_attribute);  
            //递归函数返回时即回溯时需要1 将新结点加入父节点孩子容器 2清除new_state容器  
            p->childs.push_back(new_node);  
            new_state.erase(new_state.begin()+1,new_state.end());//注意先清空new_state中的前一个取值的样例,准备遍历下一个取值样例  
        }  
        return p;  
    }  

    1.2.3、ID3算法决策树的形成

        OK,下图为ID3算法第一步后形成的部分决策树。这样综合起来看,就容易理解多了。1、overcast样例必为正,所以为叶子结点,总为yes;2、ID3无回溯,局部最优,而非全局最优,还有另一种树后修剪决策树。下图是ID3算法第一步后形成的部分决策树:

        如上图,训练样例被排列到对应的分支结点。分支Overcast的所有样例都是正例,所以成为目标分类为Yes的叶结点。另两个结点将被进一步展开,方法是按照新的样例子集选取信息增益最高的属性。

    1.3、C4.5算法

    1.3.1、ID3算法的改进:C4.5算法

        C4.5,是机器学习算法中的另一个分类决策树算法,它是决策树(决策树也就是做决策的节点间的组织方式像一棵树,其实是一个倒树)核心算法,也是上文1.2节所介绍的ID3的改进算法,所以基本上了解了一半决策树构造方法就能构造它。

        决策树构造方法其实就是每次选择一个好的特征以及分裂点作为当前节点的分类条件。

        既然说C4.5算法是ID3的改进算法,那么C4.5相比于ID3改进的地方有哪些呢?:

    1. 用信息增益率来选择属性。ID3选择属性用的是子树的信息增益,这里可以用很多方法来定义信息,ID3使用的是熵(entropy,熵是一种不纯度度量准则),也就是熵的变化值,而C4.5用的是信息增益率。对,区别就在于一个是信息增益,一个是信息增益率。
    2. 在树构造过程中进行剪枝,在构造决策树的时候,那些挂着几个元素的节点,不考虑最好,不然容易导致overfitting。
    3. 对非离散数据也能处理。
    4. 能够对不完整数据进行处理

        针对上述第一点,解释下:一般来说率就是用来取平衡用的,就像方差起的作用差不多,比如有两个跑步的人,一个起点是10m/s的人、其10s后为20m/s;另一个人起速是1m/s、其1s后为2m/s。如果紧紧算差值那么两个差距就很大了,如果使用速度增加率(加速度,即都是为1m/s^2)来衡量,2个人就是一样的加速度。因此,C4.5克服了ID3用信息增益选择属性时偏向选择取值多的属性的不足。

    C4.5算法之信息增益率

        OK,既然上文中提到C4.5用的是信息增益率,那增益率的具体是如何定义的呢?:

        是的,在这里,C4.5算法不再是通过信息增益来选择决策属性。一个可以选择的度量标准是增益比率gain ratioQuinlan 1986)。增益比率度量是用前面的增益度量Gain(S,A)和分裂信息度量SplitInformation(S,A)来共同定义的,如下所示:

        其中,分裂信息度量被定义为(分裂信息用来衡量属性分裂数据的广度和均匀):

       

        其中S1到Sc是c个值的属性A分割S而形成的c个样例子集。注意分裂信息实际上就是S关于属性A的各值的熵。这与我们前面对熵的使用不同,在那里我们只考虑S关于学习到的树要预测的目标属性的值的熵。

        请注意,分裂信息项阻碍选择值为均匀分布的属性。例如,考虑一个含有n个样例的集合被属性A彻底分割(译注:分成n组,即一个样例一组)。这时分裂信息的值为log2n。相反,一个布尔属性B分割同样的n个实例,如果恰好平分两半,那么分裂信息是1。如果属性A和B产生同样的信息增益,那么根据增益比率度量,明显B会得分更高。

        使用增益比率代替增益来选择属性产生的一个实际问题是,当某个Si接近S(|Si|»|S|)时分母可能为0或非常小。如果某个属性对于S的所有样例有几乎同样的值,这时要么导致增益比率未定义,要么是增益比率非常大。为了避免选择这种属性,我们可以采用这样一些启发式规则,比如先计算每个属性的增益,然后仅对那些增益高过平均值的属性应用增益比率测试(Quinlan 1986)。

        除了信息增益,Lopez de Mantaras1991)介绍了另一种直接针对上述问题而设计的度量,它是基于距离的(distance-based)。这个度量标准基于所定义的一个数据划分间的距离尺度。具体更多请参看:Tom M.Mitchhell所著的机器学习之3.7.3节。

    1.3.2、C4.5算法构造决策树的过程

    Function C4.5(R:包含连续属性的无类别属性集合,C:类别属性,S:训练集)
    /*返回一棵决策树*/
    Begin
       If S为空,返回一个值为Failure的单个节点;
       If S是由相同类别属性值的记录组成,
          返回一个带有该值的单个节点;
       If R为空,则返回一个单节点,其值为在S的记录中找出的频率最高的类别属性值;
       [注意未出现错误则意味着是不适合分类的记录];
      For 所有的属性R(Ri) Do
            If 属性Ri为连续属性,则
         Begin
               将Ri的最小值赋给A1:
            将Rm的最大值赋给Am;/*m值手工设置*/
               For j From 2 To m-1 Do Aj=A1+j*(A1Am)/m;
               将Ri点的基于{< =Aj,>Aj}的最大信息增益属性(Ri,S)赋给A;
         End;
      将R中属性之间具有最大信息增益的属性(D,S)赋给D;
       将属性D的值赋给{dj/j=1,2...m};
      将分别由对应于D的值为dj的记录组成的S的子集赋给{sj/j=1,2...m};
       返回一棵树,其根标记为D;树枝标记为d1,d2...dm;
       再分别构造以下树:
       C4.5(R-{D},C,S1),C4.5(R-{D},C,S2)...C4.5(R-{D},C,Sm);
    End C4.5

    1.3.3、C4.5算法实现中的几个关键步骤

        在上文中,我们已经知道了决策树学习C4.5算法中4个重要概念的表达,如下:

        接下来,咱们写下代码实现,
        1、信息
    double C4_5::entropy(int *attrClassCount, int classNum, int allNum){
    	double iEntropy = 0.0;
    	for(int i = 0; i < classNum; i++){
    		double temp = ((double)attrClassCount[i]) / allNum;
    		if(temp != 0.0)
    			iEntropy -= temp * (log(temp) / log(2.0));
    	}
    	return iEntropy;
    }
        2、信息增益率
    double C4_5::gainRatio(int classNum, vector<int *> attriCount, double pEntropy){
    	int* attriNum = new int[attriCount.size()];
    	int allNum = 0;
    
    	for(int i = 0; i < (int)attriCount.size(); i++){
    		attriNum[i] = 0;
    		for(int j = 0; j < classNum; j++){
    			attriNum[i] += attriCount[i][j];
    			allNum += attriCount[i][j];
    		}
    	}
    	double gain = 0.0;
    	double splitInfo = 0.0;
    	for(int i = 0; i < (int)attriCount.size(); i++){
    		gain -= ((double)attriNum[i]) / allNum * entropy(attriCount[i], classNum, attriNum[i]);
    		splitInfo -= ((double)attriNum[i]) / allNum * (log(((double)attriNum[i])/allNum) / log(2.0));
    	}
    	gain += pEntropy;
    	delete[] attriNum; 
    	return (gain / splitInfo);
    }
        3、选取最大增益属性作为分类条件
    int C4_5::chooseAttribute(vector<int> attrIndex, vector<int *>* sampleCount){
    	int bestIndex = 0;
    	double maxGainRatio = 0.0;
    	int classNum = (int)(decisions[attrIndex[(int)attrIndex.size()-1]]).size();//number of class
    
    	//computer the class entropy
    	int* temp = new int[classNum];
    	int allNum = 0;
    	for(int i = 0; i < classNum; i++){
    		temp[i] = sampleCount[(int)attrIndex.size()-1][i][i];
    		allNum += temp[i];
    	}
    	double pEntropy = entropy(temp, classNum, allNum);
    	delete[] temp;
    
    	//computer gain ratio for every attribute
    	for(int i = 0; i < (int)attrIndex.size()-1; i++){
    		double gainR = gainRatio(classNum, sampleCount[i], pEntropy);
    		if(gainR > maxGainRatio){
    			bestIndex = i;
    			maxGainRatio = gainR;
    		}
    	}
    	return bestIndex;
    }
        4、还有一系列建树,打印树的步骤,此处略过。

    1.4、读者点评

    1. form Wind:决策树使用于特征取值离散的情况,连续的特征一般也要处理成离散的(而很多文章没有表达出决策树的关键特征or概念)。实际应用中,决策树overfitting比较的严重,一般要做boosting。分类器的性能上不去,很主要的原因在于特征的鉴别性不足,而不是分类器的好坏,好的特征才有好的分类效果,分类器只是弱相关。
    2.  那如何提高 特征的鉴别性呢?一是设计特征时尽量引入domain knowledge,二是对提取出来的特征做选择、变换和再学习,这一点是机器学习算法不管的部分(我说的这些不是针对决策树的,因此不能说是决策树的特点,只是一些机器学习算法在应用过程中的经验体会)。

    第二部分、贝叶斯分类

        
        插播:关于贝叶斯方法,更清晰简洁的论述请见此文第一部分:从贝叶斯方法谈到贝叶斯网络。July、2014年11月14日更新。

        
        关于贝叶斯,有篇文章介绍的不错:数学之美番外篇:平凡而又神奇的贝叶斯方法,本文第二部分之大部分基本整理自未鹏兄之手(做了部分改动),若有任何不妥之处,还望原作者和众读者海涵,谢谢(当然,日后找机会会重新贝叶斯。PS:后续已经重写,见此文第一部分)。

    2.1、什么是贝叶斯分类

         据维基百科上的介绍,贝叶斯定理是关于随机事件A和B的条件概率和边缘概率的一则定理。
        如上所示,其中P(A|B)是在B发生的情况下A发生的可能性。在贝叶斯定理中,每个名词都有约定俗成的名称:
    • P(A)是A的先验概率或边缘概率。之所以称为"先验"是因為它不考虑任何B方面的因素。
    • P(A|B)是已知B发生后A的条件概率(直白来讲,就是先有B而后=>才有A),也由于得自B的取值而被称作A的后验概率。
    • P(B|A)是已知A发生后B的条件概率(直白来讲,就是先有A而后=>才有B),也由于得自A的取值而被称作B的后验概率。
    • P(B)是B的先验概率或边缘概率,也作标准化常量(normalized constant)。
        按这些术语,Bayes定理可表述为:后验概率 = (相似度*先验概率)/标准化常量,也就是說,后验概率与先验概率和相似度的乘积成正比。另外,比例P(B|A)/P(B)也有时被称作标准相似度(standardised likelihood),Bayes定理可表述为:后验概率 = 标准相似度*先验概率。

    2.2 贝叶斯公式如何而来

        贝叶斯公式是怎么来的?下面再举wikipedia 上的一个例子:

    一所学校里面有 60% 的男生,40% 的女生。男生总是穿长裤,女生则一半穿长裤一半穿裙子。有了这些信息之后我们可以容易地计算“随机选取一个学生,他(她)穿长裤的概率和穿裙子的概率是多大”,这个就是前面说的“正向概率”的计算。然而,假设你走在校园中,迎面走来一个穿长裤的学生(很不幸的是你高度近似,你只看得见他(她)穿的是否长裤,而无法确定他(她)的性别),你能够推断出他(她)是男生的概率是多大吗?

        一些认知科学的研究表明(《决策与判断》以及《Rationality for Mortals》第12章:小孩也可以解决贝叶斯问题),我们对形式化的贝叶斯问题不擅长,但对于以频率形式呈现的等价问题却很擅长。在这里,我们不妨把问题重新叙述成:你在校园里面随机游走,遇到了 N 个穿长裤的人(仍然假设你无法直接观察到他们的性别),问这 N 个人里面有多少个女生多少个男生。

        你说,这还不简单:算出学校里面有多少穿长裤的,然后在这些人里面再算出有多少女生,不就行了?

        我们来算一算:假设学校里面人的总数是 U 个。60% 的男生都穿长裤,于是我们得到了 U * P(Boy) * P(Pants|Boy) 个穿长裤的(男生)(其中 P(Boy) 是男生的概率 = 60%,这里可以简单的理解为男生的比例;P(Pants|Boy) 是条件概率,即在 Boy 这个条件下穿长裤的概率是多大,这里是 100% ,因为所有男生都穿长裤)。40% 的女生里面又有一半(50%)是穿长裤的,于是我们又得到了 U * P(Girl) * P(Pants|Girl) 个穿长裤的(女生)。加起来一共是 U * P(Boy) * P(Pants|Boy) + U * P(Girl) * P(Pants|Girl) 个穿长裤的,其中有 U * P(Girl) * P(Pants|Girl) 个女生。两者一比就是你要求的答案。

        下面我们把这个答案形式化一下:我们要求的是 P(Girl|Pants) (穿长裤的人里面有多少女生),我们计算的结果是 U * P(Girl) * P(Pants|Girl) / [U * P(Boy) * P(Pants|Boy) + U * P(Girl) * P(Pants|Girl)] 。容易发现这里校园内人的总数是无关的,两边同时消去U,于是得到

    P(Girl|Pants) = P(Girl) * P(Pants|Girl) / [P(Boy) * P(Pants|Boy) + P(Girl) * P(Pants|Girl)]

        注意,如果把上式收缩起来,分母其实就是 P(Pants) ,分子其实就是 P(Pants, Girl) 。而这个比例很自然地就读作:在穿长裤的人( P(Pants) )里面有多少(穿长裤)的女孩( P(Pants, Girl) )。

        上式中的 Pants 和 Boy/Girl 可以指代一切东西,So,其一般形式就是:

    P(B|A) = P(A|B) * P(B) / [P(A|B) * P(B) + P(A|~B) * P(~B) ]

        收缩起来就是:

    P(B|A) = P(AB) / P(A)

        其实这个就等于:

    P(B|A) * P(A) = P(AB)

        更进一步阐述,P(B|A)便是在条件A的情况下,B出现的概率是多大。然看似这么平凡的贝叶斯公式,背后却隐含着非常深刻的原理。

    2.3、拼写纠正

        经典著作《人工智能:现代方法》的作者之一 Peter Norvig 曾经写过一篇介绍如何写一个拼写检查/纠正器的文章,里面用到的就是贝叶斯方法,下面,将其核心思想简单描述下。

        首先,我们需要询问的是:“问题是什么?

        问题是我们看到用户输入了一个不在字典中的单词,我们需要去猜测:“这个家伙到底真正想输入的单词是什么呢?”用刚才我们形式化的语言来叙述就是,我们需要求:

    P(我们猜测他想输入的单词 | 他实际输入的单词)

        这个概率。并找出那个使得这个概率最大的猜测单词。显然,我们的猜测未必是唯一的,就像前面举的那个自然语言的歧义性的例子一样;这里,比如用户输入: thew ,那么他到底是想输入 the ,还是想输入 thaw ?到底哪个猜测可能性更大呢?幸运的是我们可以用贝叶斯公式来直接出它们各自的概率,我们不妨将我们的多个猜测记为 h1 h2 .. ( h 代表 hypothesis),它们都属于一个有限且离散的猜测空间 H (单词总共就那么多而已),将用户实际输入的单词记为 D ( D 代表 Data ,即观测数据),于是

    P(我们的猜测1 | 他实际输入的单词)

        可以抽象地记为:

    P(h1 | D)

        类似地,对于我们的猜测2,则是 P(h2 | D)。不妨统一记为:

    P(h | D)

    运用一次贝叶斯公式,我们得到:

    P(h | D) = P(h) * P(D | h) / P(D)

        对于不同的具体猜测 h1 h2 h3 .. ,P(D) 都是一样的,所以在比较 P(h1 | D) 和 P(h2 | D) 的时候我们可以忽略这个常数。即我们只需要知道:

    P(h | D) ∝ P(h) * P(D | h) (注:那个符号的意思是“正比例于”,不是无穷大,注意符号右端是有一个小缺口的。)

        这个式子的抽象含义是:对于给定观测数据,一个猜测是好是坏,取决于“这个猜测本身独立的可能性大小(先验概率,Prior )”和“这个猜测生成我们观测到的数据的可能性大小”(似然,Likelihood )的乘积。具体到我们的那个 thew 例子上,含义就是,用户实际是想输入 the 的可能性大小取决于 the 本身在词汇表中被使用的可能性(频繁程度)大小(先验概率)和 想打 the 却打成 thew 的可能性大小(似然)的乘积。

        剩下的事情就很简单了,对于我们猜测为可能的每个单词计算一下 P(h) * P(D | h) 这个值,然后取最大的,得到的就是最靠谱的猜测。更多细节请参看未鹏兄之原文。

    2.4、贝叶斯的应用

    2.4.1、中文分词

        贝叶斯是机器学习的核心方法之一。比如中文分词领域就用到了贝叶斯。浪潮之巅的作者吴军在《数学之美》系列中就有一篇是介绍中文分词的。这里介绍一下核心的思想,不做赘述,详细请参考吴军的原文

        分词问题的描述为:给定一个句子(字串),如:

        南京市长江大桥

        如何对这个句子进行分词(词串)才是最靠谱的。例如:

    1. 南京市/长江大桥

    2. 南京/市长/江大桥

        这两个分词,到底哪个更靠谱呢?

        我们用贝叶斯公式来形式化地描述这个问题,令 X 为字串(句子),Y 为词串(一种特定的分词假设)。我们就是需要寻找使得 P(Y|X) 最大的 Y ,使用一次贝叶斯可得:

    P(Y|X) ∝ P(Y)*P(X|Y)

         用自然语言来说就是 这种分词方式(词串)的可能性 乘以 这个词串生成我们的句子的可能性。我们进一步容易看到:可以近似地将 P(X|Y) 看作是恒等于 1 的,因为任意假想的一种分词方式之下生成我们的句子总是精准地生成的(只需把分词之间的分界符号扔掉即可)。于是,我们就变成了去最大化 P(Y) ,也就是寻找一种分词使得这个词串(句子)的概率最大化。而如何计算一个词串:

    W1, W2, W3, W4 ..

        的可能性呢?我们知道,根据联合概率的公式展开:P(W1, W2, W3, W4 ..) = P(W1) * P(W2|W1) * P(W3|W2, W1) * P(W4|W1,W2,W3) * .. 于是我们可以通过一系列的条件概率(右式)的乘积来求整个联合概率。然而不幸的是随着条件数目的增加(P(Wn|Wn-1,Wn-2,..,W1) 的条件有 n-1 个),数据稀疏问题也会越来越严重,即便语料库再大也无法统计出一个靠谱的 P(Wn|Wn-1,Wn-2,..,W1) 来。为了缓解这个问题,计算机科学家们一如既往地使用了“天真”假设:我们假设句子中一个词的出现概率只依赖于它前面的有限的 k 个词(k 一般不超过 3,如果只依赖于前面的一个词,就是2元语言模型(2-gram),同理有 3-gram 、 4-gram 等),这个就是所谓的“有限地平线”假设。

         虽然上面这个假设很傻很天真,但结果却表明它的结果往往是很好很强大的,后面要提到的朴素贝叶斯方法使用的假设跟这个精神上是完全一致的,我们会解释为什么像这样一个天真的假设能够得到强大的结果。目前我们只要知道,有了这个假设,刚才那个乘积就可以改写成: P(W1) * P(W2|W1) * P(W3|W2) * P(W4|W3) .. (假设每个词只依赖于它前面的一个词)。而统计 P(W2|W1) 就不再受到数据稀疏问题的困扰了。对于我们上面提到的例子“南京市长江大桥”,如果按照自左到右的贪婪方法分词的话,结果就成了“南京市长/江大桥”。但如果按照贝叶斯分词的话(假设使用 3-gram),由于“南京市长”和“江大桥”在语料库中一起出现的频率为 0 ,这个整句的概率便会被判定为 0 。 从而使得“南京市/长江大桥”这一分词方式胜出。

    2.4.2、贝叶斯图像识别,Analysis by Synthesis

        贝叶斯方法是一个非常 general 的推理框架。其核心理念可以描述成:Analysis by Synthesis (通过合成来分析)。06 年的认知科学新进展上有一篇 paper 就是讲用贝叶斯推理来解释视觉识别的,一图胜千言,下图就是摘自这篇 paper :

    i3

        首先是视觉系统提取图形的边角特征,然后使用这些特征自底向上地激活高层的抽象概念(比如是 E 还是 F 还是等号),然后使用一个自顶向下的验证来比较到底哪个概念最佳地解释了观察到的图像。

    2.4.3、最大似然与最小二乘

    i5

        学过线性代数的大概都知道经典的最小二乘方法来做线性回归。问题描述是:给定平面上 N 个点,(这里不妨假设我们想用一条直线来拟合这些点——回归可以看作是拟合的特例,即允许误差的拟合),找出一条最佳描述了这些点的直线。

        一个接踵而来的问题就是,我们如何定义最佳?我们设每个点的坐标为 (Xi, Yi) 。如果直线为 y = f(x) 。那么 (Xi, Yi) 跟直线对这个点的“预测”:(Xi, f(Xi)) 就相差了一个 ΔYi = |Yi – f(Xi)| 。最小二乘就是说寻找直线使得 (ΔY1)^2 + (ΔY2)^2 + .. (即误差的平方和)最小,至于为什么是误差的平方和而不是误差的绝对值和,统计学上也没有什么好的解释。然而贝叶斯方法却能对此提供一个完美的解释。

        我们假设直线对于坐标 Xi 给出的预测 f(Xi) 是最靠谱的预测,所有纵坐标偏离 f(Xi) 的那些数据点都含有噪音,是噪音使得它们偏离了完美的一条直线,一个合理的假设就是偏离路线越远的概率越小,具体小多少,可以用一个正态分布曲线来模拟,这个分布曲线以直线对 Xi 给出的预测 f(Xi) 为中心,实际纵坐标为 Yi 的点 (Xi, Yi) 发生的概率就正比于 EXP[-(ΔYi)^2]。(EXP(..) 代表以常数 e 为底的多少次方)。

        现在我们回到问题的贝叶斯方面,我们要想最大化的后验概率是:

    P(h|D) ∝ P(h) * P(D|h)

        又见贝叶斯!这里 h 就是指一条特定的直线,D 就是指这 N 个数据点。我们需要寻找一条直线 h 使得 P(h) * P(D|h) 最大。很显然,P(h) 这个先验概率是均匀的,因为哪条直线也不比另一条更优越。所以我们只需要看 P(D|h) 这一项,这一项是指这条直线生成这些数据点的概率,刚才说过了,生成数据点 (Xi, Yi) 的概率为 EXP[-(ΔYi)^2] 乘以一个常数。而 P(D|h) = P(d1|h) * P(d2|h) * .. 即假设各个数据点是独立生成的,所以可以把每个概率乘起来。于是生成 N 个数据点的概率为 EXP[-(ΔY1)^2] * EXP[-(ΔY2)^2] * EXP[-(ΔY3)^2] * .. = EXP{-[(ΔY1)^2 + (ΔY2)^2 + (ΔY3)^2 + ..]} 最大化这个概率就是要最小化 (ΔY1)^2 + (ΔY2)^2 + (ΔY3)^2 + .. 。 熟悉这个式子吗?

        除了以上所介绍的之外,贝叶斯还在词义消岐,语言模型的平滑方法中都有一定应用。下节,咱们再来简单看下朴素贝叶斯方法。

    2.5、朴素贝叶斯方法

        朴素贝叶斯方法是一个很特别的方法,所以值得介绍一下。在众多的分类模型中,应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型(Naive Bayesian Model,NBC)。 朴素贝叶斯模型发源于古典数学理论,有着坚实的数学基础,以及稳定的分类效率。
         同时,NBC模型所需估计的参数很少,对缺失数据不太敏感,算法也比较简单。理论上,NBC模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此,这是因为NBC模型假设属性之间相互独立,这个假设在实际应用中往往是不成立的,这给NBC模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时,NBC模型的分类效率比不上决策树模型。而在属性相关性较小时,NBC模型的性能最为良好

        接下来,我们用朴素贝叶斯在垃圾邮件过滤中的应用来举例说明。

    2.5.1、贝叶斯垃圾邮件过滤器

        问题是什么?问题是,给定一封邮件,判定它是否属于垃圾邮件。按照先例,我们还是用 D 来表示这封邮件,注意 D 由 N 个单词组成。我们用 h+ 来表示垃圾邮件,h- 表示正常邮件。问题可以形式化地描述为求:

    P(h+|D) = P(h+) * P(D|h+) / P(D)

    P(h-|D) = P(h-) * P(D|h-) / P(D)

        其中 P(h+) 和 P(h-) 这两个先验概率都是很容易求出来的,只需要计算一个邮件库里面垃圾邮件和正常邮件的比例就行了。然而 P(D|h+) 却不容易求,因为 D 里面含有 N 个单词 d1, d2, d3, .. ,所以P(D|h+) = P(d1,d2,..,dn|h+) 。我们又一次遇到了数据稀疏性,为什么这么说呢?P(d1,d2,..,dn|h+) 就是说在垃圾邮件当中出现跟我们目前这封邮件一模一样的一封邮件的概率是多大!开玩笑,每封邮件都是不同的,世界上有无穷多封邮件。瞧,这就是数据稀疏性,因为可以肯定地说,你收集的训练数据库不管里面含了多少封邮件,也不可能找出一封跟目前这封一模一样的。结果呢?我们又该如何来计算 P(d1,d2,..,dn|h+) 呢?

        我们将 P(d1,d2,..,dn|h+)  扩展为: P(d1|h+) * P(d2|d1, h+) * P(d3|d2,d1, h+) * .. 。熟悉这个式子吗?这里我们会使用一个更激进的假设,我们假设 di 与 di-1 是完全条件无关的,于是式子就简化为 P(d1|h+) * P(d2|h+) * P(d3|h+) * .. 。这个就是所谓的条件独立假设,也正是朴素贝叶斯方法的朴素之处。而计算 P(d1|h+) * P(d2|h+) * P(d3|h+) * .. 就太简单了,只要统计 di 这个单词在垃圾邮件中出现的频率即可。关于贝叶斯垃圾邮件过滤更多的内容可以参考这个条目,注意其中提到的其他资料。

    2.6、层级贝叶斯模型

    i6

        层级贝叶斯模型是现代贝叶斯方法的标志性建筑之一。前面讲的贝叶斯,都是在同一个事物层次上的各个因素之间进行统计推理,然而层次贝叶斯模型在哲学上更深入了一层,将这些因素背后的因素(原因的原因,原因的原因,以此类推)囊括进来。一个教科书例子是:如果你手头有 N 枚硬币,它们是同一个工厂铸出来的,你把每一枚硬币掷出一个结果,然后基于这 N 个结果对这 N 个硬币的 θ (出现正面的比例)进行推理。如果根据最大似然,每个硬币的 θ 不是 1 就是 0 (这个前面提到过的),然而我们又知道每个硬币的 p(θ) 是有一个先验概率的,也许是一个 beta 分布。也就是说,每个硬币的实际投掷结果 Xi 服从以 θ 为中心的正态分布,而 θ 又服从另一个以 Ψ 为中心的 beta 分布。层层因果关系就体现出来了。进而 Ψ 还可能依赖于因果链上更上层的因素,以此类推。

    2.7、基于newsgroup文档集的贝叶斯算法实现

    2.7.1、newsgroup文档集介绍与预处理
        Newsgroups最早由Lang于1995收集并在[Lang 1995]中使用。它含有20000篇左右的Usenet文档,几乎平均分配20个不同的新闻组。除了其中4.5%的文档属于两个或两个以上的新闻组以外,其余文档仅属于一个新闻组,因此它通常被作为单标注分类问题来处理。Newsgroups已经成为文本分类聚类中常用的文档集。美国MIT大学Jason Rennie对Newsgroups作了必要的处理,使得每个文档只属于一个新闻组,形成Newsgroups-18828。 

     (:本2.7节内容主要援引自参考文献条目9的内容,有任何不妥之处,还望原作者及众读者海涵,谢谢)

        要做文本分类首先得完成文本的预处理,预处理的主要步骤如下:

    1. 英文词法分析,去除数字、连字符、标点符号、特殊 字符,所有大写字母转换成小写,可以用正则表达式:String res[] = line.split("[^a-zA-Z]");
    2. 去停用词,过滤对分类无价值的词;
    3. 词根还原stemming,基于Porter算法
        private static String lineProcess(String line, ArrayList<String> stopWordsArray) throws IOException {  
            // TODO Auto-generated method stub  
            //step1 英文词法分析,去除数字、连字符、标点符号、特殊字符,所有大写字母转换成小写,可以考虑用正则表达式  
            String res[] = line.split("[^a-zA-Z]");  
            //这里要小心,防止把有单词中间有数字和连字符的单词 截断了,但是截断也没事  
              
            String resString = new String();  
            //step2去停用词  
            //step3stemming,返回后一起做  
            for(int i = 0; i < res.length; i++){  
                if(!res[i].isEmpty() && !stopWordsArray.contains(res[i].toLowerCase())){  
                    resString += " " + res[i].toLowerCase() + " ";  
                }  
            }  
            return resString;  
        } 
    2.7.2、特征词的选取
        首先统计经过预处理后在所有文档中出现不重复的单词一共有87554个,对这些词进行统计发现:
    出现次数大于等于1次的词有87554个
    出现次数大于等于3次的词有36456个 
    出现次数大于等于4次的词有30095个
        特征词的选取策略:
    策略一:保留所有词作为特征词 共计87554个
    策略二:选取出现次数大于等于4次的词作为特征词共计30095个 
        特征词的选取策略:采用策略一,后面将对两种特征词选取策略的计算时间和平均准确率做对比
    2.7.3、贝叶斯算法描述及实现

        根据朴素贝叶斯公式,每个测试样例属于某个类别的概率 =  所有测试样例包含特征词类条件概率P(tk|c)之积 * 先验概率P(c)
    在具体计算类条件概率和先验概率时,朴素贝叶斯分类器有两种模型:
        (1) 多项式模型( multinomial model )  –以单词为粒度
    类条件概率P(tk|c)=(类c下单词tk在各个文档中出现过的次数之和+1)/(类c下单词总数+训练样本中不重复特征词总数)
    先验概率P(c)=类c下的单词总数/整个训练样本的单词总数
        (2) 伯努利模型(Bernoulli model)   –以文件为粒度
    类条件概率P(tk|c)=(类c下包含单词tk的文件数+1)/(类c下文件总数+2)
    先验概率P(c)=类c下文件总数/整个训练样本的文件总数
    本分类器选用多项式模型计算,根据斯坦福的《Introduction to Information Retrieval 》课件上所说,多项式模型计算准确率更高。
        贝叶斯算法的实现有以下注意点:
    1. 计算概率用到了BigDecimal类实现任意精度计算;
    2. 用交叉验证法做十次分类实验,对准确率取平均值;
    3. 根据正确类目文件和分类结果文计算混淆矩阵并且输出;
    4.  Map<String,Double> cateWordsProb key为“类目_单词”, value为该类目下该单词的出现次数,避免重复计算。

    2.7.4、朴素贝叶斯算法对newsgroup文档集做分类的结果
        在经过一系列Newsgroup文档预处理、特征词的选取、及实现了贝叶斯算法之后,下面用朴素贝叶斯算法那对newsgroup文档集做分类,看看此贝叶斯算法的效果。
        贝叶斯算法分类结果-混淆矩阵表示,以交叉验证的第6次实验结果为例,分类准确率最高达到80.47%。

        程序运行硬件环境:Intel Core 2 Duo CPU T5750 2GHZ, 2G内存,实验结果如下:
        取所有词共87554个作为特征词:10次交叉验证实验平均准确率78.19%,用时23min,准确率范围75.65%-80.47%,第6次实验准确率超过80%,取出现次数大于等于4次的词共计30095个作为特征词: 10次交叉验证实验平均准确率77.91%,用时22min,准确率范围75.51%-80.26%,第6次实验准确率超过80%。如下图所示:

         结论:朴素贝叶斯算法不必去除出现次数很低的词,因为出现次数很低的词的IDF比较   大,去除后分类准确率下降,而计算时间并没有显著减少
    2.7.5、贝叶斯算法的改进
        为了进一步提高贝叶斯算法的分类准确率,可以考虑
    1. 优化特征词的选取策略;
    2. 改进多项式模型的类条件概率的计算公式,改进为 类条件概率P(tk|c)=(类c下单词tk在各个文档中出现过的次数之和+0.001)/(类c下单词总数+训练样本中不重复特征词总数),分子当tk没有出现时,只加0.001(之前上面2.7.3节是+1),这样更加精确的描述的词的统计分布规律,
        做此改进后的混淆矩阵如下

        可以看到第6次分组实验的准确率提高到84.79%,第7词分组实验的准确率达到85.24%,平均准确率由77.91%提高到了82.23%,优化效果还是很明显的。更多内容,请参考原文:参考文献条目8。谢谢。
        复播:关于贝叶斯方法,更清晰简洁的论述请见此文第一部分:从贝叶斯方法谈到贝叶斯网络。July、2014年11月14日更新。

    第三部分、从EM算法到隐马可夫模型(HMM)

    3.1、EM 算法与基于模型的聚类

         在统计计算中,最大期望 (EM,Expectation–Maximization)算法是在概率(probabilistic)模型中寻找参数最大似然估计的算法,其中概率模型依赖于无法观测的隐藏变量(Latent Variabl)。最大期望经常用在机器学习和计算机视觉的数据集聚(Data Clustering)领域。

        通常来说,聚类是一种无指导的机器学习问题,如此问题描述:给你一堆数据点,让你将它们最靠谱地分成一堆一堆的。聚类算法很多,不同的算法适应于不同的问题,这里仅介绍一个基于模型的聚类,该聚类算法对数据点的假设是,这些数据点分别是围绕 K 个核心的 K 个正态分布源所随机生成的,使用 Han JiaWei 的《Data Ming: Concepts and Techniques》中的图:

    i4

        图中有两个正态分布核心,生成了大致两堆点。我们的聚类算法就是需要根据给出来的那些点,算出这两个正态分布的核心在什么位置,以及分布的参数是多少。这很明显又是一个贝叶斯问题,但这次不同的是,答案是连续的且有无穷多种可能性,更糟的是,只有当我们知道了哪些点属于同一个正态分布圈的时候才能够对这个分布的参数作出靠谱的预测,现在两堆点混在一块我们又不知道哪些点属于第一个正态分布,哪些属于第二个。反过来,只有当我们对分布的参数作出了靠谱的预测时候,才能知道到底哪些点属于第一个分布,那些点属于第二个分布。这就成了一个先有鸡还是先有蛋的问题了。为了解决这个循环依赖,总有一方要先打破僵局,说,不管了,我先随便整一个值出来,看你怎么变,然后我再根据你的变化调整我的变化,然后如此迭代着不断互相推导,最终收敛到一个解。这就是 EM 算法。

        EM 的意思是“Expectation-Maximazation”,在这个聚类问题里面,我们是先随便猜一下这两个正态分布的参数:如核心在什么地方,方差是多少。然后计算出每个数据点更可能属于第一个还是第二个正态分布圈,这个是属于 Expectation 一步。有了每个数据点的归属,我们就可以根据属于第一个分布的数据点来重新评估第一个分布的参数(从蛋再回到鸡),这个是 Maximazation 。如此往复,直到参数基本不再发生变化为止。这个迭代收敛过程中的贝叶斯方法在第二步,根据数据点求分布的参数上面。

    3.2、隐马可夫模型(HMM)

        大多的书籍或论文都讲不清楚这个隐马可夫模型(HMM),包括未鹏兄之原文也讲得不够具体明白。接下来,我尽量用直白易懂的语言阐述这个模型。然在介绍隐马可夫模型之前,有必要先行介绍下单纯的马可夫模型(本节主要引用:统计自然语言处理,宗成庆编著一书上的相关内容)。

    3.2.1、马可夫模型

        我们知道,随机过程又称随机函数,是随时间而随机变化的过程。马可夫模型便是描述了一类重要的随机过程。我们常常需要考察一个随机变量序列,这些随机变量并不是相互独立的(注意:理解这个非相互独立,即相互之间有千丝万缕的联系)。

        如果此时,我也搞一大推状态方程式,恐怕我也很难逃脱越讲越复杂的怪圈了。所以,直接举例子吧,如,一段文字中名词、动词、形容词三类词性出现的情况可由三个状态的马尔科夫模型描述如下:

    状态s1:名词
    状态s2:动词
    状态s3:形容词

    假设状态之间的转移矩阵如下:

                                    s1     s2    s3
                            s1   0.3      0.5    0.2
        A = [aij] =     s2   0.5      0.3    0.2
                            s3   0.4      0.2     0.4

        如果在该段文字中某一个句子的第一个词为名词,那么根据这一模型M,在该句子中这三类词出现顺序为O="名动形名”的概率为:

        P(O|M)=P(s1,s2,s3,s1 | M) = P(s1) × P(s2 | s1) * P(s3 | s2)*P(s1 | s3)
                    =1* a12 * a23 * a31=0.5*0.2*0.4=0.004

        马尔可夫模型又可视为随机的有限状态机。马尔柯夫链可以表示成状态图(转移弧上有概率的非确定的有限状态自动机),如下图所示,

        在上图中,圆圈表示状态,状态之间的转移用带箭头的弧表示,弧上的数字为状态转移的概率,初始状态用标记为start的输入箭头表示,假设任何状态都可作为终止状态。图中零概率的转移弧省略,且每个节点上所有发出弧的概率之和等于1。从上图可以看出,马尔可夫模型可以看做是一个转移弧上有概率的非确定的有限状态自动机

    3.2.2、隐马可夫模型(HMM)

        在上文介绍的马可夫模型中,每个状态代表了一个可观察的事件,所以,马可夫模型有时又称作视马可夫模型(VMM),这在某种程度上限制了模型的适应性。而在我们的隐马可夫模型(HMM)中,我们不知道模型所经过的状态序列,只知道状态的概率函数,也就是说,观察到的事件是状态的随机函数,因此改模型是一个双重的随机过程。其中,模型的状态转换是不可观察的,即隐蔽的,可观察事件的随机过程是隐蔽的状态过程的随机函数。

        i7

        理论多说无益,接下来,再举个例子。N 个袋子,每个袋子中有M 种不同颜色的球。一实验员根据某一概率分布选择一个袋子,然后根据袋子中不同颜色球的概率分布随机取出一个球,并报告该球的颜色。对局外人:可观察的过程是不同颜色球的序列,而袋子的序列是不可观察的。每只袋子对应HMM中的一个状态,球的颜色对应于HMM 中状态的输出。

    3.2.2、HMM在中文分词、机器翻译等方面的具体应用

        隐马可夫模型在很多方面都有着具体的应用,如由于隐马可夫模型HMM提供了一个可以综合利用多种语言信息的统计框架,因此,我们完全可以讲汉语自动分词与词性标注统一考察,建立基于HMM的分词与词性标注的一体化系统。

        根据上文对HMM的介绍,一个HMM通常可以看做由两部分组成:一个是状态转移模型,一个是状态到观察序列的生成模型。具体到中文分词这一问题中,可以把汉字串或句子S作为输入,单词串Sw为状态的输出,即观察序列,Sw=w1w2w3...wN(N>=1),词性序列St为状态序列,每个词性标记ct对应HMM中的一个状态qi,Sc=c1c2c3...cn。

        那么,利用HMM处理问题问题恰好对应于解决HMM的三个基本问题:

    1. 估计模型的参数;
    2. 对于一个给定的输入S及其可能的输出序列Sw和模型u=(A,B,*),快速地计算P(Sw|u),所有可能的Sw中使概率P(Sw|u)最大的解就是要找的分词效果;
    3. 快速地选择最优的状态序列或词性序列,使其最好地解释观察序列。
        除中文分词方面的应用之外,HMM还在统计机器翻译中有应用,如基于HMM的词对位模型,更多请参考:统计自然语言处理,宗成庆编著
        注:本文着重讲决策树分类和贝叶斯分类算法,后面的EM、HMM都是一笔带过,篇幅有限+懒,未能详尽阐述。日后,有机会,会再讲讲EM和HMM算法的。当然,你还可以先看看一个叫做HMM学习最佳范例的系列,原文写得好,翻译也翻译的精彩,推荐给大家:http://www.52nlp.cn/category/hidden-markov-model/page/4


    参考文献及推荐阅读

    1. 机器学习,Tom M.Mitchhell著;
    2. 数据挖掘导论,[美] Pang-Ning Tan / Michael Steinbach / Vipin Kumar 著
    3. 数据挖掘领域十大经典算法初探
    4. 数学之美番外篇:平凡而又神奇的贝叶斯方法(本文第二部分、贝叶斯分类主要来自此文);
    5. 贝叶斯方法谈到贝叶斯网络
    6. http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html
    7. 数学之美:http://www.google.com.hk/ggblog/googlechinablog/2006/04/blog-post_2507.html
    8. 决策树ID3分类算法的C++实现 & yangliuy:http://blog.csdn.net/yangliuy/article/details/7322015
    9. yangliuy,http://blog.csdn.net/yangliuy/article/details/7400984
    10. 统计自然语言处理,宗成庆编著(本文第三部分之HMM主要参考此书);
    11. 推荐引擎算法学习导论
    12. 支持向量机导论,[美] Nello Cristianini / John Shawe-Taylor 著
    13. Porter算法,http://qinxuye.me/article/porter-stemmer/
    14. 漫谈Clustering之k-means:http://blog.pluskid.org/?p=17
    15. HMM学习最佳范例:http://www.52nlp.cn/category/hidden-markov-model/page/4
    16. 朴素贝叶斯新闻分类器详解:http://www.sobuhu.com/archives/610
    17. 一堆 Wikipedia 条目,一堆 paper ,《机器学习与人工智能资源导引》。

    后记

        研究了一年有余的数据结构方面的算法,现在可以逐渐转向应用方面(机器学习 & 数据挖掘)的算法学习了。OK,本文或本聚类 & 分类算法系列中任何一篇文章有任何问题,漏洞,或bug,欢迎任何读者随时不吝赐教 & 指正,感谢大家,谢谢。

        这些东西现在只是一个大致粗略的预览学习,以后若有机会,都会逐一更进一步深入(每一个分类方法或算法都足以写成一本书)。July、二零一二年五月二十八日晚十点。

    展开全文
  • 分类算法】什么是分类算法

    千次阅读 2019-12-14 11:47:10
    分类算法的本意就是对我们的数据分进行分类。把它们分到已知的每一个类别。就像一个篮子里面有很多橙子和苹果,机器会通过我们训练出来的模型,对篮子里的水果进行分类。比如:红色 = 苹果,橙色 = 橙子。若要让机器...
  • 多分类及多标签分类算法

    万次阅读 2019-04-08 19:49:55
    1、单标签二分类算法原理 1、单标签二分类这种问题是我们最常见的算法问题,主要是指label 标签的取值只有两种,并且算法中只有一个需要预测的label标签; 直白来讲就是每个实例的可能类别只有两种(A or B);...
  • 传统分类算法以及流计算分类算法

    千次阅读 2016-11-27 11:18:50
    传统的数据挖掘算法如ID3、C4.5首先都是通过先将数据存储到静态数据库中,当需要进行数据挖掘时再将数据提取出来进行处理,并且现行...K近邻分类算法、决策树分类算法和贝叶斯分类算法都是一些常用的针对静态数据集的分
  • 聚类算法和分类算法

    千次阅读 2019-03-05 20:22:56
    常用的分类算法包括: 决策树分类法 朴素的贝叶斯分类算法(native Bayesian classifier) 基于支持向量机(SVM)的分类器 神经网络法 k-最近邻法(k-nearest neighbor,kNN) 模糊分类法 下文出处 常见的聚类算法...
  • 贝叶斯分类算法

    千次阅读 多人点赞 2018-07-31 16:09:12
    贝叶斯分类是一类分类算法的总称,这类算法均以贝叶斯定理为基础,故统称为贝叶斯分类。而朴素朴素贝叶斯分类是贝叶斯分类中最简单,也是常见的一种分类方法。这篇文章我尽可能用直白的话语总结一下我们学习会上讲到...
  • KNN分类算法

    千次阅读 2017-04-08 18:08:31
    KNN分类算法原理 KNN概述 KNN算法图示 KNN算法要点 KNN算法不足之处 KNN分类算法Python实战 KNN简单数据分类实践 KNN实现手写数字识别 KNN算法...
  • 常见分类算法

    万次阅读 2018-05-17 11:38:48
    常见分类算法 朴素贝叶斯网络、贝叶斯信念网络、随机森林、k-最近邻分类 云聚类算法引擎 k-Means、Canopy、Fuzzy K-Means、Mean Shift 云关联规则算法引起 FP-Growth关联规则 云智能推荐算法引擎 基于内存的...
  • 数据分类算法之KNN算法

    千次阅读 2018-08-11 21:12:56
    在现实生活中我们会遇到要把大量的数据进行分类的问题,这个时候一些常见的分类算法就可以对数据进行分类了。一般有1.KNN算法 2.贝克斯算法 3.决策树 4.人工神经网络 5.支持向量机(SVM)等很多分类算法。我们这里...
  • 分类算法评价

    千次阅读 2017-04-26 21:33:56
    不同的分类算法有不同的特征,在不同的数据集上表现的效果也不同,我们需要根据特定的任务进行算法的选择,如何选择分类,如何评价一个分类算法的好坏,前面关于决策树的介绍,我们主要用的正确率(accuracy)来评价...
  • 单标签多分类及多标签多分类算法

    千次阅读 2020-03-27 15:45:07
    单标签二分类算法,单标签多分类算法,多标签多分类算法及多标签多分类在Scikit-learn中的实现方式。
  • 分类算法简述

    万次阅读 多人点赞 2016-05-21 16:56:32
    分类算法简述一、什么是分类算法数据挖掘任务通常分为两大类: 预测任务,根据其他属性的值,预测特定属性的值。 描述任务,概括数据中潜在联系的模式(相关性,趋势,聚类,轨迹和异常)  分类属于预测任务,...
  • 聚类算法和分类算法总结

    万次阅读 2015-09-21 21:56:24
    聚类算法和分类算法总结
  • 分类算法总结

    千次阅读 2018-05-21 15:37:12
    本文先系统的介绍一下机器学习中的分类算法,主要目录如下:常用分类算法Bayes朴素贝叶斯的优缺点朴素贝叶斯的公式Decision Tree决策树的优缺点决策树公式SVM支持向量机的优缺点支持向量机的公式KNNK近邻的优缺点K...
  • 详解朴素贝叶斯分类算法

    万次阅读 多人点赞 2018-08-15 22:25:31
    带你搞懂朴素贝叶斯分类算法   带你搞懂朴素贝叶斯分类算 贝叶斯分类是一类分类算法的总称,这类算法均以贝叶斯定理为基础,故统称为贝叶斯分类。而朴素朴素贝叶斯分类是贝叶斯分类中最简单,也是常见的一种分类...
  • 分类算法 - K-近邻算法

    千次阅读 2019-03-26 17:40:02
    了解分类算法的评估标准准确率 应用:Facebook签到位置预测 1 K-近邻算法(KNN) 1.1 定义 如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别,即...
  • K-Means算法的扩展,采用简单匹配方法来度量分类型数据的相似度 k-prototypes: 结合了K-Means和K-Modes两种算法,能够处理混合型数据 k-medoids: 在迭代过程中选择簇中的某点作为聚点,...
  • 基本分类算法 The Assign Class Algorithm【指向分类算法】 基本描述 适用范围 The Classification Algorithm【特征分类算法】 基本描述 适用范围 The Hierarchical Classification Algorithm【层次分类算法...
  • 分类算法评价标准

    万次阅读 2016-04-06 17:24:07
    不同的分类算法有不同的特定,在不同的数据集上表现的效果也不同,我们需要根据特定的任务进行算法的选择,如何选择分类,如何评价一个分类算法的好坏,前面关于决策树的介绍,我们主要用的正确率(accuracy)来评价...
  • 分类算法 -- 决策树ID3算法

    千次阅读 多人点赞 2019-02-17 01:27:43
    决策树算法是非常常用的分类算法,其分类的思路非常清晰,简单易懂。并且它也是一个很基础的算法,集成学习和随机森林算法是以其为基础的。 算法简介 对于决策树算法,其输入是带有标签的数据,输出是一颗决策树。...
  • python+分类算法

    千次阅读 2018-05-10 18:09:07
    # -*- coding: utf-8 -*- ...比较不同分类算法效果 分类算法:LR/RF/GBDT/ADABOOST @author: DELL """ from sklearn.linear_model import LogisticRegression from sklearn.ensemble imp...
  • 浅谈分类算法原理

    万次阅读 2018-09-10 15:23:21
    二、分类算法用来解决什么问题 人群分类,新闻分类,query分类,商品分类,网页分类,垃圾邮件过滤,网页排序 三、有哪些分类算法(不保证完全,会不断补充) 1. Naive Bayesian Mode 朴素贝叶斯模型 最...
  • 实验二 分类算法实验

    万次阅读 2017-12-24 16:32:06
    巩固4种基本的分类算法的算法思想:朴素贝叶斯算法,决策树算法,人工神经网络,支持向量机算法; 2.能够使用现有的分类器算法代码进行分类操作 3.学习如何调节算法的参数以提高分类性能;二、实验的硬件、软件平台...
  • ML笔记 - 常用分类算法

    千次阅读 2019-01-04 17:11:07
    分类算法的定义 KNN最近邻算法 决策树 朴素贝叶斯 支持向量机 人工神经网络 集成学习 随机森林
  • 【模式识别】K-近邻分类算法KNN

    万次阅读 多人点赞 2014-04-15 20:19:35
    K-近邻(K-Nearest Neighbors, KNN)是一种很好理解的分类算法,简单说来就是从训练样本中找出K个与其最相近的样本,然后看这K个样本中哪个类别的样本多,则待判定的值(或说抽样)就属于这个类别。 KNN算法的步骤 ...
  • 朴素贝叶斯分类算法

    万次阅读 2015-01-13 18:40:00
    参考资料地址: http://www.cnblogs.com/leoo2sk/archive/2010/09/17/naive-bayesian-classifier.html 我的数据挖掘算法实现源码... 介绍 要介绍朴素贝叶斯算法(Naive Bayes),那就得先介绍贝叶斯分类算法,贝叶斯分

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 80,926
精华内容 32,370
关键字:

分类算法