K邻近分类法（KNN）

算法步骤：
1.计算距离：对于一个新的输入样本，计算其与训练集中每一个样本的距离。
2.找到K个最近邻：选择距离最近的K个训练样本。
3.多数表决：根据这K个最近邻的标签，通过多数表决来决定新样本的类别。

实现最基本的KNN形式非常简单。给定训练样本集和对应的标记列表，下面是一个示例

import numpy as np
from collections import Counter
import matplotlib.pyplot as plt# 定义一个KNN分类器类
class KNNClassifier:def __init__(self, k=3):self.k = kdef fit(self, X, y):self.X_train = Xself.y_train = ydef predict(self, X):y_pred = [self._predict(x) for x in X]return np.array(y_pred)def _predict(self, x):# 计算距离distances = [self.euclidean_distance(x, x_train) for x_train in self.X_train]# 获取最近的k个邻居的索引k_indices = np.argsort(distances)[:self.k]# 获取最近的k个邻居的标签k_nearest_labels = [self.y_train[i] for i in k_indices]# 通过投票选择最常见的标签most_common = Counter(k_nearest_labels).most_common(1)return most_common[0][0]@staticmethoddef euclidean_distance(x1, x2):return np.sqrt(np.sum((x1 - x2) ** 2))# 示例数据
X = np.array([[1, 1],[1, 2],[2, 2],[2, 3],[3, 3],[3, 4],[4, 4],[4, 5],[5, 5]
])
y = np.array([0, 0, 0, 0, 1, 1, 1, 1, 1])# 创建KNN分类器对象
clf = KNNClassifier(k=3)
clf.fit(X, y)# 测试数据
X_test = np.array([[1, 1], [3, 3], [5, 5]])# 进行预测
predictions = clf.predict(X_test)
print("Predictions:", predictions)# 绘制数据点
plt.scatter(X[:, 0], X[:, 1], c=y, s=100, cmap='viridis')
plt.scatter(X_test[:, 0], X_test[:, 1], c=predictions, s=100, marker='x', cmap='viridis')
plt.show()

结果如下：

用稠密SIFT作为图像特征

使用下面代码可实现稠密SIFT特征向量

import sift
from PIL import Image
import numpy as np
import osdef process_image_dsift(imagename, resultname, size=20, steps=10,force_orientation=False, resize=None):""" 用密集采样的 SIFT 描述子处理一幅图像，并将结果保存在一个文件中。可选的输入：特征的大小 size，位置之间的步长 steps，是否强迫计算描述子的方位 force_orientation（False 表示所有的方位都是朝上的），用于调整图像大小的元组 """# 打开并转换图像为灰度模式im = Image.open(imagename).convert('L')# 根据提供的 resize 参数调整图像大小if resize is not None:im = im.resize(resize)# 获取图像尺寸m, n = im.sizeif imagename[-3:] != 'pgm':# 创建一个 pgm 文件im.save('tmp.pgm')imagename = 'tmp.pgm'# 创建帧，并保存到临时文件scale = size / 3.0x, y = np.meshgrid(range(steps, m, steps), range(steps, n, steps))xx, yy = x.flatten(), y.flatten()frame = np.array([xx, yy, scale * np.ones(xx.shape[0]), np.zeros(xx.shape[0])])np.savetxt('tmp.frame', frame.T, fmt='%03.3f')# 根据是否需要强迫计算描述子的方位，选择相应的命令if force_orientation:cmmd = f"sift {imagename} --output={resultname} --read-frames=tmp.frame --orientations"else:cmmd = f"sift {imagename} --output={resultname} --read-frames=tmp.frame"# 执行命令os.system(cmmd)print(f'processed {imagename} to {resultname}')

结果如下：

使用用于定位描述子的局部梯度方向，该代码可以在整个图像中计算出稠密SIFT特征。如上图圆圈所示。

贝叶斯分类器

贝叶斯分类器是一种基于贝叶斯条件概率定理的概率分类器，它假设特征是彼此独立不相关的（这就是它“朴素”的部分）。贝叶斯分类器可以非常有效地被训练出来，原因在于每一个特征模型都是独立选取的。

算法步骤：
1.估计先验概率：对于每个类别，计算该类别的先验概率。
2.估计似然：对于每个特征值，计算其在每个类别下的条件概率。
3.后验概率：使用贝叶斯定理计算后验概率，并根据最大后验概率原则进行分类。

