NULL

NULL 查看完整档案

南昌编辑复旦大学  |  电子信息 编辑  |  填写所在公司/组织 blog.benull.top 编辑
编辑

Tomorrow is another day!

个人动态

NULL 发布了文章 · 11月23日

Scrapy 豆瓣搜索页爬虫

Scrapy 豆瓣搜索页爬虫

使用scrapy爬虫框架对豆瓣图书搜索结果进行爬取

Scrapy

Scrapy是一个为了爬取网站数据,提取结构性数据而编写的应用框架

可以应用在包括数据挖掘,信息处理或存储历史数据等一系列的程序

它提供了多种类型爬虫的基类,如BaseSpider、CrawlSpider等

主要组件

Scrapy框架主要由五大组件组成

  1. 调度器(Scheduler)
    调度器,说白了把它假设成为一个URL的优先队列,由它来决定下一个要抓取的网址是什么,同时去除重复的网址,用户可以自己的需求定制调度器。
  2. 下载器(Downloader)
    下载器,是所有组件中负担最大的,它用于高速地下载网络上的资源
    Scrapy的下载器代码不会太复杂,但效率高,主要的原因是Scrapy下载器是建立在twisted这个高效的 异步模型上的
  3. 爬虫(Spider)

    爬虫,是用户最关心的部份。用户定制自己的爬虫(通过定制正则表达式等语法),用于从特定的网页中提取自己需要的信息,即所谓的实体(Item)。 用户也可以从中提取出链接,让Scrapy继续抓取下一个页面

  4. 实体管道(Item Pipeline)

    实体管道,用于处理爬虫(spider)提取的实体(Item)

主要的功能是持久化实体、验证实体的有效性、清除不需要的信息

  1. Scrapy引擎(Scrapy Engine)

    Scrapy引擎是整个框架的核心
    它用来控制调试器、下载器、爬虫。实际上,引擎相当于计算机的CPU,它控制着整个流程

在这里插入图片描述

数据流(Data flow)

Scrapy中的数据流由执行引擎控制,其过程如下:

  1. 引擎打开一个网站,找到处理该网站的Spider并向该spider请求第一个要爬取的URL(s)
  2. 引擎从Spider中获取到第一个要爬取的URL并在调度器(Scheduler)以Request调度
  3. 引擎向调度器请求下一个要爬取的URL
  4. 调度器返回下一个要爬取的URL给引擎,引擎将URL通过下载中间件(request方向)转发给下载器(Downloader)
  5. 一旦页面下载完毕,下载器生成一个该页面的Response,并将其通过下载中间件(response方向)发送给引擎
  6. 引擎从下载器中接收到Response并通过Spider中间件(输入方向)发送给Spider处理
  7. Spider处理Response并返回爬取到的Item及(跟进的)新的Request给引擎
  8. 引擎将(Spider返回的)爬取到的Item给Item Pipeline,将(Spider返回的)Request给调度器
  9. (从第二步)重复直到调度器中没有更多地request,引擎关闭该网站

简单使用

创建项目 scrapy startproject xxx
创建爬虫 scrapy genspider xxx(爬虫名) xxx.com (爬取域)
生成文件 scrapy crawl xxx -o xxx.json (生成json/csv文件)
运行爬虫 scrapy crawl XXX
列出所有爬虫 scrapy list

scrapy项目目录结构

通过命令scrapy startproject tutorial创建一个新的项目tutorial

将会创建包含下列内容的 tutorial 目录

tutorial/                        
    scrapy.cfg            # 项目的配置文件
    tutorial/            # 该项目的python模块之后将在此加入代码
        __init__.py
        items.py        # 项目中的item文件
        pipelines.py    # 项目中的pipelines文件
        settings.py        # 项目的设置文件
        spiders/        # 放置spider代码的目录
            __init__.py
            ...

使用scrapy爬取豆瓣搜索页

分析

https://search.douban.com/movie/subject_search?search_text={search_text}&cat=1002&start={start}

search_text 搜索关键字

cat 搜索类别

start 开始的条数

url规则可以适用到图书电影搜索页面,后面的爬取也一样

爬取后发现页面信息都无法获取,但是可以找到有个window.__DATA__猜测数据都被加密成了这串字符串
在这里插入图片描述
一轮百度发现有大佬把加密的js代码提取出来了!

于是直接给出大佬的链接豆瓣读书搜索页的window.__DATA__的解密

解决了这个问题其他的就很好爬取了

代码

完整代码见github仓库

提取出的js在third_party/main.js

class DoubanBookSearchSpider(scrapy.Spider):
    name = 'douban_book_search'
    allowed_domains = ['douban.com']

    def __init__(self,keyword=None,start=None,*args, **kwargs):
        super(DoubanBookSearchSpider, self).__init__(*args, **kwargs)
        self.keyword = keyword
        self.start = start
        self.start_urls.append(f'https://search.douban.com/book/subject_search?search_text={self.keyword}&cat=1001&start={self.start}')

    def parse(self, response):
        r = re.search('window.__DATA__ = "([^"]+)"', response.text).group(1)
        # 导入js
        file_path = pathlib.Path.cwd() / 'third_party/main.js'
        with open(file_path, 'r', encoding='gbk') as f:
            decrypt_js = f.read()
        ctx = execjs.compile(decrypt_js)
        data = ctx.call('decrypt', r)
        for item in data['payload']['items']:
            if item.get('rating', None):
                cover_url = item['cover_url']
                score = item['rating']['value']
                score_num = item['rating']['count']
                url = item['url']
                abstract = item['abstract']
                title = item['title']
                id = item['id']
                yield DouBanBookSearchItem(
                    cover_url=cover_url,
                    score=score,
                    score_num=score_num,
                    url=url,
                    abstract=abstract,
                    title=title,
                    id=id)

参考

爬虫框架Scrapy个人总结(详细)熟悉

架构概览

Scrapy爬虫框架,入门案例(非常详细)

豆瓣读书搜索页的window.__DATA__的解密

查看原文

赞 0 收藏 0 评论 0

NULL 发布了文章 · 11月23日

使用crontab完成定时任务

使用crontab完成定时任务

crond是linux下用来周期性的执行某种任务或等待处理某些事件的一个守护进程,与windows下的计划任务类似,当安装完成操作系统后,默认会安装此服务工具,并且会自动启动crond进程,crond进程每分钟会定期检查是否有要执行的任务,如果有要执行的任务,则自动执行该任务

语法

usage:  crontab [-u user] file
        crontab [-u user] [ -e | -l | -r ]
        -e      (执行文字编辑器来设定时程表,内定的文字编辑器是 vi)
        -l      (列出user的时间表)
        -r      (删除user的时间表)

