发表于 | 分类于

Mix Gaussian In EM

算法原理简述：

概率模型有时即含有观测变量，又含有隐变量或者潜在变量。如果概率模型的变量都是观测变量，那么给定数据，可以直接用最大似然估计的方法或者贝叶斯估计法估计参数模型。当含有隐变量时，我们就不能直接使用这些方法，EM方法就是含有隐含变量的概率模型参数的极大似然估计法。
EM算法主要包括了:

  • 得到 Q函数
  • E步计算
  • Q步计算

其中Q函数是完全数据的对数似然函数在给定观测数据和当前参数下，对未观测数据的条件概率分布的期望。

本文中实现的是利用EM算法对高斯混合模型的进行参数估计.

代码如下：

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
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @File  : MixGaussianInEM.py
# @Author: mfzhu
# @Date  : 2017/5/3
# @Desc  :
import numpy as np
import copy
class mixGaussianInEM(object):
    def __init__(self, train_data, num_Gaussian):
        self.epsilon = 0.0000001
        # 设定模型停止迭代的阈值
        self.num = num_Gaussian
        # 设定高斯函数的个数
        self.num_sample = len(train_data)
        # 初始化训练数据个数
        self.sample = train_data
        # 初始化训练数据
        self.mean = np.array([15, 35], float)
        # 初始化高斯函数的均值
        self.var = np.array([15, 35], float)
        # 初始化高斯函数的方差
        self.alpha = np.array([0.4, 0.6], float)
        # 初始化高斯函数的系数
        self.gamma = np.zeros([self.num_sample, self.num], float)
        # 初始化每个观测值在每个高斯函数上的分量
    def norm_pdf(self, miu, sigma, value):
        # 计算某个均值和方差下的value对应的概率值
        return (1 / (np.sqrt(2 * np.pi) * sigma)) * np.exp(-1 * (value - miu) ** 2 / (2 * (sigma ** 2)))
    def E_step(self):
        # E步函数更新gamma矩阵中的各个系数
        for i in range(self.num_sample):
            demon = 0
            for j in range(self.num):
                demon += self.alpha[j] * self.norm_pdf(self.mean[j], np.sqrt(self.var[j]), self.sample[i])
                # 计算某个观测值在所有高斯函数上分量的和
            for j in range(self.num):
                self.gamma[i][j] = self.alpha[j] * self.norm_pdf(self.mean[j], np.sqrt(self.var[j]), self.sample[i]) / demon
                # 计算某个高斯函数的分量
    def Q_step(self):
        #  Q步函数更新均值、方差和系数
        for i in range(self.num):
            # 更新方差
            difference = np.square(self.sample - self.mean[i])
            self.var[i] = np.sum(difference * self.gamma[:, i]) / np.sum(self.gamma[:, i])
        for i in range(self.num):
            # 更新均值
            self.mean[i] = (np.sum(self.gamma[:, i] * self.sample)) / np.sum(self.gamma[:, i])
        for i in range(self.num):
            # 更新系数
            self.alpha[i] = np.sum(self.gamma[:, i]) / self.num_sample
    def train(self):
        time = 0
        # 训练次数
        while time < 1000:
            # print(self.mean, self.var, self.alpha, time)
            old_mean = copy.deepcopy(self.mean)
            old_var = copy.deepcopy(self.var)
            # 记录上一次的均值和方差
            self.E_step()
            self.Q_step()
            # 训练
            if np.sum(np.abs(self.mean - old_mean)) < self.epsilon\
                    or np.sum(np.abs(self.var - old_var)) < self.epsilon:
                break
                # 如果两次结果的差值小于阈值则结束训练
            time += 1
    def output(self):
        # 输出训练结果
        print("the estimation of mean:")
        print(self.mean)
        print("the estimation of var:")
        print(self.var)
        print("the estimation of alpha:")
        print(self.alpha)
if __name__ == '__main__':
    test_data = []
    sigma = [20, 40]
    miu = [20, 40]
    for i in range(10000):
        if np.random.random(1) > 0.5:
            test_data.append(np.random.normal() * sigma[0] + miu[0])
        else:
            test_data.append(np.random.normal() * sigma[1] + miu[1])
    # 初始化训练数据
    test_data = np.array(test_data)
    mix = mixGaussianInEM(test_data, 2)
    mix.train()
    mix.output()

结果说明：

在利用两个高斯分布分别为N(20, 20)和N(40, 40)的情况下，按照概率0.5和0.5分别产生10000个数据。通过EM算法的估计结果如下：
img

可以看到对于参数的估计还是相当准确的。需要注意的是在训练模型的初始值的设定时，偏离与待估计参数太大的情况容易导致估计失败，即EM算法对于初始值敏感，并且不能保证收敛到全局最优。所以我们可以多次选取初始值而后对估计结果取平均来保证参加估计的正确性。

