发表于 | 分类于

Logistic In MNIST

算法原理简述：

二项逻辑斯蒂回归模型是一种分类模型，有条件概率P(Y|X)表示，形式为参数化的逻辑斯蒂分布。

在本实验中，对于该模型的二项形式，因为只能做二分类，所以我们对数据集的标签进行的改变只剩下0和1;而后输入的依旧是图像的向量，主要需要掌握的是关于该模型的推导和如何迭代得到近似最优解。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @File  : LogisticRegression.py
# @Author: mfzhu
# @Date  : 2017/4/15
# @Desc  :
import time
import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
def binary(data, threshold):
    """
    :param data: 需要二值化的数据
    :param threshold: 二值化的阈值
    :return: 二值化后的数据
    """
    index_1 = np.array(data > threshold)
    index_2 = np.array(data <= threshold)
    data[index_1] = 1
    data[index_2] = 0
    return data
class LogisticRegression(object):
    def __init__(self):
        self.max_iteration = 10000
        # 定义权重的迭代次数
        self.step = 0.00001
        # 定义每次迭代的步长
        self.weights = []
        # 定义权重
    def sigmoid(self, x):
        """
        :param x: 样本数据
        :return: 该样本数据对应的sigmoid函数值
        """
        return np.exp(x) / (1 + np.exp(x))
    # 定义计算Logit函数值
    def _predict(self, feature):
        """
        :param feature: 内部预测函数用于调用，预测样本为feature的结果
        :return: 返回该样本对应的标签
        """
        wx = sum([self.weights[i] * feature[i] for i in range(len(feature))])
        predict1 = self.sigmoid(wx)
        predict0 = 1 - predict1
        if predict1 > predict0:
            return 1
        else:
            return 0
    # 内部预测函数用于调用，先计算权重和输入向量的乘积，然后计算sigmoid值
    def train(self, train_data, label_data):
        """
        :param train_data: 训练数据
        :param label_data: 训练数据对应的标签
        :return:
        """
        self.weights = np.ones(train_data.shape[1] + 1, float)
        # 权重加上一维截距项
        self.weights.shape = (train_data.shape[1] + 1, 1)
        # 定义权重的行和列（python中列值为空）
        train_data = np.column_stack((train_data, np.ones(train_data.shape[0])))
        # 训练数据在末尾加上一列全1的数据
        train_data = np.matrix(train_data)
        # 转化为矩阵方便计算
        time = 0
        # 计算当前迭代次数
        while time < self.max_iteration:
            wx_matrix = train_data * self.weights
            # 计算权重和训练数据的乘积
            exp_wx = self.sigmoid(wx_matrix)
            # 计算sigmoid值
            difference = np.matrix(label_data) - exp_wx.T
            # 计算sigmoid值和标签值的差
            self.weights += self.step * (difference * train_data).T
            # 改变权重值
            time += 1
    def predict(self, features):
        """
        :param features:
        :return:
        """
        label = []
        for feature in features:
            x = list(feature)
            x.append(1)
            label.append(self._predict(x))
            # 调用先前定义的内部预测函数用来预测测试数据的标签
        return label
if __name__ == '__main__':
    time1 = time.time()
    print("start reading the data:")
    raw_path = r'F:\work and learn\ML\dataset\MNIST\train.csv'
    raw_data = np.loadtxt(raw_path, delimiter=',', skiprows=1)
    # 读入原始数据
    label = raw_data[:, 0]
    data = raw_data[:, 1:]
    # 区分标签数据和原始数据
    data = binary(data, 100)
    label[label != 0] = 1
    # 进行二值化和对标签二值化（这边做的是二分类）
    train_data, test_data, train_label, test_label = train_test_split(data, label, test_size=0.33, random_state=23323)
    time2 = time.time()
    print("read data cost:", time2 - time1, " seconds", '\n')
    # 将训练数据切分成三块用于训练和测试
    print("start training the model:")
    lr = LogisticRegression()
    lr.train(train_data, train_label)
    time3 = time.time()
    print("training cost:", time3 - time2, ' seconds', '\n')
    print("start predicting:")
    # 定义logit类然后训练
    test_predict = lr.predict(test_data)
    score = accuracy_score(test_label, test_predict)
    time4 = time.time()
    print("predicting cost:", time4 - time3, ' seconds', '\n')
    # 利用训练到的模型预测测试集的标签
    print("the accuracy_score is:", score)

模型的训练结果：

