Z.H.Chen's Blog
0%

发表于 分类于 ， Valine：
2.4k 4 分钟

## 介绍

  图是最有用的数据结构之一。它们可用于对几乎所有事物进行建模——对象关系和网络是最常见的。图像可以表示为网格状的像素图，句子可以表示为单词的图。图表被用于各个领域，从制图到社会心理学，当然它们在计算机科学中也被广泛使用。因此图搜索和遍历起着重要的计算作用。Dijkstra 算法旨在找到 图中节点 之间的最短路径。它是由荷兰计算机科学家 Edsger Wybe Dijkstra 于 1956 年在思考从鹿特丹到格罗宁根的最短路线时设计的。Dijkstra 算法 多年来一直在发生变化，并且存在各种版本和变体。最初用于计算两个节点之间的最短路径。由于它的工作方式 ，适用于计算起始节点和图中每个其他节点之间的最短路径。这种方式可用于生成 最短路径树，该树由两个节点以及所有其他节点之间的最短路径组成。然后你可以修剪掉你不感兴趣的树，得到两个节点之间的最短路径，但你不可避免地必须计算整个树，这是 Dijkstra 算法 的一个缺点，它不适合大型图。

Dijkstra 算法

  Dijkstra 算法 适用于无向、连接、加权图，Dijkstra 算法 可以求出源节点到其他所有节点的最短路径。
  一开始，我们要创建一组已访问顶点，以跟踪所有已分配正确最短路径的顶点。我们还需要设置图中所有顶点的“成本”（通向它的当前最短路径的长度）。开始时所有成本都将设置为 “无穷大(inf)” ，以确保我们可以与之比较的所有其他成本都小于起始成本。唯一的例外是第一个起始顶点的成本——这个顶点的成本为 0，因为它没有通往自身的路径——标记为 源节点 s。然后依据以下三个规则，直到遍历整个图：

  • 每次从未标记的节点中选择距离出发点最近的节点，标记，收录到最优路径集合中。
  • 对于当前节点 n 和其的邻居节点 m 如果 cheapestPath(s, n) + cheapestPath(n, m) < cheapestPath(s, m)，则更新 s 到 m 的最短路径为 cheapestPath(s, n) + cheapestPath(n, m)。
  • 且每次更新最短路径时会保存该节点的前节点。
阅读全文 »

发表于 分类于 ， Valine：
4k 7 分钟

前言

  在机器学习模型中，我们会使用损失函数对模型的输出和标注信息计算他们之间的差异，然后使用损失进行反向传播，在反向传播中，我们的目的是不断地更新参数使得模型损失越来越小直至达到最小，这过程是优化参数的过程，基础的优化算法是使用梯度下降法(如下图)，梯度下降法利用了梯度的反方向是函数下降最快的方向的特性，该过程可以理解成寻找山谷。随后为了提高效率和准确率许多的改进的优化算法被提出，下面我们将介绍几种常用的优化算法。

在这里插入图片描述

1 梯度下降算法

  假设线性回归函数为：$\boldsymbol{h_\theta(x^{(i)}) = \theta _1x^{(i)} + \theta_0}$，代价函数为：$\boldsymbol{J(\theta_0,
\theta_1) = \frac{1}{2m}\sum_{i=1}^{m}(h_\theta(x^{(i)}) - y^{(i)})^2}$，其中 $\boldsymbol{i= 1,2, … ,𝑚}$ 表示样本数，$\boldsymbol{𝑗 = 0,1}$ 表示特征数，这里我们使用偏置项 $\boldsymbol{x_0^{(i)} = 1}$。

阅读全文 »

发表于 分类于 ， Valine：
2.9k 5 分钟

1 定义

  激活函数 (Activation functions) 对于人工神经网络模型去学习、理解非常复杂和非线性的函数来说具有十分重要的作用。它们将非线性特性引入到神经网络中。在下图中，输入的 inputs 通过加权，求和后，还被作用了一个函数，这个函数就是激活函数。引入激活函数是为了增加神经网络模型的非线性。没有激活函数的每层都相当于矩阵相乘。就算你叠加了若干层之后，无非还是个矩阵相乘罢了。
在这里插入图片描述

2 激活函数的必要性

  如果不用激活函数，每一层输出都是上层输入的线性函数，无论神经网络有多少层，输出都是输入的线性组合，这种情况就是最原始的感知机(Perceptron)。这种情况无论有多少层神经网络均可以仅使用输入层和输出层代替，不同的地方就是线性函数的系数不同。激活函数给神经元引入了非线性因素，使得神经网络可以任意逼近任何非线性函数，这样神经网络就可以应用到众多的非线性模型中。

