knn算法 ppt 大数据_knn算法knn邻居数量变化对鸢尾花数据集 - CSDN
  • 大数据十大经典算法PPT系列,详细讲解了Kmeans、SVM、KNN三种算法。
  • 一步步教你轻松学KNN模型算法( 白宁超 2018年7月24日08:52:16 ) 导读:机器学习算法KNN属于比较简单的典型算法,既可以做聚类又可以做分类使用。本文通过一个模拟的实际案例进行讲解。整个流程包括:采集数据...
    一步步教你轻松学KNN模型算法
    ( 白宁超 2018年7月24日08:52:16 )

    导读:机器学习算法中KNN属于比较简单的典型算法,既可以做聚类又可以做分类使用。本文通过一个模拟的实际案例进行讲解。整个流程包括:采集数据、数据格式化处理、数据分析、数据归一化处理、构造算法模型、评估算法模型和算法模型的应用。(本文原创,转载必须注明出处: 一步步教你轻松学KNN模型算法

    目录

    机器学习:一步步教你轻松学KNN模型算法

    机器学习:一步步教你轻松学决策树算法

    机器学习:一步步教你轻松学朴素贝叶斯模型算法理论篇1 

    机器学习:一步步教你轻松学朴素贝叶斯模型实现篇2 

    机器学习:一步步教你轻松学朴素贝叶斯模型算法Sklearn深度篇3

    机器学习:一步步教你轻松学逻辑回归模型算法

    机器学习:一步步教你轻松学K-means聚类算法

    机器学习:一步步教你轻松学关联规则Apriori算法

    机器学习: 一步步教你轻松学支持向量机SVM算法之理论篇1

    10 机器学习: 一步步教你轻松学支持向量机SVM算法之案例篇2

    11 机器学习: 一步步教你轻松学主成分分析PCA降维算法

    12 机器学习: 一步步教你轻松学支持向量机SVM降维算法

    更多文章请点击这里>>

    1 理论介绍

    什么是KNN?

           k-近邻(kNN,k-NearestNeighbor)算法是一种基本分类与回归方法,我们这里只讨论分类问题中的 k-近邻算法。k-近邻算法的输入为实例的特征向量,对应于特征空间的点;输出为实例的类别,可以取多类。k-邻算法假设给定一个训练数据集,其中的实例类别已定。分类时,对新的实例,根据其 k 个最近邻的训练实例的类别,通过多数表决等方式进行预测。因此,k近邻算法不具有显式的学习过程即属于有监督学习范畴。k近邻算法实际上利用训练数据集对特征向量空间进行划分,并作为其分类的“模型”。k值的选择、距离度量以及分类决策规则是k近邻算法的三个基本要素。

    KNN算法思想

    1 计算已知类别中数据集的点与当前点的距离。[即计算所有样本点跟待分类样本之间的距离]
    2 按照距离递增次序排序。[计算完样本距离进行排序]
    3 选取与当前点距离最小的k个点。[选取距离样本最近的k个点]
    4 确定前k个点所在类别的出现频率。[针对这k个点,统计下各个类别分别有多少个]
    5 返回前k个点出现频率最高的类别作为当前点的预测分类。[k个点中某个类别最多,就将样本划归改点]
    

    KNN工作原理

    1 假设有一个带有标签的样本数据集(训练样本集),其中包含每条数据与所属分类的对应关系。
    2 输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较。
    3 计算新数据与样本数据集中每条数据的距离。
    4 对求得的所有距离进行排序(从小到大,越小表示越相似)。
    5 取前 k (k 一般小于等于 20 )个样本数据对应的分类标签。
    6 求 k 个数据中出现次数最多的分类标签作为新数据的分类。
    

    KNN算法流程

    1 搜集数据:数据采集过程,其分为非结构化数据,半结构化数据和数据化数据。诸如:网络爬取,数据库,文件等。
    2 准备数据:格式化处理,对不同类别的数据进行统一的格式化处理。诸如:将pdf,word,excel,sql等等统一转化为txt文本。
    3 分析数据:主要看看数据特点,有没有缺失值,数据连续性还是离散型,进而选择不同模型。诸如:可视化数据分析
    4 训练数据:不适用于KNN,但是在其他一些监督学习中会经常遇到,诸如:朴素贝叶斯分类等。
    5 测试算法:评价指标,如计算错误率,准确率,召回率,F度量值等。
    6 应用算法:针对完善的模型进行封装重构,然后进行实际应用。
    

    KNN优缺点

    优点:精度高、对异常值不敏感、无数据输入假定
    缺点:计算复杂度高、空间复杂度好
    适用数据范围:数值型和标称型
    

    2 KNN算法实现与分析

    2.1 数据准备

    创建模拟数据集

    描述:现在你来了一个新的任务,任务其实非常简单,就是根据吃冰淇淋和喝水的数量判断成都天气冷热程度。你现在要做的就是去成都春熙路街头采访记录一些游客吃了多少冰淇淋,又喝了几瓶水,他觉得成都天气怎么样(这里只考虑二分类问题,假设只有‘非常热’和‘一般热’)。其中特征向量包括两个分别是冰激凌数t1和喝水数t2,标签类别分别是非常热A和一般热B。

    现在我们开始行动,随机采访4个游客(暂时不考虑样本数量问题),询问每个游客吃多少冰淇淋和喝多少水(两个整型的特征向量,不考虑特征重要程度),并记录下他们口中的成都天气感受(非常热A与一般热B)。然后通过采访数据训练一个KNN分类器,新的游客只需要说出特征向量自动判别成都天气冷热程度。创建模拟数据集代码如下:

    '''KNN创建数据源,返回数据集和标签'''
    def create_dataset():
        group = array(random.randint(0,10,size=(4,2))) # 数据集
        labels = ['A','A','B','B'] # 标签
        return group,labels
    

    运行查看数据集的特征向量和分类标签:

    '''1 KNN模拟数据分类算法'''
    dataset,labels = create_dataset()
    print('特征集:\n'+str(dataset))
    print('标签集:\n'+str(labels))
    

    运行结果:

    特征集:
    [[8 4]
     [7 1]
     [1 4]
     [3 0]]
    标签集:
    ['A', 'A', 'B', 'B']
    

    分析解读:

    本段代码没有实际意义,只是帮助读者理解特征向量和分类标签。可以这么理解,A代表非常热,B代表一般热,属性1代表吃冰淇淋数量,属性2代表喝水的数量。那么样本数据可以解读为:

    游客     冰淇淋    喝水    冷热程度        判断描述
    
    小王      8       4       A           小王吃了8个冰淇淋喝了4瓶水,成都天气非常热
    
    小张      7       1       A           小张吃了7个冰淇淋喝了1瓶水,成都天气非常热
    
    小李      1       4       B           小王吃了1个冰淇淋喝了4瓶水,成都天气一般热
    
    小赵      3       0       B           小王吃了3个冰淇淋喝了0瓶水,成都天气一般热
    

    思考:

    计算机是不能直接处理自然语言,往往需要将自然语言转化成特征向量,再通过计算机处理。比如这里不是吃喝看天气情况了,而是垃圾邮件自动识别,我们就需要对邮件转化成数值型特征向量再输入计算机进行处理。

    规范文件数据集处理

    如下是一个规范文件的数据集(已经经过数采集、数据格式化、数据预处理等),特征向量包括3个,样本属于一个多分类的情况。即我们通过周飞行里程数、玩游戏占比、吃冰激凌数量判断一个人的优秀程度。假设1代表普通,2代表比较优秀,3代表非常优秀。(ps:一个人一周都在飞机上度过忙碌的工作,又不太玩游戏,关键还注意饮食,说明优秀是有道理的。)

    周飞行里程数(km)   周玩游戏占比(%)    周消耗冰激凌(公升)        样本分类
    40920                8.326976            0.953952                3
    14488                7.153469            1.673904                2
    26052                1.441871            0.805124                1
    ...                  ...                 ...                    ...
    75136                13.147394           0.428964                1
    38344                1.669788            0.134296                1
    72993                10.141740           1.032955                1
    

    上面是处理好保存在txt文本的数据,计算机如何去识别并处理这些数据呢?这里我们分别提取特征向量和标签向量。数据集处理代码如下:

    '''对文件进行格式处理,便于分类器可以理解'''
    def file_matrix(filename):
        f = open(filename)
        arrayLines = f.readlines()
        returnMat = zeros((len(arrayLines),3))    # 数据集
        classLabelVactor = []                     # 标签集
        index = 0
        for line in arrayLines:
            listFromLine = line.strip().split('    ')    # 分析数据,空格处理
            returnMat[index,:] = listFromLine[0:3]
            classLabelVactor.append(int(listFromLine[-1]))
            index +=1
        return returnMat,classLabelVactor
    

    代码说明:

    1 zeros(Y,X):填充矩阵,需要导入NumPy包。Y向量代表样本行数,X向量代表样本特征数即列数。
    2 returnMat[index,:]:遍历样本特征向量
    

    运行查看数据集的特征向量和分类标签:

    ''' KNN针对文件的分类算法'''
    filename = os.path.abspath(r'./datasource/datingTestSet2.txt')
    dataset,labels = file_matrix(filename)
    print('特征集:\n'+str(dataset))
    print('标签集:\n'+str(labels))
    

    运行结果:

    特征集:
    [[4.0920000e+04 8.3269760e+00 9.5395200e-01]
     [1.4488000e+04 7.1534690e+00 1.6739040e+00]
     [2.6052000e+04 1.4418710e+00 8.0512400e-01]
     ...
     [2.6575000e+04 1.0650102e+01 8.6662700e-01]
     [4.8111000e+04 9.1345280e+00 7.2804500e-01]
     [4.3757000e+04 7.8826010e+00 1.3324460e+00]]
    标签集:
    [3, 2, 1, 1, 1, 1, 3, 3, 1, 3, 1, 1, 2, 1, 1, 
     1, 1, 1, 2, 3, 2, 1, 2, 3, 2, 3, 2, 3, 2, 1, 
     3, 1, 3, 1, 2, 1, 1, 2, 3, 3, 1, 2, 3, 3, 3, 
     ...    
     3, 3, 1, 2, 3, 1, 3, 1, 2, 2, 1, 1, 1, 1, 1]
    

    不规范数据集处理

    这里我们只是提供一个思路。比如做文本分类算法,如何将一篇篇新闻转化为规范的数值型数据集呢。假设Z政治新闻100篇,T体育新闻100篇,Y娱乐新闻100篇,K科技新闻100篇。我们进行分类:

    1 遍历所有文本转化统一的txt格式文件(2.2节会讲到)
    2 对全部ZTYK文本进行分词和停用词处理。
    3 统计全部样本词频尺寸(可以采用TF-IDF或者深度学习方法处理)。
    4 每个样本进行词频统计
    

    最终模拟效果如下:

    样本      词1      词2      词3      词4      ...     词n      标签
    p1       200       0       100      50       ...    20         Z
    p2       100       0       80       40       ...    10         Z
    p3       0         100     5        5        ...    200        T
    p4       6         230     40       12       ...    670        T
    p5       0         2       110      57       ...    234        Y
    ...      ...       ...     ...      ...      ...    ...        ...
    pn       123       45      0        580      ...    24         K
    

    2.2 数据格式化

    数据文件转化

    自然语言处理、数据挖掘、机器学习技术应用愈加广泛。针对大数据的预处理工作是一项庞杂、棘手的工作。首先数据采集和存储,尤其高质量数据采集往往不是那么简单。采集后的信息文件格式不一,诸如pdf,doc,docx,Excel,ppt等多种形式。然而最常见便是txt、pdf和word类型的文档。这里所谓格式转化主要对pdf和word文档进行文本格式转换成txt。格式一致化以后再进行后续预处理工作。具体详情请参照之前写的数据分析:基于Python的自定义文件格式转换系统一文。

    文件格式化处理

    这里可以采用多种方式,诸如上文提到的矩阵填充法,当然也可以采用现成的工具。比如百度的Echarts中表格数据转换工具。其支持纯数组的转换,数组+对象,地理坐标等方式,还支持json数据的转化,这对使用百度EChart可视化是非常友好的,也有助于可视化数据分析。文本数据格式效果如下图:

    图2-1 文本数据表格转化

    [
        ['40920    8.326976    0.953952    3'],
        ['14488    7.153469    1.673904    2'],
        ['26052    1.441871    0.805124    1'],
        ['75136    13.147394    0.428964    1'],
        ['38344    1.669788    0.134296    1'],
        ['72993    10.141740    1.032955    1'],
        ...
        ['35948    6.830792    1.213192    3'],
        ['42666    13.276369    0.543880    3'],
        ['67497    8.631577    0.749278    1'],
        ['35483    12.273169    1.508053    3'],
        ['50242    3.723498    0.831917    1'],
        ['63275    8.385879    1.669485    1'],
        ['5569    4.875435    0.728658    2'],
        ['15669    0.000000    1.250185    2'],
        ['28488    10.528555    1.304844    3'],
        ['6487    3.540265    0.822483    2'],
        ['37708    2.991551    0.833920    1']
    ]
    

    2.3 数据归一化

    数据归一化

    机器学习、数据挖掘、自然语言处理等数据科学工作中,数据前期准备、数据预处理过程、特征提取等几个步骤比较花费时间。同时,数据预处理的效果也直接影响了后续模型能否有效的工作。然而,目前的很多研究主要集中在模型的构建、优化等方面,对数据预处理的理论研究甚少,很多数据预处理工作仍然是靠工程师的经验进行的。也不是所有数据都需要归一化,诸如

    1.  数据类型一致且分布均匀。
    2.  概率模型可以不做归一化,如决策树。
    

    数据归一化优点

    1. 归一化后加快了梯度下降求最优解的速度;
    2. 归一化有可能提高精度;
    

    归一化方法

    1 sklearn线性归一化

    # 线性函数将原始数据线性化的方法转换到[0, 1]的范围   
    min_max_scaler = preprocessing.MinMaxScaler()
    X_train_minmax = min_max_scaler.fit_transform(X_train)
    X_test_minmax = min_max_scaler.transform(X_test)
    

    2 标准差标准化

    # 经过处理的数据符合标准正态分布,即均值为0,标准差为1,其转化函数为:
    scaler = preprocessing.StandardScaler().fit(X_train)
    scaler.transform(X_test)
    

    3 非线性归一化

    经常用在数据分化比较大的场景,有些数值很大,有些很小。通过一些数学函数,将原始值进行映射。该方法包括 log、指数,正切等。需要根据数据分布的情况,决定非线性函数的曲线,比如log(V, 2)还是log(V, 10)等。

    线性归一化方法代码实现

    '''数值归一化:特征值转化为0-1之间:newValue = (oldValue-min)/(max-min)'''
    def norm_dataset(dataset):
        minVals = dataset.min(0)  # 参数0是取得列表中的最小值,而不是行中最小值
        maxVals = dataset.max(0)
        ranges = maxVals - minVals
        normdataset = zeros(shape(dataset)) # 生成原矩阵一样大小的0矩阵
    
        m = dataset.shape[0]
        # tile:复制同样大小的矩阵
        molecular = dataset - tile(minVals,(m,1))  # 分子: (oldValue-min)
        Denominator = tile(ranges,(m,1))           # 分母:(max-min)
        normdataset = molecular/Denominator     # 归一化结果。
    
        return normdataset,ranges,minVals
    

    数据归一化前:

    归一化的数据结果:
    [[4.0920000e+04 8.3269760e+00 9.5395200e-01]
     [1.4488000e+04 7.1534690e+00 1.6739040e+00]
     [2.6052000e+04 1.4418710e+00 8.0512400e-01]
     ...
     [2.6575000e+04 1.0650102e+01 8.6662700e-01]
     [4.8111000e+04 9.1345280e+00 7.2804500e-01]
     [4.3757000e+04 7.8826010e+00 1.3324460e+00]]
    

    展开第一条信息“40920 8.326976 0.953952 3”,其中里程40000多,而公升数才0.9.两者根本不在同一个数量级上面,也就是说,如果特征属性相同的情况下,公升数即使变动100倍对里程数的影响也微乎其微。而里程数轻微变化就直接影响公升数的结果。所以我们将其放在同一尺度下进行处理,也就是本文采用的线性缩放方,数据归一化后结果如下:

    归一化的数据结果:
    [[0.44832535 0.39805139 0.56233353]
     [0.15873259 0.34195467 0.98724416]
     [0.28542943 0.06892523 0.47449629]
     ...
     [0.29115949 0.50910294 0.51079493]
     [0.52711097 0.43665451 0.4290048 ]
     [0.47940793 0.3768091  0.78571804]]
    

    分析:

    经过上述归一化处理后,各个特征指标都是0-1这样一个范畴中进行比较。当然实际工作中不同特征的权重不同,这个可以通过增加权重方法处理即可,本文不在进行深入讨论。

    2.4 数据分析

    基于matplotlib的可视化分析

    我们对数据处理后,很不容易进行数据分析。毕竟密密麻麻的数字略显冰冷无趣。我们可以将其可视化展示出来,进而查看数据稀疏程度,离散程度等等。我们查看'玩游戏所耗时间百分比','每周消耗在冰淇淋的公升数'两个属性的散点图,实现代码如下:

    '''
    散列表分析数据:
    dataset:数据集
    datingLabels:标签集
    Title:列表,标题、横坐标标题、纵坐标标题。
    '''
    def analyze_data_plot(dataset,datingLabels,Title):
        fig = plt.figure()
        # 将画布划分为1行1列1块
        ax = fig.add_subplot(111)
        ax.scatter(dataset[:,1],dataset[:,2],15.0*array(datingLabels),15.0*array(datingLabels))
    
         # 设置散点图标题和横纵坐标标题
        plt.title(Title[0],fontsize=25,fontname='宋体',fontproperties=myfont)
        plt.xlabel(Title[1],fontsize=15,fontname='宋体',fontproperties=myfont)
        plt.ylabel(Title[2],fontsize=15,fontname='宋体',fontproperties=myfont)
    
        # 设置刻度标记大小,axis='both'参数影响横纵坐标,labelsize刻度大小
        plt.tick_params(axis='both',which='major',labelsize=10)
    
        # 设置每个坐标轴取值范围
        # plt.axis([-1,25,-1,2.0])
    
        # 截图保存图片
        # plt.savefig('datasets_plot.png',bbox_inches='tight')
    
        # 显示图形
        plt.show()
    

    这里注意一个问题,横纵坐标是乱码显示,解决这个问题,添加如下代码:

    #加入中文显示
    import  matplotlib.font_manager as fm
    # 解决中文乱码,本案例使用宋体字
    myfont=fm.FontProperties(fname=r"C:\\Windows\\Fonts\\simsun.ttc")
    

    调用可视化数据分析方法如下:

    ''' 文件数据图形化分析数据 '''
    dataset,labels = file_matrix(filename)
    noredataset = norm_dataset(dataset)[0] # 数据归一化
    title = ['约会数据游戏和饮食散列点','玩游戏所耗时间百分比','每周消耗在冰淇淋的公升数']
    visualplot.analyze_data_plot(noredataset,labels,title)
    

    游戏占比与冰淇淋公升数关系散点图可视化:

    图2-2 游戏占比与冰淇淋公升数关系散点图

    折线图代码实现如下:

    '''折线图'''
    def line_chart(xvalues,yvalues):
        # 绘制折线图,c颜色设置,alpha透明度
        plt.plot(xvalues,yvalues,linewidth=0.5,alpha=0.5,c='red') # num_squares数据值,linewidth设置线条粗细
    
        # 设置折线图标题和横纵坐标标题
        plt.title("Python绘制折线图",fontsize=30,fontname='宋体',fontproperties=myfont)
        plt.xlabel('横坐标',fontsize=20,fontname='宋体',fontproperties=myfont)
        plt.ylabel('纵坐标',fontsize=20,fontname='宋体',fontproperties=myfont)
    
        # 设置刻度标记大小,axis='both'参数影响横纵坐标,labelsize刻度大小
        plt.tick_params(axis='both',labelsize=14)
    
        # 显示图形
        plt.show()
    

    游戏占比与冰淇淋公升数关系折线图可视化:(此处折线图明显不合适,只是突出另一种分析方式。)

    图2-3 游戏占比与冰淇淋公升数关系折线图

    扩展:

    更多matplotlib可视化实现效果图参考文章 70个注意的Python小Notes:完整的matplotlib可视化

    基于Echart的可视化分析

    我们上面采用的matplotlib可视化效果,采用该方式主要是结合python数据分析绑定比较方便。有些时候我们为了取得更加漂亮的可视化效果,可以选择百度echart进行分析,百度Echart使用简单且文档规范容易上手。我们对原数据进行分析并转化为json代码:

    '''array数据转化json'''
    def norm_Json(dataset):
        noredataset = norm_dataset(dataset)[0] # 数据归一化
        number1 = np.around(noredataset[:,1], decimals=4) # 获取数据集第二列
        number2 = np.around(noredataset[:,2], decimals=4) # 获取数据集第三列
        returnMat=zeros((dataset.shape[0],2))             # 二维矩阵
        returnMat[:,0] = number1
        returnMat[:,1] = number2
    
        file_path = os.path.abspath(r"./datasource/test.json")
        json.dump(returnMat.tolist(), codecs.open(file_path, 'w', encoding='utf-8'), separators=(',', ':'), sort_keys=True, indent=4)
    

    生成json数据保存在指定文件中,打开文件查看数据如下:

    [
        [
            0.3981,
            0.5623
        ],
        [
            0.342,
            0.9872
        ],
        [
            0.0689,
            0.4745
        ],
        [
            0.6285,
            0.2525
        ]
        ...
        [
            0.4367,
            0.429
        ],
        [
            0.3768,
            0.7857
        ]
    ]
    

    从百度Echart实例中选择一种散点图并绑定json文件,其html代码如下:

    <!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>图案例</title>
        <script src="https://cdn.bootcss.com/jquery/2.2.0/jquery.min.js"></script>
        <script type="text/javascript" src="./js/echarts.js"></script>
    </head>
    <body>
        <div id="chartmain" style="width:800px; height: 400px; margin:auto; ">
        </div>
    
        <script type="text/javascript">
            //初始化echarts实例
            var myChart = echarts.init(document.getElementById('chartmain'));
            $.getJSON('game-food.json', function (data) {
            var option = {
                title: {
                    text: '玩游戏时间占比和饮食数据描述',
                    left: 'center',
                    top: 0
                },
                visualMap: {
                    min: 15202,
                    max: 159980,
                    dimension: 1,
                    orient: 'vertical',
                    right: 10,
                    top: 'center',
                    text: ['优秀', '一般'],
                    calculable: true,
                    inRange: {
                        color: ['#f2c31a', '#24b7f2']
                    }
                },
                tooltip: {
                    trigger: 'item',
                    axisPointer: {
                        type: 'cross'
                    }
                },
                xAxis: [{
                    type: 'value'
                }],
                yAxis: [{
                    type: 'value'
                }],
                series: [{
                    name: 'price-area',
                    type: 'scatter',
                    symbolSize: 5,
                    data: data
                }]
            };
            myChart.setOption(option);
    });
        </script>
    </body>
    </html>
    

    json文件读取需要在web运行环境中,单纯的运行效果如下图所示:

     

    图2-4 游戏占比与冰淇淋公升数Echarts关系散点图

    数据转化工具

    本文采用自己构建的方式进行json文件生成,此外我们也可以采用现有的数据转化工具进行处理。比如百度的表格数据转化工具(2.2节已经介绍了)。

    另一个便是在线json验证格式工具:http://www.bejson.com/

    2.5 KNN分类器实现

    通过数据分析,我们查看数据样本是否偏态分别,数据规模情况等等。针对性进行数据预处理后,编写具体算法模型。本文主要是KNN分类器,其代码如下:

    ''' 构造KNN分类器
        vecX:输入向量,待测数据
        filename: 特征集文件路径
        isnorm:是否进行归一化处理
        k:k值的选择,默认选择3
    '''
    def knn_classifier(vecX,dataset,labels,isnorm='Y',k=3):
        # 距离计算(方法1)
        if isnorm == 'Y':
            normMat,ranges,minVals = norm_dataset(dataset)     # 对数据进行归一化处理
            normvecX = norm_dataset(vecX)
        else:
            normMat = dataset
            normvecX = vecX
    
        m = normMat.shape[0]
        # tile方法是在列向量vecX,datasetSize次,行向量vecX1次叠加
        diffMat = tile(normvecX,(m,1)) - normMat
        sqDiffMat = diffMat ** 2
        sqDistances = sqDiffMat.sum(axis=1)   # axis=0 是列相加,axis=1是行相加
        distances = sqDistances**0.5
        # print('vecX向量到数据集各点距离:\n'+str(distances))
    
        sortedDistIndexs = distances.argsort(axis=0)  # 距离排序,升序
        # print(sortedDistIndicies)
    
        classCount = {}   # 统计前k个类别出现频率
        for i in range(k):
            votelabel = labels[sortedDistIndexs[i]]
            classCount[votelabel] = classCount.get(votelabel,0) + 1 #统计键值
        # 类别频率出现最高的点,itemgetter(0)按照key排序,itemgetter(1)按照value排序
        sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
        print(str(vecX)+'KNN的投票决策结果:\n'+str(sortedClassCount[0][0]))
        return sortedClassCount[0][0]
    

    3 KNN算法模型评估

    3.1 评价指标介绍

    基本知识

    混淆矩阵:正元组和负元组的合计

    图3-1 混淆矩阵表

    评估度量:(其中P:正样本数 N:负样本数 TP:真正例 TN:真负例 FP:假正例 FN:假负例)

    图3-2 评估信息度量表

    注意:学习器的准确率最好在检验集上估计,检验集的由训练集模型时未使用的含有标记的元组组成数据。

    各参数描述如下:

    TP(真正例/真阳性):是指被学习器正确学习的正元组,令TP为真正例的个数。

    TN(真负例/真阴性):是指被学习器正确学习的负元组,令TN为真负例的个数。

    FP(假正例/假阳性):是被错误的标记为正元组的负元组。令FP为假正例的个数。

    FN(假负例/假阴性):是被错误的标记为负元组的正元组。令FN为假负例的个数。

    准确率:正确识别的元组所占的比例。

    评价指标优点

    一般采用精确率和召回率作为度量的方法具有以下几个优点:

    (1) 准确率数值对于小数据不是特别敏感,而精确率和召回率对于这样数据比较敏感。 (2) 在相同实验环境下,F度量这种倾向和我们直观感觉是一致的,我们对目标事件很敏感,甚至返回一些垃圾数据也在所不惜。 (3) 通过精确率和找回来衡量目标事件和垃圾事件的差异。

    模型评估拓展

    参见《自然语言处理理论与实战》一书第13章模型评估

    3.2 评估算法模型实现

    本文只是对错误率进行评估,其也是knn分类器核心指标,实现代码如下:

    '''测试评估算法模型'''
    def test_knn_perfor(filename):
        hoRatio = 0.1
        dataset,label = file_matrix(filename)              # 获取训练数据和标签
        normMat,ranges,minVals = norm_dataset(dataset)     # 对数据进行归一化处理
        m = normMat.shape[0]
        numTestVecs = int(m*hoRatio)                       # 10%的测试数据条数
    
        errorCount = 0.0                                   # 统计错误分类数
        for i in range(numTestVecs):
            classifierResult = knn_classifier(normMat[i,:],normMat[numTestVecs:m,:],label[numTestVecs:m],3)          # 此处分类器可以替换不同分类模型
            print('分类结果:'+str(classifierResult)+'\t\t准确结果:'+str(label[i]))
    
            if classifierResult != label[i]:
                errorCount += 1.0
            Global.all_FileNum += 1
        print('总的错误率为:'+str(errorCount/float(numTestVecs))+"\n总测试数据量: "+str(Global.all_FileNum))
    

    运行效果如下:

    [0.44832535 0.39805139 0.56233353]KNN的投票决策结果:
    分类结果:3      准确结果:3
    [0.15873259 0.34195467 0.98724416]KNN的投票决策结果:
    分类结果:2      准确结果:2
    ...
    分类结果:3      准确结果:3
    [0.19385799 0.30474213 0.01919426]KNN的投票决策结果:
    分类结果:2      准确结果:2
    [0.24463971 0.10813023 0.60259472]KNN的投票决策结果:
    分类结果:1      准确结果:1
    [0.51022756 0.27138082 0.41804137]KNN的投票决策结果:
    分类结果:3      准确结果:1
    
    总的错误率为:0.05
    总测试数据量: 100
    耗时:0.0300 s
    

    评估结果分析:

    本文采用封闭评估的方法,前100条数据作为测试集,后900条数据作为训练集。如上结果最后一条信息表明knn分类器的结果是3,而标准结果是1.knn分类存在错误。将所有错误占比分析出来即错误率。本文错误率5%,即准确率95%.

    读者可以选取200:800、300:700等等数据进行测试查看错误率。

    4 KNN算法模型的实际应用

    knn分类器应用

    经过如上的改进最终形成实际应用的算法模型API开发给外部程序使用,调用knn算法代码如下:

    '''调用可用算法'''
    def show_classifyPerson(filename):
        resultlist = ['不喜欢','还可以','特别喜欢']
        ffMiles = float(input('每年飞行的历程多少公里?\n'))
        percentTats = float(input('玩游戏时间占百分比多少?\n')) # [751,13,0.4][40920 ,8.326976,0.953952]
        iceCream = float(input('每周消费冰淇淋多少公升?\n'))
    
        dataset,labels = file_matrix(filename) # 数据格式化处理
        inArr = array([ffMiles,percentTats,iceCream])
    
        classifierResult = knn_classifier(inArr,dataset,labels,3) # 数据归一化并进行分类
        print('预测的约会结果是:'+resultlist[classifierResult-1])
    

    运行结果如下:

    每年飞行的历程多少公里?
    10000
    玩游戏时间占百分比多少?
    10
    每周消费冰淇淋多少公升?
    0.5
    KNN的投票决策结果:
    2
    预测的约会结果是:还可以
    

    展望

    我们还可以采用knn分类器进行实际应用,比如新闻分类系统。大致思路如下:

    1 采集数据:选用复旦大学的文本分类新闻语料 2 准备数据:数据格式化、分词、停用词处理等 3 分析数据:看看数据特点,有没有缺失值,数据连续性还是离散型,进而选择不同模型。诸如:可视化数据分析 4 数据转化:采用IF-IDF或者神经网络的方法对词频进行处理,最终转化为机器可以处理的数值型矩阵。 5 构建模型:KNN新闻分类器模型构建。 6 测试算法:评价指标,如计算错误率,准确率,召回率,F度量值等。 7 应用算法:针对完善的模型进行封装重构,然后进行实际的新闻分类应用。

    5 参考文献

    1. 归一化学习:https://blog.csdn.net/hyq3235356/article/details/78472307
    2. 归一化方法:https://blog.csdn.net/zxd1754771465/article/details/73558103
    3. 百度Echart转化工具:http://echarts.baidu.com/spreadsheet.html
    4. 在线json验证格式工具:http://www.bejson.com/
    5. 模型评估:http://www.cnblogs.com/baiboy/p/mxpg2.html

    完整代码下载

    机器学习和自然语言QQ群:436303759。 微信公众号:datathinks

    自然语言处理和机器学习QQ交流群:436303759自然语言处理和机器学习微信公众号:datathinks

    源码请进QQ群文件下载:

    作者声明

    本文版权归作者所有,旨在技术交流使用。未经作者同意禁止转载,转载后需在文章页面明显位置给出原文连接,否则相关责任自行承担。转载必须注明出处【伏草惟存】:一步步教你轻松学KNN模型算法

     

     

     

     

    展开全文
  • KNN模型算法研究与案例分析( 白宁超2018年8月29日15:39:13 ) 导读:机器学习算法KNN属于比较简单的典型算法,既可以做聚类又可以做分类使用。本文通过一个模拟的实际案例进行讲解。整个流程包括:采集数据、数据...

    KNN模型算法研究与案例分析( 白宁超 2018年8月29日15:39:13 )

    导读:机器学习算法中KNN属于比较简单的典型算法,既可以做聚类又可以做分类使用。本文通过一个模拟的实际案例进行讲解。整个流程包括:采集数据、数据格式化处理、数据分析、数据归一化处理、构造算法模型、评估算法模型和算法模型的应用。(本文原创,转载必须注明出处: KNN模型算法研究与案例分析

    1 理论介绍

    什么是KNN?

           k-近邻(kNN,k-NearestNeighbor)算法是一种基本分类与回归方法,我们这里只讨论分类问题中的 k-近邻算法。k-近邻算法的输入为实例的特征向量,对应于特征空间的点;输出为实例的类别,可以取多类。k-邻算法假设给定一个训练数据集,其中的实例类别已定。分类时,对新的实例,根据其 k 个最近邻的训练实例的类别,通过多数表决等方式进行预测。因此,k近邻算法不具有显式的学习过程即属于有监督学习范畴。k近邻算法实际上利用训练数据集对特征向量空间进行划分,并作为其分类的“模型”。k值的选择、距离度量以及分类决策规则是k近邻算法的三个基本要素。

    KNN算法思想

    1 计算已知类别中数据集的点与当前点的距离。[即计算所有样本点跟待分类样本之间的距离]
    2 按照距离递增次序排序。[计算完样本距离进行排序]
    3 选取与当前点距离最小的k个点。[选取距离样本最近的k个点]
    4 确定前k个点所在类别的出现频率。[针对这k个点,统计下各个类别分别有多少个]
    5 返回前k个点出现频率最高的类别作为当前点的预测分类。[k个点中某个类别最多,就将样本划归改点]
    

    KNN工作原理

    1 假设有一个带有标签的样本数据集(训练样本集),其中包含每条数据与所属分类的对应关系。
    2 输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较。
    3 计算新数据与样本数据集中每条数据的距离。
    4 对求得的所有距离进行排序(从小到大,越小表示越相似)。
    5 取前 k (k 一般小于等于 20 )个样本数据对应的分类标签。
    6 求 k 个数据中出现次数最多的分类标签作为新数据的分类。
    

    KNN算法流程

    1 搜集数据:数据采集过程,其分为非结构化数据,半结构化数据和数据化数据。诸如:网络爬取,数据库,文件等。
    2 准备数据:格式化处理,对不同类别的数据进行统一的格式化处理。诸如:将pdf,word,excel,sql等等统一转化为txt文本。
    3 分析数据:主要看看数据特点,有没有缺失值,数据连续性还是离散型,进而选择不同模型。诸如:可视化数据分析
    4 训练数据:不适用于KNN,但是在其他一些监督学习中会经常遇到,诸如:朴素贝叶斯分类等。
    5 测试算法:评价指标,如计算错误率,准确率,召回率,F度量值等。
    6 应用算法:针对完善的模型进行封装重构,然后进行实际应用。
    

    KNN优缺点

    优点:精度高、对异常值不敏感、无数据输入假定
    缺点:计算复杂度高、空间复杂度好
    适用数据范围:数值型和标称型
    

    2 KNN算法实现与分析

    2.1 数据准备

    创建模拟数据集

    描述:现在你来了一个新的任务,任务其实非常简单,就是根据吃冰淇淋和喝水的数量判断成都天气冷热程度。你现在要做的就是去成都春熙路街头采访记录一些游客吃了多少冰淇淋,又喝了几瓶水,他觉得成都天气怎么样(这里只考虑二分类问题,假设只有‘非常热’和‘一般热’)。其中特征向量包括两个分别是冰激凌数t1和喝水数t2,标签类别分别是非常热A和一般热B。

    现在我们开始行动,随机采访4个游客(暂时不考虑样本数量问题),询问每个游客吃多少冰淇淋和喝多少水(两个整型的特征向量,不考虑特征重要程度),并记录下他们口中的成都天气感受(非常热A与一般热B)。然后通过采访数据训练一个KNN分类器,新的游客只需要说出特征向量自动判别成都天气冷热程度。创建模拟数据集代码如下:

    '''KNN创建数据源,返回数据集和标签'''
    def create_dataset():
        group = array(random.randint(0,10,size=(4,2))) # 数据集
        labels = ['A','A','B','B'] # 标签
        return group,labels
    

    运行查看数据集的特征向量和分类标签:

    '''1 KNN模拟数据分类算法'''
    dataset,labels = create_dataset()
    print('特征集:\n'+str(dataset))
    print('标签集:\n'+str(labels))
    

    运行结果:

    特征集:
    [[8 4]
     [7 1]
     [1 4]
     [3 0]]
    标签集:
    ['A', 'A', 'B', 'B']
    

    分析解读:

    本段代码没有实际意义,只是帮助读者理解特征向量和分类标签。可以这么理解,A代表非常热,B代表一般热,属性1代表吃冰淇淋数量,属性2代表喝水的数量。那么样本数据可以解读为:

    游客     冰淇淋    喝水    冷热程度        判断描述
    
    小王      8       4       A           小王吃了8个冰淇淋喝了4瓶水,成都天气非常热
    
    小张      7       1       A           小张吃了7个冰淇淋喝了1瓶水,成都天气非常热
    
    小李      1       4       B           小王吃了1个冰淇淋喝了4瓶水,成都天气一般热
    
    小赵      3       0       B           小王吃了3个冰淇淋喝了0瓶水,成都天气一般热
    

    思考:

    计算机是不能直接处理自然语言,往往需要将自然语言转化成特征向量,再通过计算机处理。比如这里不是吃喝看天气情况了,而是垃圾邮件自动识别,我们就需要对邮件转化成数值型特征向量再输入计算机进行处理。

    规范文件数据集处理

    如下是一个规范文件的数据集(已经经过数采集、数据格式化、数据预处理等),特征向量包括3个,样本属于一个多分类的情况。即我们通过周飞行里程数、玩游戏占比、吃冰激凌数量判断一个人的优秀程度。假设1代表普通,2代表比较优秀,3代表非常优秀。(ps:一个人一周都在飞机上度过忙碌的工作,又不太玩游戏,关键还注意饮食,说明优秀是有道理的。)

    周飞行里程数(km)   周玩游戏占比(%)    周消耗冰激凌(公升)        样本分类
    40920                8.326976            0.953952                3
    14488                7.153469            1.673904                2
    26052                1.441871            0.805124                1
    ...                  ...                 ...                    ...
    75136                13.147394           0.428964                1
    38344                1.669788            0.134296                1
    72993                10.141740           1.032955                1
    

    上面是处理好保存在txt文本的数据,计算机如何去识别并处理这些数据呢?这里我们分别提取特征向量和标签向量。数据集处理代码如下:

    '''对文件进行格式处理,便于分类器可以理解'''
    def file_matrix(filename):
        f = open(filename)
        arrayLines = f.readlines()
        returnMat = zeros((len(arrayLines),3))    # 数据集
        classLabelVactor = []                     # 标签集
        index = 0
        for line in arrayLines:
            listFromLine = line.strip().split('    ')    # 分析数据,空格处理
            returnMat[index,:] = listFromLine[0:3]
            classLabelVactor.append(int(listFromLine[-1]))
            index +=1
        return returnMat,classLabelVactor
    

    代码说明:

    1 zeros(Y,X):填充矩阵,需要导入NumPy包。Y向量代表样本行数,X向量代表样本特征数即列数。
    2 returnMat[index,:]:遍历样本特征向量
    

    运行查看数据集的特征向量和分类标签:

    ''' KNN针对文件的分类算法'''
    filename = os.path.abspath(r'./datasource/datingTestSet2.txt')
    dataset,labels = file_matrix(filename)
    print('特征集:\n'+str(dataset))
    print('标签集:\n'+str(labels))
    

    运行结果:

    特征集:
    [[4.0920000e+04 8.3269760e+00 9.5395200e-01]
     [1.4488000e+04 7.1534690e+00 1.6739040e+00]
     [2.6052000e+04 1.4418710e+00 8.0512400e-01]
     ...
     [2.6575000e+04 1.0650102e+01 8.6662700e-01]
     [4.8111000e+04 9.1345280e+00 7.2804500e-01]
     [4.3757000e+04 7.8826010e+00 1.3324460e+00]]
    标签集:
    [3, 2, 1, 1, 1, 1, 3, 3, 1, 3, 1, 1, 2, 1, 1, 
     1, 1, 1, 2, 3, 2, 1, 2, 3, 2, 3, 2, 3, 2, 1, 
     3, 1, 3, 1, 2, 1, 1, 2, 3, 3, 1, 2, 3, 3, 3, 
     ...    
     3, 3, 1, 2, 3, 1, 3, 1, 2, 2, 1, 1, 1, 1, 1]
    

    不规范数据集处理

    这里我们只是提供一个思路。比如做文本分类算法,如何将一篇篇新闻转化为规范的数值型数据集呢。假设Z政治新闻100篇,T体育新闻100篇,Y娱乐新闻100篇,K科技新闻100篇。我们进行分类:

    1 遍历所有文本转化统一的txt格式文件(2.2节会讲到)
    2 对全部ZTYK文本进行分词和停用词处理。
    3 统计全部样本词频尺寸(可以采用TF-IDF或者深度学习方法处理)。
    4 每个样本进行词频统计
    

    最终模拟效果如下:

    样本      词1      词2      词3      词4      ...     词n      标签
    p1       200       0       100      50       ...    20         Z
    p2       100       0       80       40       ...    10         Z
    p3       0         100     5        5        ...    200        T
    p4       6         230     40       12       ...    670        T
    p5       0         2       110      57       ...    234        Y
    ...      ...       ...     ...      ...      ...    ...        ...
    pn       123       45      0        580      ...    24         K
    

    2.2 数据格式化

    数据文件转化

    自然语言处理、数据挖掘、机器学习技术应用愈加广泛。针对大数据的预处理工作是一项庞杂、棘手的工作。首先数据采集和存储,尤其高质量数据采集往往不是那么简单。采集后的信息文件格式不一,诸如pdf,doc,docx,Excel,ppt等多种形式。然而最常见便是txt、pdf和word类型的文档。这里所谓格式转化主要对pdf和word文档进行文本格式转换成txt。格式一致化以后再进行后续预处理工作。具体详情请参照之前写的数据分析:基于Python的自定义文件格式转换系统一文。

    文件格式化处理

    这里可以采用多种方式,诸如上文提到的矩阵填充法,当然也可以采用现成的工具。比如百度的Echarts中表格数据转换工具。其支持纯数组的转换,数组+对象,地理坐标等方式,还支持json数据的转化,这对使用百度EChart可视化是非常友好的,也有助于可视化数据分析。文本数据格式效果如下图:

    图2-1 文本数据表格转化

    [
        ['40920    8.326976    0.953952    3'],
        ['14488    7.153469    1.673904    2'],
        ['26052    1.441871    0.805124    1'],
        ['75136    13.147394    0.428964    1'],
        ['38344    1.669788    0.134296    1'],
        ['72993    10.141740    1.032955    1'],
        ...
        ['35948    6.830792    1.213192    3'],
        ['42666    13.276369    0.543880    3'],
        ['67497    8.631577    0.749278    1'],
        ['35483    12.273169    1.508053    3'],
        ['50242    3.723498    0.831917    1'],
        ['63275    8.385879    1.669485    1'],
        ['5569    4.875435    0.728658    2'],
        ['15669    0.000000    1.250185    2'],
        ['28488    10.528555    1.304844    3'],
        ['6487    3.540265    0.822483    2'],
        ['37708    2.991551    0.833920    1']
    ]
    

    2.3 数据归一化

    数据归一化

    机器学习、数据挖掘、自然语言处理等数据科学工作中,数据前期准备、数据预处理过程、特征提取等几个步骤比较花费时间。同时,数据预处理的效果也直接影响了后续模型能否有效的工作。然而,目前的很多研究主要集中在模型的构建、优化等方面,对数据预处理的理论研究甚少,很多数据预处理工作仍然是靠工程师的经验进行的。也不是所有数据都需要归一化,诸如

    1.  数据类型一致且分布均匀。
    2.  概率模型可以不做归一化,如决策树。
    

    数据归一化优点

    1. 归一化后加快了梯度下降求最优解的速度;
    2. 归一化有可能提高精度;
    

    归一化方法

    1 sklearn线性归一化

    # 线性函数将原始数据线性化的方法转换到[0, 1]的范围   
    min_max_scaler = preprocessing.MinMaxScaler()
    X_train_minmax = min_max_scaler.fit_transform(X_train)
    X_test_minmax = min_max_scaler.transform(X_test)
    

    2 标准差标准化

    # 经过处理的数据符合标准正态分布,即均值为0,标准差为1,其转化函数为:
    scaler = preprocessing.StandardScaler().fit(X_train)
    scaler.transform(X_test)
    

    3 非线性归一化

    经常用在数据分化比较大的场景,有些数值很大,有些很小。通过一些数学函数,将原始值进行映射。该方法包括 log、指数,正切等。需要根据数据分布的情况,决定非线性函数的曲线,比如log(V, 2)还是log(V, 10)等。

    线性归一化方法代码实现

    '''数值归一化:特征值转化为0-1之间:newValue = (oldValue-min)/(max-min)'''
    def norm_dataset(dataset):
        minVals = dataset.min(0)  # 参数0是取得列表中的最小值,而不是行中最小值
        maxVals = dataset.max(0)
        ranges = maxVals - minVals
        normdataset = zeros(shape(dataset)) # 生成原矩阵一样大小的0矩阵
    
        m = dataset.shape[0]
        # tile:复制同样大小的矩阵
        molecular = dataset - tile(minVals,(m,1))  # 分子: (oldValue-min)
        Denominator = tile(ranges,(m,1))           # 分母:(max-min)
        normdataset = molecular/Denominator     # 归一化结果。
    
        return normdataset,ranges,minVals
    

    数据归一化前:

    归一化的数据结果:
    [[4.0920000e+04 8.3269760e+00 9.5395200e-01]
     [1.4488000e+04 7.1534690e+00 1.6739040e+00]
     [2.6052000e+04 1.4418710e+00 8.0512400e-01]
     ...
     [2.6575000e+04 1.0650102e+01 8.6662700e-01]
     [4.8111000e+04 9.1345280e+00 7.2804500e-01]
     [4.3757000e+04 7.8826010e+00 1.3324460e+00]]
    

    展开第一条信息“40920 8.326976 0.953952 3”,其中里程40000多,而公升数才0.9.两者根本不在同一个数量级上面,也就是说,如果特征属性相同的情况下,公升数即使变动100倍对里程数的影响也微乎其微。而里程数轻微变化就直接影响公升数的结果。所以我们将其放在同一尺度下进行处理,也就是本文采用的线性缩放方,数据归一化后结果如下:

    归一化的数据结果:
    [[0.44832535 0.39805139 0.56233353]
     [0.15873259 0.34195467 0.98724416]
     [0.28542943 0.06892523 0.47449629]
     ...
     [0.29115949 0.50910294 0.51079493]
     [0.52711097 0.43665451 0.4290048 ]
     [0.47940793 0.3768091  0.78571804]]
    

    分析:

    经过上述归一化处理后,各个特征指标都是0-1这样一个范畴中进行比较。当然实际工作中不同特征的权重不同,这个可以通过增加权重方法处理即可,本文不在进行深入讨论。

    2.4 数据分析

    基于matplotlib的可视化分析

    我们对数据处理后,很不容易进行数据分析。毕竟密密麻麻的数字略显冰冷无趣。我们可以将其可视化展示出来,进而查看数据稀疏程度,离散程度等等。我们查看'玩游戏所耗时间百分比','每周消耗在冰淇淋的公升数'两个属性的散点图,实现代码如下:

    '''
    散列表分析数据:
    dataset:数据集
    datingLabels:标签集
    Title:列表,标题、横坐标标题、纵坐标标题。
    '''
    def analyze_data_plot(dataset,datingLabels,Title):
        fig = plt.figure()
        # 将画布划分为1行1列1块
        ax = fig.add_subplot(111)
        ax.scatter(dataset[:,1],dataset[:,2],15.0*array(datingLabels),15.0*array(datingLabels))
    
         # 设置散点图标题和横纵坐标标题
        plt.title(Title[0],fontsize=25,fontname='宋体',fontproperties=myfont)
        plt.xlabel(Title[1],fontsize=15,fontname='宋体',fontproperties=myfont)
        plt.ylabel(Title[2],fontsize=15,fontname='宋体',fontproperties=myfont)
    
        # 设置刻度标记大小,axis='both'参数影响横纵坐标,labelsize刻度大小
        plt.tick_params(axis='both',which='major',labelsize=10)
    
        # 设置每个坐标轴取值范围
        # plt.axis([-1,25,-1,2.0])
    
        # 截图保存图片
        # plt.savefig('datasets_plot.png',bbox_inches='tight')
    
        # 显示图形
        plt.show()
    

    这里注意一个问题,横纵坐标是乱码显示,解决这个问题,添加如下代码:

    #加入中文显示
    import  matplotlib.font_manager as fm
    # 解决中文乱码,本案例使用宋体字
    myfont=fm.FontProperties(fname=r"C:\\Windows\\Fonts\\simsun.ttc")
    

    调用可视化数据分析方法如下:

    ''' 文件数据图形化分析数据 '''
    dataset,labels = file_matrix(filename)
    noredataset = norm_dataset(dataset)[0] # 数据归一化
    title = ['约会数据游戏和饮食散列点','玩游戏所耗时间百分比','每周消耗在冰淇淋的公升数']
    visualplot.analyze_data_plot(noredataset,labels,title)
    

    游戏占比与冰淇淋公升数关系散点图可视化:

    图2-2 游戏占比与冰淇淋公升数关系散点图

    折线图代码实现如下:

    '''折线图'''
    def line_chart(xvalues,yvalues):
        # 绘制折线图,c颜色设置,alpha透明度
        plt.plot(xvalues,yvalues,linewidth=0.5,alpha=0.5,c='red') # num_squares数据值,linewidth设置线条粗细
    
        # 设置折线图标题和横纵坐标标题
        plt.title("Python绘制折线图",fontsize=30,fontname='宋体',fontproperties=myfont)
        plt.xlabel('横坐标',fontsize=20,fontname='宋体',fontproperties=myfont)
        plt.ylabel('纵坐标',fontsize=20,fontname='宋体',fontproperties=myfont)
    
        # 设置刻度标记大小,axis='both'参数影响横纵坐标,labelsize刻度大小
        plt.tick_params(axis='both',labelsize=14)
    
        # 显示图形
        plt.show()
    

    游戏占比与冰淇淋公升数关系折线图可视化:(此处折线图明显不合适,只是突出另一种分析方式。)

    图2-3 游戏占比与冰淇淋公升数关系折线图

    扩展:

    更多matplotlib可视化实现效果图参考文章 70个注意的Python小Notes:完整的matplotlib可视化

    基于Echart的可视化分析

    我们上面采用的matplotlib可视化效果,采用该方式主要是结合python数据分析绑定比较方便。有些时候我们为了取得更加漂亮的可视化效果,可以选择百度echart进行分析,百度Echart使用简单且文档规范容易上手。我们对原数据进行分析并转化为json代码:

    '''array数据转化json'''
    def norm_Json(dataset):
        noredataset = norm_dataset(dataset)[0] # 数据归一化
        number1 = np.around(noredataset[:,1], decimals=4) # 获取数据集第二列
        number2 = np.around(noredataset[:,2], decimals=4) # 获取数据集第三列
        returnMat=zeros((dataset.shape[0],2))             # 二维矩阵
        returnMat[:,0] = number1
        returnMat[:,1] = number2
    
        file_path = os.path.abspath(r"./datasource/test.json")
        json.dump(returnMat.tolist(), codecs.open(file_path, 'w', encoding='utf-8'), separators=(',', ':'), sort_keys=True, indent=4)
    

    生成json数据保存在指定文件中,打开文件查看数据如下:

    [
        [
            0.3981,
            0.5623
        ],
        [
            0.342,
            0.9872
        ],
        [
            0.0689,
            0.4745
        ],
        [
            0.6285,
            0.2525
        ]
        ...
        [
            0.4367,
            0.429
        ],
        [
            0.3768,
            0.7857
        ]
    ]
    

    从百度Echart实例中选择一种散点图并绑定json文件,其html代码如下:

    <!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>图案例</title>
        <script src="https://cdn.bootcss.com/jquery/2.2.0/jquery.min.js"></script>
        <script type="text/javascript" src="./js/echarts.js"></script>
    </head>
    <body>
        <div id="chartmain" style="width:800px; height: 400px; margin:auto; ">
        </div>
    
        <script type="text/javascript">
            //初始化echarts实例
            var myChart = echarts.init(document.getElementById('chartmain'));
            $.getJSON('game-food.json', function (data) {
            var option = {
                title: {
                    text: '玩游戏时间占比和饮食数据描述',
                    left: 'center',
                    top: 0
                },
                visualMap: {
                    min: 15202,
                    max: 159980,
                    dimension: 1,
                    orient: 'vertical',
                    right: 10,
                    top: 'center',
                    text: ['优秀', '一般'],
                    calculable: true,
                    inRange: {
                        color: ['#f2c31a', '#24b7f2']
                    }
                },
                tooltip: {
                    trigger: 'item',
                    axisPointer: {
                        type: 'cross'
                    }
                },
                xAxis: [{
                    type: 'value'
                }],
                yAxis: [{
                    type: 'value'
                }],
                series: [{
                    name: 'price-area',
                    type: 'scatter',
                    symbolSize: 5,
                    data: data
                }]
            };
            myChart.setOption(option);
    });
        </script>
    </body>
    </html>
    

    json文件读取需要在web运行环境中,单纯的运行效果如下图所示:

     

    图2-4 游戏占比与冰淇淋公升数Echarts关系散点图

    数据转化工具

    本文采用自己构建的方式进行json文件生成,此外我们也可以采用现有的数据转化工具进行处理。比如百度的表格数据转化工具(2.2节已经介绍了)。

    另一个便是在线json验证格式工具:http://www.bejson.com/

    2.5 KNN分类器实现

    通过数据分析,我们查看数据样本是否偏态分别,数据规模情况等等。针对性进行数据预处理后,编写具体算法模型。本文主要是KNN分类器,其代码如下:

    ''' 构造KNN分类器
        vecX:输入向量,待测数据
        filename: 特征集文件路径
        isnorm:是否进行归一化处理
        k:k值的选择,默认选择3
    '''
    def knn_classifier(vecX,dataset,labels,isnorm='Y',k=3):
        # 距离计算(方法1)
        if isnorm == 'Y':
            normMat,ranges,minVals = norm_dataset(dataset)     # 对数据进行归一化处理
            normvecX = norm_dataset(vecX)
        else:
            normMat = dataset
            normvecX = vecX
    
        m = normMat.shape[0]
        # tile方法是在列向量vecX,datasetSize次,行向量vecX1次叠加
        diffMat = tile(normvecX,(m,1)) - normMat
        sqDiffMat = diffMat ** 2
        sqDistances = sqDiffMat.sum(axis=1)   # axis=0 是列相加,axis=1是行相加
        distances = sqDistances**0.5
        # print('vecX向量到数据集各点距离:\n'+str(distances))
    
        sortedDistIndexs = distances.argsort(axis=0)  # 距离排序,升序
        # print(sortedDistIndicies)
    
        classCount = {}   # 统计前k个类别出现频率
        for i in range(k):
            votelabel = labels[sortedDistIndexs[i]]
            classCount[votelabel] = classCount.get(votelabel,0) + 1 #统计键值
        # 类别频率出现最高的点,itemgetter(0)按照key排序,itemgetter(1)按照value排序
        sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
        print(str(vecX)+'KNN的投票决策结果:\n'+str(sortedClassCount[0][0]))
        return sortedClassCount[0][0]
    

    3 KNN算法模型评估

    3.1 评价指标介绍

    基本知识

    混淆矩阵:正元组和负元组的合计

    图3-1 混淆矩阵表

    评估度量:(其中P:正样本数 N:负样本数 TP:真正例 TN:真负例 FP:假正例 FN:假负例)

    图3-2 评估信息度量表

    注意:学习器的准确率最好在检验集上估计,检验集的由训练集模型时未使用的含有标记的元组组成数据。

    各参数描述如下:

    TP(真正例/真阳性):是指被学习器正确学习的正元组,令TP为真正例的个数。

    TN(真负例/真阴性):是指被学习器正确学习的负元组,令TN为真负例的个数。

    FP(假正例/假阳性):是被错误的标记为正元组的负元组。令FP为假正例的个数。

    FN(假负例/假阴性):是被错误的标记为负元组的正元组。令FN为假负例的个数。

    准确率:正确识别的元组所占的比例。

    评价指标优点

    一般采用精确率和召回率作为度量的方法具有以下几个优点:

    (1) 准确率数值对于小数据不是特别敏感,而精确率和召回率对于这样数据比较敏感。 (2) 在相同实验环境下,F度量这种倾向和我们直观感觉是一致的,我们对目标事件很敏感,甚至返回一些垃圾数据也在所不惜。 (3) 通过精确率和找回来衡量目标事件和垃圾事件的差异。

    模型评估拓展

    参见《自然语言处理理论与实战》一书第13章模型评估

    3.2 评估算法模型实现

    本文只是对错误率进行评估,其也是knn分类器核心指标,实现代码如下:

    '''测试评估算法模型'''
    def test_knn_perfor(filename):
        hoRatio = 0.1
        dataset,label = file_matrix(filename)              # 获取训练数据和标签
        normMat,ranges,minVals = norm_dataset(dataset)     # 对数据进行归一化处理
        m = normMat.shape[0]
        numTestVecs = int(m*hoRatio)                       # 10%的测试数据条数
    
        errorCount = 0.0                                   # 统计错误分类数
        for i in range(numTestVecs):
            classifierResult = knn_classifier(normMat[i,:],normMat[numTestVecs:m,:],label[numTestVecs:m],3)          # 此处分类器可以替换不同分类模型
            print('分类结果:'+str(classifierResult)+'\t\t准确结果:'+str(label[i]))
    
            if classifierResult != label[i]:
                errorCount += 1.0
            Global.all_FileNum += 1
        print('总的错误率为:'+str(errorCount/float(numTestVecs))+"\n总测试数据量: "+str(Global.all_FileNum))
    

    运行效果如下:

    [0.44832535 0.39805139 0.56233353]KNN的投票决策结果:
    分类结果:3      准确结果:3
    [0.15873259 0.34195467 0.98724416]KNN的投票决策结果:
    分类结果:2      准确结果:2
    ...
    分类结果:3      准确结果:3
    [0.19385799 0.30474213 0.01919426]KNN的投票决策结果:
    分类结果:2      准确结果:2
    [0.24463971 0.10813023 0.60259472]KNN的投票决策结果:
    分类结果:1      准确结果:1
    [0.51022756 0.27138082 0.41804137]KNN的投票决策结果:
    分类结果:3      准确结果:1
    
    总的错误率为:0.05
    总测试数据量: 100
    耗时:0.0300 s
    

    评估结果分析:

    本文采用封闭评估的方法,前100条数据作为测试集,后900条数据作为训练集。如上结果最后一条信息表明knn分类器的结果是3,而标准结果是1.knn分类存在错误。将所有错误占比分析出来即错误率。本文错误率5%,即准确率95%.

    读者可以选取200:800、300:700等等数据进行测试查看错误率。

    4 KNN算法模型的实际应用

    knn分类器应用

    经过如上的改进最终形成实际应用的算法模型API开发给外部程序使用,调用knn算法代码如下:

    '''调用可用算法'''
    def show_classifyPerson(filename):
        resultlist = ['不喜欢','还可以','特别喜欢']
        ffMiles = float(input('每年飞行的历程多少公里?\n'))
        percentTats = float(input('玩游戏时间占百分比多少?\n')) # [751,13,0.4][40920 ,8.326976,0.953952]
        iceCream = float(input('每周消费冰淇淋多少公升?\n'))
    
        dataset,labels = file_matrix(filename) # 数据格式化处理
        inArr = array([ffMiles,percentTats,iceCream])
    
        classifierResult = knn_classifier(inArr,dataset,labels,3) # 数据归一化并进行分类
        print('预测的约会结果是:'+resultlist[classifierResult-1])
    

    运行结果如下:

    每年飞行的历程多少公里?
    10000
    玩游戏时间占百分比多少?
    10
    每周消费冰淇淋多少公升?
    0.5
    KNN的投票决策结果:
    2
    预测的约会结果是:还可以
    

    展望

    我们还可以采用knn分类器进行实际应用,比如新闻分类系统。大致思路如下:

    1 采集数据:选用复旦大学的文本分类新闻语料 2 准备数据:数据格式化、分词、停用词处理等 3 分析数据:看看数据特点,有没有缺失值,数据连续性还是离散型,进而选择不同模型。诸如:可视化数据分析 4 数据转化:采用IF-IDF或者神经网络的方法对词频进行处理,最终转化为机器可以处理的数值型矩阵。 5 构建模型:KNN新闻分类器模型构建。 6 测试算法:评价指标,如计算错误率,准确率,召回率,F度量值等。 7 应用算法:针对完善的模型进行封装重构,然后进行实际的新闻分类应用。

    5 参考文献

    1. 归一化学习:https://blog.csdn.net/hyq3235356/article/details/78472307
    2. 归一化方法:https://blog.csdn.net/zxd1754771465/article/details/73558103
    3. 百度Echart转化工具:http://echarts.baidu.com/spreadsheet.html
    4. 在线json验证格式工具:http://www.bejson.com/
    5. 模型评估:http://www.cnblogs.com/baiboy/p/mxpg2.html

    完整代码下载

    机器学习和自然语言QQ群:436303759。 微信公众号:datathinks

    自然语言处理和机器学习QQ交流群:436303759自然语言处理和机器学习微信公众号:datathinks

    源码请进QQ群文件下载:

    作者声明

    本文原创,旨在学术和科研使用。转载必须注明出处【伏草惟存】: KNN模型算法研究与案例分析

    展开全文
  • 下周二算法课需要讲一个算法PPT,趁着自己在学习大数据,最佳的算法选择无疑是机器学习了。除了K-means我还接触过KNN以及反向传播神经网络。等到后面在系统学习复习(开天辟地)的时候再做一个详细的梳理。 K-...

    下周二算法课需要讲一个算法PPT,趁着自己在学习大数据,最佳的算法选择方向无疑是机器学习了。除了K-means我还接触过KNN以及反向传播神经网络。等到后面在系统学习复习(开天辟地)的时候再做一个详细的梳理。

    K-means


    K-means算法是硬聚类算法,是典型的基于原型的目标函数聚类方法的代表,它是数据点到原型的某种距离作为优化的目标函数,利用函数求极值的方法得到迭代运算的调整规则。K-means算法以欧式距离作为相似度测度,它是求对应某一初始聚类中心向量V最优分类,使得评价指标J最小。算法采用误差平方和准则函数作为聚类准则函数。

    在这里插入图片描述
    算法使用小案例

    假设有一批人的年龄的数据,大致知道其中有一堆少年儿童,一堆青年人,一堆老年人。.

    聚类就是自动发现这三堆数据,并把相似的数据聚合到同一堆中。所以对于这个例子,如果要聚成3堆的话,那么输入就是一堆年龄数据,注意,此时的年龄数据并不带有类标号,也就是说我只知道里面大致有三堆人,至于谁是哪一堆,现在是不知道的,而输出就是每个数据所属的类标号,聚类完成之后,就知道谁和谁是一堆了。

    什么叫聚类?

    聚类的目标:将一组向量分成若干组,组内数据是相似的,而组间数据是有较明显差异。

    与分类区别:分类与聚类最大的区别在于分类的目标事先已知,聚类也被称为无监督机器学习

    K 是什么?

    K是聚类算法中当前类的个数

    Means 是什么?

    means是均值算法

    算法描述:

    算法核心很简单,我感觉K打头的算法都挺简单的。相信你看了也会对机器学习充满自信。

    • 任选K个点作为初始聚类中心
    • 根据每个聚类的中心,计算每个对象与这些中心的距离,并根据最小距离重新对对象进行划分
    • 重新计算每个聚类的中心(质心实际上不存在的)
    • 当满足一定条件,如类别划分不在发生变化时,算法终止,否则继续2-3

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IVq95gX4-1593870599134)(https://i.imgur.com/6Zdir1p.png)]
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1OzcYvPb-1593870599137)(https://i.imgur.com/3XPw8g7.png)]
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-J0H5ByAr-1593870599144)(https://i.imgur.com/AhLBZqA.png)]

    使用场景

    • 样本球形分布
    • 密度,大小不同的聚类

    时间复杂度:

    该算法的时间复杂度为:O(nkt)

    • n->聚类对象数
    • t->迭代次数
    • k->初始中心个数

    平面划分

    两点之间的垂直平分线,迭代划分。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MNRYFFZ4-1593870599147)(https://i.imgur.com/tQVzJJQ.png)]

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PLra3fqQ-1593870599150)(https://i.imgur.com/v8dbhoe.png)]

    欧式距离

    对于欧式空间的样本数据,以平方误差和(sum of the squared error, SSE)作为聚类的目标函数,同时也可以衡量不同聚类结果好坏的指标:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-O1ngmHhS-1593870599152)(https://i.imgur.com/mXaB1Ic.png)]

    表示样本点x到cluster Ci 的质心 ci 距离平方和;最优的聚类结果应使得SSE达到最小值。

     //欧式距离,计算两点距离
        public double EurDistance(Point point, Point center)
        {
            double detX = point.getX() - center.getX();
            double detY = point.getY() - center.getY();
    
            return Math.sqrt(detX * detX + detY * detY);
        }
    

    重新计算每个聚类的中心对象

    中心对象:均值

      /*
         * 调整聚类中心,按照求平衡点的方法获得新的簇心
         */
        public void adjustCenters()
        {
            double sumx[] = new double[k];
            double sumy[] = new double[k];
            int count[] = new int[k];
    
            // 保存每个簇的横纵坐标之和
            for (int i = 0; i < k; i++)
            {
                sumx[i] = 0.0;
                sumy[i] = 0.0;
                count[i] = 0;
            }
    
            // 计算每个簇的横纵坐标总和、记录每个簇的个数
            for (Point point : points)
            {
                int clusterID = point.getClusterID();
    
                // System.out.println(clusterID);
                sumx[clusterID - 1] += point.getX();
                sumy[clusterID - 1] += point.getY();
                count[clusterID - 1]++;
            }
    
            // 更新簇心坐标
            for (int i = 0; i < k; i++)
            {
                Point tmpPoint = centers.get(i);
                tmpPoint.setX(sumx[i] / count[i]);
                tmpPoint.setY(sumy[i] / count[i]);
                tmpPoint.setClusterID(i + 1);
    
                centers.set(i, tmpPoint);
            }
        }
    
    

    终止条件

    最小化蔟内对象到质心的距离,从而最小化WCSS。通过损失函数来衡量算法停止条件。

    • 损失函数:WCSS

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qrs2Mhwy-1593870599156)(https://i.imgur.com/xDt54Q7.png)]

    xi代表某个样本点,ck代表每个类的中心点。每个类里的元素越凝聚越好。

    中心点选择

    • K(类别)的选择 细粒度 越多越准确
    • 随机选取
    • 多次随机:选择最小的WCSS那次聚类

    算法优点

    1. 时间复杂度低,速度快。
    2. 由具有出色的速度和良好的可扩展性
    3. 当簇接近高斯分布时,它的效果较好
      算法缺点
    • 在簇的平均值可被定义的情况下才能使用,可能不适用于某些应用;
    • 在 K-means 算法中 K 是事先给定的,这个 K 值的选定是非常难以估计的。很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适;
    • 在 K-means 算法中,首先需要根据初始聚类中心来确定一个初始划分,然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响,一旦初始值选择的不好,可能无法得到有效的聚类结果;
    • 该算法需要不断地进行样本分类调整,不断地计算调整后的新的聚类中心,因此当数据量非常大时,算法的时间开销是非常大的;
    • 若簇中含有异常点,将导致均值偏离严重(即:对噪声和孤立点数据敏感);
    • 不适用于发现非凸形状的簇或者大小差别很大的簇。

    你可别说为啥这算法缺点比有点还多。“存在即合理!”

    Java实现


    这里结果可视化我用了JfreeChart图表绘制类库。数据集是iris数据集。另外提醒一下就是使用本代码时记得创建文件输出路径,以及导入绘图的核心包。

    package com.xianglei.kmeansback;
    
    public class Point
    {
        // 点的坐标
        private Double x;
        private Double y;
        private Double z;
        public int getTag() {
    		return tag;
    	}
    
    
    
    	public void setTag(int tag) {
    		this.tag = tag;
    	}
    
    	private Double w;
    
        // 所在类ID
        private int clusterID = -1;
        private int tag=0;
    
        public Point(Double x, Double y,Double w, Double z) {
    
            this.x = x;
            this.y = y;
            this.w = w;
            this.z = z;
        }
    
      
    
        public Double getX()
        {
            return x;
        }
    
        public void setX(Double x)
        {
            this.x = x;
        }
    
        public Double getY()
        {
            return y;
        }
    
        public Double getZ() {
    		return z;
    	}
    
    
    
    	@Override
    	public String toString() {
    		return "Point [x=" + x + ", y=" + y + ", z=" + z + ", w=" + w + ", clusterID=" + clusterID + "]";
    	}
    
    
    
    	public void setZ(Double z) {
    		this.z = z;
    	}
    
    
    
    	public Double getW() {
    		return w;
    	}
    
    
    
    	public void setW(Double w) {
    		this.w = w;
    	}
    
    
    
    	public void setY(Double y)
        {
            this.y = y;
        }
    
        public int getClusterID()
        {
            return clusterID;
        }
    
        public void setClusterID(int clusterID)
        {
            this.clusterID = clusterID;
        }
    }
    
    
    package com.xianglei.kmeansback;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class KMeansCluster
    {
        // 聚类中心数
        public int k = 5;
    
        // 迭代最大次数
        public int maxIter = 50;
    
        // 测试点集
        public List<Point> points;
    
        // 中心点
        public List<Point> centers;
    
        public static final double MINDISTANCE = 10000.00;
    
        public KMeansCluster(int k, int maxIter, List<Point> points) {
            this.k = k;
            this.maxIter = maxIter;
            this.points = points;
    
            //初始化中心点
            initCenters();
        }
    
        /*
         * 初始化聚类中心
         * 这里的选取策略是,从点集中按序列抽取K个作为初始聚类中心
         */
        public void initCenters()
        {
            centers = new ArrayList<>(k);
    
            for (int i = 0; i < k; i++)
            {
                Point tmPoint = points.get(i*33+48);
                Point center = new Point(tmPoint.getX(), tmPoint.getY(),tmPoint.getW(), tmPoint.getZ());
                center.setClusterID(i + 1);
                centers.add(center);
            }
        }
    
    
        /*
         * 停止条件是满足迭代次数
         */
        public void runKmeans()
        {
            // 已迭代次数
            int count = 1;
    
            while (count++ <= maxIter)
            {
                // 遍历每个点,确定其所属簇
                for (Point point : points)
                {
                	if(point.getTag()==0)
                    assignPointToCluster(point);
                	
                }
    
                //调整中心点
                adjustCenters();
            }
        }
    
    
    
        /*
         * 调整聚类中心,按照求平衡点的方法获得新的簇心
         */
        public void adjustCenters()
        {
            double sumx[] = new double[k];
            double sumy[] = new double[k];
            double sumw[] = new double[k];
            double sumz[] = new double[k];
            int count[] = new int[k];
    
            // 保存每个簇的横纵坐标之和 K=3
            for (int i = 0; i < k; i++)
            {
                sumx[i] = 0.0;
                sumy[i] = 0.0;
                sumw[i] = 0.0;
                sumz[i] = 0.0;
                count[i] = 0;
            }
    
            // 计算每个簇的横纵坐标总和、记录每个簇的个数
            for (Point point : points)
            {
            	if(point.getTag()==0){
                int clusterID = point.getClusterID();
    
                // System.out.println(clusterID);
                sumx[clusterID - 1] += point.getX();
                sumy[clusterID - 1] += point.getY();
                sumw[clusterID - 1] += point.getW();
                sumz[clusterID - 1] += point.getZ();
                count[clusterID - 1]++;
            	}
            }
    
            // 更新簇心坐标
            for (int i = 0; i < k; i++)
            {
                Point tmpPoint = centers.get(i);
                tmpPoint.setX(sumx[i] / count[i]);
                tmpPoint.setY(sumy[i] / count[i]);
                tmpPoint.setW(sumw[i] / count[i]);
                tmpPoint.setZ(sumz[i] / count[i]);
                tmpPoint.setClusterID(i + 1);
    
                centers.set(i, tmpPoint);
            }
        }
    
    
        /*划分点到某个簇中,欧式距离标准
         * 对传入的每个点,找到与其最近的簇中心点,将此点加入到簇
         */
        public void assignPointToCluster(Point point)
        {
            double minDistance = MINDISTANCE;
    
            int clusterID = -1;
    
            for (Point center : centers)
            {
                double dis = EurDistance(point, center);
                if (dis < minDistance)
                {
                    minDistance = dis;
                    clusterID = center.getClusterID();
                }
            }
            point.setClusterID(clusterID);
    
        }
    
        //欧式距离,计算两点距离
        public double EurDistance(Point point, Point center)
        {
            double detX = point.getX() - center.getX();
            double detY = point.getY() - center.getY();
            double detW = point.getW() - center.getW();
            double detZ = point.getZ() - center.getZ();
    
            return Math.sqrt(detX * detX + detY * detY+ detW * detW+ detZ * detZ);
        }
    }
    
    
    
    package com.xianglei.kmeansback;
    
    import java.awt.BasicStroke;
    import java.awt.Color;
    import java.awt.Font;
    import java.awt.Image;
    import java.awt.image.ImageObserver;
    import java.awt.image.ImageProducer;
    import java.io.File;
    import java.io.FileWriter;
    import java.io.IOException;
    import java.text.DecimalFormat;
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    import java.util.Scanner;
    
    import org.jfree.chart.ChartFactory;
    import org.jfree.chart.ChartFrame;
    import org.jfree.chart.JFreeChart;
    import org.jfree.chart.StandardChartTheme;
    import org.jfree.chart.annotations.XYTextAnnotation;
    import org.jfree.chart.axis.NumberAxis;
    import org.jfree.chart.axis.ValueAxis;
    import org.jfree.chart.plot.CategoryPlot;
    import org.jfree.chart.plot.Plot;
    import org.jfree.chart.plot.PlotOrientation;
    import org.jfree.chart.plot.XYPlot;
    import org.jfree.chart.renderer.xy.XYLineAndShapeRenderer;
    import org.jfree.data.xy.DefaultXYDataset;
    import org.jfree.data.xy.XYDataset;
    import org.jfree.ui.RefineryUtilities;
    
    public class Kmean {
    	// 用来聚类的点集
    	public List<Point> points;
    
    	// 将聚类结果保存到文件
    	FileWriter out = null;
    
    	// 格式化double类型的输出,保留两位小数
    	DecimalFormat dFormat = new DecimalFormat("00.00");
    
    	// 具体执行聚类的对象
    	public KMeansCluster kMeansCluster;
    
    	// 簇的数量,迭代次数
    	public int numCluster = 0;
    
    	public int numIterator = 200;
    
    	// 点集的数量,生成指定数量的点集
    	public int numPoints = 50;
    
    	// 聚类结果保存路径
    	public static final String FILEPATH = "f:/kmeans/res.txt";
    	public static final String DATAPATH = "f:/kmeans/iris.txt";
    
    	public static void main(String[] args) {
    		// 指定点集个数,簇的个数,迭代次数
    		Kmean kmeans = new Kmean(0, 3, 200000);
    
    		// 初始化点集、KMeansCluster对象
    		kmeans.init();
    
    		// 使用KMeansCluster对象进行聚类
    		kmeans.runKmeans();
    
    		kmeans.printRes();
    		kmeans.Test();
    		kmeans.saveResToFile(FILEPATH);
    
    	}
    
    	
    
    	private void Test() {
    		// TODO Auto-generated method stub
    		
    	}
    
    
    
    	public Kmean(int numPoints, int cluster_number, int iterrator_number) {
    
    		this.numPoints = numPoints;
    		this.numCluster = cluster_number;
    		this.numIterator = iterrator_number;
    	}
    
    	private void init() {
    		this.initPoints();
    		kMeansCluster = new KMeansCluster(numCluster, numIterator, points);
    	}
    
    	private void runKmeans() {
    		kMeansCluster.runKmeans();
    	}
    
    	// 初始化点集
    	public void initPoints() {
    		points = new ArrayList<>(numPoints);
    
    		try {
    			Scanner in = new Scanner(new File(DATAPATH));// 读入文件
    			while (in.hasNextLine() && numPoints <= 154) {
    				Point tmpPoint = new Point(null, null, null, null);
    				numPoints++;
    				String str = in.nextLine();// 将文件的每一行存到str的临时变量中
    				String[] split = str.split(" ");
    
    				tmpPoint.setX(Double.valueOf(split[1]));
    				tmpPoint.setY(Double.valueOf(split[2]));
    				tmpPoint.setZ(Double.valueOf(split[3]));
    				tmpPoint.setW(Double.valueOf(split[4]));
    				if (split[5].contains("setosa"))
    					tmpPoint.setClusterID(1);
    				if (split[5].contains("versicolor"))
    					tmpPoint.setClusterID(2);
    				if (split[5].contains("virginica"))
    					tmpPoint.setClusterID(3);
    
    				points.add(tmpPoint);
    				System.out.println(numPoints);
    				System.out.println(split[1] + "-" + split[2] + "-" + split[3] + "-" + split[4] + "-" + split[5]
    						+ " - - - 类别:" + tmpPoint.getClusterID());
    			}
    	
    		} catch (Exception e) {
    
    		}
    
    	}
    
    	public void printRes() {
    
    		System.out.println("==================Centers-I====================");
    		for (Point center : kMeansCluster.centers) {
    			System.out.println(center.toString());
    		}
    
    		System.out.println("==================Points====================");
    
    		for (Point point : points) {
    			if (point.getTag() == 0)
    				System.out.println(point.toString());
    		}
    	}
    
    	public void saveResToFile(String filePath) {
    		try {
    			out = new FileWriter(new File(filePath));
    			String[] stinga = new String[numPoints];
    			String[] stingb = new String[numPoints];
    			String[] tag = new String[numPoints];
    			int i = 0;
    			for (Point point : points) {
    				if (point.getTag() == 0) {
    					out.write(String.valueOf(point.getClusterID()));
    					out.write("-");
    
    					out.write(dFormat.format(point.getX()));
    					out.write("-");
    					out.write(dFormat.format(point.getY()));
    					out.write(dFormat.format(point.getW()));
    					out.write("-");
    					out.write(dFormat.format(point.getZ()));
    					out.write("\r\n");
    
    					stinga[i] = Double.toString(point.getZ());
    					stingb[i] = Double.toString(point.getW());
    					tag[i] = Double.toString(point.getClusterID());
    					i++;
    					System.out.println("=================================");
    					System.out.println("聚类后结果:" + point.toString());
    				}
    			}
    
    			data("k-means", stinga, stingb, tag);
    			out.flush();
    			out.close();
    
    		} catch (IOException e) {
    			e.printStackTrace();
    		}
    	}
    
    	public static void data(String title, String[] a, String[] b, String[] t) {
    		DefaultXYDataset xydataset = new DefaultXYDataset();
    
    		double[][] data = new double[2][a.length];
    		double[][] data2 = new double[2][a.length];
    		double[][] data3 = new double[2][a.length];
    
    		for (int i = 0; i < a.length; i++) {
    
    			if (t[i].contains("1")) {
    				data[0][i] = Double.parseDouble(a[i]);
    				data[1][i] = Double.parseDouble(b[i]);
    
    			}
    			if (t[i].contains("2")) {
    				data2[0][i] = Double.parseDouble(a[i]);
    				data2[1][i] = Double.parseDouble(b[i]);
    
    			}
    			if (t[i].contains("3")) {
    				data3[0][i] = Double.parseDouble(a[i]);
    				data3[1][i] = Double.parseDouble(b[i]);
    			}
    
    		}
    
    		xydataset.addSeries("Setosa", data);
    		xydataset.addSeries("Versicolor", data2);
    		xydataset.addSeries("Virginica", data3);
    
    		final JFreeChart chart = ChartFactory.createScatterPlot("K-Means", "X", "Y", xydataset,
    				PlotOrientation.VERTICAL, true, true, false);
    
    		chart.setBorderVisible(false);
    
    		XYPlot xyPlot2 = chart.getXYPlot();
    		xyPlot2.getRenderer().setSeriesPaint(0, Color.RED);
    		xyPlot2.getRenderer().setSeriesPaint(1, Color.GREEN);
    		xyPlot2.getRenderer().setSeriesPaint(2, Color.black);
    
    		ChartFrame frame = new ChartFrame(title, chart);
    		frame.pack();
    		RefineryUtilities.centerFrameOnScreen(frame);
    		frame.setVisible(true);
    	}
    
    }
    
    

    聚类结果

    一:随机模拟数据集
    在这里插入图片描述

    二.iris数据集

    在这里插入图片描述


    总结

    就算法的思想和实现来讲是比较简单的,也为我的算法学习开了个好头。但是我看了其他大牛的博客后,发现这个算法更多可玩的地方是如何去解决这些缺点。但是由于时间关系,在当下这个时间段我就不深挖了,你要是有兴趣的话给你一个传送门深入理解 K-means算法。???

    展开全文
  • 数据挖掘算法,不是我的强项,对数学,对逻辑有太多的要求了。比较不适合我。  数据挖掘十大经典算法  一、 C4.5  C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3 算法. C4.5算法继承了ID...

    数据挖掘算法,不是我的强项,对数学,对逻辑有太多的要求了。比较不适合我。 

    数据挖掘十大经典算法

     一、 C4.5 
    C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3 算法.   C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进: 
    1) 用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足; 
    2) 在树构造过程中进行剪枝; 
    3) 能够完成对连续属性的离散化处理; 
    4) 能够对不完整数据进行处理。 
    C4.5算法有如下优点:产生的分类规则易于理解,准确率较高。其缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。

    1、机器学习中,决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,而每个叶结点则
    对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出,若欲有复数输出,可以建立独立的决策树以处理不同输出。 
    2、 从数据产生决策树的机器学习技术叫做决策树学习,  通俗说就是决策树。 
    3、决策树学习也是数据挖掘中一个普通的方法。在这里,每个决策树都表述了一种树型结构,他由他的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割
    进行数据测试。这个过程可以递归式的对树进行修剪。当不能再进行分割或一个单独的类可以被应用于某一分支时,递归过程就完成了。另外,随机森林分类器将许多决策树结合起来
    以提升分类的正确率。

    决策树是如何工作的? 
    1、决策树一般都是自上而下的来生成的。 
    2、选择分割的方法有好几种,但是目的都是一致的:对目标类尝试进行最佳的分割。 
    3、从根到叶子节点都有一条路径,这条路径就是一条―规则 
    4、决策树可以是二叉的,也可以是多叉的。 
    对每个节点的衡量: 
    1)         通过该节点的记录数 
    2)         如果是叶子节点的话,分类的路径 
    3)         对叶子节点正确分类的比例。 
    有些规则的效果可以比其他的一些规则要好。 
    由于ID3算法在实际应用中存在一些问题,于是Quilan提出了C4.5算法,严格上说C4.5只能是ID3的一个改进算法。相信大家对ID3算法都很.熟悉了,这里就不做介绍。 
    C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进: 
    1) 用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足;
    2) 在树构造过程中进行剪枝; 
    3) 能够完成对连续属性的离散化处理; 
    4) 能够对不完整数据进行处理。 
    C4.5算法有如下优点:产生的分类规则易于理解,准确率较高。其缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。此外,C4.5只适合于
    能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。  来自搜索的其他内容: 
     C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法.  分类决策树算法是从大量事例中进行提取分类规则的自上而下的决策树. 决策树的各部分是: 
                 根:    学习的事例集. 
                 枝:    分类的判定条件. 
                 叶:    分好的各个类. 

     ID3算法 
       1.概念提取算法CLS 
    1)      初始化参数C={E},E包括所有的例子,为根. 
    2)        IF      C中的任一元素e同属于同一个决策类则创建一个叶子     
                   节点YES终止. 
               ELSE      依启发式标准,选择特征Fi={V1,V2,V3,...Vn}并创建 
                           判定节点 
      
    划分C为互不相交的N个集合C1,C2,C3,...,Cn; 
    3)      对任一个Ci递归. 
        2.      ID3算法 
    1)      随机选择C的一个子集W    (窗口). 
    2)      调用CLS生成W的分类树DT(强调的启发式标准在后). 
    3)      顺序扫描C搜集DT的意外(即由DT无法确定的例子). 
    4)      组合W与已发现的意外,形成新的W. 
     
     
    5)      重复2)到4),直到无例外为止. 
      
    启发式标准: 
           只跟本身与其子树有关,采取信息理论用熵来量度. 
           熵是选择事件时选择自由度的量度,其计算方法为 
                   P    =    freq(Cj,S)/|S|; 
           INFO(S)=    -    SUM(    P*LOG(P)    )    ;        SUM()函数是求j 从1到n和. 
           Gain(X)=Info(X)-Infox(X); 
           Infox(X)=SUM(    (|Ti|/|T|)*Info(X); 
    为保证生成的决策树最小,ID3 算法在生成子树时,选取使生成的子树的熵(即Gain(S))最小的
    的特征来生成子树. 
      
      3、  ID3算法对数据的要求 
    1).      所有属性必须为离散量. 
    2).      所有的训练例的所有属性必须有一个明确的值. 
    3).      相同的因素必须得到相同的结论且训练例必须唯一. 
      
       C4.5对ID3算法的改进: 
           1.      熵的改进,加上了子树的信息. 
                 Split_Infox(X)=    -    SUM(      (|T|/|Ti|    )    *LOG(|Ti|/|T|)      ); 
                 Gain    ratio(X)=      Gain(X)/Split    Infox(X); 
            2.      在输入数据上的改进. 
             1) 
    因素属性的值可以是连续量,C4.5 对其排序并分成不同的集合后按照ID3 算法当作离散量进行处理,但结论属性的值必须是离散值. 
           2)    训练例的因素属性值可以是不确定的,以    ?    表示,但结论必须是确定的 
           3.      对已生成的决策树进行裁剪,减小生成树的规模.

    二、数据挖掘十大经典算法(2) k-means 
    术语“k-means”最早是由James MacQueen在1967年提出的,这一观点可以追溯到1957年 Hugo Steinhaus所提出的想法。1957年,斯图亚特·劳埃德最先提出这一标准算法,当初是作为一门应用于脉码调制的技术,直到1982年,这一算法才在贝尔实验室被正式提出。1965年, E.W.Forgy发表了一个本质上是相同的方法,1975年和1979年,Hartigan和Wong分别提出了一个更高效的版本。

    算法描述
    输入:簇的数目k;包含n个对象的数据集D。
    输出:k个簇的集合。

    方法:

    从D中任意选择k个对象作为初始簇中心;
    repeat;
    根据簇中对象的均值,将每个对象指派到最相似的簇;
    更新簇均值,即计算每个簇中对象的均值;
    计算准则函数;
    until准则函数不再发生变化。
    算法的性能分析
       1)优点
    (1)k-平均算法是解决聚类问题的一种经典算法,算法简单、快速。
    (2)对处理大数据集,该算法是相对可伸缩的和高效率的,因为它的复杂度大约是O(nkt),其中n是所有对象的数目,k是簇的数目,t是迭代的次数。通常k<<n。这个算法经常以局部最优结束。
    (3)算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的,而簇与簇之间区别明显时,它的聚类效果很好。
       2)缺点
    (1)k-平均方法只有在簇的平均值被定义的情况下才能使用,不适用于某些应用,如涉及有分类属性的数据不适用。
    (2)要求用户必须事先给出要生成的簇的数目k。
    (3)对初值敏感,对于不同的初始值,可能会导致不同的聚类结果。
    (4)不适合于发现非凸面形状的簇,或者大小差别很大的簇。
    (5)对于"噪声"和孤立点数据敏感,少量的该类数据能够对平均值产生极大影响。
    算法的改进
    针对算法存在的问题,对K-means算法提出一些改进:
    一是数据预处理,
    二是初始聚类中心选择,
    三是迭代过程中聚类种子的选择。
    1、首先对样本数据进行正规化处理,这样就能防止某些大值属性的数据左右样本间的距离。给定一组含有n个数据的数据集,每个数据含有m个属性,分别计算每一个属性的均值、标准差对每条数据进行标准化。
    3、其次,初始聚类中心的选择对最后的聚类效果有很大的影响,原K-means算法是随机选取k个数据作为聚类中心,而聚类的结果要是同类间尽可能相似,不同类间尽可能相异,所以初始聚类中心的选取要尽可能做到这一点。采用基于距离和的孤立点定义来进行孤立点的预先筛选,并利用两两数据之间的最大距离在剩余数据集合中寻找初始聚类中心。但对于实际数据,孤立点个数往往不可预知。在选择初始聚类中心时,先将孤立点纳入统计范围,在样本中计算对象两两之间的距离,选出距离最大的两个点作为两个不同类的聚类中心,接着从其余的样本对象中找出已经选出来的所有聚类中心的距离和最大的点为另一个聚类中心,直到选出k个聚类中心。这样做就降低了样本输入顺序对初始聚类中心选择的影响。

    聚类中心选好以后,就要进行不断的迭代计算,在K-means算法中,是将聚类均值点(类中所有数据的几何中心点)作为新的聚类种子进行新一轮的聚类计算,在这种情况下,新的聚类种子可能偏离真正的数据密集区,从而导致偏差,特别是在有孤立点存在的情况下,有很大的局限性。在选择初始中心点时,由于将孤立点计算在内,所以在迭代过程中要避免孤立点的影响。这里根据聚类种子的计算时,采用簇中那些与第k-1轮聚类种子相似度较大的数据,计算他们的均值点作为第k轮聚类的种子,相当于将孤立点排除在外,孤立点不参与聚类中心的计算,这样聚类中心就不会因为孤立点的原因而明显偏离数据集中的地方。在计算聚类中心的时候,要运用一定的算法将孤立点排除在计算均值点那些数据之外,这里主要采用类中与聚类种子相似度大于某一阈值的数据组成每个类的一个子集,计算子集中的均值点作为下一轮聚类的聚类种子。为了能让更多的数据参与到聚类中心的计算种去,阈值范围要包含大多数的数据。在第k-1轮聚类获得的类,计算该类中所有数据与该类聚类中心的平均距离S,选择类中与聚类种子相似度大于2S的数据组成每个类的一个子集,以此子集的均值点作为第k轮聚类的聚类种子。在数据集中无论是否有明显的孤立点存在,两倍的平均距离都能包含大多数的数据。

    对孤立点的改进—基于距离法
    经典k均值算法中没有考虑孤立点。所谓孤立点都是基于距离的, 是数据U集中到U中最近邻居的距离最大的对象, 换言之, 数据集中与其最近邻居的平均距离最大的对象。针对经典k均值算法易受孤立点的影响这一问题, 基于距离法移除孤立点, 具体过程如下:
    首先扫描一次数据集, 计算每一个数据对象与其临近对象的距离, 累加求其距离和, 并计算出距离和均值。如果某个数据对象的距离和大于距离和均值, 则视该点为孤立点。把这个对象从数据集中移除到孤立点集合中, 重复直到所有孤立点都找到。最后得到新的数据集就是聚类的初始集合。

    对随机选取初始聚类中心的改进
    经典k均值算法随机选取k个点作为初始聚类中心进行操作。由于是随机选取, 则变化较大, 初始点选取不同, 获得聚类的结果也不同。并且聚类分析得到的聚类的准确率也不一样。对k均值算法的初始聚类中心选择方法—随机法进行改进, 其依据是聚类过程中相同聚类中的对象是相似的, 相异聚类中的对象是不相似的。因此提出了一种基于数据对象两两间的距离来动态寻找并确定初始聚类中心的思路, 具体过程如下:
    首先整理移除孤立点后的数据集U,记录数据个数y,令m=1。比较数据集中所有数据对象两两之间的距离。找出距离最近的2个数据对象形成集合Am;比较Am中每一个数据对象与数据对象集合U中每一个对象的距离,在U中找出与Am 中最近的数据对象,优先吸收到Am 中,直到Am 中的数据对象个数到达一定数值,然后令m=m+1。再从U中找到对象两两间距离最近的2个数据对象构成Am,重复上面的过程,直到形成k个对象集合。这些集合内部的数据是相似的,而集合间是相异的。 可以看出,这种聚类方法同时满足以下2个条件:①每个组至少包含一个数据对象; ②每个数据对象必须属于且仅属于一个组。即数据对象Xi ∈Ai ,且U={{A1 ∪A2 ∪…∪Ak} ∪A0} ,且Ai ∩Aj =Φ。最后对k个对象集合分别进行算术平均,形成k个初始聚类中心。
     
    近似的k平均算法已经被设计用于原始数据子集的计算。 从算法的表现上来说,它并不保证一定得到全局最优解,最终解的质量很大程度上取决于初始化的分组。由于该算法的速度很快,因此常用的一种方法是多次运行k平均算法,选择最优解。 
    k平均算法的一个缺点是,分组的数目k是一个输入参数,不合适的k可能返回较差的结果。另外,算法还假设均方误差是计算群组分散度的最佳参数。

    三、数据挖掘十大经典算法(3) Svm 
    支持向量机,英文为Support  Vector  Machine,简称SV机(论文中一般简称SVM)。它是一
    种监督式学习的方法,它广泛的应用于统计分类以及回归分析中。 
      
    支持向量机属于一般化线性分类器.他们也可以认为是提克洛夫规范化(Tikhonov Regularization)方法的一个特例.这族分类器的特点是他们能够同时最小化经验误差与最大化
    几何边缘区.因此支持向量机也被称为最大边缘区分类器。在统计计算中,最大期望(EM)算法是在概率(probabilistic)模型中寻找参数最大似然估计的算法,其中概率模型依赖于无
    法观测的隐藏变量(Latent  Variabl)。最大期望经常用在机器学习和计算机视觉的数据集聚(Data Clustering)领域。最大期望算法经过两个步骤交替进行计算:

    第一步是计算期望(E),也就是将隐藏变量象能够观测到的一样包含在内从而计算最大似然的期望值;

    另外一步是最大化(M),也就是最大化在  E 步上找到的最大似然的期望值从而计算参数的最大似然估计。M 步上找到的参数然后用于另外一个  E 步计算,这个过程不断交替进行。 
      
    Vapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。其原理也从线性可分说起,然后扩展到线性不可分的情况。甚至扩展到使用非线性函数中去,这
    种分类器被称为支持向量机(Support Vector Machine,简称SVM)。支持向量机的提出有很深的理论背景。支持向量机方法是在近年来提出的一种新方法。 
    SVM 的主要思想可以概括为两点: 

     (1) 它是针对线性可分情况进行分析,对于线性不可分的情况,通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使
    其线性可分,从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能;

    (2) 它基于结构风险最小化理论之上在特征空间中建构最优分割超平面,使得学习器得到全局最优化,并且在整个样本空间的期望风险以某个概率满足一定上界。 
    在学习这种方法时,首先要弄清楚这种方法考虑问题的特点,这就要从线性可分的最简单情况讨论起,在没有弄懂其原理之前,不要急于学习线性不可分等较复杂的情况,支持向量机

    在设计时,需要用到条件极值问题的求解,因此需用拉格朗日乘子理论,但对多数人来说,以前学到的或常用的是约束条件为等式表示的方式,但在此要用到以不等式作为必须满足的条件,此时只要了解拉格朗日理论的有关结论就行。 
      
    介绍 

    支持向量机将向量映射到一个更高维的空间里,在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大,分类器的总误差越小。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。van der Walt 和  Barnard 将支持向量机和其他分类器进行了比较。 
      
      
    动机

    有很多个分类器(超平面)可以把数据分开,但是只有一个能够达到最大分割。 我们通常希望分类的过程是一个机器学习的过程。这些数据点并不需要是中的点,而可以是任意(统计学符号)中或者  (计算机科学符号) 的点。我们希望能够把这些点通过一个n-1维的超平面分开,通常这个被称为线性分类器。有很多分类器都符合这个要求,但是我们还希望找到分类最佳的平面,即使得属于两个不同类的数据点间隔最大的那个面,该面亦称为最大间隔超平面。如果我们能够找到这个面,那么这个分类器就称为最大间隔分类器。 
      
    四、数据挖掘十大经典算法(4)Apriori 

    Apriori算法是种最有影响的挖掘布尔关联规则频繁项集的算法。它的核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里,所有支持度大于最小支持度的项集称为频繁项集(简称频集),也常称为最大项目集。
    在Apriori算法中,寻找最大项目集(频繁项集)的基本思想是:算法需要对数据集进行多步处理。第一步,简单统计所有含一个元素项目集出现的频数,并找出那些不小于最小支持度的项目集,即一维最大项目集。从第二步开始循环处理直到再没有最大项目集生成。循环过程是:第k步中,根据第k-1步生成的(k-1)维最大项目集产生k维侯选项目集,然后对数据库进行搜索,得到侯选项目集的项集支持度,与最小支持度进行比较,从而找到k维最大项目集。

    从算法的运行过程,我们可以看出该Apriori算法的优点:简单、易理解、数据要求低,然而我们也可以看到Apriori算法的缺点:

    (1)在每一步产生侯选项目集时循环产生的组合过多,没有排除不应该参与组合的元素;

    (2)每次计算项集的支持度时,都对数据库D中的全部记录进行了一遍扫描比较,如果是一个大型的数据库的话,这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求更好性能的算法,如F-P算法。

    五、数据挖掘十大经典算法(5) EM 
     最大期望算法(Expectation-maximization algorithm,又译期望最大化算法)在统计中被用于寻找,依赖于不可观察的隐性变量的概率模型中,参数的最大似然估计。
    在统计计算中,最大期望(EM)算法是在概率模型中寻找参数最大似然估计或者最大后验估计的算法,其中概率模型依赖于无法观测的隐藏变量(Latent Variable)。最大期望经常用在机器学习和计算机视觉的数据聚类(Data Clustering)领域。最大期望算法经过两个步骤交替进行计算,第一步是计算期望(E),利用对隐藏变量的现有估计值,计算其最大似然估计值;第二步是最大化(M),最大化在 E 步上求得的最大似然值来计算参数的值。M 步上找到的参数估计值被用于下一个 E 步计算中,这个过程不断交替进行。

    M是一个在已知部分相关变量的情况下,估计未知变量的迭代技术。EM的算法流程如下:

    1. 初始化分布参数
    2. 重复直到收敛:
      1. E步骤:估计未知参数的期望值,给出当前的参数估计。
      2. M步骤:重新估计分布参数,以使得数据的似然性最大,给出未知变量的期望估计。

    应用于缺失值

    最大期望过程说明
    我们用  表示能够观察到的不完整的变量值,用  表示无法观察到的变量值,这样  和  一起组成了完整的数据。 可能是实际测量丢失的数据,也可能是能够简化问题的隐藏变量,如果它的值能够知道的话。例如,在混合模型(Mixture Model)中,如果“产生”样本的混合元素成分已知的话最大似然公式将变得更加便利(参见下面的例子)。

    估计无法观测的数据
    让  代表矢量 :  定义的参数的全部数据的概率分布(连续情况下)或者概率聚类函数(离散情况下),那么从这个函数就可以得到全部数据的最大似然值,另外,在给定的观察到的数据条件下未知数据的条件分布可以表示为:


    六、数据挖掘十大经典算法(6) PageRank 

    PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由搜索引擎根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。Google用它来体现网页的相关性和重要性,在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。Google的创始人拉里·佩奇和谢尔盖·布林于1998年在斯坦福大学发明了这项技术。


    PageRank通过网络浩瀚的超链接关系来确定一个页面的等级。Google把从A页面到B页面的链接解释为A页面给B页面投票,Google根据投票来源(甚至来源的来源,即链接到A页面的页面)和投票目标的等级来决定新的等级。简单的说,一个高等级的页面可以使其他低等级页面的等级提升。

    PageRank让链接来"投票"
    一个页面的“得票数”由所有链向它的页面的重要性来决定,到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面(“链入页面”)的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级,相反如果一个页面没有任何链入页面,那么它没有等级。
    2005年初,Google为网页链接推出一项新属性nofollow,使得网站管理员和网志作者可以做出一些Google不计票的链接,也就是说这些链接不算作"投票"。nofollow的设置可以抵制垃圾评论。
    Google工具条上的PageRank指标从0到10。它似乎是一个对数标度算法,细节未知。PageRank是Google的商标,其技术亦已经申请专利。
    PageRank算法中的点击算法是由Jon Kleinberg提出的。

    PageRank算法

    1.PageRank 
    基本思想:如果网页T存在一个指向网页A的连接,则表明T的所有者认为A比较重要,从而把T的一部分重要性得分赋予A。这个重要性得分值为:PR(T)/C(T) 
    其中PR(T)为T的PageRank值,C(T)为T的出链数,则A的PageRank值为一系列类似于T的页面重要性得分值的累加。 
    优点:是一个与查询无关的静态算法,所有网页的PageRank值通过离线计算获得;有效减少在线查询时的计算量,极大降低了查询响应时间。 
    不足:人们的查询具有主题特征,PageRank忽略了主题相关性,导致结果的相关性和主题性降低;另外,PageRank有很严重的对新网页的歧视。 
    2.Topic-Sensitive PageRank(主题敏感的PageRank) 
    基本思想:针对PageRank对主题的忽略而提出。核心思想:通过离线计算出一个  PageRank向量集合,该集合中的每一个向量与某一主题相关,即计算某个页面关于不同主题的得分。
    主要分为两个阶段:主题相关的PageRank向量集合的计算和在线查询时主题的确定。 

    优点:根据用户的查询请求和相关上下文判断用户查询相关的主题(用户的兴趣)返回查询结果准确性高。 
    不足:没有利用主题的相关性来提高链接得分的准确性。 
    3.Hilltop 
    基本思想:与PageRank的不同之处:仅考虑专家页面的链接。主要包括两个步骤:专家页面搜索和目标页面排序。 
    优点:相关性强,结果准确。 
    不足:专家页面的搜索和确定对算法起关键作用,专家页面的质量决定了算法的准确性,而
     
    专家页面的质量和公平性难以保证;忽略了大量非专家页面的影响,不能反应整个Internet的民意;当没有足够的专家页面存在时,返回空,所以Hilltop适合对于查询排序进行求精。 
    那么影响google PageRank的因素有哪些呢? 
    1 与pr高的网站做链接: 
    2 内容质量高的网站链接 
    3加入搜索引擎分类目录 
    4 加入免费开源目录 
    5 你的链接出现在流量大、知名度高、频繁更新的重要网站上 
    6 google对DPF格式的文件比较看重。 
    7 安装Google工具条 
    8 域名和tilte标题出现关键词与meta标签等 
    9 反向连接数量和反向连接的等级 
    10 Google抓取您网站的页面数量 
    11导出链接数量


    七、数据挖掘十大经典算法(7) AdaBoost 

    AdaBoost,是英文"Adaptive Boosting"(自适应增强)的缩写,是一种机器学习方法,由Yoav Freund和Robert Schapire提出。

    AdaBoost方法的自适应在于:前一个分类器分错的样本会被用来训练下一个分类器。AdaBoost方法对于噪声数据和异常数据很敏感。但在一些问题中,AdaBoost方法相对于大多数其它学习算法而言,不会很容易出现过拟合现象。

    AdaBoost方法中使用的分类器可能很弱(比如出现很大错误率),但只要它的分类效果比随机好一点(比如两类问题分类错误率略小于0.5),就能够改善最终得到的模型。而错误率高于随机分类器的弱分类器也是有用的,因为在最终得到的多个分类器的线性组合中,可以给它们赋予负系数,同样也能提升分类效果。


    AdaBoost方法是一种迭代算法,在每一轮中加入一个新的弱分类器,直到达到某个预定的足够小的错误率。每一个训练样本都被赋予一个权重,表明它被某个分类器选入训练集的概率。

    如果某个样本点已经被准确地分类,那么在构造下一个训练集中,它被选中的概率就被降低;

    相反,如果某个样本点没有被准确地分类,那么它的权重就得到提高。通过这样的方式,AdaBoost方法能“聚焦于”那些较难分(更富信息)的样本上。

    在具体实现上,最初令每个样本的权重都相等,对于第k次迭代操作,我们就根据这些权重来选取样本点,进而训练分类器Ck。然后就根据这个分类器,来提高被它分错的的样本的权重,并降低被正确分类的样本权重。然后,权重更新过的样本集被用于训练下一个分类器Ck[2]。整个训练过程如此迭代地进行下去。

    Adaboost算法的具体步骤如下: 
    1. 给定训练样本集  ,其中  分别对应于正例样本和负例样本;  为训练的最大循环次数; 
    2. 初始化样本权重  ,即为训练样本的初始概率分布; 
    3. 第一次迭代: 
    (1)  训练样本的概率分布  下,训练弱分类器: 
    (2) 计算弱分类器的错误率: 
    (3) 选取  ,使得  最小 
    (4) 更新样本权重: 
    (5) 最终得到的强分类器: 
    Adaboost算法是经过调整的Boosting算法,其能够对弱学习得到的弱分类器的错误进行适应
    性调整。上述算法中迭代了次的主循环,每一次循环根据当前的权重分布对样本x定一个分
    布P,然后对这个分布下的样本使用若学习算法得到一个错误率为的弱分类器  ,对于这个算
    法定义的弱学习算法,对所有的  ,都有,而这个错误率的上限并不需要事先知道,实际上。
    每一次迭代,都要对权重进行更新。更新的规则是:减小弱分类器分类效果较好的数据的概
    率,增大弱分类器分类效果较差的数据的概率。最终的分类器是个弱分类器的加权平均。

    八、数据挖掘十大经典算法(8) kNN 

    1、K最近邻(k-Nearest  Neighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空
    间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。
    2、KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。  KNN方法虽然从原理上也依赖于极限定理,但在类别决策时,只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本,
    而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。 
    3、KNN算法不仅可以用于分类,还可以用于回归。通过找出一个样本的k个最近邻居,将这些邻居的属性的平均值赋给该样本,就可以得到该样本的属性。更有用的方法是将不同距离的
    邻居对该样本产生的影响给予不同的权值(weight),如权值与距离成正比。 
    4、该算法在分类时有个主要的不足是,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法(和该样本距离小的邻居权值大)来改进。

          该方法的另一个不足之处是计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。
    算法分类过程如下:
    1 首先我们事先定下k值(就是指k近邻方法的k的大小,代表对于一个待分类的数据点,我们要寻找几个它的邻居)。这边为了说明问题,我们取两个k值,分别为3和9;
    2 根据事先确定的距离度量公式(如:欧氏距离),得出待分类数据点和所有已知类别的样本点中,距离最近的k个样本。
    3 统计这k个样本点中,各个类别的数量。根据k个样本中,数量最多的样本是什么类别,我们就把这个数据点定为什么类别。

    训练样本是多维特征空间向量,其中每个训练样本带有一个类别标签。算法的训练阶段只包含存储的特征向量和训练样本的标签。 在分类阶段,k是一个用户定义的常数。一个没有类别标签的向量 (查询或测试点)将被归类为最接近该点的K个样本点中最频繁使用的一类。

     一般情况下,将欧氏距离作为距离度量,但是这是只适用于连续变量。在文本分类这种非连续变量情况下,

    另一个度量——重叠度量(或海明距离)可以用来作为度量。

    通常情况下,如果运用一些特殊的算法来计算度量的话,K近邻分类精度可显著提高,如运用大边缘最近邻法或者近邻成分分析法。

    “多数表决”分类的一个缺点是出现频率较多的样本将会主导测试点的预测结果,那是因为他们比较大可能出现在测试点的K邻域而测试点的属性又是通过K领域内的样本计算出来的。解决这个缺点的方法之一是在进行分类时将样本到测试点的距离考虑进去。
    K值得选择
    如何选择一个最佳的K值取决于数据。一般情况下,在分类时较大的K值能够减小噪声的影响。但会使类别之间的界限变得模糊。一个较好的K值能通过各种启发式技术来获取,比如,交叉验证。
    噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。对于选择特征向量进行分类已经作了很多研究。一个普遍的做法是利用进化算法优化功能扩展[3],还有一种较普遍的方法是利用训练样本的互信息进行选择特征。

    K近邻算法也适用于连续变量估计,比如适用反距离加权平均多个K近邻点确定测试点的值。该算法的功能有:
    1、从目标区域抽样计算欧式或马氏距离;
    2、在交叉验证后的RMSE基础上选择启发式最优的K邻域;
    3、计算多元k-最近邻居的距离倒数加权平均。

    九、数据挖掘十大经典算法(9) Naive Baye

    简介
    贝叶斯分类的基础是概率推理,就是在各种条件的存在不确定,仅知其出现概率的情况下,如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的,即假设样本每个特征与其他特征都不相关。举个例子,如果一种水果其具有红,圆,直径大概4英寸等特征,该水果可以被判定为是苹果。

    尽管这些特征相互依赖或者有些特征由其他特征决定,然而朴素贝叶斯分类器认为这些属性在判定该水果是否为苹果的概率分布上独立的。朴素贝叶斯分类器依靠精确的自然概率模型,在有监督学习的样本集中能获取得非常好的分类效果。在许多实际应用中,朴素贝叶斯模型参数估计使用最大似然估计方法,换而言之朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。

    尽管是带着这些朴素思想和过于简单化的假设,但朴素贝叶斯分类器在很多复杂的现实情形中仍能够取得相当好的效果。2004年,一篇分析贝叶斯分类器问题的文章揭示了朴素贝叶斯分类器取得看上去不可思议的分类效果的若干理论上的原因。尽管如此,2006年有一篇文章详细比较了各种分类方法,发现更新的方法(如boosted trees和随机森林)的性能超过了贝叶斯分类器。朴素贝叶斯分类器的一个优势在于只需要根据少量的训练数据估计出必要的参数(变量的均值和方差)。由于变量独立假设,只需要估计各个变量的方法,而不需要确定整个协方差矩阵。

    两种分类模型:

    分类是将一个未知样本分到几个预先已知类的过程。数据分类问题的解决是一个两步过程:

    第一步,建立一个模型,描述预先的数据集或概念集。通过分析由属性描述的样本(或实例,对象等)来构造模型。假定每一个样本都有一个预先定义的类,由一个被称为类标签的属性
    确定。为建立模型而被分析的数据元组形成训练数据集,该步也称作有指导的学习。 在众多的分类模型中,应用最为广泛的两种分类模型是:

    决策树模型(Decision Tree Model)和朴素贝叶斯模型(Naive  Bayesian  Model,NBC)

    决策树模型通过构造树来解决分类问题。

    1、首先利用训练数据集来构造一棵决策树,一旦树建立起来,它就可为未知样本产生一个分类。在分类问题中使用决策树模型有很多的优点,决策树便于使用,而且高效;根据决策树可以
    很容易地构造出规则,而规则通常易于解释和理解;决策树可很好地扩展到大型数据库中,同时它的大小独立于数据库的大小;决策树模型的另外一大优点就是可以对有许多属性的数据集构造决策树。

    决策树模型也有一些缺点,比如处理缺失数据时的困难,过度拟合问题的出现,以及忽略数据集中属性之间的相关性等。 
    2、和决策树模型相比,朴素贝叶斯模型发源于古典数学理论,有着坚实的数学基础,以及稳定的分类效率。同时,NBC模型所需估计的参数很少,对缺失数据不太敏感,算法也比较简单。
    理论上,NBC模型与其他分类方法相比具有最小的误差率。

    但是实际上并非总是如此,这是因为NBC模型假设属性之间相互独立,这个假设在实际应用中往往是不成立的,这给NBC
    模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时,NBC模型的分类效率比不上决策树模型。而在属性相关性较小时,NBC模型的性能最为良好。 

    贝叶斯分类器特点
    1、 需要知道先验概率
    先验概率是计算后验概率的基础。在传统的概率理论中,先验概率可以由大量的重复实验所获得的各类样本出现的频率来近似获得,其基础是“大数定律”,这一思想称为“频率主义”。而在称为“贝叶斯主义”的数理统计学派中,他们认为时间是单向的,许多事件的发生不具有可重复性,因此先验概率只能根据对置信度的主观判定来给出,也可以说由“信仰”来确定。
    2、按照获得的信息对先验概率进行修正
    在没有获得任何信息的时候,如果要进行分类判别,只能依据各类存在的先验概率,将样本划分到先验概率大的一类中。而在获得了更多关于样本特征的信息后,可以依照贝叶斯公式对先验概率进行修正,得到后验概率,提高分类决策的准确性和置信度。
    3、分类决策存在错误率
    由于贝叶斯分类是在样本取得某特征值时对它属于各类的概率进行推测,并无法获得样本真实的类别归属情况,所以分类决策一定存在错误率,即使错误率很低,分类错误的情况也可能发生。

    十、数据挖掘十大经典算法(10) CART 

    分类回归树(CART,Classification And Regression Tree)也属于一种决策树,分类回归树是一棵二叉树,且每个非叶子节点都有两个孩子,所以对于第一棵子树其叶子节点数比非叶子节点数多1。

    决策树生长的核心是确定决策树的分枝准则。
    1、 如何从众多的属性变量中选择一个当前的最佳分支变量;
    也就是选择能使异质性下降最快的变量。
    异质性的度量:GINI、TWOING、least squared deviation。
    前两种主要针对分类型变量,LSD针对连续性变量。
    代理划分、加权划分、先验概率
    2、 如何从分支变量的众多取值中找到一个当前的最佳分割点(分割阈值)。
    (1) 分割阈值:
     A、数值型变量——对记录的值从小到大排序,计算每个值作为临界点产生的子节点的异质性统计量。能够使异质性减小程度最大的临界值便是最佳的划分点。
     B、分类型变量——列出划分为两个子集的所有可能组合,计算每种组合下生成子节点的异质性。同样,找到使异质性减小程度最大的组合作为最佳划分点。
      

    在决策树的每一个节点上我们可以按任一个属性的任一个值进行划分。按哪种划分最好呢?有3个标准可以用来衡量划分的好坏:GINI指数、双化指数、有序双化指数。

    终止条件:

    一个节点产生左右孩子后,递归地对左右孩子进行划分即可产生分类回归树。这里的终止条件是什么?什么时候节点就可以停止分裂了?

    满足以下一个即停止生长。
    (1) 节点达到完全纯性;
    (2) 数树的深度达到用户指定的深度;
    (3) 节点中样本的个数少于用户指定的个数;
    (4) 异质性指标下降的最大幅度小于用户指定的幅度。

    剪枝

    当分类回归树划分得太细时,会对噪声数据产生过拟合作用。因此我们要通过剪枝来解决。剪枝又分为前剪枝和后剪枝:前剪枝是指在构造树的过程中就知道哪些节点可以剪掉,于是干脆不对这些节点进行分裂,在N皇后问题和背包问题中用的都是前剪枝,上面的χ2方法也可以认为是一种前剪枝;后剪枝是指构造出完整的决策树之后再来考查哪些子树可以剪掉。

    在分类回归树中可以使用的后剪枝方法有多种,比如:代价复杂性剪枝、最小误差剪枝、悲观误差剪枝等等。这里我们只介绍代价复杂性剪枝法。

    预测
    回归树——预测值为叶节点目标变量的加权均值
    分类树——某叶节点预测的分类值应是造成错判损失最小的分类值。



    展开全文
  • 一.KNN算法 1.既可用于分类也可用于回归 2.主要思想是找到预测样本中最近的K个邻居(一般通过欧式距离或者曼哈顿距离公式计算),用K个邻居的目标值中占多数的目标代表预测样本的目标 分类:K个邻居投票决定,少数...

    一.KNN算法
    1.既可用于分类也可用于回归
    2.主要思想是找到预测样本中最近的K个邻居(一般通过欧式距离或者曼哈顿距离公式计算),用K个邻居的目标值中占多数的目标代表预测样本的目标
    分类:K个邻居投票决定,少数服从多数
    回归:K个邻居目标的平均值
    3.所以KNN算法最关键的点就是K值的选取决定了模型的效果,一般可通过K-折交叉验证或者网格搜索法选择一个模型评分最优的K值
    二、线性回归
    线性回归的本质就是通过自变量(特征)的线性组合来描述因变量
    使用线性回归模型:各自变量(特征)之间不能有多重共线性或者 自变量(特征)的数量不能多于样本数,因为自变量的矩阵必须为满秩矩阵(可逆)
    1.预测函数: y= XW
    2.损失函数:loss= 1/2(y-y_)^2 y_为预测值
    求回归系数W:使用最小二乘法,它通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以简便地求得未知的数据,并使得这些求得的数据与实际数据之间误差的平方和为最小。即loss最小,当导数为0时最小
    推导过程:
    在这里插入图片描述
    X^TX必须可逆,即X为满秩矩阵
    三、岭回归、lasso回归

    当X^TX
    不可逆时,即特征之间有多重共线性,或者特征数多于样本数时,无法求出回归系数W,且当|X^TX|越趋近于0,
    |X^TX|的逆(逆=矩阵的伴随/矩阵的行列式)趋近于无穷大,即回归系数W趋近无穷大,这样的W没有意义
    故引入岭回归 = 线性回归+L2正则项
    在这里插入图片描述
    在这里插入图片描述
    1.可通过网格搜索法确定L2正则项系数
    2.交叉验证法确定λ值
    交叉验证法的思想是,将数据集拆分为k个数据组(每组样本量大体相当),从k组中挑选k-1组用于模型的训练,剩下的1组用于模型的测试,则会有k-1个训练集和测试集配对,每一种训练集和测试集下都会有对应的一个模型及模型评分(如均方误差),进而可以得到一个平均评分。对于λ值则选择平均评分最优的λ值。
    lasso回归
    lasso回归 = 线性回归+L1正则项
    岭回归无法剔除变量,而LASSO回归模型,将惩罚项由L2范数变为L1范数,可以将一些不重要的回归系数缩减为0,达到剔除变量的目的。故lasso回归比岭回归迭代快
    多元线性回归模型中,如果所有特征一起上,容易造成过拟合使测试数据误差方差过大;因此减少不必要的特征,简化模型是减小方差的一个重要步骤。除了直接对特征筛选,来也可以进行特征压缩,减少某些不重要的特征系数,系数压缩趋近于0就可以认为舍弃该特征。

    参数资料地址:https://blog.csdn.net/weixin_43374551/article/details/83688913?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

    逻辑斯蒂回归
    Logistic回归是一种广义线性回归模型,解决的是因变量为二分类变量的预测或判别问题。
    找到预测函数:sigmod函数把线性回归模型的预测值转变为[0,1]之间的概率值
    怎么求解参数β, 转化为条件概率,通过最大似然估计得到似然函数,对似然函数取对数,
    通过梯度下降法迭代求解
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    地址:https://blog.csdn.net/weixin_43374551/article/details/83721861
    树模型
    一、决策树
    ID3算法:1.特征选取:准则“信息增益”,每次根据最大的信息增益选取当前最佳的特征来分割数据,一旦按某特征切分后,该特征在算法之后的执行中将不再起作用
    信息增益=信息熵-条件熵。条件熵越小,信息增益越大
    在信息增益中,重要性的衡量标准就是看特征能够为分类系统带来多少信息,带来的信息越多,该特征越重要。
    信息熵:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    outlook特征的条件熵:
    在这里插入图片描述
    2.根据切分的特征生成一颗树
    3.剪枝(预剪枝:在树的生成过程时,提前停止,如max_depth参数。
    后剪枝:决策树构建好之后再比较剪枝前后误差,决定是否剪枝)
    ID3算法的缺点:1.ID3算法对可取值数目较多的特征有所偏好,因为特征值多的特征有相对较大的信息增益(信息增益反映的是给定一个条件以后,不确定性减少的程度。必然是分的越细的数据集确定性越高,这可能会导致过拟合)
    2.ID3算法特征只能是离散型特征
    C4.5算法
    ID3算法信息增益会偏向于取值较多的变量,极端例子如果一个变量的取值正好是N个,则其条件熵会等于0,在该变量下因变量的信息增益一定是最大的,为了克服这种缺点,
    C4.5算法使用信息增益比对根节点或中间节点进行选择。
    即特征A的信息增益/A的信息熵, 信息增益GainA(D)可能越大,但同时A的信息熵也会越大,这样就以商的形式实现了对信息增益的惩罚。
    CART
    cart 即分类回归树
    ID3和C4.5只能对离散型自变量进行分类,而CART可以处理连续型自变量。CART算法以基尼指数对根节点或中间节点进行选择。
    基尼指数代表了模型的不纯度,基尼指数越小,不纯度越低,特征越好
    在这里插入图片描述
    在这里插入图片描述
    首先对数据集特征{是否有房,婚姻状况,年收入}分别计算它们的Gini系数增益,取Gini系数增益值最大(即基尼指数最小)的属性作为决策树的根节点属性。

    根节点的Gini系数:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    剪枝的方法
    预剪枝:预剪枝是在树的生长过程中就对其进行必要的剪枝,如限制树的最大深度、限制中间节点和叶节点所包含的最小样本量、限制生成的最多叶节点数量等。
    后剪枝:树充分生长后再对其返工剪枝。
    1.误差降低剪枝法(Reduced-Error Pruning, REP)
    将某一非叶节点的 子孙节点删除,使其变为新的叶节点。新叶节点的类别确定是利用该节点剪枝前包含的所有叶节点投票,频数最高的类别作为新的类别。利用测试集的数据对比剪枝前后的误判样本量,如果新树的误判样本量少于老树,则可以剪枝,否则不可剪枝。重复此步骤直到达到最大的预测准确率。由于使用测试集,该方法可能导致剪枝过度。
    在这里插入图片描述
    3.代价复杂度剪枝法(Cost-Complexity Pruning, CCP)
    剪枝的代价是误判率会上升,但同时树的复杂度会减少,代价复杂度剪枝法引入了一个系数α来平衡代价和复杂度。
    在这里插入图片描述
    Nleaf为叶子节点个数
    决策树的优缺点
    优点:

    简单直观,生成的决策树很直观。
    基本不需要预处理,不需要提前归一化和处理缺失值。
    使用决策树预测的代价是O(log2m)。m为样本数。
    既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
    可以处理多维度输出的分类问题。
    相比于神经网络之类的黑盒分类模型,决策树在逻辑上可以很好解释。
    可以交叉验证的剪枝来选择模型,从而提高泛化能力。
    对于异常点的容错能力好,健壮性高。
    缺点:

    决策树算法非常容易过拟合,导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
    决策树会因为样本发生一点的改动,导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
    寻找最优的决策树是一个NP难题,我们一般是通过启发式方法,容易陷入局部最优。可以通过集成学习的方法来改善。
    有些比较复杂的关系,决策树很难学习,比如异或。这个就没有办法了,一般这种关系可以换神经网络分类方法来解决。
    如果某些特征的样本比例过大,生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

    集成学习树
    有两个流派
    bagging流派
    1.对原始数据集进行采样,每轮从原始样本集中使用Bootstraping的方法(有放回的采样)抽取n个训练样本,若进行K轮,得到K个训练集,训练K个模型(模型之间相互独立)
    (注:这里并没有具体的分类算法或回归方法,我们可以根据具体问题采用不同的分类或回归方法,如决策树、感知器等)
    2.对分类问题:将上步得到的k个模型采用投票的方式得到分类结果;对回归问题,计算上述模型的均值作为最后的结果。(所有模型的重要性相同)
    boosting流派
    主要思想是将弱分类器组装成一个强分类器
    引入了权值的概念,即采样时的每个样本都有权值,每个模型也都有权值
    1.在每一轮如何改变训练数据的权值或概率分布?
    答:通过提高那些在前一轮被弱分类器分错样例的权值,减小前一轮分对样例的权值,来使得分类器对误分的数据有较好的效果。因为提高了上一轮分错的样本,则上轮分错的样本在本轮有更大的概率被重新分类
    2.通过什么方式来组合弱分类器?
    答:通过加法模型将弱分类器进行线性组合,比如AdaBoost通过加权多数表决的方式,即增大错误率小的分类器的权值,同时减小错误率较大的分类器的权值。
    而提升树通过拟合残差的方式逐步减小残差,将每一步生成的模型叠加得到最终模型。

    boosting概率上的效果证明这里略去,只引出一个结论,不断地迭代更新能使得最终的结果无限接近最优分类,不过boosting会倾向于一直分错的样本,如果样本中有离群的错误样本(异常值),boosting就会出现效果不好的情况。

    Bagging和Boosting的区别:
    1.样本选择上:
    Bagging:训练集是在原始集中有放回选取的,从原始集中选出的各轮训练集之间是独立的。
    Boosting:每一轮的训练集不变,只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。

    2.样例权重:
    Bagging:使用均匀取样,每个样例的权重相等
    Boosting:根据错误率不断调整样例的权值,错误率越大则权重越大。

    3.预测函数权重:
    Bagging:所有预测函数的权重相等。
    Boosting:每个弱分类器都有相应的权重,对于分类误差小的分类器会有更大的权重。

    4.并行计算:
    Bagging:各个预测函数可以并行生成
    Boosting:各个预测函数只能顺序生成,因为后一个模型参数需要前一轮模型的结果。

    梯度下降法
    1、批量梯度下降(Batch Gradient Descent,BGD):
    批量梯度下降法是最原始的形式,它是指在每一次迭代时使用所有样本来进行梯度的更新
    优点:
      (1)一次迭代是对所有样本进行计算,此时利用矩阵进行操作,实现了并行。
      (2)由全数据集确定的方向能够更好地代表样本总体,从而更准确地朝向极值所在的方向。当目标函数为凸函数时,BGD一定能够得到全局最优。
    缺点:
      (1)当样本数目很大时,每迭代一步都需要对所有样本计算,训练过程会很慢。
      从迭代的次数上来看,BGD迭代的次数相对较少。
      
    2、随机梯度下降(Stochastic Gradient Descent,SGD):
    随机梯度下降法不同于批量梯度下降,随机梯度下降是每次迭代使用一个样本来对参数进行更新。使得训练速度加快
      优点:
      (1)由于不是在全部训练数据上的损失函数,而是在每轮迭代中,随机优化某一条训练数据上的损失函数,这样每一轮参数的更新速度大大加快。
      缺点:
      (1)准确度下降。由于即使在目标函数为强凸函数的情况下,SGD仍旧无法做到线性收敛。
      (2)可能会收敛到局部最优,由于单个样本并不能代表全体样本的趋势。
      (3)不易于并行实现。
      
    3、小批量梯度下降(Mini-Batch Gradient Descent, MBGD):
    小批量梯度下降,是对批量梯度下降以及随机梯度下降的一个折中办法。其思想是:每次迭代 使用 ** batch_size** 个样本来对参数进行更新
    优点:
      (1)通过矩阵运算,每次在一个batch上优化神经网络参数并不会比单个数据慢太多。
      (2)每次使用一个batch可以大大减小收敛所需要的迭代次数,同时可以使收敛到的结果更加接近梯度下降的效果。(比如上例中的30W,设置batch_size=100时,需要迭代3000次,远小于SGD的30W次)
      (3)可实现并行化。
      缺点:
      (1)batch_size的不当选择可能会带来一些问题。

      batcha_size的选择带来的影响:
    

    (1)在合理地范围内,增大batch_size的好处:
        a. 内存利用率提高了,大矩阵乘法的并行化效率提高。
        b. 跑完一次 epoch(全数据集)所需的迭代次数减少,对于相同数据量的处理速度进一步加快。
        c. 在一定范围内,一般来说 Batch_Size 越大,其确定的下降方向越准,引起训练震荡越小。
      (2)盲目增大batch_size的坏处:
        a. 内存利用率提高了,但是内存容量可能撑不住了。
        b. 跑完一次 epoch(全数据集)所需的迭代次数减少,要想达到相同的精度,其所花费的时间大大增加了,从而对参数的修正也就显得更加缓慢。
        c. Batch_Size 增大到一定程度,其确定的下降方向已经基本不再变化。
    地址:https://www.cnblogs.com/bnuvincent/p/11183206.html
    RF(随机森林)
    它有两层随机,1.每轮从原始数据集中有放回的选取n个样本
    2.每个训练集生成cart树时,特征的选取是随机的,随机的从所有特征中选择一部分特征,从部分特征中选择最佳的那个特征作为切分点。
      
    每棵树的按照如下规则生成:
      1)如果训练集大小为N,对于每棵树而言,随机且有放回地从训练集中的抽取N个训练样本(这种采样方式称为bootstrap sample方法),作为该树的训练集;
    从这里我们可以知道:每棵树的训练集都是不同的,而且里面包含重复的训练样本(理解这点很重要)。

    为什么要随机抽样训练集?(add @2016.05.28)
    如果不进行随机抽样,每棵树的训练集都一样,那么最终训练出的树分类结果也是完全一样的,这样的话完全没有bagging的必要;

    为什么要有放回地抽样?(add @2016.05.28)
    我理解的是这样的:如果不是有放回的抽样,那么每棵树的训练样本都是不同的,都是没有交集的,这样每棵树都是"有偏的",都是绝对"片面的"(当然这样说可能不对),也就是说每棵树训练出来都是有很大的差异的;而随机森林最后分类取决于多棵树(弱分类器)的投票表决,这种表决应该是"求同",因此使用完全不同的训练集来训练每棵树这样对最终分类结果是没有帮助的,这样无异于是"盲人摸象"。

    2)如果每个样本的特征维度为M,指定一个常数m<<M,随机地从M个特征中选取m个特征子集,每次树进行分裂时,从这m个特征中选择最优的;

    3)每棵树都尽最大程度的生长,并且没有剪枝过程。

    一开始我们提到的随机森林中的“随机”就是指的这里的两个随机性。两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入,使得随机森林不容易陷入过拟合,并且具有很好得抗噪能力(比如:对缺省值不敏感)。
    随机森林分类效果(错误率)与两个因素有关
    森林中任意两棵树的相关性:相关性越大,错误率越大;
    森林中每棵树的分类能力:每棵树的分类能力越强,整个森林的错误率越低。
      减小特征选择个数m,树的相关性和分类能力也会相应的降低;增大m,两者也会随之增大。所以关键问题是如何选择最优的m(或者是范围),这也是随机森林唯一的一个参数。

    如果不放回抽样,每棵树用的样本完全不同,结果是有偏的,基学习器之间的相似性小,投票结果差,模型偏差大
    如果不抽样,基学习器用所有样本,那么模型的泛化能力弱,基学习器之前相似性太大差异性太小,模型的偏差大
    为什么不随机抽样? 自助采样首先可以产生一部分袋外样本,可以用来做袋外估计,另一方自助采样一定程度上改变了每个基学习器的所用数据的样本分布,一定程度上引入了噪音,增加了模型的泛化能力
    在这里插入图片描述

    GBDT(梯度提升树)
    1.gbdt 的算法的流程?
    首先gbdt 是通过采用加法模型(即基函数的线性组合),以及不断减小训练过程产生的残差来达到将数据分类或者回归的算法。
    gbdt通过多轮迭代,每轮迭代产生一个弱分类器,每个分类器在上一轮分类器的残差基础上进行训练。对弱分类器的要求一般是足够简单,并且是低方差和高偏差的。因为训练的过程是通过降低偏差来不断提高最终分类器的精度
    弱分类器一般会选择为cart tree(也就是分类回归树)。由于上述高偏差和简单的要求 每个分类回归树的深度不会很深。最终的总分类器 是将每轮训练得到的弱分类器加权求和得到的

    损失函数:如果我们选择平方损失函数,那么这个差值其实就是我们平常所说的残差。
    其实我们真正关注的,1.是希望损失函数能够不断的减小,2.是希望损失函数能够尽可能快的减小。所以如何尽可能快的减小呢?
    让损失函数沿着梯度方向的下降。这个就是gbdt 的 gb的核心了。 利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值去拟合一个回归树。gbdt 每轮迭代的时候,都去拟合损失函数在当前模型下的负梯度。

    2.gbdt如何选择特征?
    gbdt选择特征的细节其实是想问你CART Tree生成的过程
    CART Tree 生成的过程其实就是一个选择特征的过程,假设我们目前总共有 M 个特征。第一步我们需要从中选择出一个特征 j,做为二叉树的第一个节点。然后对特征 j 的值选择一个切分点 m,一个样本的特征j的值 如果小于m,则分为一类,如果大于m,则分为另外一类。如此便构建了CART 树的一个节点。其他节点的生成过程和这个是一样的。现在的问题是在每轮迭代的时候,如何选择这个特征 j,以及如何选择特征 j 的切分点 m:

    原始的gbdt的做法非常的暴力,首先遍历每个特征,然后对每个特征遍历它所有可能的切分点,找到最优特征 m 的最优切分点 j
    我们先遍历训练样本的所有的特征,对于特征 j,我们遍历特征 j 所有特征值的切分点 c。找到可以让下面这个式子最小的特征 j 以及切分点c.
    在这里插入图片描述
    举个例子:
    gbdt 无论用于分类还是回归一直都是使用的CART 回归树,因为GBDT的每轮训练在上一轮的训练的残差基础之上进行训练的。这里的残差就是当前模型的负梯度值 。这个要求每轮迭代的时候,弱分类器的输出的结果相减是有意义的。残差相减是有意义的。如果是两个分类类别,类别相减没有意义。
    gbdt 多分类:我们在训练的时候,是针对样本 X 每个可能的类都训练一个分类回归树
    在这里插入图片描述
    这是一个有6个样本的三分类问题,我们用一个三维向量来标志样本的label。[1,0,0] 表示样本属于山鸢尾,[0,1,0] 表示样本属于杂色鸢尾,[0,0,1] 表示属于维吉尼亚鸢尾。
    gbdt 的多分类是针对每个类都独立训练一个 CART Tree。所以这里,我们将针对山鸢尾类别训练一个 CART Tree 1。杂色鸢尾训练一个 CART Tree 2 。维吉尼亚鸢尾训练一个CART Tree 3,这三个树相互独立。
    我们以样本 1 为例。针对 CART Tree1 的训练样本是[5.1,3.5,1.4,0.2],label 是 1
    最终输入到模型当中的为[5.1,3.5,1.4,0.2,1]
    针对 CART Tree2最终输入到模型当中的为[5.1,3.5,1.4,0.2,0]
    针对 CART Tree3最终输入到模型当中的为[5.1,3.5,1.4,0.2,0]
    下面我们来看 CART Tree1 是如何生成的,其他树 CART Tree2 , CART Tree 3的生成方式是一样的。CART Tree1的生成过程是从这四个特征中找一个特征做为CART Tree1 的节点。比如花萼长度做为节点。6个样本当中花萼长度 大于5.1 cm的就是 A类,小于等于 5.1 cm 的是B类。生成的过程其实非常简单,
    问题 1.是哪个特征最合适? 2.是这个特征的什么特征值作为切分点?
    即使我们已经确定了花萼长度做为节点。花萼长度本身也有很多值。在这里我们的方式是遍历所有的可能性,找到一个最好的特征和它对应的最优特征值可以让当前式子的值最小。
    在这里插入图片描述
    我们以第一个特征的第一个特征值为例。R1 为所有样本中花萼长度小于 5.1 cm 的样本集合,R2 为所有样本当中花萼长度大于等于 5.1cm 的样本集合。所以 R1={2}(只有样本2小于5.1cm),R2={1,3,4,5,6}
    在这里插入图片描述
    y1 为 R1 所有样本的label 的均值 1/1=1。y2 为 R2 所有样本的label 的均值 (1+0+0+0+0)/5=0.2 损失函数:(实际值-预测的样本均值)的平方和
    下面便开始针对所有的样本计算这个式子的值
    山鸢尾类型在特征1 的第一个特征值的损失值:
    (1-0.2)^2 + (1-1)^2 + (0-0.2)2+(0-0.2)2+(0-0.2)^2 +(0-0.2)^2= 0.8
    接着我们计算第一个特征的第二个特征值,计算方式同上
    在这里插入图片描述
    R1 为所有样本中 花萼长度小于 4.9 cm 的样本集合,R2 为所有样本当中 花萼长度大于等于 4.9 cm 的样本集合.所以 R1={},R2={1,2,3,4,5,6},y1 为 R1 所有样本的label 的均值 = 0。y2 为 R2 所有样本的label 的均值 (1+1+0+0+0+0)/6=0.3333
    山鸢尾类型在特征1 的第二个特征值的损失值:
    (1-0.333)^2+ (1-0.333)^2 + (0-0.333)2+(0-0.333)2+(0-0.333)^2 +(0-0.333)^2 = 2.244189. 这里的损失值大于 特征一的第一个特征值的损失值,所以我们不取这个特征的特征值。
    这样我们可以遍历所有特征的所有特征值,找到让这个式子最小的特征以及其对应的特征值
    一共有24种情况,4个特征*每个特征有6个特征值
    在这里我们算出来让这个式子最小的特征花萼长度,特征值为5.1 cm。这个时候损失函数最小为 0.8。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    GBDT如何进行特征组合的
    在这里插入图片描述
    地址:https://www.cnblogs.com/bnuvincent/p/9693190.html

    RF(随机森林)与GBDT之间的区别与联系
    相同点:

    都是由多棵树组成,最终的结果都是由多棵树一起决定。
    RF和GBDT在使用CART树时,可以是分类树或者回归树。
    不同点:
    组成随机森林的树可以并行生成,而GBDT是串行生成
    随机森林的结果是多数表决表决的,而GBDT则是多棵树累加之和
    随机森林对异常值不敏感,而GBDT对异常值比较敏感
    随机森林是减少模型的方差,而GBDT是减少模型的偏差
    随机森林不需要进行特征归一化。而GBDT则需要进行特征归一化

    XGBoost
    XGBoost 高效地实现了GBDT算法并进行了算法和工程上的许多改进,XGBoost本质上还是一个GBDT,但是力争把速度和效率发挥到极致
    1.1 XGBoost树的定义
    先来举个例子,我们要预测一家人对电子游戏的喜好程度,考虑到年轻和年老相比,年轻更可能喜欢电子游戏,以及男性和女性相比,男性更喜欢电子游戏,故先根据年龄大小区分小孩和大人,然后再通过性别区分开是男是女,逐一给各人在电子游戏喜好程度上打分,如下图所示。
    在这里插入图片描述
    就这样,训练出了2棵树tree1和tree2,类似之前gbdt的原理,两棵树的结论累加起来便是最终的结论,所以小孩的预测分数就是两棵树中小孩所落到的结点的分数相加:2 + 0.9 = 2.9。爷爷的预测分数同理:-1 + (-0.9)= -1.9。具体如下图所示:
    在这里插入图片描述
    如果不考虑工程实现、解决问题上的一些差异,XGBoost与GBDT比较大的不同就是目标函数的定义。XGBoost的目标函数如下图所示:
    在这里插入图片描述
    其中:
    红色箭头所指向的L 即为损失函数(比如平方损失函数:l(yi,yi)=(yi−yi)2)
    红色方框所框起来的是正则项(包括L1正则、L2正则)
    红色圆圈所圈起来的为常数项
    对于f(x),XGBoost利用泰勒展开三项,做一个近似。f(x)表示的是其中一颗回归树。

    XGBoost的核心算法思想不难,基本就是:
    不断地添加树,不断地进行特征分裂来生长一棵树,每次添加一个树,其实是学习一个新函数f(x),去拟合上次预测的残差。
    当我们训练完成得到k棵树,我们要预测一个样本的分数,其实就是根据这个样本的特征,在每棵树中会落到对应的一个叶子节点,每个叶子节点就对应一个分数
    最后只需要将每棵树对应的分数加起来就是该样本的预测值。
    在这里插入图片描述
    那接下来,我们如何选择每一轮加入什么 f 呢?答案是非常直接的,选取一个 f 来使得我们的目标函数尽量最大地降低。这里 f 可以使用泰勒展开公式近似。
    在这里插入图片描述
    实质是把样本分配到叶子结点会对应一个obj,优化过程就是obj优化。也就是分裂节点到叶子不同的组合,不同的组合对应不同obj,所有的优化围绕这个思想展开。到目前为止我们讨论了目标函数中的第一个部分:训练误差。接下来我们讨论目标函数的第二个部分:正则项,即如何定义树的复杂度。
    1.2 正则项:树的复杂度
    XGBoost对树的复杂度包含了两个部分:

    一个是树里面叶子节点的个数T
    一个是树上叶子节点的得分w的L2模平方(对w进行L2正则化,相当于针对每个叶结点的得分增加L2平滑,目的是为了避免过拟合)
    在这里插入图片描述
    我们再来看一下XGBoost的目标函数(损失函数揭示训练误差 + 正则化定义复杂度):
    在这里插入图片描述
    正则化公式也就是目标函数的后半部分,对于上式而言,y′i是整个累加模型的输出,正则化项∑kΩ(ft)是则表示树的复杂度的函数,值越小复杂度越低,泛化能力越强
    1.3 树该怎么长
    一棵树的生成是由一个节点一分为二,然后不断分裂最终形成为整棵树。那么树怎么分裂的就成为了接下来我们要探讨的关键。对于一个叶子节点如何进行分裂,XGBoost作者在其原始论文中给出了一种分裂节点的方法:枚举所有不同树结构的贪心法

    XGBoost使用了和CART回归树一样的想法,利用贪婪算法,遍历所有特征的所有特征划分点,不同的是使用的目标函数不一样。具体做法就是分裂后的目标函数值比单子叶子节点的目标函数的增益,同时为了限制树生长过深,还加了个阈值,只有当增益大于该阈值才进行分裂。从而继续分裂,形成一棵树,再形成一棵树,每次在上一次的预测基础上取最优进一步分裂/建树。
    1.4 如何停止树的循环生成
    凡是这种循环迭代的方式必定有停止条件,什么时候停止呢?简言之,设置树的最大深度、当样本权重和小于设定阈值时停止生长以防止过拟合。具体而言,则

    当引入的分裂带来的增益小于设定阀值的时候,我们可以忽略掉这个分裂,所以并不是每一次分裂loss function整体都会增加的,有点预剪枝的意思,阈值参数为(即正则项里叶子节点数T的系数);
    当树达到最大深度时则停止建立决策树,设置一个超参数max_depth,避免树太深导致学习局部样本,从而过拟合;
    样本权重和小于设定阈值时则停止建树。什么意思呢,即涉及到一个超参数-最小的样本权重和min_child_weight,和GBM的 min_child_leaf 参数类似,但不完全一样。大意就是一个叶子节点样本太少了,也终止同样是防止过拟合;
    2. XGBoost与GBDT有什么不同
    除了算法上与传统的GBDT有一些不同外,XGBoost还在工程实现上做了大量的优化。总的来说,两者之间的区别和联系可以总结成以下几个方面。

    GBDT是机器学习算法,XGBoost是该算法的工程实现。
    在使用CART作为基分类器时,XGBoost显式地加入了正则项来控制模 型的复杂度,有利于防止过拟合,从而提高模型的泛化能力。
    GBDT在模型训练时只使用了代价函数的一阶导数信息,XGBoost对代 价函数进行二阶泰勒展开,可以同时使用一阶和二阶导数。
    传统的GBDT采用CART作为基分类器,XGBoost支持多种类型的基分类 器,比如线性分类器。
    传统的GBDT在每轮迭代时使用全部的数据,XGBoost则采用了与随机 森林相似的策略,支持对数据进行采样。
    传统的GBDT没有设计对缺失值进行处理,XGBoost能够自动学习出缺 失值的处理策略。
    3. 为什么XGBoost要用泰勒展开,优势在哪里?
    XGBoost使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准. 使用泰勒展开取得函数做自变量的二阶导数形式, 可以在不选定损失函数具体形式的情况下, 仅仅依靠输入数据的值就可以进行叶子分裂优化计算, 本质上也就把损失函数的选取和模型算法优化/参数选择分开了. 这种去耦合增加了XGBoost的适用性, 使得它按需选取损失函数, 可以用于分类, 也可以用于回归。
    地址:https://www.cnblogs.com/mantch/p/11164221.html

    1.xgboost相比传统gbdt有何不同?
    传统GBDT以CART作为基分类器,xgboost还支持线性分类器,这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归(分类问题)或者线性回归(回归问题)。

    传统GBDT在优化时只用到一阶导数信息,xgboost则对代价函数进行了二阶泰勒展开,同时用到了一阶和二阶导数。顺便提一下,xgboost工具支持自定义代价函数,只要函数可一阶和二阶求导。

    xgboost在代价函数里加入了正则项,用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲,正则项降低了模型的variance,使学习出来的模型更加简单,防止过拟合,这也是xgboost优于传统GBDT的一个特性。

    Shrinkage(缩减),相当于学习速率(xgboost中的eta)。xgboost在进行完一次迭代后,会将叶子节点的权重乘上该系数,主要是为了削弱每棵树的影响,让后面有更大的学习空间。实际应用中,一般把eta设置得小一点,然后迭代次数设置得大一点。(补充:传统GBDT的实现也有学习速率)

    对缺失值的处理。对于特征的值有缺失的样本,xgboost可以自动学习出它的分裂方向。
    2. xgboost为什么快?
    列抽样(column subsampling)。xgboost借鉴了随机森林的做法,支持列抽样,不仅能降低过拟合,还能减少计算,这也是xgboost异于传统gbdt的一个特性。借鉴了Random Forest的思想,sklearn里的gbm好像也有类似实现。
    这一点借鉴的是随机森林,就是对特征属性抽样。行采样是对样本的数目采样
    3. xgboost如何支持并行?
    xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的?注意xgboost的并行不是tree粒度的并行,xgboost也是一次迭代完才能进行下一次迭代的(第t次迭代的代价函数里包含了前面t-1次迭代的预测值)。xgboost的并行是在特征粒度上的。我们知道,决策树的学习最耗时的一个步骤就是对特征的值进行排序(因为要确定最佳分割点),xgboost在训练之前,预先对数据进行了排序,然后保存为block结构,后面的迭代中重复地使用这个结构,大大减小计算量。这个block结构也使得并行成为了可能,在进行节点的分裂时,需要计算每个特征的增益,最终选增益最大的那个特征去做分裂,那么各个特征的增益计算就可以开多线程进行。
    4. 随机森林是怎样改变决策树容易过拟合的问题的?
    1)Boostrap从袋内有放回的抽取样本值
      2)每次随机抽取一定数量的特征(通常为sqr(n))。
      分类问题:采用Bagging投票的方式选择类别频次最高的
      回归问题:直接取每颗树结果的平均值。
    5. XGBoost怎么给特征评分?
    在训练的过程中,通过Gini指数选择分离点的特征,一个特征被选中的次数越多,那么该特征评分越高。
    6. 怎么理解决策树、xgboost能处理缺失值?而有的模型(svm)对缺失值比较敏感
    sklearn包里的算法代入数据不能有缺失值,而xgboost可以。不是xgboost对缺失值不敏感,而是它对缺失值有默认的处理方法。就是把缺失值分别放到左叶子节点和右叶子节点中,计算增益。哪个增益大就放到哪个叶子节点

    在这里插入图片描述
    在这里插入图片描述
    7. 为什么XGBoost要用泰勒展开,优势在哪里?
    XGBoost使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准. 使用泰勒展开取得二阶倒数形式, 可以在不选定损失函数具体形式的情况下用于算法优化分析.本质上也就把损失函数的选取和模型算法优化/参数选择分开了. 这种去耦合增加了XGBoost的适用性。
    在这里插入图片描述
    在这里插入图片描述

    8. XGBoost如何寻找最优特征?是有放回还是无放回的呢?
    XGBoost在训练的过程中给出各个特征的评分,从而表明每个特征对模型训练的重要性.。XGBoost利用梯度优化模型算法, 样本是不放回的(想象一个样本连续重复抽出,梯度来回踏步会不会高兴)。
    XGBoost还提出了两种防止过拟合的方法:Shrinkage and Column Subsampling。Shrinkage方法就是在每次迭代中对树的每个叶子结点的分数乘上一个缩减权重η,这可以使得每一棵树的影响力不会太大,留下更大的空间给后面生成的树去优化模型。Column Subsampling类似于随机森林中的选取部分特征进行建树。其可分为两种,一种是按层随机采样,在对同一层内每个结点分裂之前,先随机选择一部分特征,然后只需要遍历这部分的特征,来确定最优的分割点。另一种是随机选择特征,则建树前随机选择一部分特征然后分裂就只遍历这些特征。一般情况下前者效果更好。
    9. 请问GBDT和XGBoost的区别是什么?
    XGBoost类似于GBDT的优化版,不论是精度还是效率上都有了提升。与GBDT相比,具体的优点有:
    1.损失函数是用泰勒展式二项逼近,而不是像GBDT里的就是一阶导数;
    2.对树的结构进行了正则化约束,防止模型过度复杂,降低了过拟合的可能性;
    3.节点分裂的方式不同,GBDT是用的基尼系数,XGBoost是经过优化推导后的。

    xgboost选择某个特征的分裂点位的方法有两种,一种是全局扫描法,另一种是候选分位点法。

    全局扫描法将所有样本该特征的取值按从小到大排列,将所有可能的分裂位置都试一遍,找到其中增益最大的那个分裂点,其计算复杂度和叶子节点上的样本特征不同的取值个数成正比。

    而候选分位点法是一种近似算法,仅选择常数个(如256个)候选分裂位置,然后从候选分裂位置中找出最优的那个。
    对于连续型特征值,当样本数量非常大,该特征取值过多时,遍历所有取值会花费很多时间,且容易过拟合。因此XGBoost思想是对特征进行分桶,即找到l个划分点,将位于相邻分位点之间的样本分在一个桶中。在遍历该特征的时候,只需要遍历各个分位点,从而计算最优划分。从算法伪代码中该流程还可以分为两种,全局的近似是在新生成一棵树之前就对各个特征计算分位点并划分样本,之后在每次分裂过程中都采用近似划分,而局部近似就是在具体的某一次分裂节点的过程中采用近似算法。

    SVM(支持向量机)
    数学原理
    地址:https://zhuanlan.zhihu.com/p/31886934
    在这里插入图片描述
    SVM是一种二分类模型,它的基本模型是定义在特征空间上的间隔最大的线性分类器
    SVM还引入核函数,这使它成为实质上的非线性分类器。SVM的的学习策略就是间隔最大化,可形式化为一个求解凸二次规划的问题,也等价于正则化的损失函数的最小化问题。SVM的学习算法就是求解凸二次规划的最优化算法。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    SVM面试
    一、SVM 原理

    SVM 是一种二分类模型。它的基本模型是在特征空间中寻找间隔最大化的分离超平面(间隔最大使它有别于普通的感知机)的线性分类器。

    1).当训练样本线性可分时,通过几何间隔最大化,学习一个线性分类器,即线性可分支持向量机;

    2).当训练数据近似线性可分时,引入松弛变量(放宽约束条件),通过软间隔最大化,学习一个线性分类器,即线性支持向量机;

    3)当训练数据线性不可分时,通过使用核技巧及软间隔最大化,学习非线性支持向量机。

    以上各种情况下的数学推导应当掌握,硬间隔最大化(几何间隔)、学习的对偶问题、软间隔最大化(引入松弛变量)、非线性支持向量机(核技巧)。
    二. SVM 为什么采用间隔最大化
    当训练数据线性可分时,存在无穷个分离超平面可以将两类数据正确分开。感知机利用误分类最小策略,求得分离超平面,不过此时的解有无穷多个。线性可分支持向量机利用间隔最大化求得最优分离超平面,这时,解是唯一的。另一方面,此时的分隔超平面所产生的分类结果是最鲁棒的,对未知实例的泛化能力最强。
    1 确定超平面及函数间隔
    由空间上的平面公式确定超平面 wx+b = 0,且 |wx+b| 表示点 x 到平面上的距离。正类负例位于分割平面两侧,因此y(wx+b) 可同时表示分类正确性以及距离确信度。这也就是函数间隔,其被定义为训练集中所有点到超平面距离的最小值。
    2 几何间隔
    由于成比例地缩放w和b会使得 |wx+b| 跟着成比例缩放,因此,需要对法向量w加上约束,使得间隔是确定的,也就是函数间隔整体除以 ||w||,也就得到了几何间隔
    3 间隔最大化(硬间隔)
    分为硬间隔最大和软间隔最大
    SVM的基本思想就是求解可以正确划分数据集并且几何间隔最大的分离超平面,其原因是线性可分超平面有无数个,但是间隔最大超平面是唯一的。
    间隔最大化的意思就是以充分大的确信度对训练数据进行分类,也就是说,不仅将正负实例分开,同时对最难分的实例点(距离超平面最近的点)也有足够大的确信度将其分离。
    4 支持向量
    与超平面最近的点被称为支持向量,也就是使得原始问题约束项成立的点。
    实际上离超平面很远的点已经被正确分类,我们让它离超平面更远并没有意义。反而我们最关心是那些离超平面很近的点,这些点很容易被误分类。如果我们可以让离超平面比较近的点尽可能的远离超平面,那么我们的分类效果会好有一些
    三. SVM的目标
    有两个目标:第一个是使间隔最大化,即W的模最小化,第二个是使样本正确分类
    四. 为什么要将求解 SVM 的原始问题转换为其对偶问题
    之所以说换为对偶问题更容易求解,其原因在于降低了算法的计算复杂度。在原问题下,算法的复杂度与样本维度相关,即等于权重w的维度,而在对偶问题下,算法复杂度与样本数量有关,即为拉格朗日算子的个数。
    因此,如果你是做线性分类,且样本维度低于样本数量的话,在原问题下求解就好了,Liblinear之类的线性SVM默认都是这样做的;但如果你是做非线性分类,那就会涉及到升维(比如使用高斯核做核函数,其实是将样本升到无穷维),升维后的样本维度往往会远大于样本数量,此时显然在对偶问题下求解会更好。

    另一方面,我们有分析过,只有在支持向量上的样本对应的拉格朗日算子λ才大于0,其余的λ都是=0,而转为对偶问题的计算对象仅有λ,所以大大降低了计算复杂度。
    五. 为什么 SVM 要引入核函数
    当样本在原始空间线性不可分时,可将样本从原始空间映射到一个更高维的特征空间,使得样本在这个特征空间内线性可分。而引入这样的映射后,所要求解的对偶问题的求解中,无需求解真正的映射函数,而只需要知道其核函数。核函数的定义:K(x,y)=<ϕ(x),ϕ(y)>,即在特征空间的内积等于它们在原始样本空间中通过核函数 K 计算的结果。一方面数据变成了高维空间中线性可分的数据,另一方面不需要求解具体的映射函数,只需要给定具体的核函数即可,这样使得求解的难度大大降低。
    核函数的真正意义是做到了没有真正映射到高维空间却达到了映射的作用,即减少了大量的映射计算。
    六、为什么SVM对缺失数据敏感
    这里说的缺失数据是指缺失某些特征数据,向量数据不完整。SVM 没有处理缺失值的策略。而 SVM 希望样本在特征空间中线性可分,所以特征空间的好坏对SVM的性能很重要。缺失特征数据将影响训练结果的好坏。
    七、SVM 核函数之间的区别
    一般选择线性核和高斯核,也就是线性核与 RBF 核。 线性核:主要用于线性可分的情形,参数少,速度快,对于一般数据,分类效果已经很理想了。 RBF 核:主要用于线性不可分的情形,参数多,分类结果非常依赖于参数。有很多人是通过训练数据的交叉验证来寻找合适的参数,不过这个过程比较耗时。 如果 Feature 的数量很大,跟样本数量差不多,这时候选用线性核的 SVM。 如果 Feature 的数量比较小,样本数量一般,不算大也不算小,选用高斯核的 SVM。

    利用专家先验知识选定核函数,例如已经知道问题是线性可分的,就可以使用线性核,不必选用非线性核。
    如果特征的数量大到和样本数量差不多,则选用线性核函数SVM或LR。
    如果特征的数量小,样本的数量正常,则选用高斯核函数SVM。
    如果特征的数量小,样本数量很多,由于求解最优化问题的时候,目标函数涉及两两样本计算内积,使用高斯核明显计算量会大于线性核,所以手动添加一些特征,使得线性可分,然后可以用LR或者线性核的SVM;
    利用交叉验证,试用不同的核函数,误差最小的即为效果最好的核函数。
    混合核函数方法,将不同的核函数结合起来。

    SVM对噪声敏感
    少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单,而且具有较好的“鲁棒”性。这种“鲁棒”性主要体现在:
    增、删非支持向量样本对模型没有影响;
    支持向量样本集具有一定的鲁棒性;
    有些成功的应用中,SVM 方法对核的选取不敏感
    但当噪声出现的过多,以及当噪声出现并成为支持向量时,那么噪声对模型对影响是巨大的。所以此时SVM对噪声不具备鲁棒性!以下两种情况会增大噪声成为支持向量的概率:
    噪声数量太多
    噪声以新的分布形式出现,与原先样本集的噪声分布表现的相当不同。此时噪声也有大概率落在最大分类间隔中间,从而成为支持向量,大大影响模型。
    所以我们常说的鲁棒性其实是主要是体现在对Outlier(异常点、离群点)上。
    SVM在大数据上有哪些缺陷
    SVM的空间消耗主要是在存储训练样本和核矩阵,由于SVM是借助二次规划来求解支持向量,而求解二次规划将涉及m阶矩阵的计算(m为样本的个数),当m数目很大时该矩阵的存储和计算将耗费大量的及其内存和运算时间。如果数据量很大,SVM的训练时间就会比较长,所以SVM在大数据的使用中比较受限。
    SVM参数C的选择
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    朴素贝叶斯
    先验概率:
    通过经验来判断事情发生的概率,比如说“贝叶死”的发病率是万分之一,就是先验概率。
    后验概率:
    后验概率就是发生结果之后,推测原因的概率。比如说某人查出来了患有“贝叶死”,那么患病的原因可能是 A、B 或 C。**患有“贝叶死”是因为原因 A 的概率就是后验概率。**它是属于条件概率的一种。
    条件概率:
    事件 A 在另外一个事件 B 已经发生条件下的发生概率,表示为 P(A|B)。比如原因 A 的条件下,患有“贝叶死”的概率,就是条件概率

    朴素贝叶斯分类常用于文本分类,尤其是对于英文等语言来说,分类效果很好。它常用于垃圾文本过滤、情感预测、推荐系统等。

    在所有机器学习分类算法中,朴素贝叶斯和其他绝大多数的分类算法不同。如决策树、KNN、LR、SVM等,他们都是判别方法,也就是直接学习出特征输出Y和特征X之间的关系,要么是决策函数Y=f(x),要么是条件分布P(Y|X)。但朴素贝叶斯却是生成方法,也就是直接找出特征输出Y与特征X的联合分布p(x,y).然后用条件概率得出

    1、 朴素贝叶斯与LR的区别?
    朴素贝叶斯是生成模型,根据已有样本进行贝叶斯估计学习出先验概率P(Y)和条件概率P(X|Y),进而求出联合分布概率P(XY),最后利用贝叶斯定理求解P(Y|X),

    面试的时候怎么回答朴素贝叶斯呢?
    首先朴素贝斯是一个生成模型(很重要),其次它通过学习已知样本,计算出联合概率,再求条件概率。

    而LR是判别模型,根据极大化对数似然函数直接求出条件概率P(Y|X);
    朴素贝叶斯是基于很强的条件独立假设(在已知分类Y的条件下,各个特征变量取值是相互独立的),而LR则对此没有要求;
    朴素贝叶斯适用于数据集少的情景,而LR适用于大规模数据集。

    2、朴素贝叶斯“朴素”在哪里?
    朴素贝叶斯做了一个很强的条件独立假设(当Y确定时,X的各个分量取值之间相互独立)
    3、 在估计条件概率P(X|Y)时出现概率为0的情况怎么办?
    简单来说:引入λ,当λ=1时称为拉普拉斯平滑。
    贝叶斯算法的优缺点
    优点:
        (1)朴素贝叶斯模型发源于古典数学理论,有稳定的分类效率。
        (2)对小规模的数据表现很好,能个处理多分类任务,适合增量式训练,尤其是数据量超出内存时,我们可以一批批的去增量训练。
        (3)对缺失数据不太敏感,算法也比较简单,常用于文本分类。
      缺点:
        (1)理论上,朴素贝叶斯模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此,这是因为朴素贝叶斯模型给定输出类别的情况下,假设属性之间相互独立,这个假设在实际应用中往往是不成立的,在属性个数比较多或者属性之间相关性较大时,分类效果不好。而在属性相关性较小时,朴素贝叶斯性能最为良好。对于这一点,有半朴素贝叶斯之类的算法通过考虑部分关联性适度改进。
        (2)需要知道先验概率,且先验概率很多时候取决于假设,假设的模型可以有很多种,因此在某些时候会由于假设的先验模型的原因导致预测效果不佳。
        (3)由于我们是通过先验和数据来决定后验的概率从而决定分类,所以分类决策存在一定的错误率。
        (4)对输入数据的表达形式很敏感。

    PCA降维算法(主成分分析)
    地址:https://zhuanlan.zhihu.com/p/44371812
    PCA 是为了降低特征的维度。在实际工作中,可能会遇到特征维数过多,且部分特征具有一定相关性。如:在一个学生成绩数据集中,一个特征是学习时长,另一个特征是成绩,一般来讲,学习时间越长,越容易取得好成绩,即时长与成绩呈正相关。因此没必要用两个维度(时长和成绩)表达这一特征。我们可以找出另一个维度,表现这两个特征,且不会带来过多信息损失。
    在这里插入图片描述
    如何 PCA
    为了让高维度特征向低维度特征的映射更加精确,在上例中,我们需要找出一条使得所有的实例(entity)到坐标轴垂直距离(图中虚线部分)最短的一条坐标轴 Z。同时这条坐标轴也满足数据在其上散布最广
    在这里插入图片描述
    回到问题,我们想找出指定的 K 个维度(即把数据从高维降到K维),使数据在这 K 个维度上损失最少 -> 散布最广 。除了用方差衡量我们要取的坐标轴外,还应考虑数据在新维度上的散布不具有任何相关性,回到最开头的问题,在原始数据中,两个属性(学习时长和成绩)具有相关性,我们希望降维来去除这种相关性,这也是 PCA 的意义之一。

    回顾上面的公式,协方差表示了向量间的相关性,协方差为 0,向量完全不相关,向量互相正交。

    问题被转化成了,我们希望找出一组基向量(需要是标准正交基),数据在这组基向量构成的空间中表示时,任何两个属性间相关性为零。我们取出数据散布最广的前 K 个维度,就是我们希望求取的新坐标系(基向量),将原本的数据以新的基向量为参考系表示出来,就是数据压缩后的结果。
    在这里插入图片描述
    把矩阵的每一项除以 entity 的个数 m,你会发现,这是一个实对称矩阵,对角线上的值是其方差,其他值对应两个属性之间的协方差
    在数学中一个实对称矩阵有 3 个性质:
    1 不同特征值对应的特征向量必然正交
    2 k 重特征值必定对应 k 个线性无关的特征向量
    在这里插入图片描述
    PCA的主要思想是将N维高维特征映射到K维上,要求降维后数据损失最小,数据散步最广
    原始数据中,具有相关性的特征,通过降维后希望去除这种相关性。
    协方差表示了向量间的相关性,协方差为 0,向量完全不相关,向量互相正交。
    问题转化为算计数据矩阵的协方差矩阵,得到协方差矩阵的特征值和特征向量
    把特征值排序,选择特征值最大(即方差最大)的K个特征对应的特征向量组成的矩阵,将新的数据矩阵转换到新的空间中,实现数据特征的降维。

    SVD(奇异值分解)
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    DBSCAN算法(基于密度的聚类)
    地址:https://www.jianshu.com/p/d2eddc733c4d
    该算法利用基于密度的聚类的概念,即要求聚类空间中的一定区域内所包含对象(点或其他空间对象)的数目不小于某一给定阈值。过滤低密度区域,发现稠密度样本点。同一类别的样本,他们之间的紧密相连的,也就是说,在该类别任意样本周围不远处一定有同类别的样本存在。
    在这里插入图片描述
    在这里插入图片描述
    DBSCAN算法流程:
    1.初始,给定数据集D中所有对象都被标记为“未访问”,随机选择一个未被访问的对象p,
    并检查p的ϵ-领域是否至少包含MinPts个对象。如果不是,则p被标记为噪声点。否则为p创建一个新的簇C,并且把p的ϵ-领域中所有对象都放在候选集合N中,迭代地把N中不属于其他簇的对象添加到C中,对应N中标记为“未访问”的对象 P’ ,DBSCAN把它标记为“已访问”,并且检查它的ϵ-领域,如果 P’ 的ϵ-领域至少包含MinPts个对象,则P’ 的ϵ-领域中的对象都被添加到N中。
    DBSCAN继续添加对象到C,直到C不能扩展,即直到N为空。此时簇C完成生成,输出(就像传销一样)
    为了找到下一个簇,DBSCAN从剩下的对象中随机选择一个未访问过的对象。聚类过程继续,直到所有对象都被访问。
    还需考虑三个问题:

        第一个是一些异常样本点或者说少量游离于簇外的样本点,这些点不在任何一个核心对象在周围,在DBSCAN中,我们一般将这些样本点标记为噪音点。DBSCAN算法很容易检测异常点。
    
        第二个是距离的度量问题,即如何计算某样本和核心对象样本的距离。在DBSCAN中,一般采用最近邻思想,采用某一种距离度量来衡量样本距离,比如欧式距离。这和KNN分类算法的最近邻思想完全相同。对应少量的样本,寻找最近邻可以直接去计算所有样本的距离,如果样本量较大,则一般采用KD树或者球树来快速的搜索最近邻。
    
        第三种问题,某些样本可能到两个核心对象的距离都小于ϵ,但是这两个核心对象由于不是密度直达,又不属于同一个聚类簇,那么如果界定这个样本的类别呢?一般来说,此时DBSCAN采用先来后到,先进行聚类的类别簇会标记这个样本为它的类别。也就是说BDSCAN的算法不是完全稳定的算法。
    

    在这里插入图片描述
    在这里插入图片描述
    Kmeans算法
    原文链接:https://blog.csdn.net/WangZixuan1111/article/details/98970139
    一.原理流程:
    kmeans是无监督学习聚类算法
    (1)在数据集中随机的选取K个初始点作为初始聚类中心(质心)(这里如何确定k将在下面给出解释)
    (2)将数据集中的每个点分配到一个簇中,即为每个点找距离其最近的质心,并将其分配给之心所对应的簇
    (3)簇分好后,计算每个簇所有点的平均值,将平均值作为对应簇新的质心
    (4)循环2、3步骤,直到质心不变
    二、K-means中常用的到中心距离的度量有哪些
    在这里插入图片描述
    三、K-means中的k值如何选取
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    求出所有样本的轮廓系数后再求平均值就得到了平均轮廓系数。平均轮廓系数的取值范围为[-1,1],且簇内样本的距离越近,簇间样本距离越远,平均轮廓系数越大,聚类效果越好。那么,很自然地,平均轮廓系数最大的k便是最佳聚类数。
    在这里插入图片描述
    可以看到,轮廓系数最大的k值是2,这表示我们的最佳聚类数为2。但是,值得注意的是,从k和SSE的手肘图可以看出,当k取2时,SSE还非常大,所以这是一个不太合理的聚类数,我们退而求其次,考虑轮廓系数第二大的k值4,这时候SSE已经处于一个较低的水平,因此最佳聚类系数应该取4而不是2。
    但是,讲道理,k=2时轮廓系数最大,聚类效果应该非常好,那为什么SSE会这么大呢?在我看来,
    原因在于轮廓系数考虑了分离度b,也就是样本与最近簇中所有样本的平均距离。为什么这么说,
    因为从定义上看,轮廓系数大,不一定是凝聚度a(样本与同簇的其他样本的平均距离)小,而可
    能是b和a都很大的情况下b相对a大得多,这么一来,a是有可能取得比较大的。a一大,样本与同
    簇的其他样本的平均距离就大,簇的紧凑程度就弱,那么簇内样本离质心的距离也大,从而导致
    SSE较大。所以,虽然轮廓系数引入了分离度b而限制了聚类划分的程度,但是同样会引来最优结果的SSE比较大的问题,这一点也是值得注意的。
    在这里插入图片描述
    8、如何快速收敛数据量超大的K-means?
    相关解释可以去这个博客稍做了解https://blog.csdn.net/sunnyxidian/article/details/89630815
    9、K-means算法的优点和缺点是什么?
    K-Means的主要优点:
    (1)原理简单,容易实现
    (2)可解释度较强

    K-Means的主要缺点:
    (1)K值很难确定
    (2)局部最优
    (3)对噪音和异常点敏感
    (4)需样本存在均值(限定数据种类)
    (5)聚类效果依赖于聚类中心的初始化
    (6)对于非凸数据集或类别规模差异太大的数据效果不好

    Kmeans++
    K-means ++为K-means聚类选择初始簇质心
    在某些情况下,如果簇的初始化不合适,K-means可能导致产生坏的簇。这就是K-means ++产生作用的地方。它指定了在使用标准K-means聚类算法向前推进之前初始化簇质心的过程。

    使用K-means ++算法,我们优化了随机选择簇质心的步骤。在使用K-means ++初始化时,我们更有可能找到与最佳K-means解决方案竞争的解决方案。

    使用K-means ++初始化质心的步骤是:
    从我们想要聚类的数据点随机均匀地选择第一个簇。这类似于我们在K-means中所做的,但不是随机挑选所有质心,而是在这里选择一个质心
    接下来,我们计算每个数据点到已经选择的簇的质心的距离(D(x))
    然后,从数据点中选择新的簇质心,最大点到起其最近的质心的距离的平方对应的点为新的簇的质心
    然后,我们重复步骤2和3,直到选择了k个簇
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 前海征信“好信杯”大数据算法竞赛 - H&M队【附源码】 原创 2017-06-17 高铭 科赛Kesci 赛题回顾  自2006年Hinton等人提出“深度学习”概念至今,深度学习在海量数据的挖掘分析中发挥了巨大的...
  • 要实现高效的大数据机器学习,需要构建一个能同时支持机器学习算法设计和大规模数据处理的一体化大数据机器学习系统。研究设计高效、可扩展且易于使用的大数据机器学习系统面临诸多技术挑战。近年来,大数据浪潮的...
  • 本文很长~请耐心观看 ...单变量线性回归,多变量线性回归,逻辑回归,多项式回归,神经网络,支持向量机,决策树,KNN,朴素贝叶斯,集成学习,等 2.无监督: 聚类:K-Means,K-Means++,K-means||...
  • 说起分类算法,相信学过...KNN算法的优缺点是什么? Naive Bayes算法的基本假设是什么? entropy loss是如何定义的? 最后,分类算法调参常用的图像又有哪些? 答不上来?别怕!一起来通过这篇文章回顾一下机...
  • 很多时候困惑人们都是,很多算法是一类算法,而有些算法又是从其他算法中延伸出来的。这里,我们从两个方面来给大家介绍,第一个方面是学习的方式,第二个方面是算法的类似性。 学习方式 根据数据类型的不同,对一...
  • AI时代的机器学习算法毋庸置疑,AI时代已到。作为AI的重要分支,机器学习在推荐系统、在线广告、金融市场分析、计算机视觉、语言学、生物信息学等诸多领域都取得了巨大的成功。...
  • from Algorithms to Hardware Architectures」的演讲概括性地介绍了目前深度学习加速领域的进展,看后觉得这个演讲的逻辑清晰,于是想结合演讲ppt内容和近期调研的一些加速器相关内容,总括性地理一下深度学习加速...
  • 向AI转型的程序员都关注了这个号?...(回答时对算法要有一定的见解,最好不要照书上的背) (一) 机器学习方面SVM 1、 支撑平面---和支持向量相交的平面;;;分割平面---支撑平面中间的平面(最优分类平面)2
  • 每位老师出了一部分题,第一部分是崔院长出的,占50分,鹿老师和李老师各出了25分的,特别标注一下,李老师有一章ppt没讲,所以没出那一部分的题,但是以后就不知道了,可能会出没讲的那一章的算法之类的。...
  • 点上方蓝字计算机视觉联盟获取更多干货在右上方···设为星标★,与你不见不散编辑:Sophia计算机视觉联盟 报道 |公众号CVLianMeng转载于 :meton知乎链接:...
  • 机器学习算法

    2017-06-27 15:35:05
    这里只是算法简单介绍,笔试面试准备 一、朴素贝叶斯:  有以下几个地方需要注意: 其中一项条件概率可以通过朴素贝叶斯条件独立展开。要注意一点就是的计算方法,而由朴素贝叶斯的前提假设可知,=, 因此一般...
  • BAT机器学习面试1000题系列 整理:July、元超、立娜、德伟、贾茹、王剑、AntZ、孟莹等众人。本系列大部分题目来源于公开网络,取之分享,用之分享,且在撰写答案过程中若引用他人解析则必注明原作者及来源链接...
  • 导读:OpenCV 的构建是为了提供计算机视觉的通用基础接口,现在已经成为经典和最优秀的计算机视觉和机器学习的综合算法工具集。作为一个开源项目,研究者、商业用户和政府部门...
1 2 3 4 5 ... 12
收藏数 236
精华内容 94
关键字:

knn算法 ppt 大数据