可以看到，逻辑斯蒂的正确率很高，但是相对的，训练的时间也较长。

img

发表于 | 分类于

Decision Tree In MNIST

决策树作为机器学习算法的基础算法之一，其优点是模型具有可读性，分类速度快。决策树的基本算法可以参考李航老师的《统计机器学习》,本文中的主要思路也是基于此。对于决策树而言，主要有三部分的工作需要实现，特征提取，决策树构造和决策树的剪枝。在特征提取部分，常用的是信息增益和信息增益比，分别对应于ID3和C4.5决策树算法；决策树的构造部分主要是利用递归的思想构建；本文中未涉及到决策树剪枝部分。

本文中实现的是利用信息增益进行特征提取的ID3决策树，主要需要提及的部分是关于树的节点构造的部分。树的节点中主要包含了节点类型，包括叶节点和内部节点，用于在预测过程中当预测到达叶节点时，返回所属类别；也包含了节点所属类别(只针对叶节点存在)；包含当前节点的最优切分位置(对于非叶节点存在)；以及切分位置取不同值所属的不同子树，用字典保存。

基本思路是：我们在函数中输入训练数据，训练标签，可切分维度集合和信息增益阈值。

  • 首先判断当前训练标签的类数，如果只有一类，我们将其设置为叶节点，节点类别取当前标签，然后返回；然后判断可切分维度的数量，如果不存在切分维度，则取当前训练标签中的最多那一类作为节点的类别，设置节点为叶节点返回；

  • 以上情况都不符合的情况下，我们遍历所有的切分点，找到信息增益最大的位置，提取出这一列的值；并根据这一列的不同取值所对应的标签得到下一步的训练数据、训练标签和切分维度集合用于构建子树，并将子树添加到当前树中。

  • 然后不断的递归调用即可
  • 其中在找到最大信息增益位置的最后需要判断和阈值的关系，在小于阈值的情况下，我们直接构建叶节点和所属类别返回。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
import numpy as np
import math
import pandas as pd
from collections import Counter
# 容易混淆的是，feature是指用特征中的哪一维进行切分
# index是指当前还剩下可以用于切分的维数的集合
class Tree(object):
    def __init__(self, node_type, category=None, feature=None):
        self.node_type = node_type
        # 节点类型，分为内部节点和叶节点
        self.category = category
        # 如果是叶节点的情况，该值记录节点的所属类别
        self.feature = feature
        # 如果是内部节点，该值记录切分位置
        self.dic = {}
        # 用来保存切分点不同取值所对应的子树
    def add_tree(self, value, tree):
        self.dic[value] = tree
        # 将子树添加到当前树中
    def predict(self, index_list):
        if self.node_type == "lef":
            return self.category
        tree = self.dic[index_list[self.feature]]
        return tree.predict(index_list)
        # 预测给定特征的所属类别
def binary(data, threshold):
    """
    :param data: 需要二值化的数据
    :param threshold: 二值化的阈值
    :return: 二值化后的数据
    """
    data[data > threshold] = 255
    data[data <= threshold] = 0
    return data
def calculate_entropy(x):
    """
    :param x: 待计算的特征向量
    :return: 返回特征向量的熵
    """
    catogory_list = set(x)
    ent = 0
    for catogory in catogory_list:
        probability = x[x == catogory].shape[0] / x.shape[0]
        ent = ent + probability * math.log2(probability)
    return -1 * ent
def conditonal_entropy(x, y):
    """
    :param x: 条件特征向量
    :param y: 标签特征向量
    :return: 返回条件熵
    """
    catogory_list = set(x)
    conditional_ent = 0
    for catogory in catogory_list:
        sub_set = y[x == catogory]
        conditional_ent += (sub_set.shape[0] / x.shape[0]) * calculate_entropy(sub_set)
    return conditional_ent
def information_gain(x, y):
    """
    :return: 返回信息增益
    """
    return calculate_entropy(y) - conditonal_entropy(x, y)