发表于 | 分类于

树专题总结

在leetcode上的树相关的题目中，除掉一些偏题，大部分题目都是有着类似的或者相同的套路。所以在做完树专题的题目的后在这边做一个简单的总结。

树数据结构中常见的问题有以下几类：

  • 树的遍历问题
  • 树的构建问题
  • 树类型判断问题
  • 树的形态变换问题
  • 树的公共祖先问题
  • 树的序列化问题
  • 其他问题

所以以下我就分这些专题问题来总结树常见问题的解法。

树的遍历问题

对于树的遍历问题，作为树中的基础问题，必须熟练掌握。树的遍历常见的有先序遍历，中序遍历，后序遍历。遍历的方式分为递归和非递归的形式。在熟练掌握遍历方式的基础上，对于一些遍历的延伸题也能做到举一反三。以下我以leetcode上题目总结一下关于这些问题的解法。

1.基础三种遍历方式的递归和非递归实现 　　

  • LeetCode144: 要求返回树的先序遍历的结果。

  • LeetCode94: 要求中序遍历一棵二叉树，然后返回遍历结果。

具体的解法和思路可以看我的另外一篇博客。

2.按层遍历的递归和非递归实现及其变型题

  • LeetCode102: 要求按层遍历一棵树，并返回每层的节点。

  • LeetCode103: 按照Z字型遍历一棵树的节点并返回结果。

  • LeetCode116: 树的层指针的实现。

  • LeetCode117: 树的层指针实现。

  • LeetCode107: 自底向上按层遍历树的每一层节点。

  • LeetCode513: 找到树的最左下的那个叶节点。

  • LeetCode199: 从右侧看树的结果。

    以上题目的具体解答可以看我的另外一篇博客

3.树的路径和问题

  • LeetCode112: 找到树中是否存在从根节点到叶节点和为目标值的路径。

  • LeetCode113: 找到树中从根节点到叶节点和为目标值的所有路径结果并返回。

  • LeetCode437: 不要求从根节点开始，找到树中所有和为目标值的路径的总数。

  • LeetCode124: 找到树中的路径，路径可以是由子节点向父节点前进，其路径和为最大。

  • LeetCode129: 树中的每一条从根节点到叶节点的路径代表一个数，要求计算这棵树所有路径代表数的和。

  • LeetCode257: 要求返回树的从根节点到叶节点的路径表示。

  • LeetCode515: 找到树中每条路径上的最大值。

以上的树的路径问题可以看我的另外两篇博客1和博客2

4.其他树的遍历问题

  • LeetCode501: 找到一棵树中出现次数最多的那个数。

  • LeetCode508: 找到树的所有子树和中最经常出现的那个数。

  • LeetCode337: 树的相邻节点代表邻居，要求找到最大的能偷得的财富数。

  • LeetCode230: 找到二叉搜索树的第k小的值。

  • LeetCode104: 找到树的最深高度。

  • LeetCode111: 找到树的最浅深度。

  • LeetCode404: 找到所有的左叶节点的和。

    以上问题的解答可以看我的另外一篇博客

树的构建问题

树的构建问题通常是给定一个特定序列的数组，要求根据数组重建二叉树。其中最为经典的题目就是根据两种遍历的结果重建原始的二叉树问题。另外一个常见的问题是通过根据二叉搜索树的性质，给定排序数组要求重建二叉排序树。

  • LeetCode105: 从先序遍历和中序遍历重建二叉树。

  • LeetCode106: 从中序遍历和后序遍历重建二叉树。

  • LeetCode108: 给定一个排序后的数组，要求根据数组重建二叉搜索树。

  • LeetCode95: 唯一的二叉树的构建。

  • LeetCode96: 唯一的二叉树的个数。

以上的树的构建问题可以看我的另外一篇博客。

树类型判断问题

树的类型判断问题一般是给定一棵树的头结点，要求判断树是否符合某种特征。常见的有判断平衡二叉树，搜索二叉树等。

以上关于树的类型问题的总结可以看我的另外一篇博客

树的形态变换问题

树的形态变化问题较为灵活，通常要根据题目的要求来进行操作。常见的解题思路是递归和回溯的使用。

树的公共祖先问题

树的序列化问题

树的序列化问题可以看的另外一篇博客

树的其他问题

发表于 | 分类于

Other Traversal Problem

题目描述1：

给定一棵搜索二叉树的头结点，要求找到树中出现次数最多的那个数。

例子：

见LeetCode501

解题思路：