3 常用的激活函数

阅读全文 »

发表于 分类于 ， Valine：
359 1 分钟

二叉树主要有两种遍历方式：

  • 深度优先遍历：先往深走，遇到叶子节点再往回走。
  • 广度优先遍历：一层一层的去遍历，也就是常说的层遍历。

在深度优先遍历中：有三个顺序，前中后序遍历，这中间的”前中后”指的是遍历父节点的先后顺序，且左节点永远在右节点前面遍历。

  • 前序遍历(父左右)：F、B、A、D、C、E、G、I、H。

在这里插入图片描述

阅读全文 »

发表于 分类于 ， Valine：
1.5k 3 分钟

1 原理

KMeans算法概述

  • KMeans算法的作者是MacQueen， KMeans的算法是对数据进行分类的算法，采用的硬分类方式，是属于非监督学习的算法；
  • 对于给定的样本集，按照样本之间的距离大小，将样本划分为K个簇，让簇内的点尽量紧密的连接在一起，而让簇间的距离尽量的大。

KMeans算法流程

  • 1：选择K个点作为初始质心。
  • 2：Repeat
  • 3： 计算邻近度，将每个点指派到最近的质心，形成K个簇；
  • 4： 重新计算每个簇的质心；
  • 5： Until 质心不发生变化或者新的中心和之前的中心之间的距离小于某阈值，或迭代次数超过某阈值，认为聚类已经收敛，终止。
阅读全文 »

发表于 分类于 ， Valine：
1.5k 3 分钟

1 原理

  分水岭分割方法，是一种基于拓扑理论的数学形态学的分割方法，其基本思想是把图像看作是测地学上的拓扑地貌，图像中每一点像素的灰度值表示该点的海拔高度，每一个局部极小值及其影响区域称为集水盆，而集水盆的边界则形成分水岭。分水岭的概念和形成可以通过模拟浸入过程来说明。在每一个局部极小值表面，刺穿一个小孔，然后把整个模型慢慢浸入水中，随着浸入的加深，每一个局部极小值的影响域慢慢向外扩展，在两个集水盆汇合处构筑大坝，即形成分水岭。这种方法也称作泛洪法，对应的还有降雨法。

在这里插入图片描述
  分水岭的计算过程是一个迭代标注过程。分水岭比较经典的计算方法是L. Vincent提出的。在该算法中，分水岭计算分两个步骤，一个是排序过程，一个是淹没过程。首先对每个像素的灰度级进行从低到高排序，然后在从低到高实现淹没过程中，对每一个局部极小值在 $h$ 阶高度的影响域采用先进先出(FIFO)结构进行判断及标注。具体流程如下：

  • 把梯度图像中的像素按照灰度值进行分类，设定一个测地距离阈值(测地线距离(Geodesic Distance)：地球表面两点之间的最短路径的距离)。
  • 找到灰度值最小的像素点，让 $threshold$ 从最小值开始增长，这些点为起始点。
  • 水平面在增长的过程中，会碰到周围的邻域像素，测量这些像素到起始点(灰度值最低点)的测地距离，如果小于设定阈值，则将这些像素淹没，否则在这些像素上设置大坝，这样就对这些邻域像素进行了分类。
  • 随着水平面越来越高，会设置更多更高的大坝，直到灰度值的最大值，所有区域都在分水岭线上相遇，这些大坝就对整个图像像素的进行了分区。
    在这里插入图片描述

2 算法改进

阅读全文 »

发表于 分类于 ， Valine：
589 1 分钟

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

在这里插入图片描述
示例：

1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
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
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "" :
            return []
        #数字字母映射表
        mapping = {
            '2' : 'abc', 
            '3' : 'def', 
            '4' : 'ghi', 
            '5' : 'jkl', 
            '6' : 'mno', 
            '7' : 'pqrs', 
            '8' : 'tuv', 
            '9' : 'wxyz'
        }
        res = []
        res_str = []

        mapping_digits = []
        for i in range(len(digits)) :
            mapping_digits.append(mapping[digits[i]])

        def backtracking(res_str, index) :
            #递归终止条件
            if len(res_str) == len(digits) :
                res.append("".join(res_str))
                return 
            
            for i in range(len(mapping_digits[index])) :
                res_str.append(mapping_digits[index][i])
                #回溯
                backtracking(res_str, index + 1)
                #撤销
                res_str.pop()
        backtracking(res_str, 0)
        return res
阅读全文 »