def recursive_train(train_data, train_label, index, threashold):
    """
    :param train_data: 训练数据
    :param train_label: 训练的标签
    :param index: 特征的索引列表
    :param threashold: 阈值
    :return: 决策树头结点
    """
    most_common = Counter(train_label).most_common(1)
    # 得到标签中出现最多的类别
    max_infor_gain = 0
    # 记录最大信息增益
    max_entropy_index = 0
    # 记录最大信息增益所属的列
    if len(set(train_label)) == 1:
        return Tree("lef", category=train_label[0])
    # 如果当前标签只有一类的情况
    if len(index) == 0:
        return Tree("lef", category=most_common[0][0])
    # 如果没有可以继续切分的特征
    for col in index:
        condition_data = train_data[:, col]
        current_gain = information_gain(condition_data, train_label)
        # 找到每个切分点计算信息增益
        if current_gain > max_infor_gain:
            max_infor_gain = current_gain
            max_entropy_index = col
        # 找到最大的信息增益和其对应的列
    if max_infor_gain < threashold:
        return Tree("lef", category=most_common[0][0])
    # 如果小于阈值，直接返回叶节点，类别取出现最多的那个标签
    tree = Tree("internal", feature=max_entropy_index)
    # 构建树，节点类型为内部节点，切分点最大信息增益切分
    max_feature_list = train_data[:, max_entropy_index]
    # 提取出用于切分的那一列
    feature_value_list = set(max_feature_list)
    # 找到切分列中的不同取值列表
    next_index = list(filter(lambda x: x != max_entropy_index, index))
    # 得到子树的切分列表
    for value in feature_value_list:
        next_train_set = train_data[max_feature_list == value]
        # 得到子树的训练集
        next_train_label = train_label[max_feature_list == value]
        # 子树的训练标签
        next_tree = recursive_train(next_train_set, next_train_label, next_index, threashold)
        # 得到子树
        tree.add_tree(value, next_tree)
        # 将子树按照不同的切分值添加到当前树中
    return tree
if __name__ == '__main__':
    raw_path = r'F:\work and learn\ML\dataset\MNIST\train.csv'
    # 原始数据
    test_path = r'F:\work and learn\ML\dataset\MNIST\test.csv'
    # 训练数据
    index = [i for i in range(784)]
    # 初始的切分标签列表
    raw_data = np.loadtxt(raw_path, delimiter=',', skiprows=1)
    label = raw_data[:, 0]
    data = raw_data[:, 1:]
    # 得到标签和训练数据
    data = binary(data, 100)
    tree = recursive_train(data, label, index, 0.1)
    # 二值化后进行训练
    test_data = np.loadtxt(test_path, delimiter=',', skiprows=1)
    test_data = binary(test_data, 100)
    # 得到测试数据，并进行二值化
    result = []
    for i in range(test_data.shape[0]):
        print(i)
        result.append(tree.predict(test_data[i]))
    # 对于每个训练数据进行预测其所属类别
    index = [i for i in range(1, 28001)]
    res = pd.DataFrame(index, columns=['ImageId'])
    res['Label'] = result
    res.to_csv(r"C:\Users\PC\Desktop\result.csv", index=False)
    # 保存结果

对于本文中所实现的决策树在MNIST上的分类结果在Kaggle平台上测试结果为85.07%左右，相比于KNN，其分类效果要差不少，但是所需要的计算时间较少于KNN算法。

发表于 | 分类于

Longest Palindromic Substring(最长的回文子串)

题目描述：

给定一个字符串，找到字符串中的最长回文子串。见LeetCode5

解题思路：

本题的常见解法有三种。第一种是中心扩展的方法。在遍历字符串的过程，以当前字符串为中心向左右两侧扩展，扩展结束后判断子串的长度。需要注意的是：这种方法中有偶回文串和奇数回文串的区别，遍历的过程需要区别对待。aba奇回文子串，abba是偶回文子串。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    string longestPalindrome(string s) {
        int max_length = 1;//记录最长串的长度
        string res = s.substr(0,1);//以第一个字母为初始值回文串
        int left = 0; //记录向左扩展的下标
        int right = 0;//记录向右扩展的下标
        
        for (int i = 0; i < s.size(); i++){
            left = i;
            right = i;
            while((left >= 0) && (right < s.size()) && (s[left] == s[right])){
                left--;
                right++;
            }
            //判断奇回文串；如果下标满足要求并且左右相等的情况，左右扩展
            
            if ((right - left - 1) > max_length){
                max_length = right - left - 1;
                res = s.substr(left + 1, max_length);
            }//如果比当前长度长，改变长度和返回值
        }
        for (int i = 0; i < s.size() - 1; i++){
            if (s[i] == s[i + 1]){
                left = i - 1;
                right = i + 2;
            }else{
                continue;
            }//如果没有连续的两个字母相等，则当前遍历不可能是偶回文串
            
            while((left >= 0) && (right < s.size()) && (s[left] == s[right])){
                left--;
                right++;
            }
            //符合条件则左右扩展
            if ((right - left - 1) > max_length){
                max_length = right - left - 1;
                res = s.substr(left + 1, max_length);
            }//改变最长长度和返回值
        }
        return res;
        
    }
};

