-
【基础方法】Traveling Salesman Problem 问题和解决办法
TSP问题其实之前就学过，但是之前介绍的是递归贪心和动规的方法，这次看论文，看到了2-opt算法和蚁群算法，做一个简单的介绍。 TSP问题简单介绍 TSP（Traveling Salesman Problem），即旅行商问题或货郎担问题。假设有一个商人，需要去$n$个城市进行售卖，要求每个城市去且仅去一次，城市与城市之间的距离为确定值，最后返回出发城市，目标是求得一条最优路线，使得商人所走的路程最短。 这一个NP-hard问题，即在确定多项式时间内无法求解的问题。从图论的角度来看，这…
-
【课程学习】《统计学习方法》之k近邻法
相似度查询有两种方法： 1. 范围查询，给定阈值。 2. k近邻查询，给定查询点和k。 k近邻法是一种基本分类与回归的方法。其基本思想是：一个样本的k个最相近的样本大多属于某一个类，则该样本也属于这个类。因此，k近邻算法不具有显式的学习过程。k值的选择、距离度量和分类决策规则是k近邻方法的三个基本要素。 k近邻算法 k近邻算法流程 输入：训练数据集$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$，其中，$x \in X \subseteq R^n$为实…
-
【课程学习】Machine Learning 第一周和第二周
一直有想看Andrew Ng的机器学习课程，但是拖了很久都没有看完。之前也写过一些相关的博客，但是在博客搬家的时候没有保存下来。 第一周和第二周的内容比较少，作业也是在一起布置的。 WEEK 1 Introduction What is machine learning? 1. 机器学习的定义：为了完成某个目标T，从经验E中学习，同时具有一定的判断标准P。 Supervised Learning 1. 监督学习：部分样本已有正确的结果。 2. 分类： 回归…
-
【课程学习】《统计学习方法》之感知机
感知机（perceptron）是一种二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，通常取$+1$和$-1$两值。感知机学习目的是求出将训练数据进行线性划分的分离超平面。 感知机模型 超平面 对于超平面，我们常用以下的方程来表示： $$\omega\cdot x+b=0$$ 其中，$\omega$是超平面的法向量，这决定超平面的方向，$b$是超平面的截距，决定超平面到原点的距离。 一般来说，超平面维度都大于3。百度百科上解释超平面是$n$维空间到$n-…
-
【基础方法】Gradient Descent（梯度下降）
这段时间不是很忙，也看到Andrew Ng在Coursera上的machine learning开课了，就顺带着看看。第一周和第二周讲的都是比较简单的问题，主要就是介绍了Cost Function以及最小化的几个方法。我这里要说的就是其中的一种：Gradient desxcent（梯度下降）。 梯度下降这个概念对很多人来说都不是很熟悉了，我之前看过关于HOG(方向梯度直方图)的一篇论文，再看梯度下降就有种熟悉感。 梯度下降的思想 在介绍梯度下降之前我们先引入一个Cost functio…
-
【刷题小结】华为2016研发工程师编程题-删数
我原来是没有打算把做过的题写成博客的，因为大部分还是基础题，而且我往往都是暴力求解，不太优雅。但是做了这道数独题对我还是很有启发的，虽然我仍然用的是暴力求解。做过的很多题有些有着很精巧的解法，但是往往随着时间过去也不太记得了。本地的很多cpp文件总是不能同步带走，而且很多做题的网站查看代码也不是很方便，所以就记录一下权当纪念了。 题目描述 有一个数组a[N]顺序存放0~N-1，要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数的原始下标位置。以8个数(N=7)为例:…
-
【基础方法】Harr 小波变换
我在网上了解小波变换的时候，发现它是常用于信号处理的一种方法，但是在论文里也常看到小波变换用于图像处理。小波函数在一定的时间间隔内波形幅度的平均值为0。现在有很多小波函数，Haar小波变换函数是其中最基础的一种，是最简单的正交归一化小波 Harr 简介 我们先看一下Harr相关的函数图形： 由上图可以以得知Harr小波函数是一个支撑域(函数$\psi(t)$不为0的区间)在$[0,1]$内的单个矩形波，公式如下： $$\psi(t)=\begin{equation} \left \{…
-
【基础方法】主成分分析（Principal Component Analysis）
我们在做图像处理的时候，为了避免提取的特征维数太高使得计算速度变慢，可以用下面几种方法降低特征的维数： * 在一开始的时候对图片预处理，降低图片本身的维数。 * 在特征提取的过程中对特征进行处理，降低特征的的维数。（比如对LBP特征进行直方图统计，就有均衡模式的LBP这个方法来降低特征的维数） * 采用一些降维德方法。（比如我们要介绍的PCA） 数学理论 PCA降维的思想方法是找到一个投影矩阵，这个矩阵对应了一个维数更低的空间，样本经过和这个投影矩阵运算，可以变成维数更小的…
-
【课程学习】行列式
讲真我也只是记得这个概念了，计算方法什么的都不太记得了，真是对不起我线性代数的老师。大概也是因为现在都是用的矩阵的运算，行列式接触的比较少吧。不过原来学习过的基础还在，复习起来还是很快的。 行列式的概念 二阶行列式 行列式是一种基本的数学工具，行列式理论是由求解n元线性方程组的实际需要建立、发展起来的。 行列式是有一个数值的，最简单的是二阶行列式，二阶行列式计算有一个很简单的公式： $$ \left|\begin{array}{cccc} a_{11} & a…
-
【基础方法】K近邻分类器
K近邻分类器是机器识别中很常用的一种分类方法，以前在做单样本人脸识别的时候常用的最近邻分类方法就是其中k=1的特殊情况。以前都是用matlab写的代码，最近老师动员大家一起来学python，然后我们就都从K近邻算法开始学习编程了。 K近邻算法 该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。其实也很好理解，就是现在有n个训练样本，分别对应c个类，现在有一个未知的测试样本，要找到这个测试样本的类别。K近…