标签归档：Machine Learning

简单理解KMP算法

1条回复

KMP是非常著名的字符串匹配算法，学生时代看了几遍都没有真正理解。偶然的，今天在微博上看到有人在哔哩哔哩上直播讲解KMP，看完之后觉得没讲到点子上，他只是教你怎么使用，却没有说出为什么要这么做。
网上关于KMP算法的介绍太多了，我就不再写了，可以先看完这几篇文章：
字符串匹配的KMP算法-阮一峰
（原创）详解KMP算法-孤影
KMP算法的Next数组详解-北京小王子
看完之后感觉自己好像是理解了，但是又总感觉没有真正理解。直到某一个瞬间突然灵光乍现，豁然开朗！我们知道，KMP有个重要的概念是要构造查询串的前缀和后缀，然后通过一个next数组来移动指针，以加快匹配效率。
但是为什么要构造前缀和后缀呢？
string_match
如上图所示，当我我们移动到红圈位置时，发现C和D是不一样的，这时候蛮力的做法就是把下面的字符串一个个往右移，但这样做效率并不高。仔细观察一下会发现：C和D之前的最长公共子序列肯定是一样的（也就是上图的ABCDAB），我们定义上面的为X，下面的为Y。现在想象一下：X不动，Y开始向右移动1个长度，那么匹配的就是X的后5位（BCDAB）和Y的前5位（ABCDA）,发现并不匹配。[……]

继续阅读

Machine Learning-聚类(Clustering)(一)-K均值算法

发表评论

之前机器学习系列的所有文章讲得都是监督学习（supervised learning），今天我们来讲一讲无监督学习（unsupervised learning）。本文覆盖Coursera Machine Learning Week 8的内容，将会介绍一个无监督学习算法-K均值聚类算法（K-means Algorithm for clustering）

K-means Algorithm
无监督学习和监督学习最大的不同是他不需要对样本数据集打标签，而是只根据样本数据分析其内在规律而自动进行簇分类。直观意义上的理解：比如我们有这样一堆样本数据，他的分布如下图：
clustering_1
事先我们并没有对样本数据打标签以标识它属于哪个分类，通过聚类算法，我们希望这堆看上去很容易被分开的数据能够自动分类。那么具体怎么做呢？

对于K个分类的聚类算法而言，步骤如下：

  • 1).首先，我们先随机选取K个样本点，我们称之为“簇中心”(cluster centroids)，如下图所示：
    clustering_2
  • 2).对每一个簇中心（1-K），我们找到所有离该中心最近的样本点，并且给它涂上不同的颜色，如下图所示：
    clustering_3

    • [……]

    继续阅读

    Machine Learning-支持向量机（SVM-Support Vector Machines）

    2条回复

    好久没有更新文章了，距离上一篇文章已经快大半个月了。主要是最近这段时间太忙了，在两个项目之间来回切换，再加上好多同事要离职，组里有点动荡。其实在5月5号那天我就一口气提前把整个course都学完了，主要是每个周末都要空出来完成作业好烦（虽然不做作业我也没啥好干的），那还不如一下子全部做完吧。全部学下来感觉最难的两部分内容就是神经网络和支持向量机了，我这里说的难，指的是真正理解这两个算法，知道他们的工作原理，甚至是理解他们背后的数学原理。如果你仅仅为了完成课后的assignment，那这两部分的内容其实也是很easy的。课程中一涉及到算法背后的原理，感觉Andrew Ng讲得不够清楚，他只会告诉你用什么样的公式去计算，但不会告诉你为什么要用这个公式，以及这个公式是怎么来的。当然，我这么说并不是质疑Andrew Ng讲得不好，而是这门课设计的初衷就是为了让更多人的学会机器学习，而不管你有没有数学背景，所以Andrew Ng一直在说don’t worry about the math,don’t worry about the math…哈哈
    本来这篇文章是要写Week6的内容的，但是我[……]

    继续阅读

    Machine Learning-神经网络（Neural Network）

    2条回复

    本文覆盖Coursera Machine Learning Week 4&Week 5的内容。

    什么是神经网络？
    在机器学习和认知科学领域，人工神经网络（Artificial Neural Network，缩写ANN），简称神经网络（英文：Neural Network，缩写NN）或类神经网络，是一种模仿生物神经网络(动物的中枢神经系统，特别是大脑)的结构和功能的数学模型或计算模型，用于对函数进行估计或近似。（摘自：维基百科-人工神经网络）
    神经网络并不是什么新鲜的玩意儿，早在1958年,美国心理学家Frank Rosenblatt就提出了一种具有单层计算单元的神经网络,称为感知器(Perceptron)。这个概念一经提出就被认为有着良好的发展潜能，因为他结构简单，也能解决一些复杂问题。但是感知器有一个天生不可解决的问题：只能解决线性可分问题，连最简单的异或（XOR）模型都无能为力。1969年Marvin Minsky写了一本叫做《Perceptrons》的书，他提出了著名的两个观点：1.单层感知机没用，我们需要多层感知机来解决复杂问题 2.没有有效的训练算法。大意就是这玩意儿[……]

    继续阅读

    Machine Learning-逻辑回归（Logistic Regression）

    2条回复

    本文覆盖Coursera Machine Learning Week 3的内容。

    二元分类问题（Binary Classification Problem）
    所谓的二元分类问题，指的是他的预测输出结果只有两个值 y = {0,1}，比如“预测某封邮件是否为垃圾邮件”就是一个二元分类问题。之所以称之为二元分类是相对于多分类问题（Multi Classfication Problem）而言的，比如识别10个数字就是一个多分类问题（一共有10个类别，分别是0-9）。而二元分类问题的求解是解决多分类问题的基础，具体方法下文会介绍。
    现在如果要你使用一个函数来模拟分类问题，你最先想到的肯定是一个分段函数（或者叫阶跃函数：unit-step function），简单的如下：
    seg_function
    这个函数是非常契合我们对这个问题的直觉的，模型非常简单，大于某个值输出1，否则输出0。看上去很理想，但是这个模型却存在很多问题，比如它不够光滑，不连续，在数学上不容易被处理。那么有没有替代的模型呢？

    逻辑回归（Logistic Regression）
    为了达到和分段函数一样的效果，并且是连续，光滑的，我[……]

    继续阅读