-
用于文档关键字提取的TFIDF指标
关键字提取问题 在大规模网络文章整合的过程中，我们经常需要对某一篇文章提取关键字。比如对于某一篇关于计算机的文章，我们应该提取出类似于“计算机”、“编程”、“CPU”之类的符合人类认知习惯的关键词，但是这个过程却不是那么容易。现在，我们把问题归结为，在不使用机器学习方法的情况下，给定一个文档集，仅从单词频率等角度对文档集当中的某一篇文档进行考虑，期望能够对于该篇文章，我们能从文章中依次提取出最有代表性的关键词。 我们很容易想到的方法就是统计每个词的词频了，但是对于任何文章而言，出现频率最多的…
-
用LaTeX进行论文排版
都知道写文档论文之类的肯定是用LaTeX比较漂亮，虽然我对用LaTeX写数学公式稍微有点了解，但是还是没有直接用它来排版。下面就整理下用LaTeX写文档的方法。 安装 最常用的LaTeX排版工具是MikTeX。选择好windows版本，下载安装即可。可执行文件是%install_path%/miktex/bin/x64/texworks.exe。 论文模板 这里的格式通常是在网上找模板。。。毕竟自己弄还是挺麻烦的，而且还要考虑中文编码的问题。我找到的模板如下：(用pdfLaTeX+M…
-
路径匹配之单向距离OWD算法
简述 ** OWD(One Way Distance)**算法也是一种描述两个路径之间相似度的方法，最早大概提出于06年左右。最朴素的OWD算法的思路也非常简单，就是把路径之间的距离转化为点到路径的距离再加以处理。这里只对这种算法做简要介绍，至于深层次的理论有空再研究论文。 定义 在定义路径间的距离$D_{owd}$之前，我们先定义点到路径的距离$D_{point}$： 对于点$p$和一个由多个点组成的路径$T$，定义他们之间的距离为$$D_{point}(p,T)=min_{q \i…
-
GeoHash空间索引算法简述
背景 在空间索引类问题当中，一个最普遍而又最重要的问题是：”给定你某个点的坐标，你如何能够在海量的数据点中找到他所在的区域以及最靠近他的点”？ 最常见的应用就像是**POI(Point of Interest)**的查询了，比方说客户在路上突然想吃饭了，那么我就要根据他的位置查询最近的餐馆并根据这个做出推荐。 通常情况下，一提到查找类问题，我们就会想到二分查找或者是B树查找。但是问题在于我们不仅要找到这个点，而且要找到这个点附近的点。因此对于以经纬度来确定的坐标又不好直接进行二分查找。（如…
-
路径匹配之编辑距离ED算法
简述 编辑距离（Edit Distance），又称Levenshtein距离，原本是用来描述指两个字串之间，由一个转成另一个所需的最少编辑操作次数。这里的”编辑操作“是指“插入”、“删除”和“修改”。是由俄罗斯科学家Vladimir Levenshtein在1965年提出的概念。他通常就被用作一种相似度计算函数，尤其在自然语言处理方面。 问题描述 具体的讲，用编辑距离来描述处理路径相似度问题需要解决的是如下的问题，这个问题又叫”Edit Distance on Real sequence…
-
路径匹配之距离归并MD算法简析
简述 距离归并算法（Merge Distance）也是一种计算路径相似度的算法（其实“路径归并”是我自己瞎翻译的，因为没有找到更加官方的中文翻译）。跟DTW，LCSS之类不同，他提出来时间不算长，但是思想也是十分简单的。计算方便理解容易，也是进行路径相似度匹配的不错的思路。 问题描述 MD算法解决的问题是，给定两个序列$(A_1,A_2,A_3,A_4...A_n)$和$(B_1,B_2,B_3,B_4...B_m)$，其中每一个元素可以都可以是一个二维坐标点或者是更高维度的坐标。现在我…
-
路径匹配之最长公共子序列LCSS算法简析
简述 LCSS算法其实就是我们熟悉的LCS算法（Longest Common Subsequence 最长公共子序列），一个非常基础的dp。以前一直以为LCS算法没啥用，完全就是为了应付比赛用的，现在才发现原来LCS算法竟然在路径匹配上也能有很大作用。 问题描述 LCSS算法解决的问题是，给定两个序列$(A_1,A_2,A_3,A_4...A_n)$和$(B_1,B_2,B_3,B_4...B_m)$，其中每一个元素可以都可以是一个二维坐标点或者是更高维度的坐标。现在我们需要分别从序列$…
-
路径匹配之动态时间规整DTW算法简析
简述 DTW算法又叫动态时间规整（ Dynamic Time Warping），是一个比较简单的dp算法。常用于不等长的离散的路径点的匹配问题，在孤立词语音识别、手势识别、数据挖掘和信息检索等领域有着很不错的表现。 问题描述 DTW解决的问题是，给定两个序列$(A_1,A_2,A_3,A_4...A_n)$和$(B_1,B_2,B_3,B_4...B_m)$，其中每一个元素可以都是一个二维坐标点或者是更高维度的坐标。我们现在需要求出一个“距离”，使得他能够表示这两个路径的相似度。 很…
-
用投影法矫正字符旋转
这是段简单的代码，目的是处理旋转验证码的问题，主要思想就是通过将字符以45°到135°的角度投影下来，得到一系列的投影范围，然后得到这当中投影长度最小的一个角度。这个角度我们就可以简单的把他看成是字符的偏转角。然后用这个角度通过仿射变换得到矫正后的字符。 代码 #coding=utf-8 import cv2,os,sys,Image,math import numpy as np from pylab import * %matplotlib inline def getBinary(…
-
机器学习中分类准确率的评估方法
对机器学习的分类结果进行分析是一个很重要的过程，之前一直忽略了这一个过程，一直到使用了Scikit-learn之后才发现有一堆不懂的名词需要学习。下面主要解释下混淆矩阵、准确率、召回率、f1-score等概念。这些概念其实也是模式识别和信息检索里面经常碰到的东西。 混淆矩阵（Confusion Matrix） 混淆矩阵其实很好理解，就是把预测值和实际值写在同一个矩阵里。假设总共需要分为两类，那么混淆矩阵就是2x2的大小。每一行就是每一类的实际值，每一列就代表的是每一类的预测值。具体含义见下…