解题思路2：

第二种思路是使用动态规划的方法。我们用P[i, j]表示字符串中i到j位置的子串；如果这个串是回文字符串则我们设定为1；如果这个子串不是回文字符串我们则设定为0。这样我们构建一个二维的数组用来保存是否是回文的信息；然后根据一下三种情况来进行修改数组中的信息。

  • 如果i = j的情况，则P[i,j]设定为1；
  • 如果j = i + 1情况，则判断s[i]和s[j]是否相等；相等为1否则为1；
  • 如果j > i + 1的情况，我们先判断s[i]和s[j]的情况，不相等则设定为1；如果相等的情况下则P[i,j] = P[i+1,j-1]

需要注意的地方是，我们则判断P[i, j]的时候用的是P[i + 1, j - 1]的情况，所以我们需要先知道P[i + 1,j - 1]的情况，这样决定了我们i需要从末尾开始遍历开始，然后j从i位置遍历到字符串的末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() == 0) return s;
        int max_length = 1;//记录当前的最长长度
        string res = s.substr(0, 1);//设定第一个为结果
        int dp[s.size()][s.size()] = {0};//设定全部动态数组为0
        
        for (int i = s.size() - 1; i >= 0; i--){
        //i从末尾开始遍历起
            for (int j = i; j < s.size(); j++){
            //j从i开始遍历到字符串末尾
                if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])){
     //这里面先判断了当前两个位置的字符是否相等的情况，只有相等后才有后序判断
     //如果相等；间隔小于等于1的情况直接设定为1；不然根据P[i + 1, j - 1]的情况
                    dp[i][j] = 1;
                    if (j - i + 1 > max_length){
                        max_length = j - i + 1;
                        res = s.substr(i, j - i + 1);
                    }
                }
            }
        }
       return res; 
    }
};

发表于 | 分类于

Naive Bayes In MNIST

算法简述：

朴素贝叶斯方法是基于贝叶斯定理与特征条件独立假设的分类方法。对于给定的训练数据集，首先基于特征条件独立假设学习输入和输出的联合概率分布；然后基于此模型，对给定的输入利用贝叶斯定理求出后验概率最大的输出。模型的优点是实现简单学习和预测的效率都很高，是一种常用的方法。

在MNIST数据集中，我们的特征是输入图像每一维的数据，根据已有的输入和输出估计联合概率分布；在输出新的数据集的情况下，我们根据训练好的模型，计算最大后验概率来对数据集进行分类。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
"""
@Author: mfzhu
"""
import numpy as np
from collections import Counter
import time
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
def binary(data, threshold):
    """
    :param data: the data need to be binary
    :param threshold: threshold value for binaryzation
    :return:the data after binaryzation
    """
    data[data > threshold] = 255
    data[data <= threshold] = 0
    return data
def get_the_prior_probability(label):
    """
    :param label: label data
    :return: the dict contains the prior probability
    """
    prior_pro = Counter(label)
    sample_num = len(label)
    for key in prior_pro.keys():
        prior_pro[key] = (prior_pro[key] + 1) / (sample_num + 10)
    return prior_pro
def get_the_conditional_probability(data, label):
    """
    :param data: the binaryzation data
    :param label: label data
    :return: the conditional probability
    """
    per_label_data = {}
    condition_pro = {}
    for i in range(10):
        per_label_data[i] = data[np.where(label == i)]
    for key in per_label_data.keys():
        pro_array = []
        for j in range(784):
            pro_array.append(
                (np.count_nonzero(per_label_data[key][:, j]) + 1) / (per_label_data[key].shape[0] + 2))
        condition_pro[key] = pro_array
    return condition_pro
def sample_map(input_data, condition_pro, prior_pro):
    """
    :param input_data: singal sample data
    :param condition_pro: conditional probability
    :param prior_pro: prior probability
    :return: the tag of sample data according map
    """
    result = {}
    for key in prior_pro.keys():
        pro = prior_pro[key]
        for k in range(len(input_data)):
            if input_data[k] != 0:
                pro *= condition_pro[key][k]
            else:
                pro *= (1 - condition_pro[key][k])
        result[key] = pro
    return max(zip(result.values(), result.keys()))[1]
