几个算法

发表于 | 分类于

几个算法

k-means

  1. 什么是k-means算法

    k-means算法是聚类算法中最简单的一种了。聚类属于无监督学习，以往的回归、朴素贝叶斯、SVM等都是有类别标签y的，也就是说样例中已经给出了样例的分类。而聚类的样本中却没有给定y，只有特征x，比如假设宇宙中的星星可以表示成三维空间中的点集（x， y， z）聚类的目的是找到每个样本x潜在的类别y，并将同类别y的样本x放在一起。比如上面的星星，聚类后结果是一个个星团，星团里面的点相互距离比较近，星团间的星星距离就比较远了

    即知道一个整堆数据要划分成几堆，而如何把这些数据分开就是这个算法的工作

  2. （以二维数据为例子），假如我拿到了一堆数据，我需要把这一堆数据分成三堆

    ​ 1571557865262

  3. 然后我在这个平面中随机取三个点（因为需要分成三堆，所以取三个中心点），作为初始的中心点，然后遍历这一堆数据，分别求到三个点的欧式距离d，它离那个中心点的距离最下，它就被划分为那个区域

    1571558111796

    这里给出一个图片更直观形象地看到k-means的作用

    ​ 1571558140421

  4. 接下来就是更新中心点**把刚才划分出3类，每个类里面的点的 x，y，分别求平均值，比如刚才划分为红色的点，X = （x1+x2…+xn）/n , Y = (y1+y2+…yn)/n ,这个就是新的中心点，蓝色，绿色的也一样。
    更新中心，重复步骤2重新划分数据，如下图。

    1571558301897

  5. 接下来就是一直重复2.3步骤，直到中心点不再变化（至此聚类完成）。得到最终的三那个类（当然实际情况中有可能不会这么均匀）

    1571558378441

链式前向星

  1. 什么是链式前向星（来自显卡爷的教学），其是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么链式前向星就构造好了.（以下图为例子）

    1571559033932

  2. 一些全局变量

1
2
3
4
5
6
7
8
9
10
11
private final int max = 100;    
//指向的前一边
private int[] pre = new int[max];
//点
private int[] e = new int[max];
//边权
private int[] val = new int[max];
//每个点的加进去的最后一条边
private int[] h = new int[max];
//总的边数
private int cnt = 0;

  1. 在加入点和边的时候，采取（点，边权，点）的方式表示这两个点之间有联系，不过是单向的，所以如果边是没有方向的，那么就需要正反都要加入一次

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    /**
         * 加边
         *
         * @param u 起始点
         * @param v 终止点
         * @param w 边的权值
         */
        private void add(int u, int v, int w) {
            e[cnt] = v;
            pre[cnt] = h[u];
            val[cnt] = w;
            h[u] = cnt++;
        }

  2. 寻找某个点相连的所有点，只需要一开始找到每个点加进去的相连最后一条边，然后，不断寻找这条边的前一条边直到没有前一条边

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    /**
         * 寻找某个点的相连的点
         * @param point 点
         */
        List<Integer> ask(int point) {
            List<Integer> result = new ArrayList<>();
            for (int i = h[point]; i != -1; i = pre[i]) {
                result.add(i);
            }
            return result;
        }

Dijkstra

  1. 什么是Dijkstra算法

    Dijkstra算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

    类似的算法还有Floyd算法

  2. 算法的思路

    Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合path。初始的时候，点s（源点）的路径权重被赋值为0(dis[s] = 0。对于能够到达的边，则把dis[m]设为相应的权重，同时把所有其他（源点不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
    然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，
    然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。
    然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

  3. 具体的代码

    我在使用了链式前向星来存储图，还需要加上来两个全局变量来计算最短路径

    1
    2
    3
    4
    5
    //到每个点的距离
      private int[] dis = new int[max];
       
      //记录每个点出队列的前一个点
       int []path = new int[max];

    具体的算法实现，我在这里使用了一个优先队列，每循环一次就弹出队列的顶部的点，而path这个数组相对应的点存储的史上一个弹出队列的点

    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
    void dijkstra(int start) {
            //用于记录已经被收录进最短路径的点
            int[] vis = new int[max];
            Arrays.fill(vis, 0);
            Arrays.fill(dis, Integer.MAX_VALUE);
            Bean bean;

            PriorityQueue<Bean> pq = new PriorityQueue<>((Bean, t1) -> Bean.getDis() - t1.getDis());
            dis[start] = 0;
            bean = new Bean(0, start);

            path[start] = -1;
            pq.add(bean);
            while (!pq.isEmpty()) {
                //取出队顶的元素
                Bean tempBean = pq.poll();
                //栈顶的节点
                int x = tempBean.getPoint();

                vis[x] = 1;

                for (int i = h[x]; i != -1; i = pre[i]) {
                    int y = e[i];
                    if (vis[y]==1) {
                        continue;
                    }

                    if (dis[x] + val[i] < dis[y]) {
                        path[y] = x;
                        dis[y] = dis[x] + val[i];
                        bean = new Bean(dis[y], y);
                        pq.add(bean);
                    }
                }
            }
        }