机器学习相关算法实现

2017-10-07

忙了很久，却并没有在做自己喜欢的部分，也一直没有时间沉淀一下，现在把最近看过的内容做一下总结和复习吧，主要是李航《统计学习方法》中的内容。

感知器算法

感知器模型

感知机模型输入空间为x$\in$R,输出空间为{-1,1}，可以大致用一个公式概括:

$
f(x) = sign(wx+b)
$

损失函数有多种选择，一种是以误分类点的总数作为标准，但是这样的损失函数不易优化。另一种则是误分类点到超平面的总距离。对于误分类的数据，当wx+b>0时，y=-1,当wx+b<0时，y=1，因此单个点到超平面的距离可以写成：$\frac {-y_i(wx_i+b)} {|w|} $那么整个模型的损失函数就是把每个点的损失累加起来即可。

学习算法

感知器学习算法是由误分类点驱动的，采用随机梯度下降的方式来不断优化目标函数，随机选取一个误分类点，对参数w,b进行更新：

$
w = w+\eta y_ix_i
$

$
b = b + \eta y_i
$

最终感知器的算法可以这样实现：

def train(self, features, labels):
        # 列加偏置项，初始化权重为0
        self.w = [0.0] * (len(features[0]) + 1)
        correct_count = 0
        time = 0
        while time < self.max_iteration:
            index = random.randint(0, len(labels) - 1)
            x = list(features[index])
            x.append(1.0)
            # y = 1 或 -1
            y = 2 * labels[index] - 1
            wx = sum([self.w[j] * x[j] for j in range(len(self.w))])
            # 大于0 表示分类正确
            if wx * y > 0:
                correct_count += 1
                if correct_count > self.max_iteration:
                    break
                continue
            # 错误驱动，分类错误则更新权重值
            # w的梯度，对w求导，由xy给出
            # x的最后一个值为1，相当于b的梯度由y更新
            for i in range(len(self.w)):
                self.w[i] += self.learning_step * (y * x[i])
def predict(self, features):
        labels = []
        for feature in features:
            x = list(feature)
            x.append(1.0)
            wx = sum([self.w[j] * x[j] for j in range(len(self.w))])
            # 填充1或0
            labels.append(int(wx > 0))
        return labels

K近邻算法

K近邻算法模型主要由三个因素决定：距离度量，K值的选择和分类决策规则。距离度量一般采用欧氏距离或者曼哈顿距离。而对于K值的选择，如果K值选择的过小，就相当于在较小的邻域内进行预测，那么预测结果对近邻的点非常敏感，同时如果近邻点恰巧是噪点就会出现错误。所以K值选的小，会让模型变得复杂，容易过拟合。而K值选的较大，则与输入实例较远的点也会发生作用，而这些点可能并不相关，模型会变得简单。通常采用交叉验证法选取最优K值。分类决策规则通常是多数表决

实现K近邻算法，最简单的方式是线性扫描，当训练集很大时，计算量也会特别大，为了提高K近邻搜索的效率，有很多的数据结构可以用来优化，例如kd树。kd树实现起来较为复杂，后续再补充，这里介绍简单的线性扫描的方法：

def predict(self, test_set, train_set, train_labels):
        predict = []
        num = 0
        knn_list = []
        max_index = -1
        max_dist = 0
        # 计算训练集中到单个测试样本距离最近的k个数据
        for test in test_set:
            print(num)
            num = num + 1   
            for i in range(self.k):
                train_vec = train_set[i]
                label = train_labels[i]
                dist = self.get_dist(train_vec, test)
                knn_list.append((dist, label))
            for i in range(self.k, len(train_labels)):
                label = train_labels[i]
                train_vec = train_set[i]
                dist = self.get_dist(train_vec, test)
                if max_index < 0:
                    for j in range(self.k):
                        if max_dist < knn_list[j][0]:
                            max_index = j
                            max_dist = knn_list[max_index][0]
                if dist < max_dist:
                    knn_list[max_index] = (dist, label)
                    max_index = -1
                    max_dist = 0
                total = 10
                count = [0 for i in range(total)]
                for dist, label in knn_list:
                    count[label] += 1
                # 得到训练数据中出现最多的label值
                predict.append(np.argmax(count))
        return np.array(predict)
    def get_dist(self, vec1, vec2):
        return np.linalg.norm(vec1 - vec2)