def data_set_map(data, condition_pro, prior_pro):
    """
    :param data: data set
    :param condition_pro:
    :param prior_pro:
    :return: a list contains the tags of input data set
    """
    result = []
    for j in range(data.shape[0]):
        result.append(sample_map(data[j, :], condition_pro, prior_pro))
    return result
if __name__ == '__main__':
    raw_path = r'F:\work and learn\ML\dataset\MNIST\train.csv'
    # raw data file path
    test_path = r'F:\work and learn\ML\dataset\MNIST\test.csv'
    # test data file path
    print("start read data:")
    time1 = time.time()
    raw_data = np.loadtxt(raw_path, delimiter=',', skiprows=1)
    label = raw_data[:, 0]
    data = raw_data[:, 1:]
    # extract the label data and image data
    data = binary(data, 50)
    # binary the image data
    data_train, data_test, label_train, label_test = train_test_split(data, label, test_size=0.33,
                                                                      random_state=23333)
    # split the train data for training and testing
    time2 = time.time()
    print("read data cost:", time2 - time1, " seconds", '\n')
    print("start training:")
    prior_pro = get_the_prior_probability(label_train)
    condition_pro = get_the_conditional_probability(data_train, label_train)
    time3 = time.time()
    print("training cost: ", time3 - time2, " seconds", '\n')
    # using the train data and train label to calculate the prior probability
    # and conditional probability
    print("start predicting:")
    predict = data_set_map(data_test, condition_pro, prior_pro)
    train_result = accuracy_score(label_test, predict)
    time4 = time.time()
    print("predict cost: ", time4 - time3, " seconds", '\n')
    print("the accuracy is: ", train_result)

模型训练结果：

相比之下朴素贝叶斯的正确较差，但是胜在模型简单，并且训练速度快。

img

发表于 | 分类于

感知机模型在MNIST数据集上的应用

感知机模型简介：

感知机模型是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取{+1，-1}二者。感知机对应于输入空间中将实例划分为正负两类的分离超平面，属于判别模型。感知机学习旨在求出将训练数据进行线性划分的分离超平面，为此，导入基于误分类的损失函数，利用梯度下降法对损失函数进行极小化，求得感知机模型。感知机学习算法具有简单而易实现的优点。
感知机模型选择的是误分类点到超平面的总距离为损失函数。直觉上我们选择误分类的总点数作为损失函数，但是这样的损失函数不是参数的可导函数。
感知机模型中一个实例点被误分类的时候，我们调整w和b的参数，使得分类超平面向误分类点的一侧移动以减少误分类点到分类超平面的距离。

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @File  : PerceptionMachine.py
# @Author: mfzhu
# @Date  : 2017/4/21
# @Desc  :
import numpy as np
import random
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
import time
def binary(data, threshold):
    """
    :param data: 需要二值化的数据
    :param threshold: 二值化的阈值
    :return: 二值化后的数据
    """
    index_1 = np.array(data > threshold)
    index_2 = np.array(data <= threshold)
    data[index_1] = 1
    data[index_2] = 0
    return data
class PerceptionMachine(object):
    def __init__(self):
        self.max_iteration = 10000
        # 迭代次数
        self.step = 0.001
        # 迭代步长
        self.weight = []
        # 权重向量
        self.bias = 1
        # 偏置
        self.object_num = 1
        # 此处认为标签为1的为+1类，为0的为-1类
    def train(self, train_data, train_label):
        """
        :param train_data: 训练数据
        :param train_label: 训练标签
        :return:
        """
        num_sample, num_feature = train_data.shape
        # 得到输入训练数据的样本数和每个样本的维度
        self.weight = np.zeros(num_feature, float)
        # 初始化权重向量为全0向量
        time = 0
        # 记录当前迭代次数
        while time < self.max_iteration:
            index = random.randint(0, num_sample - 1)
            # 随机选取一个训练样本
            sample = train_data[index, :]
            label = train_label[index]
            # 得到这个样本的标签和数据
            y = int(label == self.object_num) * 2 - 1
            # 判断是属于+1类还是-1类
            result = (np.dot(sample, self.weight) + self.bias) * y
            # 计算是否被误分类
            if result <= 0:
                self.weight += self.step * y * sample
                self.bias += self.step * y
                time += 1
                # 被误分类的情况下，更新权重和偏置，然后迭代次数加1
    def predict(self, features):
        """
        :param features: 预测数据集合
        :return: 返回集合中每个sample的预测标签
        """
        res = []
        for index in range(features.shape[0]):
            if np.dot(features[index], self.weight) + self.bias > 0:
                # 如果对应的线性函数大于0，则判断为1
                res.append(1)
            else:
                res.append(0)
        return res
