决策树

发布在 Python

决策树是机器学习中一种简单明了的分类算法,用程序语言描述就是if...elif...else...,关键问题则是如何选择合适的特征对数据集进行切割,常见算法有: ID3、C4.5、CART等。

今天主要记录一下ID3这个算法,想使用这个算法首先要了解信息增益,想了解信息增益则要先明白什么是”熵”。熵描述了一个系统的混乱复杂程度,有一个理论叫做”熵增加”,含义就是一个没有外力干涉的系统混乱程度总是增加的,比如一个房间如果没人打扫的话只会越来越混乱,而不会自己变得整洁。

计算熵的公式如下:

$$H=-\sum_{i=i}^{n}P(x_i)log_2P(x_i)$$

其中\(P(x_i)\) 表示P发生的概率。

阅读全文

python验证码识别6:kNN

发布在 Python

什么是kNN?kNN(k-Nearest Neighbors)是机器学习中处理分类问题的一种简单明了的算法。核心精髓就是老祖宗几百年前留下的言语”物以类聚,人以群居”。忘记从哪里看到的一个说法:”你身边最好的6个朋友的平均薪资,就是你的薪资水平。”这就是kNN算法的一个应用了吧,另外我觉得之前几篇给验证码降噪用的连通域算法,分割用的滴水算法,都有kNN的味道在里面。

阅读全文

numpy学习笔记2

发布在 Python

之前一直有个疑惑,为什么要使用numpy?更本质的说,为什么要使用矩阵?矩阵是什么?意味着什么?关于关于矩阵的问题,这里推荐一个系列视频,讲的非常非常好。至于为什么用numpy,从程序的角度来讲,我认为最大的好处就是减少代码量以及提高效率(恩,写此文的时候觉得这是一句废话,但确实困扰了我一阵……)

比如,在学习KNN算法时需要计算欧式距离,公式如下:

$$d=\sqrt{ {({A_0}-{B_0})^2}+{({A_1}-{B_1})^2}+{({A_2}-{B_2})^2}+{({A_3}-{B_3})^2}+… }$$

这里用2维为例,公式变成:

$$d=\sqrt{ {({A_0}-{B_0})^2}+{({A_1}-{B_1})^2} }$$

这货貌似是已知直角三角形直角边求斜边长啊?

阅读全文

关于之前说的滴水算法,一直以为看不懂是因为智商不够,直到上周腾出时间看了原版论文才恍然大悟……之前看的都是“残篇”,怪不得很多地方看的都稀里糊涂的!

所以有英语能力的还是要看一手资料才行啊!否则看二手甚至多手的东西有时候会让人怀疑智商。

这里原版的论文链接 提供给各位,60280.pdf是最最原版的滴水算法,dropfall.pdf是经过改造的《基于惯性的滴水算法》和《基于惯性的大滴水算法》。另外改造版的算法是国人发表的,看的时候一种自豪感油然而生,虽然我也不知道自豪个什么劲……

基于惯性的滴水算法为了解决传统滴水算法遇到有“毛边”的情况,在传统水滴算法基础上多考虑了之前一步的方向。比如周围5个点都是黑或者白时,传统算法是应该向下滴落,但如果之前一步的方向是向右,那么综合考虑后滴落方向就变成了右下。另外,在基于惯性的滴水算法中,“左”是受到“歧视”的。

再进一步,对于类似字母Y这种凹陷情况,把判断范围扩大而不是仅仅考虑某一个像素点,就变成了基于惯性的大滴水算法了。

另外,关于起始点的选择,原版论文中是从上到下、从左到右依次遍历所有像素,找到第一个 左侧为黑色像素、右侧有黑的像素的白色像素点 开始滴落(确实挺拗口,看论文中的图就明白了)。

至于代码,先挖坑病好以后有空再和大家一起讨论分享。

评论和分享