root用户的任务调度操作可以通过crontab –u root –e来设置,也可以将调度任务直接写入/etc/crontab文件

cron表达式

cron表达式是一个字符串,包含五个到七个由空格分隔的字段,表示一组时间,通常作为执行某个程序的时间表

minute hour day month week command

minute: 表示分钟,可以是从0到59之间的任何整数

hour:表示小时,可以是从0到23之间的任何整数

day:表示日期,可以是从1到31之间的任何整数

month:表示月份,可以是从1到12之间的任何整数

week:表示星期几,可以是从0到7之间的任何整数,这里的0或7代表星期日

command:要执行的命令,可以是系统命令,也可以是自己编写的脚本文件

*    *    *    *    * command
-    -    -    -    -
|    |    |    |    |
|    |    |    |    +----- 星期中星期几 (0 - 7) (星期天 为0)
|    |    |    +---------- 月份 (1 - 12) 
|    |    +--------------- 一个月中的第几天 (1 - 31)
|    +-------------------- 小时 (0 - 23)
+------------------------- 分钟 (0 - 59)

星号(*):代表所有可能的值,如month字段为星号,则表示每月都执行该命令操作

逗号(,):可以用逗号隔开的值指定一个列表范围,例如,“1,2,5,7,8,9”

中杠(-):可以用整数之间的中杠表示一个整数范围,例如“2-6”表示“2,3,4,5,6”

正斜线(/):可以用正斜线指定时间的间隔频率,例如“*/2”表示每两小时执行一次

实例

  1. 每一分钟执行一次 /bin/ls
   * * * * * /bin/ls
  1. 在 12 月内, 每天的早上 6 点到 12 点,每隔 3 个小时 0 分钟执行一次 /usr/bin/backup
0 6-12/3 * 12 * /usr/bin/backup
  1. 每天22:50关闭ssh服务
50 22 * * * /sbin/service sshd stop
  1. /etc/crontab 中添加环境变量,在可执行命令之前添加命令 . /etc/profile;/bin/sh,使得环境变量生效
20 03 * * * . /etc/profile;/bin/sh test.sh

注意点

  1. crontab有2种编辑方式:直接编辑/etc/crontab文件与crontab –e,其中/etc/crontab里的计划任务是系统中的计划任务,而用户的计划任务需要通过crontab –e来编辑
  2. crontab中的command尽量使用绝对路径,否则会经常因为路径错误导致任务无法执行
  3. 新创建的 cron 任务不会马上执行,至少要过 2 分钟后才可以,可以重启 cron 来马上执行
  4. %在crontab文件中表示换行,因此假如脚本或命令含有%,需要使用\%来进行转义

Mac 下使用crontab遇到的问题

我有一个Python爬虫脚本,在命令行时可以正常工作,但在crontab下报错

can't open file ... [Errno 1] Operation not permitted

cron表达式如下

30 7 * * * /usr/local/bin/python3 script.py >> script.log 2>&1

尝试了许多不同的方法,包括尝试过赋予文件权限,以root用户身份创建cron作业,不同的Python路径,都不能正常运行

最后在Stack Overflow找到解决方案

赋予cron全磁盘访问权限,方法如下

  1. 系统偏好设置->安全和隐私->完整磁盘访问
  2. 解除锁定以允许更改
  3. 单击 +
  4. 单击Command + Shift + G输入/ usr / sbin
  5. 找到cron 添加

参考

Linux crontab 命令

crontab用法与实例

Linux crontab命令详解

Trying to run a Python script with cron Operation not permitted

查看原文

赞 0 收藏 0 评论 0

NULL 发布了文章 · 11月17日

[论文阅读]DDGCN

DDGCN: A Dynamic Directed Graph Convolutional Network for Action Recognition

作者 | Matthew Korban, Xin Li
单位 | 路易斯安那州立大学
论文地址 | https://www.ecva.net/papers/eccv_2020/papers_ECCV/papers/123650749.pdf
会议 | ECCV 2020

摘要

提出了一种动态有向图卷积网络(DDGCN),从人体行为的骨架表示出发,对人体行为的时空特征进行建模

DDGCN由三个新的特征建模模块组成:

  1. 动态卷积采样(DCS)
  2. 动态卷积权重(DCW)
  3. 有向图时空(DGST)特征提取

DCS和DCW模块可以有效地捕捉动态的非相邻关节之间的时空相关性

DSTG特征提取模块,通过包含时空的有序信息来增强动作的特征

网络架构在这里插入图片描述

动态卷积采样(DCS)

人体非相邻的子部分在人类行为中往往是相互关联的,且这种关联是动态的
在这里插入图片描述

DCS算法可以总结如下

  1. 按照骨架模板初始化静态图$G_S$,并相应地初始化所有节点的索引
  2. 初始化邻居采样:对于∀vi∈GS,分两步创建其初始有序近邻集合pi(B(Vi))

    • 创建包括图中所有其他节点的有序节点集合Oi,该有序节点集合Oi包括根据图到vi的图距离排序的图中的所有其他节点。 当两个节点Vj和Vr具有相同的图距离(例如,都离Vi有r跳距离)时,则根据它们的初始化索引对它们进行排序
    • 给定核大小r,从Oi中选取前r个节点,这些节点在此步骤pi(B(Vi))中形成有序的邻集
  3. 更新采样邻域:∀vi,通过学习减少识别损失的最优偏移量∆pi来更新索引偏移量和邻域采样

最后,在$G_{ST}$上,通过如下公式(1)的图形卷积计算特征图$f_{ST}$

$$ f_{S T}\left(v_{i}\right)=\sum_{v_{j} \in B\left(v_{i}\right)} w\left(v_{i}\right) \cdot\left(p_{i}\left(v_{j}\right)+\Delta p_{i}\left(v_{j}\right)\right) $$

其中i和j分别是中心采样节点和相邻采样节点的索引,B是动态相邻采样节点集合,w是动态权重函数,pi是动态相邻采样函数,∆pi是偏移采样函数

动态卷积权重(DCW)

DCW权重分配模块动态地将权重$w_i$分配给$v_i$的相邻节点

使用动态时间规整(DTW)算法来计算$P_v=DTW_{path} (W,B(v))$

在这里插入图片描述

$P_v$中的第一列定义了W中元素的排序索引,第二列表示所选元素及其在$B(V)$中的顺序

有向时空图(DSTG)特征

在这里插入图片描述

骨骼特征 $f_{i}^{B}=\\overline{f_{i-1} f_{i}}=f_{i-1}-f_{i}$

时间特征 $f_{i}^{T}=f_{i}^{t}-f_{i}^{t-1}$