if __name__ == '__main__':
    print("Start reading the data:")
    time1 = time.time()
    raw_path = r'F:\work and learn\ML\dataset\MNIST\train.csv'
    raw_data = np.loadtxt(raw_path, delimiter=',', skiprows=1)
    # 读入原始数据
    label = raw_data[:, 0]
    data = raw_data[:, 1:]
    # 区分标签数据和原始数据
    data = binary(data, 125)
    label[label != 0] = 1
    # 进行二值化和对标签二值化（这边做的是二分类）
    train_data, test_data, train_label, test_label = train_test_split(data, label, test_size=0.333, random_state=23333)
    # 将数据随机切分用于训练和预测
    time2 = time.time()
    print("read data cost:", time2 - time1, " seconds", '\n')
    print("Start training:")
    perception = PerceptionMachine()
    perception.train(train_data, train_label)
    # 生成感知机模型并进行训练
    time3 = time.time()
    print("training cost:", time3 - time2, " seconds", '\n')
    print("Start predicting:")
    res = perception.predict(test_data)
    score = accuracy_score(test_label, res)
    time4 = time.time()
    print("predict cost", time4 - time3, " seconds", '\n')
    # 对数据进行预测并计算正确率
    print("the accuracy_score is", score)

代码运行结果：

img

发表于 | 分类于

Find The Boundary Of Tree(找到树的边界节点)

题目描述：

来自leetcode的contest。具体的题目描述可以在这里找到。

解题思路：

本题主要的难点有：怎么找到左侧边界；怎么找到右侧边界；怎么找到下边界；以及如何将边界连接已经右侧边界的逆序。 根据代码解释一下思路；首先判断根节点是否为空决定是否返回空的vector；其次定义用于保存边界的vector并将根节点的值导入；定义用于保存遍历过程节点的集合，将根节点导入；分别定义vector用于保存左侧边界、右侧边界和下边界；根据遍历函数得到的左右下边界，遍历其中的节点找到不重复的节点连接即为整颗树的边界。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    vector<int> boundaryOfBinaryTree(TreeNode* root) {
        if (!root)
            return {}; // 返回空边界
        vector<int> res = {root->val};//导入根值到边界结果
        unordered_set<TreeNode*> hash = {root};//导入根到遍历节点集合
        
        vector<TreeNode*> left;
        vector<TreeNode*> right;
        vector<TreeNode*> leaf;// 定义三个边界的vector
        
        leftBoundary(root->left, left);
        leafNode(root, leaf);
        rightBoundary(root->right, right);
        // 通过遍历函数找到各自边界的集合，其中集合可能存在重合
        
        for (auto l : left){if (hash.count(l)) continue; res.push_back(l->val); hash.insert(l);}
        //连接左侧边界
        for (auto m : leaf){if (hash.count(m)) continue; res.push_back(m->val); hash.insert(m);}
        //连接下侧边界
        for (auto r: right){if (hash.count(r)) continue; res.push_back(r->val); hash.insert(r);}
        // 连接右侧边界
        return res;
    }
    void leftBoundary(TreeNode* node, vector<TreeNode*>& left){
        while(node){
            left.push_back(node);
            if (node->left) node = node->left;
            else node = node->right;
            // 找到最左侧的边界；不断向左侧遍历，为空就向右侧遍历知道为空
        }
    }
    void leafNode(TreeNode* root, vector<TreeNode*>&leaf){
        if (!root) return;
        if (root->left == NULL && root->right == NULL) leaf.push_back(root);
        else
        {
            leafNode(root->left, leaf);
            leafNode(root->right, leaf);
        }
        //找到所有叶节点的集合即为下边界集合；先判断是否是空节点；然后判断是否是叶节点；然后递归左侧和右侧节点。
    }
    void rightBoundary(TreeNode* node, vector<TreeNode*>& right){
        while(node){
            right.push_back(node);
            if (node->right) node = node->right;
            else node = node->left;
        }//找到右侧边界；同左侧；需要注意的是需要将结果逆序。
        reverse(right.begin(), right.end());
    }
};

发表于 | 分类于