最基础的方法是遍历这棵树的所有节点，然后将节点保存到哈希表中，而后从哈希表中找到出现最多的那个数。自然有其他的解法，待补全。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        map<int, int>hash;
        helper(root, hash);
        vector<int> res;
        int most = 1;
        for (auto it = hash.begin(); it != hash.end(); it++){
            if (it->second > most) most = it->second;
        }
        for (auto it = hash.begin(); it != hash.end(); it++){
            if (it->second == most) res.push_back(it->first);
        }
        return res;
        
    }
    void helper(TreeNode* root, map<int,int>& hash){
        if (!root) return;
        helper(root->left, hash);
        hash[root->val]++;
        helper(root->right, hash);
    }
};

题目描述2：

给定一棵树的头结点，然后要求找到所有的子树和中最经常出现的那个数。

例子：

见LeetCode508

解题思路：

主要的思路和上一题类似，用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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        vector<int> vec;
        findSumOfNode(root, vec);
        map<int, int> hash;
        vector<int> res;
        for (int i = 0; i < vec.size(); i++){
            hash[vec[i]]++;
        }
        int most = 1;
        for (auto it = hash.begin(); it != hash.end(); it++){
            if (it->second > most) most = it->second;
        }
        for (auto it = hash.begin(); it != hash.end(); it++){
            if (it->second == most) res.push_back(it->first);
        }
        return res;
    }
    int findSumOfNode(TreeNode* node, vector<int>& vec){
        if (!node) return 0;
        if (!node->left && !node->right){
            vec.push_back(node->val);
            return node->val;
        }
        int left = findSumOfNode(node->left, vec);
        int right = findSumOfNode(node->right, vec);
        int res = left + right + node->val;
        vec.push_back(res);
        return res;
    }
};

题目描述3：

给定一棵搜索二叉树的头结点，要求找到树中的第k小的的值。

例子：

见LeetCode230

解题思路：

因为是搜索二叉树，所以我们可以中序遍历整个树，然后返回第k个数即可。

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
//树中的k小数
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        vector<int> vec;
        inOrder(root, vec);
        return vec[k - 1];
        
    }
    void inOrder(TreeNode* head, vector<int>& vec){
        if (head == NULL) return;
        inOrder(head->left, vec);
        vec.push_back(head->val);
        inOrder(head->right, vec);
    }
};

题目描述4：

给定一棵树的头结点，要求找到树的最小深度。

例子：

见LeetCode111

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        if (!root->left && !root->right) return 1;
        if (!root->left) return min(root->right) + 1;
        if (!root->right) return min(root->left) + 1;
        return min(root);
        
    }
    int min(TreeNode* root) {
        if (!root->left && !root->right) return 1;
        int left = (root->left) ? (min(root->left) + 1) : INT_MAX; 
        int right = (root->right) ? (min(root->right) + 1): INT_MAX;
        return left > right ?  right : left;
        
    }
    
};

题目描述4：

给定一棵树的头结点，要求找到树的最大深度。

例子：

见LeetCode104

代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include<queue>
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL)
            return 0;
        int res = 0;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            res++;
            for (int i = 0, n = q.size(); i < n; i++){
                TreeNode* p = q.front();
                q.pop();
                if (p->left != NULL)
                    q.push(p->left);
                if (p->right != NULL)
                    q.push(p->right);
            }
        }
        return res;
    }
};

题目描述5：

给定一棵树的头结点，要求找到所有左叶节点的和。

例子：

见LeetCode404

代码如下：

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
//左侧子树的叶节点的和
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int res = 0;
        preOrder(root, res);
        return res;
        
    }
    void preOrder(TreeNode* head, int& res){
        if (head == NULL)
            return;
        
        if (head->left != NULL && head->left->left == NULL && head->left->right == NULL){
            res = res + head->left->val;
            preOrder(head->right, res);
        }else{
            preOrder(head->left, res);
            preOrder(head->right, res);
        }
    }
};
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int res = 0;
        helper(root, res);
        return res;
    }
    void helper(TreeNode* root, int& left){
        if (!root) return;
        
        if (root->left && (!root->left->left && !root->left->right)){
            left += root->left->val;
            helper(root->right, left);
        }else{
            helper(root->left, left);
            helper(root->right, left);
        }
    }
};

题目描述6：

见LeetCode337

代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        if (!root) return 0;
        int rootValue = root->val;
        int left = 0;
        int right = 0;
        if (root->left){
            int l1 = rob(root->left->left);
            int l2 = rob(root->left->right);
            rootValue += l1 + l2;
            left = rob(root->left);
        }
        if (root->right){
            int r1 = rob(root->right->left);
            int r2 = rob(root->right->right);
            rootValue += r1 + r2;
            right = rob(root->right);
        }
        if (rootValue < (left + right))
            return left + right;
        return rootValue;
    }
};

发表于 | 分类于

LCA In Tree

题目描述：

给定一棵树和树中的两个节点，要求返回这两个节点的最近公共祖先节点.

例子：

leetcode上有两道题目是关于公共祖先问题的，具体描述可以看LeetCode235和LeetCode236