串联得到节点v_i的特征向量 $F_{i}=\\left\\{f_{i}^{J}, f_{i}^{B}, f_{i}^{T}\\right\\}$

实验

在NTURGB-D 60和Kinetics数据集上性能均优于其他方法
在这里插入图片描述

消融实验

DSTG模块对于性能提升最大,完整的DDC模块可得到最高的准确率

在这里插入图片描述

识别不完整的动作

对丢失帧的动作识别进行的实验,分为以下3中情况

  • 运动开始时丢失帧
  • 运动结束时丢失帧
  • 序列中随机丢失的帧

结论是运动开始时的序列存在大部分特征
在这里插入图片描述

总结

提出了一种基于骨架图的动态有向图卷积网络(DDGCN)动作识别算法

DDGCN由三个新模块组成,动态卷积抽样(DCS)、动态卷积权重分配(DCW)和有向图时空(DGST)特征提取

这些新模块有助于更好地捕捉时空依赖关系,骨架的层次结构和时序特征。 实验表明,DDGCN在多个公共数据集上的动作识别准确率优于最先进的算法

查看原文

赞 0 收藏 0 评论 0

NULL 发布了文章 · 11月6日

[机器学习] 支持向量机(SVM)

支持向量机(SVM)

支持向量机(support vector machines, SVM)是一种二分类模型,它的基本模型是定义在特征空间上的间隔最大的线性分类器

SVM的的学习策略就是间隔最大化,可形式化为一个求解凸二次规划的问题

  • 优点:泛化错误率低,计算开销不大,结果易解释
  • 缺点:对参数调节和核函数的选择敏感,原始分类器不加修改仅适用于处理二类问题

分隔超平面

image-20201105155404909.png

上面将数据集分隔开来的直线称为分隔超平面 ( separating hyperplane)

在上面给出的例子中,由于数据点都在二维平面上,所 以此时分隔超平面就只是一条直线。但是,如果所给的数据集是三的,那么此时用来分隔数据的就是一个平面

显而易见,更高维的情况可以依此类推。如果数据集是1024维的,那么就需要一个1023维的对象来对数据进行分隔,该对象被称之为超平面(hyperplane),也就是分类的决策边界

分布在超平面一侧的所有数据都属于某个类别,而分布在另一侧的所有数据则属于另一个类别

线性可划分

存在一个划分超平面能将训练样本正确分类

而现实人物中,原始样本空间内也许并不在一个能正确划分两类样本的超平面,如下图

image-20201106153458060.png

对这样的问题, 可将样本从原始空间映射到一个更高维的特征空间, 使得样本在这个特征空间内线性可分

例如在上图中, 若将原始的二维空间映射到一个合适的三维空间, 就能找到一个合适的划分超平面

比如想要将下图的红点和蓝点变成线性可分的,那么就将映射$y = x$变成映射$y=x^2$,这样就线性可分了

在这里插入图片描述

在这里插入图片描述

间隔(margin)

对于任意一个超平面,其两侧数据点都距离它有一个最小距离(垂直距离),这两个最小距离的和就是间隔margin

img

Hard Margin SVM

当训练数据线性可分时,通过硬间隔最大化,学习一个线性的分类器,即线性可分支持向量机

svm尝试寻找一个最优决策边界,距离两个类别最近的样本距离最远

image-20201106144823908.png

在样本空间中,划分超平面可用如下线性方程来描述:

$$w^Tx+b=0$$

其中

$$ \boldsymbol{w}=\left(w_{1};w_{2};\ldots;w_{d}\right) $$

为法向量, 决定了超平面的方向; $b$ 为位移项, 决定了超平面与原点之间的距离

样本空间中任意点$x$到超平面 $(w, b)$ 的距离可写为

$$ r=\frac{\left|\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b\right|}{\|\boldsymbol{w}\|} $$

假设超平面 $(w, b)$ 能将训练样本正确分类, 即对于

$$ \left(\boldsymbol{x}_{i}, y_{i}\right) \in D $$

若 $y_{i}=$ $+1,$ 则有

$$ \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b>0 $$

若 $y_{i}=-1,$ 则有

$$ \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b<0 $$

$$ \left\{\begin{array}{ll} \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b \geqslant+1, & y_{i}=+1 \\ \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b \leqslant-1, & y_{i}=-1 \end{array}\right. $$

如上图所示, 距离超平面最近的这几个训练样本点使上式的等号成立, 它们被称为“支持向量”(support vector), 两个异类支持向量到超平面的距离之和为

$$ \gamma=\frac{2}{\|\boldsymbol{w}\|} $$

显然, 为了最大化间隔, 仅需最大化

$$ \|\boldsymbol{w}\|^{-1} $$

这等价于最小化

$$ \|\boldsymbol{w}\|^{2} $$

$$ \begin{array}{l} \min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2} \\ \text { s.t. } y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1, \quad i=1,2, \ldots, m \end{array} $$

这就是支持向量机(Support Vector Machine, 简称 SVM)的基本型

Soft Margin SVM

当训练数据近似线性可分时,通过软间隔最大化,学习一个线性支持向量机,又称为软间隔支持向量机

前面我们是假定所有的训练样本在样本空间或特征空间中是严格线性可分的,即存在一个超平面能把不同类的样本完全分开,然而现实任务中很难确定这样的超平面(不管是线性超平面还是经过核变换到高维空间的超平面),所以引入松弛变量,允许一些样本出错,但我们希望出错的样本越少越好,所以松弛变量也有限制

具体来说,前面介绍的支持向量机的形式要求所有样本满足约束,即所有的样本必须划分正确,这称为硬间隔,而软间隔则是允许某些样本不满足约束

$$ y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1 $$

如下图红色圈出了不满足约束的样本
image-20201106161049243.png

当然, 在最大化间隔的同时, 不满足约束的样本应尽可能少. 于是, 优化目标可写为

$$ \min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \ell_{0 / 1}\left(y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)-1\right) $$

其中 $C>0$ 是一个常数,

$$ \ell_{0 / 1} $$

是“0/1损失函数”

$$ \ell_{0 / 1}(z)=\left\{\begin{array}{ll} 1, & \text { if } z<0 \\ 0, & \text { otherwise } \end{array}\right. $$

引入“松他变量" (slack variables)

$$ \xi_{i} \geqslant 0 $$

可将上式重写为

$$ \min _{\boldsymbol{w}, b, \xi_{i}} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \xi_{i} $$

对偶问题

现在的目标函数是二次的,约束条件是线性的,所以它是一个凸二次规划问题

这个问题可以用现成的QP (Quadratic Programming) 优化包进行求解

此外,由于这个问题的特殊结构,还可以通过拉格朗日对偶性(Lagrange Duality)变换到对偶变量 (dual variable) 的优化问题,即通过求解与原问题等价的对偶问题(dual problem)得到原始问题的最优解,这就是线性可分条件下支持向量机的对偶算法

这样做的优点在于:

  • 一者对偶问题往往更容易求解
  • 二者可以自然的引入核函数,进而推广到非线性分类问题

具体来说, 对每条约束添加拉格朗日乘子 $\\alpha_{i} \\geqslant 0,$ 则该问题的拉格朗日函数可写为

$$ L(\boldsymbol{w}, b, \boldsymbol{\alpha})=\frac{1}{2}\|\boldsymbol{w}\|^{2}+\sum_{i=1}^{m} \alpha_{i}\left(1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)\right) $$