Array Permutation(数组的全排列)

题目描述：

给定一个数字n，和一个关于需要生成排列的长度k。要求根据这两个数字，从[1…n]的数组中生成长度为k的排列。

例子：

例如给定数字为n=4，k=2；则根据要求生成的排列为[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]。见LeetCode77.

解题思路：

这道题理解上问题不大，主要是在于用什么方法去解决。我们首先想到的是使用回溯的方法来解决。首先是使用一个标签变量来记录我们当前要确定排列中的第几个位置，然后递归的调用函数来确定下面位置的数字。主要的思路体现在代码中，可以看代码中的注释来理解。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> path;
        //保存当前的遍历结果
        vector<vector<int>> res;
        //保存结果
        helper(res, path, n, k);
        //调用函数
        return res;
        
    }
    void helper(vector<vector<int>>& res, vector<int>& path, int n, int k){
        if (k == 0){
            res.push_back(path);
            return;
        }
        //如果确定位置已经到了0，将其保存到结果中
        for (int i = n; i > 0; i--){
            path.push_back(i);
            //先确定一个数
            helper(res, path, i - 1, k - 1);
            //确定下一个数
            path.pop_back();
            //回溯一步，将刚才的数弹出
        }       
    }
};

解题思路2：

当然这道题也可以使用递归的方法来解决。主要不同的是直接生成一个当前路径数组，然后不断的确定当前位置的数字即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > rslt;
        //保存结果
        vector<int> path(k, 0);
        //保存当前遍历的排列结果
        combine(n, k, rslt, path);
        //调用函数
        return rslt;
    }
private:
    void combine(int n, int k, vector<vector<int> > &rslt, vector<int> &path) {
        if (k == 0) {
            rslt.push_back(path);
            return;
        }
        //从排列的尾部开始确定这个位置需要填入什么数字
        //当达到第0个位置的时候将其保存入结果
        for (int i = n; i >= 1; i--) {
            path[k - 1] = i;
            //确定第k个位置的数，从n到1中挑选
            combine(i - 1, k - 1, rslt, path);
        }
    }
};

发表于 | 分类于

String To Num

题目描述：

给定一个字符串，将其转化为对应的合法的数字。其中字符串可能的输入存在多种情况，需要考虑。如果是非法的转化，返回0；如果是大于2147483647则返回INT_MAX(2147483647)；如果是小于-2147483648则返回INT_MIN(-2147483648).见LeetCode8

解题思路：

题目的整体思路不难，主要利用’9’-‘0’来得到对应位数代表的数字，用上一位的累加和乘以10加上当前位数得到结果。需要考虑的部分有：输入的开头可能是空格，我们需要跳过这些字符；当到达第一位非空格的时候，记录下数字的符号；最后需要考虑的是超过整形数字的范围；我们的做法是用base=INT_MAX/10来作为标记；如果在还没到达最后一位的时候，当前已经大于base，则结果一定溢出，所以返回对应符号的数即可，如果是当前值等于base的情况下，判断当前为是否大于7，如果大于7也是同样的做法。当然好几种情况在返回0的情况可以全部合并，写入注释用于提醒。所以做题之前需要多考虑Corner case。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int myAtoi(string str) {
        int cur = 0;//记录当前遍历的位置
        int base = INT_MAX / 10;//对比大小
        int sign = 1;//记录符号
        int res = 0;//保存结果
        while(str[cur] == ' '){
            cur++;
        }//过滤掉空格
        if (str[cur] == '-' || str[cur] == '+'){
            sign = (str[cur] == '+') ? 1 : -1;
            cur++;
        }//记录符号
        while(cur < str.size() && isdigit(str[cur])){
            if (res > base || (res == base && str[cur] - '0' > 7))
                return sign > 0 ? INT_MAX : INT_MIN;
                //判断是否溢出的情况
            res = res * 10 + str[cur] - '0';
            cur++;
        }
        return res * sign;
        //返回结果
    }
};
        // if (str[cur] == str.size()) return 0;
        //全部是空格的情况
        // if (cur == str.size() || str[cur] < 48 || str[cur] > 57) return 0;
        //如果是非数字的情况
        // while(str[cur] == '0'){
        //     cur++;
        // }
        //字符开头是0的情况

1

发表于 | 分类于

题目描述：Optimal Division In Array(数组中除法的最优切分)