解题思路：

主要的思路是这样的：我们遍历当前节点为cur，如果cur为空，或者cur是等于目标结点之一的情况下，我们就直接返回这个节点即可；如果不是的情况下，我们继续下一层的遍历，记left是左侧返回的结果，right是右侧的返回的结果；如果左侧和右侧均不为空，则说明在当前节点的情况下，左侧或者右侧找到了两个目标节点，则当前节点即为最近的公共祖先；如果其中一个为空的情况下；说明某侧找到了其中的一个节点或者当前的cur即为公共祖先且为目标节点中的一个。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL || root == q || root == p)
            return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        if (left != NULL && right != NULL)
            return root;
        
        return left != NULL ? left : right;
        
    }
};

解法2

当然在需要多次查询公共祖先的情况下，我们可以采用另外一种方法来查找树的公共祖先。首先我们构造一个哈希表，表中的key是某个节点，value是其父节点。当要查询a1和a2的公共祖先的时候，先从表中查询到从a1到根节点上的所有节点构成父节点集合，然后我们开始从a2查找是否在该集合中，存在即为祖先节点，不存在则继续向上查找。

代码如下：

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 {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        map<TreeNode*, TreeNode*> hash;
        hash[root] = NULL;
        helper(root, hash);
        set<TreeNode*> ancestor;
        ancestor.insert(p);
        TreeNode* cur = p;
        while(cur != NULL){
            ancestor.insert(hash[cur]);
            cur = hash[cur];
        }
        cur = q;
        while(ancestor.find(cur) == ancestor.end()){
            cur = hash[cur];
        }
        return cur;
        
    }
    void helper(TreeNode* root, map<TreeNode*, TreeNode*>& hash){
        if (!root) return;
        if (root->left)
            hash[root->left] = root;
        if (root->right)
            hash[root->right] = root;
        helper(root->left, hash);
        helper(root->right, hash);
    }
};

发表于 | 分类于

Adaboost In MNIST

adaboost模型简介

boosting(提升)方法是一种常用的统计学习方法。在分类问题中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。本文中所介绍的adaboost就是在boost中具有代表性的方法。
我们学习分类器的基本思想是：因为相对于强分类器，弱分类器更加容易发现；所以我们通过学习一系列的弱分类器，通过对弱分类器的线性组合构成一个强分类器。其实就是”三个臭皮匠顶个诸葛亮”的基本思想。

其中adaboost方法中的特点有：

  • 我们通过上一轮学习到的弱分类器来对下一轮的数据集权重进行改变。当前学习的分类器的误分类误差率越大的其分类器权重越高，反之则不然。
  • 在通过当前分类器更改数据集的权重的时候，误分类的数据样本权重增大，正确分类的样本权重降低。

代码如下：

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
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @File  : adaBoost.py
# @Author: mfzhu
# @Date  : 2017/4/29
# @Desc  :
import numpy as np
import math
import time
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
def binary(data, threshold):
    # 二值化函数
    index_1 = np.array(data > threshold)
    index_2 = np.array(data <= threshold)
    data[index_1] = 1
    data[index_2] = 0
    return data
class sign(object):
    # 阈值函数类
    def __init__(self, sample, label, weight):
        """
        :param sample: 输入一个样本找到最优的切分位置，样本为全体数据的某一列
        :param label:  这一列样本数据所对应的标签
        :param weight: 需要输入初始的权重来确定分类函数
        """
        self.sample = sample
        # 初始样本
        self.label = label
        # 初始标签
        self.weight = weight
        # 初始权重
        self.segment_value = -1
        # 分类函数的切分值
        self.less_index = [0, 1, 2]
        # 小于函数的切分位置集合
        self.more_index = [0, 1, 2]
        # 大于函数的切分位置集合
        self.is_less = False
        self.is_more = False
        # 标签用于表示是大于函数还是小于函数
    def train_less_than(self):
        # 训练小于函数
        less_seg_value = -1
        # 小于函数的切分值
        error_score = 100000
        # 初始化分类误差率
        for seg_value in self.less_index:
            # 遍历每个切分值找到最优的
            score = 0.0
            # 对于每个切分值保存分类误差率
            for index in range(len(self.sample)):
                val = -1
                if self.sample[index] < seg_value:
                    val = 1
                if val * self.label[index] < 0:
                    score += self.weight[index]
            if score < error_score:
                less_seg_value = seg_value
                error_score = score
                # 如果比当前的分类误差要小，更新切分值和分类误差率
        return less_seg_value, error_score
    def train_more_than(self):
        # 训练大于函数
        more_seg_value = -1
        # 大于函数的初始切分值
        error_score = 100000
        # 初始误差分类率
        for seg_value in self.more_index:
            # 对于每个切分值找到最优的切分
            score = 0.0
            # 保存每个切分的误差分类率
            for index in range(len(self.sample)):
                val = 1
                if self.sample[index] < seg_value:
                    val = -1
                if val * self.label[index] < 0:
                    score += self.weight[index]
            if score < error_score:
                more_seg_value = seg_value
                error_score = score
                # 保存最优的切分值和误差分类率
        return more_seg_value, error_score
    def train(self):
        less_seg, less_score = self.train_less_than()
        more_seg, more_score = self.train_more_than()
        # 分别训练大于和小于函数
        if less_score < more_score:
            self.is_less = True
            self.segment_value = less_seg
            return less_score
        else:
            self.is_more = True
            self.segment_value = more_seg
            return more_score
        # 选择误差分类率小的那个函数，并且标注分类函数是大于还是小于
    def predict(self, feature):
        if self.is_less:
            if feature < self.segment_value:
                return 1
            else:
                return -1
        # 确定用小于分类函数
        else:
            if feature < self.segment_value:
                return -1
            else:
                return 1
        # 确定用大于分类函数