朴素贝叶斯法

朴素贝叶斯分类就是根据先验概率和条件概率来判断样本属于哪一类，可参考书中的例题看懂。代码如下：

# 浮点数连乘时会导致结果变成Inf的情况，而int类型相乘则不会
def Train(avg, train_set, train_labels):
    # 先验概率
    prior_probability = np.zeros(class_nums)
    # 条件概率
    condition_probability = np.zeros((class_nums, feature_nums, 2))
    # 计算
    for i in range(len(train_labels)):
        img = binary_image(train_set[i],avg)
        label = train_labels[i]
        # 先验概率分子，事件出现的次数
        prior_probability[label] += 1
        for j in range(feature_nums):
            # 条件概率，在y=label时，第j个特征为0或1的次数
            condition_probability[label][j][img[j]] += 1
    for i in range(class_nums):
        for j in range(feature_nums):
            pix_0 = condition_probability[i][j][0]
            pix_1 = condition_probability[i][j][1]
            # 如果不做处理，某个特征的值可能为0，最终
            p0 = (float(pix_0)/float(pix_0 + pix_1)) * 100000 + 1
            p1 = (float(pix_1)/float(pix_0 + pix_1)) * 100000 + 1
            
            condition_probability[i][j][0] = p0
            condition_probability[i][j][1] = p1
    return prior_probability, condition_probability
def calculate(img, label):
    # 属于某一类的个数
    p = int(prior_probability[label])
    # int 型可以无限乘
    # 条件独立性假设
    for i in range(len(img)):
        p *= int(condition_probability[label][i][img[i]])
    return p
def predict(avg,test_set, prior_probability, condition_probability):
    predict = []
    for img in test_set:
        img = binary_image(img, avg)
        max_label = 0   # 最有可能的类别
        max_p = calculate(img, 0)   # 计算类别为0的概率
        for i in range(1, class_nums):
            p = calculate(img, i)
            if max_p < p:
                max_p = p
                max_label = i
        predict.append(max_label)
    return np.array(predict)

拓展一些爱忘的东西

极大似然估计

假设X为离散型，概率分布则为$ P(X=x)=p(x;\theta)$，则似然函数为$K=\prod p(x;\theta) $
假设X为连续型，概率密度函数为$f(x;\theta)$, 则似然函数为$K=\prod f(x;\theta) $
极大似然估计法原理就是固定样本观测值$(x_1,x_2,x_3,…,x_n)$，挑选参数$\theta $使的似然函数最小。可以通过取对数的方式求解似然方程。举个例子:
使用极大似然估计推出朴素贝叶斯法中的概率公式:
极大似然函数
$$ L(\theta;y_1,y_2,…,y_k)=\prod P(y_i)=\prod \theta_k ^ {N_k}$$
其中N为样本总数，两边取对数得到
$$\ln(L(\theta))=\sum N_k\ln \theta_k$$
注意到约束条件$ \sum \theta_k =1$可以用拉格朗日乘子法，即$l(\theta_k,\lambda)=\sum {N_k ln\theta_k} +\lambda(\sum {\theta_k} -1)$，求导就可以得到：$\frac{N_k}{\theta_k}+\lambda=0$ 联立所有的k以及约束条件得到$\theta_k=\frac{N_k}{N}$。

贝叶斯估计

这里介绍下与极大似然估计的区别，具体公式可参考书上内容。
极大似然估计的核心思想是:找到参数θ的一个估计值，使得当前样本出现的可能性最大。而贝叶斯估计则是引入了先验概率，通过先验概率和似然概率来求解后验概率，而极大似然估计则是直接通过最大化似然概率来求解。

学业繁忙，突然发现自己感兴趣的学到的东西才这么点儿，都没太多时间看自己想看的书，写自己想写的代码，学自己想学的知识，现在回顾这几天，发现真正对自己有用的东西好像并没有太多，到底在忙些什么？哎，惜哉！