k-NearestNeighbor

KNN 近邻算法的初次实现和做法

KNN 概述

k-近邻（kNN, k-NearestNeighbor）算法是一种基本分类与回归方法，我们这里只讨论分类问题中的 k-近邻算法。

一句话总结: 近朱者赤近墨者黑！

k 近邻算法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。 k 值的选择、距离度量以及分类决策规则是 k 近邻算法的三个基本要素。

KNN 场景

电影可以按照题材分类，那么如何区分 动作片 和 爱情片 呢？

  1. 动作片: 打斗次数更多
  2. 爱情片: 亲吻次数更多

基于电影中的亲吻、打斗出现的次数，使用 k-近邻算法构造程序，就可以自动划分电影的题材类型。

KNN 原理

KNN 工作原理
  1. 假设有一个带有标签的样本数据集（训练样本集），其中包含每条数据与所属分类的对应关系。
  2. 输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较。
    1. 计算新数据与样本数据集中每条数据的距离。
    2. 对求得的所有距离进行排序（从小到大，越小表示越相似）。
    3. 取前 k （k 一般小于等于 20 ）个样本数据对应的分类标签。
  3. 求 k 个数据中出现次数最多的分类标签作为新数据的分类。
KNN 通俗理解

给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的 k 个实例，这 k 个实例的多数属于某个类，就把该输入实例分为这个类。

KNN 算法的特点
1
2
3
优点: 精度高、对异常值不敏感、无数据输入假定
缺点: 计算复杂度高、空间复杂度高
适用数据范围: 数值型和标称型
more >>

展开全文 >>

归一化

什么是归一化？

以实际例子来说，在国家贸易中，各个国家的货币价值不一样，当 A 国想买 10 吨煤的时候，我们一般是先将钱转化为美元，再用美元去买 10 吨煤，这样中间就有了一个标准

归一化有什么用？

归一化在处理数学问题和权重问题的时候具有实用的意义，比如说大学生自习室安排问题中，宿舍距各教室路线长短，教室大小，照明质量，满座率等都是影响结果的因素，这些因素本身有一个相对值，但没有一个统一的标准去衡量他们，于是出现了归一化。使每个大因素和小变量之间都有了一个桥梁，合理的去参与到对决策的影响中。

展开全文 >>

排序算法

三种排序[选择，归并，冒泡]

选择排序

优点：处理小数据的时候很快，时间复杂度(O^2)

选择排序就跟扑克牌一样，从牌堆里面选择一张牌插入到牌中，依次选择手中的牌，把相对较小的插入到其中

1
2
3
4
5
6
7
8
9
10
11
void insertionSort(int arr[]){
    for(int i = 0 ; i < 6 ; i ++){
        int key = arr[i];
        int j = i - 1;
        while(j >= 0 && arr[j] > key){
            arr[j + 1] = arr[j];
            j --;
        }
        arr[j + 1] = key;
    }
}

快速排序

时间复杂度为 O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

归并排序

**时间复杂度 O(n log n) **

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void mergeSort(int arr[], int l, int r)
{
    if (l >= r)
        return;
    int mid = (l + r) / 2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    int tmp[r - l + 1];
    while (i <= mid && j <= r)
    {
        if (arr[i] < arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }
    while (i <= mid)
        tmp[k++] = arr[i++];
    while (j <= r)
        tmp[k++] = arr[j++];

    for (i = l, j = 0; i <= r; i++, j++)
        arr[i] = tmp[j];
}

快速排序和快速排序都是分治思想

展开全文 >>

哈希表

近似 O(1)的时间复杂度

哈希表一般算法中处理的问题

  1. 插入一个数
  2. 查找一个数
  3. 删除一个数

实现哈希表的两种做法

拉链法

首先选择拉链法来解决问题，拉链法用通俗的话来说，就是数组+单链表的实现
选择 hash 函数 将大整数 x 映射成为小整数的

840. 模拟散列表

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
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100002;

int e[N],ne[N],idx;
int h[N];

void insert(int x){
    int y = (x % N + N) % N; //为了缩小y 同时也避免负数的存在
    e[idx] = x; //在每一个数组下面拉出一条链 insert等同于单链表的操作
    ne[idx] = h[y];
    h[y] = idx++;
}

bool find(int x){
    int y = (x % N + N ) % N;
    for(int i = h[y] ; i != -1 ; i = ne[i])
        if(e[i] == x)
            return true;
    return false;
}

int main(){
    int n;
    cin >> n;
    memset(h,-1,sizeof h);
    while(n --){
        char op;
        int k;
        cin >> op >> k;
        if(op == 'I')insert(k);
        else{
            if(find(k))puts("Yes");
            else puts("No");
        }
    }
    return 0;
}
more >>

展开全文 >>

堆排序

堆分为小根堆和大根堆（本质上是一颗完全二叉树）

堆可以干什么？

  • 找到一个集合当中的最小值
  • 删除一个集合当中的最小值
  • 插入一个数

如何调整小根堆或者大根堆？

以小根堆为例子

  • down -> 选择这个数和子节点的最小值进行交换
  • up -> 选择这个节点与父节点进行交换

如何存储堆？

下标从 1 开始 保证了数组子节点的可行性

选择用数组的形式来存储 1 2 3 4 5 6 7 8
k 的 子节点为 2k 2k+1

如何手写一个堆

  1. 插入一个数：heap[++size] = x;
  2. 求集合当中的最小元素：heap[1];
  3. 删除最小的元素：heap[1] = heap[size]; size ++; down(1) //将末尾的元素覆盖到头节点，数组删除头节点是很麻烦的一件事
  4. 删除任意一个元素：heap[k] = heap[size]; size ++; down(k); up(k)；
  5. 修改任意一个元素：heap[k] = x;up(x);down(x); 保证 down 和 up 只执行一次 more >>

展开全文 >>

并查集

近似 O(1)的时间复杂度

并查集能解决什么问题？

  • 如何合并两个集合
  • 如何两个元素在不在同一个区间内

并查集原理？

用一棵树来存储整个集合，树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]代表它的父节点