class adaBoost(object):
    # adaboost类
    def __init__(self):
        pass
    def __init_parameter_(self, train_data, label_data):
        self.train_data = train_data
        self.label_data = label_data
        # 初始化训练数据和训练标签
        self.sample_num = len(train_data)
        # 训练数据的数量
        self.dimension = len(train_data[0])
        # 每个训练数据的维度
        self.weight = [1.0 / self.sample_num] * self.sample_num
        # 初始化权重向量
        self.num_classifier = 50
        # 使用50个弱分类函数
        self.alpha = []
        # 记录每个分类函数的系数
        self.classifier = []
        # 保存每个分类器，其中包括了分类器和对应的分类对应的维度
    def normalization_z(self, classifier, index):
        """
        :param classifier: 当前分类函数
        :param index: 分类函数所切分的位置
        :return: 规范化因子
        """
        # 计算规范化因子
        zm = 0
        for i in range(self.sample_num):
            zm += self.weight[i] * math.exp(
                -1 * self.alpha[-1] * self.label_data[i] * classifier.predict(self.train_data[i][index]))
        # 对于训练数据中的每个样本，计算其是否被误分类计算得到规范化因子
        return zm
    def updata_weight(self, classifier, index, zm):
        # 更新权重
        for i in range(len(self.weight)):
            self.weight[i] = (self.weight[i] * math.exp(
                -1 * self.alpha[-1] * self.label_data[i] * classifier.predict(self.train_data[i][index]))) / zm
        # 遍历权重向量的每个位置，然后根据分类器和切分位置更新权重
    def train(self, train_data, label_data):
        self.__init_parameter_(train_data, label_data)
        # 初始各项数据
        for num in range(self.num_classifier):
            # 训练10个分类函数
            print("the " + str(num) + "weak classifier")
            best_classifier = (None, None, 100000)
            # 初始化一个空的分类函数
            for index in range(self.dimension):
                # 对于每一个维度都进行训练一个分类器
                classifier = sign(self.train_data[:, index], self.label_data, self.weight)
                score = classifier.train()
                if score < best_classifier[2]:
                    best_classifier = (classifier, index, score)
            # 保存下所有维度中分类误差率最小的那个
            em = best_classifier[2]
            if em == 0:
                self.alpha.append(100)
            else:
                self.alpha.append(0.5 * math.log((1 - em) / em))
            self.classifier.append([best_classifier[0], best_classifier[1]])
            # 保存分类器和切分位置
            zm = self.normalization_z(best_classifier[0], best_classifier[1])
            # 计算规范化因子
            self.updata_weight(best_classifier[0], best_classifier[1], zm)
            # 更新权重向量
    def _predict_(self, feature):
        # 预测单个样本的便签
        result = 0.0
        for i in range(self.num_classifier):
            # 取出一个一个的分类器
            classifier = self.classifier[i][0]
            # 取出切分位置
            index = self.classifier[i][1]
            # 计算所有分类器的和
            result += self.alpha[i] * classifier.predict(feature[index])
        if result > 0:
            return 1
        else:
            return -1
    def predict(self, features):
        # 计算所有样本的预测
        results = []
        for i in range(len(features)):
            results.append(self._predict_(features[i]))
        return results
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, 80)
    label[label != 1] = -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:")
    ada = adaBoost()
    ada.train(train_data, train_label)
    time3 = time.time()
    print("training cost: ", time3 - time2, " seconds", '\n')
    # 训练模型并打印训练模型所用时间
    print("start predicting:")
    result = ada.predict(test_data)
    time4 = time.time()
    print("predict cost: ", time4 - time3, " seconds", '\n')
    # 预测测试数据的标签
    score = accuracy_score(result, test_label)
    print("the accuracy is: ", score)
    # 打印正确率

预测结果：