其中 $\\alpha=\\left(\\alpha_{1} ; \\alpha_{2} ; \\ldots ; \\alpha_{m}\\right) .$ 令 $L(\\boldsymbol{w}, b, \\boldsymbol{\\alpha})$ 对 $\\boldsymbol{w}$ 和 $b$ 的偏导为零可得

$$ \begin{aligned} \boldsymbol{w} &=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i} \\ 0 &=\sum_{i=1}^{m} \alpha_{i} y_{i} \end{aligned} $$

即可将 $L(\\boldsymbol{w}, b, \\boldsymbol{\\alpha})$ 中的 $\\boldsymbol{w}$ 和 $b$ 消去, 就得到的目标函数对偶问题

$$ \max _{\boldsymbol{\alpha}} \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j} $$

非线形SVM

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

非线性SVM算法原理

对于输入空间中的非线性分类问题,可以通过非线性变换将它转化为某个维特征空间中的线性分类问题,在高维特征空间中学习线性支持向量机

令 $\\phi(x)$ 表示将 $x$ 映射后的特征向量, 于是, 在特征空间中划分超平面所对
应的模型可表示为

$$ f(\boldsymbol{x})=\boldsymbol{w}^{\mathrm{T}} \phi(\boldsymbol{x})+b $$

其中 $\\boldsymbol{w}$ 和 $b$ 是模型参数,有

$$ \begin{array}{l} \min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2} \\ \text { s.t. } y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \phi\left(\boldsymbol{x}_{i}\right)+b\right) \geqslant 1, \quad i=1,2, \ldots, m \end{array} $$

其对偶问题是

$$ \max _{\boldsymbol{\alpha}} \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}} \phi\left(\boldsymbol{x}_{j}\right) $$

$$ \begin{array}{ll} \text { s.t. } & \sum_{i=1}^{m} \alpha_{i} y_{i}=0 \\ & \alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m \end{array} $$

由于在线性支持向量机学习的对偶问题里,目标函数和分类决策函数都只涉及实例和实例之间的内积,所以不需要显式地指定非线性变换,而是用核函数替换当中的内积

有了这样的函数,我们就不必直接去计算高维甚至无穷维特征空间中的内积,于是上式可重写为

$$ \begin{array}{ll} \max _{\boldsymbol{\alpha}} & \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \\ \text { s.t. } & \sum_{i=1}^{m} \alpha_{i} y_{i}=0 \\ & \alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m \end{array} $$

常见的核函数

