07

迭代法求解线性方程组总结I - 一阶定常迭代法

高斯消去法和LU分解来求解线性方程组属于直接法, 这里我们要介绍如何利用迭代法求解线性方程组. 不妨假设方程系数矩阵的维度为n\times n, 直接法的空间复杂度为\mathcal{O}(n^2), 时间复杂度为\mathcal{O}(n^3). 也就是说, 当问题规模较小, 少于几万个未知量时, 直接法是有效的. 而实际计算中, 比如有限元数值模拟, 我们会经常碰到几十万甚至上百万的未知量, 但矩阵中有大量为0的元素存在. 此时, 直接法由于内存限制, 便不再适用, 于是我们就需要使用迭代法来求解这类问题. 与直接法相比, 迭代法虽然无法得到精确解, 但它可以得到误差容忍范围内的近似解. 通过调整误差容忍值, 我们可以让迭代尽早终止, 从而提高计算效率. 一阶定常格式迭代法 迭代法, 是指通过近似解序列x^{(0)}, x^{(1)}, \cdots, x^{(k)}, \cdots不断逼近准确解x_*. 如果相邻两次近似解满足同样的函数关系, 则称为固定格式迭代法. 在求解

十一 18

R绘制北京地图,并展示一些有趣的空间数据 - III

这篇博文,我们根据大众点评的北京店铺地理坐标和评论数量画一幅北京吃货地图。 相关博文有: http://www.36dsj.com/archives/23824 北京吃货地图数据可视化和分析 店铺坐标以及店铺评论数 我们使用的是2012年在大众点评抓的一次数据: https://drive.google.com/file/d/0B_b42HS1A9CmZld6MkEwQTM1UXM/view?usp=sharing 数据列包括:店铺ID,经度,纬度,点评数 我们可以通过使用以下命令读入数据: > shop_coord < - dget("shop_coord") > names(shop_coord) [1] "ID" "Lat" "Lng" "sum" > summary(shop_coord) ID Lat Lng sum Min. : 507539 Min. :-1.00 Min. : -1.0 Min. : 1.0 1st Qu.:2664595 … Continue reading

十一 14

R绘制北京地图,并展示一些有趣的空间数据 - II

接上一博文,我们来添加一些基于北京地图的空间数据作为case来展示R的可视化效果。 2013-2015年北京地震数据可视化 在国家地震科学数据共享中心,我们可以通过以下参数来获得北京的地震数据: 得到300+条记录,但是还包含了一些河北,天津,内蒙古的地震记录,我们把这些数据放到excel里根据地震地点筛选出70多条北京范围内的地震记录并且对一些字段的内容稍加修改方便之后的使用。我们要使用的地震记录在如下链接中: https://docs.google.com/spreadsheets/d/1w5CfR05q0YsdUAYx5CEThaRGanC-yemauNm3UlW4Wzc/edit#gid=1859473000

十一 13

R绘制北京地图,并展示一些有趣的空间数据 - I

推荐一个很赞的博文链接,本文在使用R绘制地图相关空间数据时很大程度上参照了这篇博文给出的做法: http://cos.name/2014/08/r-maps-for-china/ 中国地图的GIS数据 在进行基于地图的空间数据可视化前,第一步是导入地图,一个非官方的链接是:http://download.csdn.net/download/wangmingjiazaizhon/4864211 下载后解压缩,可以得到很多格式的地图数据文件,其中CHN_adm0.shp, CHN_adm1.shp, CHN_adm2.shp, CHN_adm3.shp是我们接下来要使用的四个文件,他们都是中国地图数据,但是精度不一样,CHN_adm3.shp精度最细,到县市级别。 原博文中给出的官方地图GIS数据连接我没有打开http://nfgis.nsdi.gov.cn

25

Ubuntu下PDF编辑工具使用经验

最近需要帮别人校对文档,没有拿到原始latex文本,所以得在pdf上直接修改。在Windows系统中,adobe是有编辑功能的,可以在pdf上做很多备注和修改,但是ubuntu系统下只能尝试其他方法。 我搜到比较好的一个中文资料是:http://blog.chinaunix.net/uid-25789104-id-3968982.html ,但里面列举的7个常用pdf编辑器,并不都能很好地满足我自己的使用需求。 在实际使用中,我是结合Inkscape和Pdftk来完成pdf修改的!

19

Simhash算法简介

Google在Detecting Near-Duplicates for Web Crawling这篇论文中介绍了如何使用simhash来实现海量网页去重。本质上,simhash也是一种局部敏感哈希(LSH),它将一个文档转换成一个64位的01串(unsigned long long),然后只需要判断他们的特征字的距离是不是小于等于k(根据经验这个k一般取值为3),就可以判断两个文档是否相似。

18

Local-Sensitive Hashing (LSH) 算法简介

Local-Sensitive Hashing (LSH), 即位置敏感哈希,与之前介绍的Hash函数不同的是它具有位置敏感性,也就是相似点经过哈希之后,也能够在一定程度上相似,并且具有一定的概率保证。正因为LSH的这一特征,它被广泛应用于海量高维数据的近似最近邻快速查找,包括网页去重,音乐检索,图像检索等。 用数学语言来描述,LSH定义为满足以下特性的hash函数: If d(x,y)\le d1, then P(h(x)=h(y))\ge p1; If d(x,y)\ge d2, then P(h(x)=h(y))\le p2. 其中d(x,y)是原始空间上x和y的距离,h(\cdot)是hash函数。

18

Introspective Sorting算法简介

我们在学习排序算法时会学到三种很重要的排序算法:快速排序,插入排序和堆排序。 快速排序虽然平均复杂度为\mathcal{O}(N\text{log}N) ,却可能由于不当的pivot选择,导致其在最坏情况下复杂度为\mathcal{O}(N^2),而堆排序在最坏情况下的复杂度也是\mathcal{O}(N\text{log}N)。由于快速排序和堆排序一般是用递归实现,在函数调用时会产生一些额外的开销,比如返回指针、参数压栈、出栈等,所以当分区长度很小时可以使用插入排序速度会更快。 David Musser在Introspective Sorting and Selection Algorithms一文中提出的Introspective Sorting(内省式排序)就是一种混合式的排序算法,集成了前面提到的三种算法各自的优点,也是C++ std::sort函数的标准实现。

14

Timsort算法简介

我们熟悉的排序算法包括插入排序,选择排序,冒泡排序,归并排序,快速排序和堆排序等,这里介绍的是另外一个有趣的排序算法Timsort. Timsort是一种结合了归并排序和插入排序的混合算法,由Tim Peters在2002年提出,并且已经成为Python 2.3版本以后内置排序算法,并且Java SE 7, Android平台,GNU Octave也引入了这一排序算法。简单来说,这个算法可以概括为两步: 1) 第一步就是把待排数组划分成一个个run,当然run不能太短,如果长度小于minrun这个阈值,则用插入排序进行扩充; 2) 第二步将run入栈,当栈顶的run的长度满足:runLen[n-2]

07

感知哈希算法 (Perceptual Hashing)

相信很多用户都在Google,Baidu,Bing这些搜索引擎上试验过以图搜图。以图搜图的功能一般是分为两种,一种是只找匹配图片,原图或者原图的主体裁剪或者缩放,另外一种就是返回相似图片,比如女性用户可以查找与大牌款式相近的衣服和手袋,时尚又实惠! 大家有没有想过为何搜索引擎可以非常迅速且高质量地返回以图搜图结果呢?