在设定弱分类器个数为50个的情况下，adaboost模型在mnist上的表现还是不错的：

img

发表于 | 分类于

Count Node In CBT

题目描述：

给定一棵完全二叉树，要求返回这棵树中的节点的个数。

例子：

见LeetCode222.

解题思路：

如果按照普通遍历的方式，会TLE；所以我们在找某个节点的左右子树的个数的时候，先判断其左右节点的深度，如果一样，说明当前节点一棵完全二叉子树，直接可以得到节点数量；否则则继续递归调用计算节点个数。

代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int getleft(TreeNode* root){
        int res = 0;
        while(root){
            root = root->left;
            res++;
        }
        return res;
        //左侧深度
    }
    int getright(TreeNode* root){
        int res = 0;
        while(root){
            root = root->right;
            res++;
        }
        return res;
        //右侧深度
    }
    int countNodes(TreeNode* root) {
        if (!root) return 0;
        int l = getleft(root);
        int r = getright(root);
        
        if (l == r) {
            return pow(2, l) - 1;
        }
        else{
            return countNodes(root->left) + countNodes(root->right) + 1;
        }
    }
};

发表于 | 分类于

Delete Node In Tree

题目描述：

给定一棵树的头结点，要求删除树中的某个节点。

例子：

见LeetCode450.

解题思路：

递归调用；首先如果是空节点直接返回；如果当前节点是目标节点，且右子树为空的情况下，我们返回左子树节点；如果右子树不为空，我们找到右子树的最小值，即最左侧节点，将其与当前节点交换后再继续递归。

代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return nullptr;
        if (root->val == key){
            if (!root->right){
                TreeNode* left = root->left;
                delete root;
                return left;
            }else{
                TreeNode* right = root->right;
                while(right->left){
                    right = right->left;
                }
                swap(root->val, right->val);
            }
        }
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return root;
    }
};

发表于 | 分类于

Invert Tree

题目描述：

给定一棵树的头结点，要求对树中的节点进行操作，即将左节点变为右节点；右节点变为左节点。

例子：

见LeetCode226.

解题思路：

主要的思路还是递归的想法：我们不断遍历树的节点，碰到空节点和叶节点返回；不然交换其左右节点，然后递归在左右子树上调用该函数。

代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        invert(root);
        return root;
    }
    void invert(TreeNode* &node){
        if (!node) return;
        if (!node->left && !node->right) return;
        TreeNode* tmp = node->left;
        node->left = node->right;
        node->right = tmp;
        //改变左右子树
        invert(node->left);
        invert(node->right);
        //递归调用
    }
};

发表于 | 分类于