给定一个数组[x1,x2,x3….xn]。我们定义其为连除模式，即x1/x2/x3/x4..xn。在这个序列中我们可以在任意位置中加上括号改变其计算顺序。要求找到其中所有加入括号的结果中最大的那个加入括号的方式，并返回加入括号所形成的字符串。

例子：

[1000,100,10,2],我们可以加入括号形成(1000/100)/(10/2),或者1000/(100/(10/2))等。详细解释可以看 leetcode553

解题思路：

初看这个题目会觉得非常的难，因为需要考虑到所有的情况中最大的那一种；并且需要在不同的位置上加上括号形成字符串。但是其实仔细考虑后我们就会发下：即不管在任意位置上加上括号，x1永远是除数，而x2永远中是被除数中的一个。所以我们就可以写成等价的方式x1/(x2/y)，其中y的方式可以是任意的。通过调整分子分母可以发现：x1/(x2/y) = x1y/(x2).所以最大值的情况在y最大的情况下出现，而y的最大化即为(x3 x4 * x5….)。所以最后的最大结果肯定是：x1/(x2/(x3/x4/x5….xn))，所以我们直接返回这样的结果即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string optimalDivision(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return "";
        if (n == 1) return to_string(nums[0]);
        if (n == 2) return to_string(nums[0]) + "/" + to_string(nums[1]);
        //分别判断数组长度只有0，1，2的情况
        string res;
        res = res + to_string(nums[0]) + "/(" + to_string(nums[1]);
        for (int i = 2; i < nums.size(); i++){
            res = res + "/" + to_string(nums[i]);
        }
        res = res + ")";
        //构造所需要的字符串即可
        return res;
        
    }
};

发表于 | 分类于

Flatten Tree

题目描述：

给定一棵树的头节点，要求将树变成指定的链表形状。具体的描述和例子可以看leetcode网站

解题思路：

最直接的一种思路是将链表中的节点按照一定的顺序放入栈或者队列中，然后按照要求将其重新连接就行。可以从题目中发现是类似树的先序遍历的样纸，所以在将树中节点放入队列的时候可以根据这个规律来实现。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        queue<TreeNode*> q;
        preOrder(root, q);
        //此时队列中保存着树的先序遍历结果
        if (root){
            q.pop();
        }
        //队列的第一个节点肯定是原来的根节点
        while(!q.empty()){
            root->right = q.front();
            //将树的右节点指向现在队列的头结点
            root->left = NULL;
            //改变左侧节点指针
            root = root->right;
            //改变当前的root节点便于继续改变下一个节点的指针
            q.pop();
            //出队
        }
        
    }
    void preOrder(TreeNode* root, queue<TreeNode*> &q){
        if (!root) return;
        q.push(root);
        preOrder(root->left, q);
        preOrder(root->right, q);
        //根据先序遍历的方法将树中的节点放入队列中
    }
};

解题思路2：

当然对于树的题目我们依旧可以使用递归的想法来实现。我们的想法是利用一个指针pre来保存不断移动的当前的位置，然后不断的改变指针的指向即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
private:
TreeNode* pre;
    void help(TreeNode* root){
        if (!root) return;
        TreeNode* left = NULL;
        TreeNode* right = NULL;
        if (root->left)
            left = root->left;
            //保存左子树
        if (root->right)
            right = root->right;
            //保存右子树
        pre->right = root;
        pre = pre->right;
        //移动pre到下一个位置
        root->left = NULL;
        //当前的子树的左指针设定为空
        help(left);
        //先遍历左边的子树
        help(right);
        //再遍历右边的子树
    }
    public:
    void flatten(TreeNode* root) {
        pre = new TreeNode(-1);
        help(root);
    }
};

解题思路3

在可以利用递归的方法的情况下，我们也可以利用非递归的思路来解决这个问题。解决的思路比较难描述，可以画一棵简单树按照代码中的思路就可以知道解法。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    void flatten(TreeNode* root) {
        while(root){
            if (root->left && root->right){
            //如果左右子树都非空的情况
                TreeNode* l = root->left;
                //记录当前的左子树
                while(l->right){
                    l = l->right;
                }
                //找到左子树的最右节点
                l->right = root->right;
                //将左子树的最右节点指向root的右节点
            }
            if (root->left)
                root->right = root->left;
                //如果当前的root的左子树不为空，将右子树改变为现在的左子树
            root->left = NULL;
            //当前root的左子树设定为空
            root = root->right;
            //移动root节点到当前的右节点
            
        }
    }
};