之前提过对于有粘连的字符可以使用滴水算法来解决分割,但智商捉急的我实在是领悟不了这个算法的精髓,幸好有小伙伴已经实现相关代码

我对上面的代码进行了一些小修改,同时升级为python3的代码。

还是以这张图片为例:


7.png

在以前的我们已经知道这种简单的粘连可以通过控制阈值来实现分割,这里我们使用滴水算法。

首先使用之前文章中介绍的垂直投影或者连通域先进行一次切割处理,得到结果如下:


11.png
阅读全文

上篇文章记录了2种分割验证码的方法,此外还有一种叫做”滴水算法”(Drop Fall Algorithm)的方法,但本人智商原因看这个算法看的云里雾里的,所以今天记录滑动验证码的处理吧。网上据说有大神已经破解了滑动验证码的算法,可以不使用selenium来破解,但本人能力不足还是使用笨方法吧。

基础原理很简单,首先点击验证码按钮后的图片是滑动后的完整结果,点击一下滑块后会出现拼图,对这2个分别截图后比较像素值来找出滑动距离,并结合selenium来实现拖拽效果。

阅读全文

今天这篇文章主要记录一下如何切分验证码,用到的主要库就是Pillow和Linux下的图像处理工具GIMP。首先假设一个固定位置和宽度、无粘连、无干扰的例子学习一下如何使用Pillow来切割图片。

使用GIMP打开图片后,按 加号 放大图片,然后点击View->Show Grid来显示网格线:


8.png

其中,每个正方形边长为10像素,所以数字1切割坐标为左20、上20、右40、下70。以此类推可以知道剩下3个数字的切割位置。代码如下:

1
2
3
4
5
6
7
from PIL import Image
p = Image.open("1.png")
# 注意位置顺序为左、上、右、下
cuts = [(20,20,40,70),(60,20,90,70),(100,10,130,60),(140,20,170,50)]
for i,n in enumerate(cuts,1):
temp = p.crop(n) # 调用crop函数进行切割
temp.save("cut%s.png" % i)

切割后得到4张图片:


9.png

那么,如果字符位置不固定怎么办呢?现在假设一种随机位置宽度、无粘连、无干扰线的情况。

阅读全文

写爬虫有一个绕不过去的问题就是验证码,现在验证码分类大概有4种:

  1. 图像类
  2. 滑动类
  3. 点击类
  4. 语音类

今天先来看看图像类,这类验证码大多是数字、字母的组合,国内也有使用汉字的。在这个基础上增加噪点、干扰线、变形、重叠、不同字体颜色等方法来增加识别难度。
相应的,验证码识别大体可以分为下面几个步骤:

  1. 灰度处理
  2. 增加对比度(可选)
  3. 二值化
  4. 降噪
  5. 倾斜校正分割字符
  6. 建立训练库
  7. 识别
阅读全文

Python面试题2

发布在 Python

最近面试了几家公司,各行各业的都有,涨了很多见识也发现了自己的技术盲点。这里来一个汇总简单纪录。

行列转换

1
2
3
4
5
6
7
8
9
10
11

已知有一个二维列表(每一行的元素个数相同),写出函数对其行列转换并输出,比如:
a = [[1,1,1,1],
[2,2,2,2]]
输出:
[
[1,2],
[1,2],
[1,2],
[1,2]
]

这里建议笔试时候尽量使用简单清晰的写法,让面试官一眼就能看出答案对错:

1
2
3
4
5
6
7
8
def convert(alist):
result = []
for x in range(len(alist[0])):
tmp = []
for y in range(len(alist)):
tmp.append(alist[y][x])
result.append(tmp)
print result
阅读全文

Pyflame安装小记

发布在 Python

火焰图是一款性能调优工具,可以清晰的看出程序运行瓶颈在哪里。

pyflame则是由Uber开源出来的针对python程序生成火焰图的工具。

这里记录一下安装过程以及遇到的错误。

阅读全文
作者的图片

Roy

微信公众号:hi-roy


野生程序猿


China