衍生出问题

  1. 如何判断树根？if(p[x] == x)
  2. 如何求 x 的编号？while(p[x] != x) x = p[x]
  3. 如何合并两个集合，x 代表第一个集合，y 代表第二个集合？p[x] = y

如何优化？

每遍历一次，让这个节点直接指向根节点，即可将时间复杂度优化为 O(1);

模版应用

836. 合并集合

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
import java.util.*;
import java.io.*;
public class Main{
    private static int p[] = new int[100010]; //声明父节点;
    public static void main(String [] args) throws IOException {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        for(int i = 1 ; i <= n ; i ++)p[i] = i;
        int m = in.nextInt();
        while(m -- != 0){
            String op = in.next();
            if(op.equals("M")){
                int a = in.nextInt();
                int b = in.nextInt();
                p[find(a)] = find(b);
            }else{
                int a = in.nextInt();
                int b = in.nextInt();
                if(find(a) == find(b))log.write("Yes\n");
                else log.write("No\n");
            }
        }
        log.flush();
        log.close();
    }
    //查找x节点的父亲
    public static int find(int x){
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
}

837. 连通块中点的数量

同时维护当前区间内，有多少个数量

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
import java.util.*;
import java.io.*;
public class Main{
    public static int p[] = new int[100010];
    public static int size[] = new int[100010];

    public static void main(String[] args) throws IOException
    {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        int m = in.nextInt();
        for(int i = 1 ; i <= n ; i ++){
            p[i] = i;
            size[i] = 1;
        }
        while(m -- != 0){
            String op = in.next();
            if(op.equals("C")){

                int a = in.nextInt();
                int b = in.nextInt();
                if(find(a) == find(b)) continue;
                size[find(b)] += size[find(a)];
                p[find(a)] = b;
            }else if(op.equals("Q1")){
                int a = in.nextInt();
                int b = in.nextInt();
                if(find(a) == find(b))log.write("Yes\n");
                else log.write("No\n");
            }else{
                int k = in.nextInt();
                log.write(size[find(k)] + "\n");
            }
        }
        log.flush();
        log.close();

    }
    public static int find(int x){
        if(p[x] != x)p[x] = find(p[x]);
        return p[x];
    }
}

240. 食物链

维护当前集合里面到根节点的距离

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
import java.io.*;
import java.util.*;
public class Main{
    public static int[] p,d; //p存储父节点 d存储距离
    public static void main(String[] args) throws IOException{
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        int m = in.nextInt();
        p = new int[n + 1];
        d = new int[n + 1];
        int ans = 0 ; //表示假话的个数
        for(int i = 1 ; i <= n ; i ++)p[i] = i;
        while(m -- != 0){
            int op = in.nextInt();
            int x = in.nextInt();
            int y = in.nextInt();
            if(x > n || y > n){
                ans += 1;
                continue;
            }
            int px = find(x);
            int py = find(y);
            switch (op) {
                case 1 : {
                    //同一个集合中，表示已确立相互关系
                    if (px == py) {
                        if ((d[x] - d[y])%3 != 0) {
                            ans++;
                            continue;
                        }
                    }
                    //不同集合中，现在建立相互关系
                    else {
                        d[px] = d[y] - d[x];
                        p[px] = py;
                    }
                    break;
                }
                case 2 : {
                    //同一个集合中，表示已确立相互关系
                    if (px == py) {
                        //推导出的关系为 （d[x]-d[y]）%3 == 1 则认为x可以吃y
                        //写成（d[x]-d[y]-1）%3 == 0 可以避免余数是负数的问题
                        //也可以写成（d[x]-d[y]）%3 +3 == 1
                        //==正确 -> != 错误
                        if ((d[x] - d[y] - 1) % 3 != 0) {
                            ans++;
                            continue;
                        }
                    }
                    //不同集合中，现在建立相互关系
                    else {
                        d[px] = d[y] - d[x] + 1;
                        p[px] = py;
                    }
                    break;
                }
                default : System.out.print("--");
            }
        }
        log.write(ans + " ");
        log.flush();
        log.close();
    }
    public static int find(int x){
        if(x != p[x]){
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }
}

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

希望你能喜欢