$$ \begin{aligned} &\text { 线性核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}\\ &\text { 多项式核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\left(\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}\right)^{d} \quad d \geqslant 1 \text { 为多项式的次数 }\\ &\text { 高斯核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\exp \left(-\frac{\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|^{2}}{2 \sigma^{2}}\right) \quad \sigma>0 \text { 为高斯核的带宽(width) }\\ &\text { 拉普拉斯核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\exp \left(-\frac{\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|}{\sigma}\right) \quad \sigma>0\\ &\text { Sigmoid 核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\tanh \left(\beta \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}+\theta\right) \quad \text { tanh 为双曲正切函数, } \beta>0, \theta<0 \end{aligned} $$

二分类扩展到多分类问题

SVM 扩展可解决多个类别分类问题

one-vs-rest

对于每个类,有一个当前类和其他类的二类分类器(one-vs-rest)
将多分类问题转化为 n 个二分类问题

svm解决回归问题

现在我们来考虑回归问题,传统回归模型通常直接基于模型输出 $f(x)$ 与真实输出 $y$ 之 间的差别来计算损失, 当且仅当 $f(\\boldsymbol{x})$ 与 $y$ 完全相同时, 损失才为零

与此不同 $,$ 支持向量回归(Support Vector Regression, 简称 SVR)假设我们能容忍 $f(x)$ 与 $y$ 之间最多有 $\\epsilon$ 的偏差, 即仅当 $f(\\boldsymbol{x})$ 与 $y$ 之间的差别绝对值大于 $\\epsilon$ 时才计算损失

如图所示, 这相当于以 $f(x)$ 为中心, 构建了一个宽度为 $2 \\epsilon$ 的间隔带, 若训练样本落入此间隔带, 则认为是被预测正确的

image-20201106150801272

于是, SVR 问题可形式化为

$$ \min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \ell_{c}\left(f\left(\boldsymbol{x}_{i}\right)-y_{i}\right) $$

其中 $C$ 为正则化常数, $\\ell_{\\epsilon}$ 是图 6.7 所示的 $\\epsilon$ -不敏感损失 $(\\epsilon$ -insensitive loss $)$ 函数

$$ \ell_{\epsilon}(z)=\left\{\begin{array}{ll} 0, & \text { if }|z| \leqslant \epsilon \\ |z|-\epsilon, & \text { otherwise } \end{array}\right. $$

参考

[机器学习算法(一)SVM]()

机器学习-周志华

支持向量机(SVM)——原理篇

Machine Learning in Action by Peter Harrington

查看原文

赞 0 收藏 0 评论 0

NULL 发布了文章 · 11月5日

[机器学习]分类算法评估指标

分类算法评估指标

精度(Accuracy)

即正确预测的正反例数 /预测总数

对于样例集D,分类错误率定义为

$$ E(f ; D)=\frac{1}{m} \sum_{i=1}^{m} \mathbb{I}\left(f\left(\boldsymbol{x}_{i}\right) \neq y_{i}\right) $$

精度则定义为

$$ \begin{aligned} \operatorname{acc}(f ; D) &=\frac{1}{m} \sum_{i=1}^{m} \mathbb{I}\left(f\left(\boldsymbol{x}_{i}\right)=y_{i}\right) \\ &=1-E(f ; D) \end{aligned} $$

  • 对于样本类别数量严重不均衡的情况(skewed)不能用精度指标来衡量

    例如:有A类1000个,B类5个,如果我把这1005个样本都预测成A类,正确率=1000/1005=99.5%

  • 对于有倾向性的问题,往往不能用精度指标来衡量

    例如:判断这个病人是不是病危,如果不是病危错误判断为病危,那只是损失一点医务人员的时间和精力,如果是把病危的人判断为非病危状态,那损失的就是一条人命

对于以上两种情况,单纯根据Accuracy来衡量算法的优劣已经失效,这个时候就需要对目标变量的真实值和预测值做更深入的分析

混淆矩阵(confusion matrix)

对于二分类问题,可将样例根据其真实类别与学习器预测类别的组合划分为

  • 真正例(True Positive)
  • 假正例(False Positive)
  • 真反例(True Negative)
  • 假反例(False Negative)

分类结果的混淆矩阵如下

预测值0预测值1
真实值0TNFP
真实值1FNTP

精准率(precision)

$$\text {precision}=\frac{T P}{T P+F P}$$

精准率就是预测为正例的那些数据里预测正确的数据个数

召回率(recall)

$$\text {recall}=\frac{T P}{T P+F N}$$

召回率就是真实为正例的那些数据里预测正确的数据个数

精准率和查全率是一对矛盾的度量,一般来说,精准率高时,召回率则偏低;而召回率高时,精准率则偏低

F1 Score

F1 Score同时关注精准率和召回率,是precision 和 recall 的调和平均值

它的值更接近于Precision与Recall中较小的值

$$ \frac{1}{F 1}=\frac{1}{2}\left(\frac{1}{\text {precision}}+\frac{1}{\text {recall}}\right) $$

$$ F 1=\frac{2 \cdot \text {precision } \cdot \text { recall}}{\text {precision }+\text {recall}} $$

PR曲线

根据学习器的预测结果对样例进行排序, 排在前面的是学习器认为“最可能”是正例的样本, 排在最后的则是学习器认为“最 不可能”是正例的样本. 按此顺序逐个把样本作为正例进行预测, 则每次可以计算出当前的精准率、召回率

以精准率为纵轴、召回率为横轴作图, 就得到了精准率-召回率曲线, 简称“P-R曲线”,显示该曲线的图称为“P-R图”

在这里插入图片描述

与ROC曲线左上凸效果好不同的是,PR曲线是右上凸效果越好

若一个学习器的P-R曲线被另一个学习器的曲线完全包住,则可断言后者的性能优于前者

ROC曲线

ROC(Receiver Operating Characteristic)受试者工作特性曲线

True Postitve Rate(真正例率):正样本中被预测对比例

$$\text {TPR}=\frac{TP}{TP+FN}$$

False Positive Rate(假正例率):负样本被预测错的比例

$$\text {FPR}=\frac{FP}{TN+FP}$$

ROC是一个以TPR为纵坐标,FPR为横坐标构造出来的一幅图

在这里插入图片描述

在ROC空间,ROC曲线越凸向左上方向效果越好,因为这说明精确率高且覆盖率大

进行学习器的比较时, 与 P-R 图相似, 若一个学习器的 ROC 曲线被另一 个学习器的曲线完全“包住”, 则可断言后者的性能优于前者; 若两个学习器的 ROC 曲线发生交叉, 则难以一般性地断言两者熟优熟劣. 此时如果一定要进行比较, 则较为合理的判据是比较 ROC曲线下的面积, 即 AUC

AUC

AUC(Area Under Curve)是一种模型分类指标,且仅仅是二分类模型的评价指标

AUC 值为 ROC 曲线所覆盖的区域面积,显然,AUC越大,分类器分类效果越好

AUC的物理意义正样本的预测结果大于负样本的预测结果的概率。所以AUC反应的是分类器对样本的排序能力。另外值得注意的是,AUC对样本类别是否均衡并不敏感,这也是不均衡样本通常用AUC评价分类器性能的一个原因

参考

机器学习评估指标

机器学习-周志华

回顾及总结--评价指标(分类指标)

查看原文

赞 0 收藏 0 评论 0

NULL 发布了文章 · 11月3日

[论文阅读]Which Is Plagiarism

Which Is Plagiarism: Fashion Image Retrieval Based on Regional Representation for Design Protection

作者 | Yining Lang, Yuan He, Fan Yang, Jianfeng Dong, Hui Xue

单位 | 阿里;浙江工商大学;AZFT

会议|CVPR2020

paper地址

概述

在服装领域,虽然打假一直不断,但盗版抄袭问题依旧普遍存在,而且从线上线下,抄袭手段越来越刁钻。目前来看,服装领域的抄袭有以下三类

图片盗用

​ 抄袭成本很低,很容易被平台的图片检索系统锁定

创意盗版

​ 抄袭成本稍高,但基于相似度度量的算法,可以对它们进行召回和治理

对服装的某些区域进行修改

抄袭成本高,需要人工审核发现,打假成本也高

psnet1.png

两组盗版示例,其中每组中左图为正版服装,右图为盗版服装

盗版服装检索的难点

盗版服装的形式层出不穷,有些盗版服装跟原图比较相似,但是有些并不相似

而且有些盗版服装与原创服装属于不同的类型,提高了网络训练时的要求

psnet2.png

盗版服装的定义

作为盗版服装检索领域的首次工作,作者对盗版服装的定义是整体上抄袭原版服装设计和风格,服装修改的局部区域数小于等于2

psnet3.png

将图像中的服装分为五个区域,包括领子、胸部、腰部和两个袖子区域

方法

基于三元组的损失函数(for 相似性检索)

$$ \begin{array}{c} \mathcal{L}_{t r i}\left(I, I^{+}, I^{-}\right)=\sum_{r=1}^{R} \max \left(D_{r}^{I, I^{+}}-D_{r}^{I, I^{-}}+m, 0\right) \\ \mathcal{L}_{t r a}=\sum_{n=1}^{N} \mathcal{L}_{t r i}\left(I, I^{+}, I^{-}\right) \end{array} $$

基于三元组的损失函数(for 盗版检索)

$$ \begin{array}{c} \mathcal{L}_{t r i}^{\prime}\left(I, I^{+}, I^{-}\right)=\sum_{r=1}^{R} \max \left(D_{r}^{I, I^{+}}-D_{r}^{I, I^{-}}+m, 0\right) \cdot \lambda_{r} \\ \alpha_{t r i}=\frac{\operatorname{avg}\left\{\left\|f_{r}(I)-f_{r}\left(I^{+}\right)\right\|_{2} ; r=1,2, \ldots R\right\}}{\max \left\{\left\|f_{r}(I)-f_{r}\left(I^{+}\right)\right\|_{2} ; r=1,2, \ldots R\right\}} \\ \mathcal{L}_{p l a}=\sum_{n=1}^{N}\left[\mathcal{L}_{t r i}^{\prime}\left(I, I^{+}, I^{-}\right) \cdot \alpha_{t r i}\right] \end{array} $$

网络框架

PS-Net总体框架

psnet4.png

Network Backbone

HR-Net提取图片的特征

​ HR-Net 的多分辨率子网并行连接,使得每一个高分辨率到低分辨率的表征都从其它并行表示中反复接受信息,从而得到丰富的高分辨率表征

​ 但HR-Net不是必须的,可以用ResNet、VGG-Net 等替代

Landmark Branch

关键点估计分支,为划分区域做准备,通过反卷积进行上采样

Retrieval Branch

聚合局部区域的特征进行检索

根据 Landmark Branch 得到的关键点预测和 输出的热力图,得到特定局部区域在特征图上的位置
再根据特定区域在特征图上的位置,通过ROI pooling得到 Retrieval Branch 的特征图中该区域相应的局部特征图

Plagiarized Fashion 数据集

•总共60,000张图片,其中40,000用于训练 20,000用于测试

•包括4类服装:短袖T恤、长袖上衣、外套以及连衣裙

•图片从淘宝网爬取并经过专家标注

psnet5.png

总结

•提出了一个新的抄袭服装检索问题

•建立了新的用于抄袭服装检索的数据集Plagiarism Fashion

•提出了一种基于区域表示的多任务网络PS-Net且达到了SOTA

•PS-Net还可以用于传统的服装检索和关键点估计任务

查看原文

赞 0 收藏 0 评论 0

NULL 发布了文章 · 10月30日

[机器学习] 集成学习

集成学习

集成学习(ensemble learning)通过构建并结合多学习器来完成学习任务,常可获得比单一学习器显著优越的泛化性能

要获得好的集成,个体学习器应好而不同,即个体学习器要有一定的准确性,并且要有多样性,即学习器间要有差异

根据个体学习器的生成方式, 目前的集成学习方法大致可分为两大类

  • 学习器间存在强依赖关系、必须串行生成的序列化方法,如Boosting
  • 学习器间不存在强依赖关系、可同时生成的并行化方法,如 Bagging 和随机森林

集成学习在各个规模的数据集上都有很好的策略

  • 数据集大:划分成多个小数据集,学习多个模型进行组合
  • 数据集小:利用Bootstrap方法(也称为自助法,一种有放回的抽样方法)进行抽样,得到多个数据集,分别训练多个模型再进行组合

Boosting

Boosting 是一族可将弱学习器提升为强学习器的算法

工作原理

  1. 先从初始训练集训练出一个基学习器
  2. 根据基学习器的表现对训练样本分布进行调整, 使得先前基学习器做错的训练样本在后续受到更多关注
  3. 基于调整后的样本分布来训练下一个基学习器;
  4. 重复进行, 直至基学习器数目达到事先指定的值 $T,$ 最终将这 $T$ 个基学习器进行加权结合

从偏差-方差分解的角度看, Boosting 主要关注降低偏差, 因此 Boosting 能基于泛化性能相当弱的学习器构建出很强的集成

Boosting 族算法最著名的代表是 AdaBoost,是通过集中关注被已有分类器错分的那些数据来获得新的分类器

AdaBoost

  • 优点:泛化错误率低,易编码,可以应用在大部分分类器上
  • 缺点:对离群点敏感

过程

  1. 训练数据中的每个样本,并赋予其一个权重,这些权重构成了向量D,权重都初始化成相等值
  2. 在训练数据上训练出一个弱分类器并计算该分类器的错误率,然后在同一数据集上再次训练弱分类器
  3. 在分类器的第二次训练当中,将会重新调整每个样本的权重,其中第一次分对的样本的权重将会降低,而第一次分错的样本 的权重将会提高
  4. 计算出D之后,AdaBoost又开始进入下一轮迭代
  5. AdaBoost算法会不断地重复训练和调整权重的过程,直到训练错误率为0或者弱分类器的数目达到用户的指定值为止

image

Bagging

Bagging 是并行式集成学习方法最著名的代表

流程

  1. 给定包含 $m$ 个样本的数据集, 我们先随机取出一个样本放入采样集中, 再把该样本放回初始数据集, 使得下次采样时该样本仍有可能被选中
  2. 经过 $m$ 次随机采样操作, 我们得到含 $m$ 个样本的采样集, 初始训练集中有的样本在采样集里多次出现, 有的则从未出现
  3. 采样出 $T$ 个含 $m$ 个训练样本的采样集, 然后基于每个采样集训练出一个基学习器
  4. 将这些基学习器进行结合

在对预测输出进行结合时, Bagging 通常对分类任务使用简单投票法, 对回归任务使用简单平均法

  • Bagging通过降低基分类器的方差,改善了泛化误差
  • 其性能依赖于基分类器的稳定性;如果基分类器不稳定,bagging有助于降低训练数据的随机波动导致的误差;如果稳定,则集成分类器的误差主要由基分类器的偏倚引起
  • 由于每个样本被选中的概率相同,因此bagging并不侧重于训练数据集中的任何特定实例

随机森林

随机森林(Random Forest) 是 Bagging 的一个扩展变体

随即森林在以决策树为基学习器构建 Bagging 集成的基础上, 进一步在决策树的训练过程中引入了随机属性选择

具体来说, 传统决策树在选择划分属性时是在当前结点的属性集合(假定有 $d$ 个属性)中选择一个最优属性

而在随即森林中, 对基决策树的每个结点, 先从该结点的属性集合中随机选择一个包含 $k$个属性的子集, 然后再从这个子集中选择一个最优属性用于划分

随机森林的训练效率常优于 Bagging, 因为在个体决策树的构建过程中, Bagging 使用的是“确定型”决策树, 在选择划分属性时要对结点的所有属性进行考察,而随机森林使用的“随机型”决策树则只需考察一个属性子集

优点

  • 具有极好的准确率
  • 能够有效地运行在大数据集上
  • 能够处理具有高维特征的输入样本,而且不需要降维
  • 能够评估各个特征在分类问题上的重要性
  • 对于缺省值问题也能够获得很好得结果

结合策略

每个基学习器之间不存在很强的依赖性,为了提高集成的泛化能力在最终预测结果时,需要一定的策略对多个结果进行结合

平均法

对数值型输出,最常见的结合策略是使用平均法,又可分为

  • 简单平均法
  • 加权平均法

一般而言,在个体学习器性能相差较大时宜使用加权平均法,而在个体学习器性能相近时宜使用简单平均法

投票法

对分类任务来说, 学习器将从类别标记集合 中预测出一个标记, 最常见的结合策略是使用投票法

  • 绝对多数投票法

    若某标记得票过半数,则预测为该标记;否则拒绝预测

  • 相对多数投票法

    预测为得票最多的标记。若同时有多个标记获得最高票,则从中随机选取一个。

  • 加权投票法

学习法

当训练数据很多时, 一种更为强大的结合策略是使用“学习法”, 即通过另一个学习器来进行结合

Stacking 是学习法的典型代表

Stacking

Stacking是通过一个元分类器或者元回归器来整合多个分类模型或回归模型的集成学习技术

基础模型通常包含不同的学习算法,利用整个训练集做训练

元模型将基础模型的特征作为特征进行训练

image

参考

机器学习--集成学习(Ensemble Learning)

集成学习--bagging、boosting、stacking

机器学习-周志华

Machine Learning in Action by Peter Harrington

随机森林算法及其实现(Random Forest)

查看原文

赞 0 收藏 0 评论 0

NULL 发布了文章 · 10月28日

[机器学习]决策树

决策树

决策树学习采用的是自顶向下的递归方法,其基本思想是以信息熵为度量构造一颗熵值下降最快的树,到叶子节点处,熵值为0

具有非常好的可解释性、分类速度快的优点,是一种有监督学习

最早提及决策树思想的是Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法,以及Breiman等人在1984年提出的CART算法

工作原理

一般的,一颗决策树包含一个根结点、若干个内部节点和若干个叶节点

构造

构造就是生成一棵完整的决策树。简单来说,构造的过程就是选择什么属性作为节点的过程

叶结点对应于决策结果, 其他每个结点则对应于一个属性测试,每个结点包含的样本集合根据属性测试的结果被划分到子结点中;

根结点包含样本全集,从根结点到每个叶结点的路径对应了一个判定测试序列. 决策树学习的目的是为了产生一棵泛化能力强, 即处理未见示例能力强的决策树,其基本流程遵循简单且直观的分而治之策略

显然, 决策树的生成是一个递归过程. 在决策树基本算法中, 有三种情形会导致递归返回:

  1. 当前结点包含的样本全属于同一类别, 无需划分
  2. 当前属性集为空, 或是所有样本在所有属性上取值相同, 无法划分
  3. 当前结点包含的样本集合为空, 不能划分

划分选择

决策树学习的关键是如何选择最优划分属性

随着划分过程不断进行, 我们希望决策树的分支结点所包含的样本尽可能属于同一类别, 即结点的“纯度”越来越高

信息熵

信息熵在信息论中代表随机变量不确定度的度量

熵越大,数据的不确定性越高,纯度越低

熵越小,数据的不确定性越低,纯度越高

假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_{k}(k=1,2, \ldots,|\mathcal{Y}|)$ 则$D$的信息嫡定义为

$$\operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|} p_{k} \log _{2} p_{k}$$

信息增益

假定离散属性 $a$ 有 $V$ 个可能的取值 $\left\{a^{1}, a^{2}, \ldots, a^{V}\right\},$ 若使用 $a$ 来对样本集 $D$ 进行划分, 则会产生 $V$ 个分支结点, 其中第 $v$ 个分支结点包含了 $D$ 中所有在 属性 $a$ 上取值为 $a^{v}$ 的样本, 记为 $D^{v} .$ 我们可根据式 (4.1) 计算出 $D^{v}$ 的信息嫡, 再考虑到不同的分支结点所包含的样本数不同, 给分支结点赋予权重 $\left|D^{v}\right| /|D|,$ 即样本数越多的分支结点的影响越大, 于是可计算出用属性 $a$ 对样本集 $D$ 进行 划分所获得的“信息增益”
$$\operatorname{Gain}(D, a)=\operatorname{Ent}(D)-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right)$$

一般而言, 信息增益越大, 则意味着使用属性 $a$ 来进行划分所获得的“纯度提升”越大. 因此, 我们可用信息增益来进行决策树的划分属性选择, 著名的 ID3 决策树学习算法就是以信息增益为准则来选择划分属性

ID3 算法的优点是方法简单,缺点是对噪声敏感。训练数据如果有少量错误,可能会产生决策树分类错误

信息增益率

$$ \text {GainRatio}(D, a)=\frac{\operatorname{Gain}(D, a)}{Ent(D)} $$

C4.5 在 IID3 的基础上,用信息增益率代替了信息增益,解决了噪声敏感的问题,并且可以对构造树进行剪枝、处理连续数值以及数值缺失等情况,但是由于 C4.5 需要对数据集进行多次扫描,算法效率相对较低

基尼指数

基尼指数是经典决策树CART用于分类问题时选择最优特征的指标

假设有$K$个类,样本点属于第$k$类的概率为$p_k$,则概率分布的基尼指数定义为

$$ G(p)=\sum_{k=1}^{K} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{K} p_{k}^{2} $$

在信息增益、增益率、基尼指数之外, 人们还设计了许多其他的准则用于决策树划分选择

然而有实验研究表明这些准则虽然对决策树的尺寸有较大影响, 但对泛化性能的影响很有限

剪枝

决策树的缺点包括对未知的测试数据未必有好的分类、泛化能力,即可能发生过拟合现象,此时可采用剪枝或随机森林

剪枝是决策树学习算法对付“过拟合”的主要手段

在决策树学习中, 为了尽可能正确分类训练样本, 结点划分过程将不断重复, 有时会造成决 策树分支过多, 这时就可能因训练样本学得太好了, 以致于把训练集自身 的一些特点当作所有数据都具有的一般性质而导致过拟合

ID3 决策树代码

参考 Machine Learning in Action by Peter Harrington

# coding = utf-8

from math import log
import numpy as np
from collections import Counter

class DecisionTree:
    """ID3 DecisionTree

    """

    def __init__(self):
        self.decisionTree = None
        self._X = None
        self._y = None

    # 计算信息熵
    def calcShannonEnt(self,y):
        lablesCounter = Counter(y)
        shannonEnt = 0.0
        for num in lablesCounter.values():
            p = num / len(y)
            shannonEnt += -p * log(p,2)
        return shannonEnt

    def fit(self, X, y):
        self._X = X
        self._y = y
        self.decisionTree = self.createTree(self._X,self._y)
        return self

    def splitDataset(self,X,y,d,value):
        features = X[X[:,d]==value]
        labels = y[X[:,d]==value]
        return np.concatenate((features[:,:d],features[:,d+1:]),axis=1), labels

    def chooseBestFeatureToSplit(self,X,y):
        numFeatures = X.shape[1]
        baseEntropy = self.calcShannonEnt(y)
        bestInfoGain, bestFeature = 0.0, -1

        for i in range(numFeatures):
            # 创建唯一的分类标签列表
            uniqueVals = np.unique(X[:,i])
            newEntropy =0.0
            # 计算每种划分方式的信息熵
            for value in uniqueVals:
                _x, _y = self.splitDataset(X,y,i,value)
                prob = len(_x)/len(X)
                newEntropy += prob * self.calcShannonEnt(_y)
            infoGain = baseEntropy - newEntropy
            if infoGain>bestInfoGain:
                bestInfoGain = infoGain
                bestFeature = i
            return bestFeature

    def majorityCnt(self,y):
        lablesCounter = Counter(y)
        return lablesCounter.most_common(1)[0]

    def createTree(self,X,y):
        # 类别完全相同则停止继续划分
        if y[y == y[0]].size == y.size :
            return y[0]
        # 遍历完所有特征时返回出现次数最多的类别
        if X.shape[1] == 0:
            return self.majorityCnt(y)
        bestFeat = self.chooseBestFeatureToSplit(X,y)
        decisionTree = {bestFeat: {}}
        for value in np.unique(X[:,bestFeat]):
            decisionTree[bestFeat][value] = self.createTree(*self.splitDataset(X,y,bestFeat, value))
        return decisionTree

if __name__ == '__main__':

    dataSet = np.array([[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']])
    labels = ['no surfacing', 'flippers']
    dt = DecisionTree()
    X = dataSet[:, :2]
    X = X.astype(np.int)
    y = dataSet[:,-1]
    dt.fit(X,y)
    print(dt.decisionTree)

参考

机器学习之-常见决策树算法(ID3、C4.5、CART)

决策树

决策树(Decision Tree):通俗易懂之介绍

机器学习-周志华

Machine Learning in Action by Peter Harrington

查看原文

赞 0 收藏 0 评论 0

NULL 发布了文章 · 10月22日

ubuntu设置时区

ubuntu设置时区

查看现在时区

benull@37c7dedb7a13:~# date -R
Wed, 21 Oct 2020 23:46:05 +0800

执行 tzselect查看时区(只能查看不能修改)

遇到tzselect报错如下

benull@37c7dedb7a13:~# tzselect
/usr/bin/tzselect: line 180: /usr/share/zoneinfo/iso3166.tab: No such file or directory
/usr/bin/tzselect: time zone files are not set up correctly

解决方案一:安装tzdata

apt-get install tzdata

解决方案二

vim /usr/bin/tzselect
将
${TZDIR=pwd}
改为
${TZDIR=/usr/share/zoneinfo}

继续执行 tzselect

benull@37c7dedb7a13:~# tzselect
Please identify a location so that time zone rules can be set correctly.
Please select a continent, ocean, "coord", or "TZ".
 1) Africa
 2) Americas
 3) Antarctica
 4) Asia
 5) Atlantic Ocean
 6) Australia
 7) Europe
 8) Indian Ocean
 9) Pacific Ocean