首先我们看一个使用高斯概率分布模型的贝叶斯分类器基本实现，也就是用从训练数据集计算得到的特征均值和方差来对每个特征单独建模。

class BayesClassifier(object):def __init__(self):""" 使用训练数据初始化分类器 """self.labels = [] # 类标签self.mean = [] # 类均值self.var = [] # 类方差self.n = 0 # 类别数def train(self,data,labels=None):""" 在数据 data（n×dim 的数组列表）上训练，标记labels是可选的，默认为0…n-1 """if labels==None:labels = range(len(data))self.labels = labelsself.n = len(labels)for c in data:self.mean.append(mean(c,axis=0))self.var.append(var(c,axis=0))def classify(self,points):""" 通过计算得出的每一类的概率对数据点进行分类，并返回最可能的标记"""# 计算每一类的概率est_prob = array([gauss(m,v,points) for m,v in zip(self.mean,self.var)])# 获取具有最高概率的索引，该索引会给出类标签ndx = est_prob.argmax(axis=0)est_labels = array([self.labels[n] for n in ndx])return est_labels, est_prob

该模型每一类都有两个变量，即类均值和协方差。train()方法获取特征数组列表（每个类对应一个特征数组），并计算每个特征数组的均值和协方差。classify()方法计算数据点构成的数组的类概率，并选概率最高的那个类，最终返回预测的类标记及概率值，同时需要一个高斯辅助函数：

def gauss(m,v,x):""" 用独立均值m和方差v评估d维高斯分布 """if len(x.shape)==1:n,d = 1,x.shape[0]else:n,d = x.shape# 协方差矩阵，减去均值S = diag(1/v)x = x-m# 概率的乘积y = exp(-0.5*diag(dot(x,dot(S,x.T))))# 归一化并返回return y * (2*pi)**(-d/2.0) / ( sqrt(prod(v)) + 1e-6)

将该贝叶斯分类器用于上一节的二维数据，下面的脚本将载入上一节中的二维数据，并训练出一个分类器：

import pickleimport bayesimport imtools# 用Pickle 模块载入二维样本点
with open('points_normal.pkl', 'r') as f:class_1 = pickle.load(f)class_2 = pickle.load(f)labels = pickle.load(f)# 训练贝叶斯分类器
bc = bayes.BayesClassifier()bc.train([class_1,class_2],[1,-1])

载入上一节中的二维测试数据对分类器进行测试：

# 用Pickle 模块载入测试数据
with open('points_normal_test.pkl', 'r') as f:class_1 = pickle.load(f)class_2 = pickle.load(f)labels = pickle.load(f)#在某些数据点上进行测试print bc.classify(class_1[:10])[0]#绘制这些二维数据点及决策边界def classify(x,y,bc=bc):points = vstack((x,y))return bc.classify(points.T)[0]imtools.plot_2D_boundary([-6,6,-6,6],[class_1,class_2],classify,[1,-1])show()

该脚本会将前10个二维数据点的分类结果打印输出到控制台，输出结果如下：

我们再次用一个辅助函数classify()在一个网格上评估该函数来可视化这一分类结果。两个数据集的分类结果如下图所示；该例中，决策边界是一个椭圆，类似于二维高斯函数的等值线。

用贝叶斯分类器对二维数据进行分类。每个例子中的颜色代表了类标记。正确分类的点用星号表示，误错分类的点用圆点表示，曲线是分类器的决策边界

支持向量机（SVM）

SVM是一类强大的分类器，可以在很多分类问题中给出现有水准很高的分类结果，特别是当数据不是线性可分时。最简单的SVM通过在高维空间中寻找一个最优线性分类面，尽可能地将两类数据分开。对于一特征向量$x$的决策函数为：$f(x)=wx-b$,该函数月阈值为0，它能够很好地将两类数据分开，使其一类为正数，另一类为负数。
SVM的一个优势是可以使用核函数,核函数能够将特征向量映射到另外一个不同维度的空间中，比如高维度空间。通过核函数映射，依然可以保持对决策函数的控制，从而可以有效地解决非线性或者很难的分类问题。