UndirectedWeightedGraph

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
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
//
// Created by mfzhu on 2017/4/19.
//
#ifndef ALGORITHM_DIJKSTRA_H
#define ALGORITHM_DIJKSTRA_H
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
class Edge;
struct CmpByValue{
  bool operator()(const pair<pair<int, int>, int>& lhs, const pair<pair<int,int>, int>& rhs) {
    return lhs.second < rhs.second;
  }
};
class undirectedGraphNode{
public:
    int label;
    vector<Edge*> neighbors;
    undirectedGraphNode(int l): label(l) {};
};
class Edge{
public:
    int weight;
    undirectedGraphNode* start;
    undirectedGraphNode* end;
    Edge(undirectedGraphNode* s, undirectedGraphNode* e, int w): weight(w), start(s), end(e){};
};
class undirectedWeightedGraph{
public:
    undirectedWeightedGraph();
    ~undirectedWeightedGraph(){};
    void prime();
    void kruskal();
    void insertEdge(int start, int end, int weight);
    void insertNode(int val);
    void print();
private:
    int nNode;
    int nEdge;
    map<int, undirectedGraphNode*> nodeTable;
    void insertNode(map<int, undirectedGraphNode*> &nodeTable, int val);
    void insertEdge(map<int, undirectedGraphNode*> &nodeTable, int start, int end, int val);
    void kruskal(map<int, undirectedGraphNode*> nodeTable);
    void prime(map<int, undirectedGraphNode*> nodeTable);
};
undirectedWeightedGraph::undirectedWeightedGraph() {
    cout << "please input the number of vertex:" << endl;
    cin >> nNode;
    cout << "please input the number of edge:" << endl;
    cin >> nEdge;
    for (int i = 0; i < nNode; i++){
        cout << "please input the label of vertex:" << endl;
        int label;
        cin >> label;
        undirectedGraphNode* node = new undirectedGraphNode(label);
        nodeTable.insert({label, node});
    }
    for (int i = 0; i < nEdge; i++){
        cout << "please input the info of Edge:" << endl;
        int start;
        int end;
        int weight;
        cin >> start >> end >> weight;
        Edge* edge1 = new Edge(nodeTable[start], nodeTable[end], weight);
        nodeTable[start]->neighbors.push_back(edge1);
        Edge* edge2 = new Edge(nodeTable[end], nodeTable[start], weight);
        nodeTable[end]->neighbors.push_back(edge2);
    }
}
void undirectedWeightedGraph::print() {
    auto it = nodeTable.begin();
    while(it != nodeTable.end()){
        cout << "the node label is :" << it->first << endl;
        cout << "the node info is:" << endl;
        for (auto i : it->second->neighbors){
            cout << i->start->label << "->" << i->end->label << "  weight:" << i->weight << endl;
        }
        it++;
    }
}
void undirectedWeightedGraph::insertNode(map<int, undirectedGraphNode *> &nodeTable, int val) {
    if (nodeTable.find(val) == nodeTable.end()){
        undirectedGraphNode* node = new undirectedGraphNode(val);
        nodeTable.insert({val, node});
    }else{
        cout << "the node is existed" << endl;
    }
}
void undirectedWeightedGraph::insertNode(int node) {
    insertNode(nodeTable, node);
}
void undirectedWeightedGraph::insertEdge(map<int, undirectedGraphNode *> &nodeTable, int start, int end, int w) {
    Edge* e = new Edge(nodeTable[start], nodeTable[end], w);
    nodeTable[start]->neighbors.push_back(e);
}
void undirectedWeightedGraph::insertEdge(int start, int end, int weight) {
    insertEdge(nodeTable, start, end, weight);
}
void undirectedWeightedGraph::kruskal(map<int, undirectedGraphNode*> nodeTable) {
    int union_array[nNode + 1];
    for (int i = 1; i < nNode + 1; i++){
        union_array[i] = i;
    }
    map<pair<int, int>, int> result;
    map<pair<int, int>, int> Edge_map;
    for(auto it = nodeTable.begin(); it != nodeTable.end(); it++){
        for (auto edge: it->second->neighbors){
            pair<int, int> forward{edge->start->label, edge->end->label};
            pair<int, int> backward{edge->end->label, edge->start->label};
            if (Edge_map.find(forward) == Edge_map.end() && Edge_map.find(backward) == Edge_map.end()){
                Edge_map.insert({forward, edge->weight});
            }
        }
    }
    vector<pair<pair<int, int>, int>> Edge_vec(Edge_map.begin(), Edge_map.end());
    sort(Edge_vec.begin(), Edge_vec.end(), CmpByValue());
    for (auto it = Edge_vec.begin(); result.size() != nNode - 1; it++){
        int start = it->first.first;
        int end = it->first.second;
        int weight = it->second;
        if (union_array[start] == union_array[end]){
            continue;
        }else{
            result.insert({{start, end}, weight});
            int head = union_array[start];
            int tail = union_array[end];
            for (int i = 1; i < nNode + 1; i++){
                if (union_array[i] == head || union_array[i] == tail){
                    union_array[i] = head;
                }
            }
        }
    }
    for (auto it = result.begin(); it != result.end(); it++){
        cout << it->first.first << "->" << it->first.second << ": " << it->second << endl;
    }
}
void undirectedWeightedGraph::kruskal() {
    kruskal(nodeTable);
}
void undirectedWeightedGraph::prime(map<int, undirectedGraphNode *> nodeTable) {
    map<pair<int, int>, int> result;
    map<pair<int, int>, int> Edge_set;
    for (auto it = nodeTable.begin(); it != nodeTable.end(); it++){
        for (auto edge : it->second->neighbors){
            Edge_set.insert({{edge->start->label, edge->end->label}, edge->weight});
        }
    }
    auto index = nodeTable.begin();
    set<int> visited{index->first};
    set<int> unvisited;
    while(++index != nodeTable.end()){
        unvisited.insert(index->first);
    }
    int cur_min_distance = INT8_MAX;
    int v_node = 0;
    int u_node = 0;
    while(!unvisited.empty()){
        for (auto i = visited.begin(); i != visited.end(); i++){
            for (auto j = unvisited.begin(); j != unvisited.end(); j++){
                pair<int, int> tmp{*i,*j};
                if (Edge_set.find(tmp) != Edge_set.end() && Edge_set[tmp] < cur_min_distance){
                    cur_min_distance = Edge_set[tmp];
                    v_node = *i;
                    u_node = *j;
                }
            }
        }
        result.insert({{v_node, u_node}, cur_min_distance});
        cur_min_distance = INT8_MAX;
        visited.insert(u_node);
        unvisited.erase(u_node);
    }
    for (auto iter = result.begin(); iter != result.end(); iter++){
        cout << iter->first.first << "->" << iter->first.second << ": " << iter->second << endl;
    }
}
void undirectedWeightedGraph::prime() {
    prime(nodeTable);
}
#endif //ALGORITHM_DIJKSTRA_H

发表于 | 分类于