10) coord - I want to use geographical coordinates.
11) TZ - I want to specify the time zone using the Posix TZ format.
#? 4
Please select a country whose clocks agree with yours.
 1) Afghanistan          18) Israel            35) Palestine
 2) Armenia          19) Japan            36) Philippines
 3) Azerbaijan          20) Jordan            37) Qatar
 4) Bahrain          21) Kazakhstan        38) Russia
 5) Bangladesh          22) Korea (North)        39) Saudi Arabia
 6) Bhutan          23) Korea (South)        40) Singapore
 7) Brunei          24) Kuwait            41) Sri Lanka
 8) Cambodia          25) Kyrgyzstan        42) Syria
 9) China          26) Laos            43) Taiwan
10) Cyprus          27) Lebanon            44) Tajikistan
11) East Timor          28) Macau            45) Thailand
12) Georgia          29) Malaysia            46) Turkmenistan
13) Hong Kong          30) Mongolia            47) United Arab Emirates
14) India          31) Myanmar (Burma)        48) Uzbekistan
15) Indonesia          32) Nepal            49) Vietnam
16) Iran          33) Oman            50) Yemen
17) Iraq          34) Pakistan
#? 9
Please select one of the following time zone regions.
1) Beijing Time
2) Xinjiang Time
#? 1