下面是一些最常见的核函数：
线性是最简单的情况，即在特征空间中的超平面是线性的，$K(x_i,x)=x_{i}x$
多项式用次数为d的多项式对特征进行映射，$K(x_i,x)=(\gamma x_i\ast (x+r){)}^d,\gamma >0$
径向基函数，通常指数函数是一种极其有效的选择
Sigmoid 函数，一个更光滑的超平面替代方案,$K(x_i,x)=tanh(\gamma x_i\ast (x+r))$
每个核函数的参数都是在训练阶段确定的。

使用LibSVM

下面的脚本会载入在前面kNN范例分类中用到的数据点，并用径向基函数训练一个SVM分类器：

import pickle
from svmutil import *
import imtools# 用Pickle 载入二维样本点
with open('points_normal.pkl', 'r') as f:
class_1 = pickle.load(f)
class_2 = pickle.load(f)
labels = pickle.load(f)# 转换成列表，便于使用libSVM
class_1 = map(list,class_1)
class_2 = map(list,class_2)
labels = list(labels)
samples = class_1+class_2 # 连接两个列表
# 创建SVM 
prob = svm_problem(labels,samples)
param = svm_parameter('-t 2')# 在数据上训练SVMm = svm_train(prob,param)#在训练数据上分类效果如何？
res = svm_predict(labels,samples,m)

我们用与前面一样的方法载入数据集，但是这次需要把数组转成列表，因为LibSVM不支持数组对象作为输入。输出结果如下：

结果表明该分类器完全分开了训练数据，400个数据点全部分类正确。
下图显示了两个不同数据集在二维平面上的分布情况。

用支持向量机SVM对二维数据进行分类。在这两幅图中，用不同颜色标识类标记。正确分类的点用星号表示，错误分类的点用圆点表示，曲线是分类器的决策边界

光学字符识别（OCR）

OCR是一个理解手写或机写文本图像的处理过程。一个常见的例子是通过扫描文件来提取文本，例如书信中的邮政编码或者谷歌图书（http://books.google.com/）里图书馆卷的页数。
OCR通常涉及多个步骤，包括特征选择、分类器训练、字符分割和识别。

训练分类器

对于这种分类问题，我们有10个类：数字1…9，以及一些什么也没有的单元格。我们给定什么也没有的单元格的类标号是0，这样所有类标记就是0…9。我们会用已经剪切好的数独单元格数据集来训练一个10类的分类器2文件sudoku_images.zip中有两个文件夹“ocr data”和“sudokus”， 后 者 包 含 了 不 同 条 件 下 的数独图像集 ，我们稍后讲解。现在我们主要来看文件夹“ocr_data”， 这个文件夹包含了两个子文件夹，一个装有训练图像，另一个装有测试图像。这些图像文件名的第一个字母是数字（0…9），用以标明它们属于哪类 。下图是训练集中的一些样本。

选取特征

我们首先要确定选取怎样的特征向量来表示每一个单元格里的图像。有很多不错的
选择；这里我们将会用某些简单而有效的特征。输入一个图像，下面的函数将返回
一个拉成一组数组后的灰度值特征向量：

def compute_feature(im):""" 对一个 ocr 图像块返回一个特征向量"""# 调整大小，并去除边界norm_im = imresize(im,(30,30))norm_im = norm_im[3:-3,3:-3]return norm_im.flatten()

用下面的函数来读取训练数据：

def load_ocr_data(path):imlist = [os.path.join(path,f) for f in os.listdir(path) if f.endswith('.jpg')]labels = [int(imfile.split('/')[-1][0]) for imfile in imlist]features = []for imname in imlist:im = array(Image.open(imname).convert('L'))features.append(compute_feature(im))return array(features),labels

用上面的函数计算出的特征向量存储在一个数组里。

多类支持向量机

在得到了训练数据之后，我们接下来要学习一个分类器，这里将使用多类支持向量机。代码如下：

from svmutil import *# 训练数据
features,labels = load_ocr_data('training/')# 测试数据
test_features,test_labels = load_ocr_data('testing/')
# 训练一个线性SVM分类器
features = map(list,features)
test_features = map(list,test_features)
prob = svm_problem(labels,features)
param = svm_parameter('-t 0')
m = svm_train(prob,param)# 在训练数据上分类效果如何
res = svm_predict(labels,features,m)# 在测试集上表现如何
res = svm_predict(test_labels,test_features,m)

得到下面输出结果：