DirectedWeightedGraph

代码如下：

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
//
// Created by mfzhu on 2017/4/19.
//
#ifndef ALGORITHM_DIJKSTRA_H
#define ALGORITHM_DIJKSTRA_H
#include <iostream>
#include <vector>
#include <map>
using namespace std;
class Edge;
class directedGraphNode{
public:
    int label;
    vector<Edge*> neighbors;
    directedGraphNode(int l): label(l) {};
};
class Edge{
public:
    int weight;
    directedGraphNode* start;
    directedGraphNode* end;
    Edge(directedGraphNode* s, directedGraphNode* e, int w): weight(w), start(s), end(e){};
};
class directedWeightedGraph{
public:
    directedWeightedGraph();
    ~directedWeightedGraph(){};
//    void dfs();
//    void bfs();
//    void prime();
//    void kruskal();
    void dijkstra(int start);
//    void Bellman_Ford();
    void insertEdge(int start, int end, int weight);
    void insertNode(int val);
    void print();
private:
    int nNode;
    int nEdge;
    map<int, directedGraphNode*> nodeTable;
    void insertNode(map<int, directedGraphNode*> &nodeTable, int val);
    void insertEdge(map<int, directedGraphNode*> &nodeTable, int start, int end, int val);
    void dijkstra(map<int, directedGraphNode*> nodeTable, int start);
};
directedWeightedGraph::directedWeightedGraph() {
    cout << "please input the number of vertex:" << endl;
    cin >> nNode;
    cout << "please input the number of edge:" << endl;
    cin >> nEdge;
    for (int i = 0; i < nNode; i++){
        cout << "please input the label of vertex:" << endl;
        int label;
        cin >> label;
        directedGraphNode* node = new directedGraphNode(label);
        nodeTable.insert({label, node});
    }
    for (int i = 0; i < nEdge; i++){
        cout << "please input the info of Edge:" << endl;
        int start;
        int end;
        int weight;
        cin >> start >> end >> weight;
        Edge* edge = new Edge(nodeTable[start], nodeTable[end], weight);
        nodeTable[start]->neighbors.push_back(edge);
    }
}
void directedWeightedGraph::print() {
    auto it = nodeTable.begin();
    while(it != nodeTable.end()){
        cout << "the node label is :" << it->first << endl;
        cout << "the node info is:" << endl;
        for (auto i : it->second->neighbors){
            cout << i->start->label << "->" << i->end->label << "  weight:" << i->weight << endl;
        }
        it++;
    }
}
void directedWeightedGraph::insertNode(map<int, directedGraphNode *> &nodeTable, int val) {
    if (nodeTable.find(val) == nodeTable.end()){
        directedGraphNode* node = new directedGraphNode(val);
        nodeTable.insert({val, node});
    }else{
        cout << "the node is existed" << endl;
    }
}
void directedWeightedGraph::insertNode(int node) {
    insertNode(nodeTable, node);
}
void directedWeightedGraph::insertEdge(map<int, directedGraphNode *> &nodeTable, int start, int end, int w) {
    Edge* e = new Edge(nodeTable[start], nodeTable[end], w);
    nodeTable[start]->neighbors.push_back(e);
}
void directedWeightedGraph::insertEdge(int start, int end, int weight) {
    insertEdge(nodeTable, start, end, weight);
}
void directedWeightedGraph::dijkstra(map<int, directedGraphNode *> nodeTable, int start) {
    map<int, int> visited{{start, 0}};
    map<int, int> unvisted;
    for (auto i : nodeTable){
        if (i.first != start) unvisted.insert({i.first, INT8_MAX});
    }
    for(auto i: nodeTable[start]->neighbors){
        unvisted[i->end->label] = i->weight;
    }
    while(!unvisted.empty()){
        int cur_min_label = unvisted.begin()->first;
        int cur_min_weight = unvisted.begin()->second;
        for (auto it = unvisted.begin(); it != unvisted.end(); it++){
            if (it->second < cur_min_weight){
                cur_min_label = it->first;
                cur_min_weight = it->second;
            }
        }
        visited.insert({cur_min_label, cur_min_weight});
        unvisted.erase(cur_min_label);
        for (auto it = unvisted.begin(); it != unvisted.end(); it++){
            int cur_distance = it->second;
            for (auto edge: nodeTable[it->first]->neighbors){
                if (edge->end->label == cur_min_label && (edge->weight + cur_min_weight) < cur_distance){
                    it->second = edge->weight + cur_min_weight;
                }
            }
        }
    }
    for(auto it = visited.begin(); it != visited.end(); it++){
        cout << start << " " << it->first << ":" << it->second << endl;
    }
}
void directedWeightedGraph::dijkstra(int start) {
    dijkstra(nodeTable, start);
}
#endif //ALGORITHM_DIJKSTRA_H