The following information has been given:

    China
    Beijing Time

Therefore TZ='Asia/Shanghai' will be used.
Local time is now:    Thu Oct 22 00:02:14 CST 2020.
Universal Time is now:    Wed Oct 21 16:02:14 UTC 2020.
Is the above information OK?
1) Yes
2) No
#? 1

You can make this change permanent for yourself by appending the line
    TZ='Asia/Shanghai'; export TZ
to the file '.profile' in your home directory; then log out and log in again.

Here is that TZ value again, this time on standard output so that you
can use the /usr/bin/tzselect command in shell scripts:
Asia/Shanghai

复制文件到 /etc/localtime

sudo cp /usr/share/zoneinfo/Asia/Shanghai /etc/localtime

参考

Ubuntu设置时区和更新时间

ubuntu设置时区

ubuntu 时区 修改时间 保存 重启 变化等

查看原文

赞 0 收藏 0 评论 0

NULL 发布了文章 · 10月21日

'ascii' codec can't encode characters in position

'ascii' codec can't encode characters in position

问题

在ubuntu中运行python3脚本输出到命令行出错

解决方案

将LANG 或 LC_ALL 设置为 en_US.utf8 或 zh_CN.utf8

  • 列出当前设置

    benull@37c7dedb7a13:~# locale
    LANG=zh_CN.UTF-8
    LANGUAGE=
    LC_CTYPE="en_US.UTF-8"
    LC_NUMERIC="en_US.UTF-8"
    LC_TIME="en_US.UTF-8"
    LC_COLLATE="en_US.UTF-8"
    LC_MONETARY="en_US.UTF-8"
    LC_MESSAGES="en_US.UTF-8"
    LC_PAPER="en_US.UTF-8"
    LC_NAME="en_US.UTF-8"
    LC_ADDRESS="en_US.UTF-8"
    LC_TELEPHONE="en_US.UTF-8"
    LC_MEASUREMENT="en_US.UTF-8"
    LC_IDENTIFICATION="en_US.UTF-8"
    LC_ALL=en_US.UTF-8
  • 列出已安装的语言环境

    benull@37c7dedb7a13:~# locale -a
    C
    C.UTF-8
    en_US.utf8
    POSIX
    zh_CN.utf8

如果不存在上述的 locale,先用 locale-gen 生成

apt-get install locales
locale-gen 'zh_CN.UTF-8'
update-locale LC_ALL="zh_CN.UTF-8"

export LC_ALL=zh_CN.UTF-8" 加到的~/.bashrc

参考

关于'ascii' codec can't encode characters in position 的问题

ubuntu locales 设置中文

Locale

查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 25 次点赞
  • 获得 5 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 5 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2017-10-27
个人主页被 1.3k 人浏览