2014年9月 ’ 的文章存档

机器学习常见算法分类汇总

机器学习无疑是当前数据分析领域的一个热点内容。很多人在平时的工作中都或多或少会用到机器学习的算法。本文为您总结一下常见的机器学习算法,以供您在工作和学习中参考。

机器学习的算法很多。很多时候困惑人们都是,很多算法是一类算法,而有些算法又是从其他算法中延伸出来的。这里,我们从两个方面来给大家介绍,第一个方面是学习的方式,第二个方面是算法的类似性。

学习方式

根据数据类型的不同,对一个问题的建模有不同的方式。在机器学习或者人工智能领域,人们首先会考虑算法的学习方式。在机器学习领域,有几种主要的学习方式。将算法按照学习方式分类是一个不错的想法,这样可以让人们在建模和算法选择的时候考虑能根据输入数据来选择最合适的算法来获得最好的结果。

监督式学习:

b1

 

在监督式学习下,输入数据被称为“训练数据”,每组训练数据有一个明确的标识或结果,如对防垃圾邮件系统中“垃圾邮件”“非垃圾邮件”,对手写数字识别中的“1“,”2“,”3“,”4“等。在建立预测模型的时候,监督式学习建立一个学习过程,将预测结果与“训练数据”的实际结果进行比较,不断的调整预测模型,直到模型的预测结果达到一个预期的准确率。监督式学习的常见应用场景如分类问题和回归问题。常见算法有逻辑回归(Logistic Regression)和反向传递神经网络(Back Propagation Neural Network)

非监督式学习:

b2

 

在非监督式学习中,数据并不被特别标识,学习模型是为了推断出数据的一些内在结构。常见的应用场景包括关联规则的学习以及聚类等。常见算法包括Apriori算法以及k-Means算法。

半监督式学习:

b3

 

在此学习方式下,输入数据部分被标识,部分没有被标识,这种学习模型可以用来进行预测,但是模型首先需要学习数据的内在结构以便合理的组织数据来进行预测。应用场景包括分类和回归,算法包括一些对常用监督式学习算法的延伸,这些算法首先试图对未标识数据进行建模,在此基础上再对标识的数据进行预测。如图论推理算法(Graph Inference)或者拉普拉斯支持向量机(Laplacian SVM.)等。

强化学习:

b4
阅读全文

大型网站系统架构演化之路

前言

一个成熟的大型网站(如淘宝、京东等)的系统架构并不是开始设计就具备完整的高性能、高可用、安全等特性,它总是随着用户量的增加,业务功能的扩展逐渐演变完善的,在这个过程中,开发模式、技术架构、设计思想也发生了很大的变化,就连技术人员也从几个人发展到一个部门甚至一条产品线。所以成熟的系统架构是随业务扩展而完善出来的,并不是一蹴而就;不同业务特征的系统,会有各自的侧重点,例如淘宝,要解决海量的商品信息的搜索、下单、支付,例如腾讯,要解决数亿的用户实时消息传输,百度它要处理海量的搜索请求,他们都有各自的业务特性,系统架构也有所不同。尽管如此我们也可以从这些不同的网站背景下,找出其中共用的技术,这些技术和手段可以广泛运行在大型网站系统的架构中,下面就通过介绍大型网站系统的演化过程,来认识这些技术和手段。

一、最开始的网站架构

最初的架构,应用程序、数据库、文件都部署在一台服务器上,如图:

LLL

 

二、应用、数据、文件分离

随着业务的扩展,一台服务器已经不能满足性能需求,故将应用程序、数据库、文件各自部署在独立的服务器上,并且根据服务器的用途配置不同的硬件,达到最佳的性能效果。

M1
阅读全文

Web开发者必备的11个精华版JavaScript工具

b1

 

JavaScript正逐步占领互联网,而它的开发工具也百花齐放,难以挑选。这里的11款新兴工具,满足你用JavaScript构建现代网站的各种要求。他们接口简洁,功能强大。这些经过改进与重构的工具会让我们写得少做得多。

1、Meteor

Meteor框架是由其七原则支撑着的。其中某些很战略,例如说要懂得整合开源插件,所以Meteor是已经有成熟的插件的。

c1

 

另外一些就比较战术了:设计简单的API,网络只用来传数据,所有地方都用同一种语言。而“用同一种语言”的意思是,用Node.js和MongoDB,使代码在服务端和客户端都能运行。图中就是在客户端构建一个集合,这些代码同样能运行在后端跟MongoDB交互,实现持久化。

2、Epoch

b2

 

现在流行数据可视化。各种工具以各种方式实现数据可视化,但依然比不上d3.js。而Epoch的创始人另辟蹊径,直接拿d3.js来用,并加入管道来使视图平滑和持续。它使你可以轻松地做出实时的数据可视化。图中展示的是一个实时向左滚动的直方图。

3、Web Starter Kit

b3

 

这个Google出品的工具是一个帮助开发者做出自适应网页的工具,你只需勾画出大概样子,该框架就帮你实现自适应。当然它的实现细节是按Google团队的审美的。

4、Reveal.js

b4

 

它是基于HTML5的,可用来替代PowerPoint。它的强大之处是有各种演示策略,适合用来讲故事或者演说。图中是页面切换的展示。

5、RxJS

b5

 

静态网页已经远去,普通的动态网页也不再新鲜,现在的潮流是是网页更具反应力,就像自动补全。无需等用户点击“搜索”,RxJS就能猜到用户想找什么并呈现出来。图示是一个绑定了维基API的事件。

6、NodeBB

b6

 

NodeBB使得搭建论坛变得简单,它是响应式和可制定的,并且是实时的。现在它加入了一些现代的主题,以及支持小屏幕,无限滚动。图示是NodeBB社区中提供的插件。

7、GulpJS

b7

 

曾几何时人们要重头写HTML、CSS和JS,但现在GilpJS包办一切。你只需写少少JavaScript指定路径,Gulp就会干完剩下的活。就如Ant和Maven之于Java,但Gulp使用JavaScript而不是XML。

8、AngularJS

b8

 

这是来自Google的一个平滑的、轻量的框架。它是MVC的,且是自适应的。

9、Odyssey

b9

 

网页中使用地图,从未如此简单!而且还能像讲故事一样写代码。这就是Odyssey

10、PlayCanvas

b10

 

理论上,做游戏都被当做不正经的。但实际上,就有人用WebGL来做出了PlayCanvas这样的游戏引擎。它包含物理效果、光影、声音。如同现实。

11、Deb.js

b11

 

这个只有1.5KB的Deb.js,轻巧且清晰的js调试工具,比肩Firebug和Chrome的内置调试器!

英文:NetWorkWorld,译者:dncszp

10个对开发项目有害的编程习惯

避免这些常见的编码习惯,会让我们的工作更轻松、软件更安全且更易于扩展。

帕雷托法则明确指出,20%的因导致80%的果。又称为80-20法则,它适用于几乎每一个需要人作为劳动主体的相关领域。

在软件开发领域,这个法则可以概括为,大多数的问题都是由少数不良编码习惯造成的。改变这些习惯,你会更有效率。

下面讲讲最要不得的10条编码习惯:

b1

 

1.拼写错误

让我特别讶异的是,为什么大家明知这个习惯百害而无一利,竟然还是任其在代码中肆虐横行,以致于经常出现拼写错误的变量名和函数名。更加悲剧的是,错误的拼写常常隐蔽得很好,很难发现。

至于解决方法,可以在一个良好的集成开发环境(IDE)上写代码,或者干脆用程序员专用的文本编辑器,这些都可以显著减少拼写错误。还可以选择特定的变量名和函数名,一方面容易拼写,另一方面即便写错了也能轻易发现。尽量避免使用很容易拼错的单词,例如“receive”,很容易拼写成“recieve”。

2.未按规定格式写代码

缩进和格式化,能让我们的代码一目了然、易于理解,有什么错误也能一览无余。而且也方便别人理解和维护。
阅读全文

关于Java的10个谎言

下面的这些都算是比较高级的问题了,面试中一般也很少问到,因为它们可能会把面试者拒之门外。不过你可以自己找个时间来实践一下。

System.exit(0)会跳过finally块的执行

System.setSecurityManager(new SecurityManager() {
        @Override
        public void checkExit(int status) {
            throw new ThreadDeath();
        }
    });
    try {
        System.exit(0);
    } finally {
        System.out.println("In the finally block");
    }

这段代码为什么会输出In the finally block?为什么没有打印出堆栈跟踪信息呢? 2. String str = “Hello”;其中str是一个字符串对象 跟C++不同的是,Java里的变量要么是基础类型,要么是引用。变量不可能是对象。这意味着像这样的表达式:

String str = "Hello";
    String text = "Bye";
    str == text; // 比较两个引用,而不是内容
    str = text; // 把text的引用赋值给str

大多数情况下其实没有太大的区别,不过这么写容易引起困惑。

final StringBuilder sb = new StringBuidler();
    sb.append("Hello"); // 这个引用是final类型的,而不是这个实例。
    method(sb); // 可以通过方法来修改这个实例,不过这个变量是无法修改的
  • Java的内存泄露跟C++程序员理解的一样 内存泄露在维基百科上的定义是”在计算机科学中,如果程序没有正确地管理好内存分配 ,就会出现内存泄露。在面向对象编程中,如果内存中的一个对象无法在代码中访问不到的话,这就是内存泄露。” 不过在Java中,对象总是可达的,那些没有强引用的对象会被清除掉。内存泄露这个术语在Java中意味着:内存中存在着不该存在的对象,通常来说是有些不再使用的资源却仍存储在集合中。

阅读全文

如何用JavaScript获取图片的真实尺寸大小

网页页面上的图片尺寸似乎都千篇一律。我们最常见到的带有多图的文章页面中,图的大小通常是和页面的宽度一致,这样看起来,页面就是一个直筒形,这样的布局看多了就会觉得很单调。之所以形成这样的局面,我想很大程度上是因为老式浏览器的限制。但随着现代浏览器(火狐/谷歌/IE11)的普及,浏览器对页面设计的限制越来越少,Web程序员的想象能力能够得到极大的发挥。

比如,冷知识:你知道每个视窗都有的 [x] 是怎么来的吗?这篇文章中,很多图片超出了文本宽度的限制,给人一种参差错落的感觉,同时,让大图片以其真实的尺寸展示,给人以更震撼的感觉。
阅读全文

程序员的十大烦恼

每个程序员都有自己烦恼的事。不论这事指的是范围蠕变(scope creep),还是 指匈牙利变量命名 (Hungarian notation),还是有臭味的同事,我们都明白,这是我们有我们行业里的特定的烦恼。 下面要说的就是十大让程序员们烦恼的事情,这是我从最 近的在StackOverflow上的一个调查里整理出来的,并且掺杂了一些我个人的经验:

10. 注释 — 只解释了“how”却没有解释“why”

入门级的编程课程通常会教育学生们写代码前先写注释、而且要尽量多注释。 这种教育的出发点是“多注释肯定比少注释好、少注释肯定比没注释好”。 可不幸的是,很多的程序员把这当成了一种任务,对每一行代码都注释一下。 这就是为什么会经常看到像Jeff Atwood在他的博客文章Coding Without Comments提到的代码:

1 	r = n / 2; // 让 r 等于 n 除以 2
2 	
3 	// 当 r - (n/r) 大于 t 时进行循环
4 	while ( abs( r - (n/r) ) > t ) {
5 	 r = 0.5 * ( r + (n/r) ); // 设置 r 等于 r + (n/r) 的一半
6 	}

经过这样的注释,你否明白了这段代码是干什么的?的确,我也没明白。 问题就在于,虽然有大量的注释,可它们只是描述了代码是干什么了,却没有说明代码为什么要这样写。

现在,请看一下我们采用另外一种方式对同一段代码进行的注释:

1 	// 使用牛顿-Raphson算法求n的平方根近似值
2 	r = n / 2;
3 	
4 	while ( abs( r - (n/r) ) > t ) {
5 	 r = 0.5 * ( r + (n/r) );
6 	}

这就好多了!也许我们还是不能完全明白这段代码的作用,但至少是有了一点方向了。
阅读全文

kmp算法实现原理及简单示例

以前看过kmp算法,当时接触后总感觉好深奥啊,抱着数据结构的数啃了一中午,最终才大致看懂,后来提起kmp也只剩下“奥,它是做模式匹配的”这点干货。最近有空,翻出来算法导论看看,原来就是这么简单(下不说程序实现,思想很简单)。

模式匹配的经典应用:从一个字符串中找到模式字串的位置。如“abcdef”中“cde”出现在原串第三个位置。从基础看起

朴素的模式匹配算法

A:abcdefg  B:cde

首先B从A的第一位开始比较,B++==A++,如果全部成立,返回即可;如果不成立,跳出,从A的第二位开始比较,以此类推。

/*
 *侯凯,2014-9-16
 *功能:模式匹配
 */
#include<iostream>
#include <string>
using namespace std;

int index(char *a,char *b)
{
    int tarindex = 0;
    while(a[tarindex]!='\0')
    {
        int tarlen = tarindex;
        int patlen;
        for(patlen=0;b[patlen]!='\0';patlen++)
        {
            if(a[tarlen++]!=b[patlen])
            {
                break;
            }
        }
        if(b[patlen]=='\0')
        {
            return tarindex;
        }
        tarindex++;
    }
    return -1;
}
int main()
{
    char *a = "abcdef";
    char *b = "cdf";
    cout<<index(a,b)<<endl;
      system("Pause");
}

思路朴实无华,十分有效,但是时间复杂度是O(mn),m、n分别是字符串和模式串的长度。模式匹配是一个常见的应用问题,用的广了,就有人想法去优化了。Rabin-Karp算法、有限自动机等等,前仆后继,最终出现了KMP(Knuth-Morris-Pratt)算法。

kmp算法

a1

 

 

优化的地方:如果我们知道模式中a和后面的是不相等的,那么第一次比较后,发现后面的的4个字符均对应相等,可见a下次匹配的位置可以直接定位到f了。说明主串对应位置i的回溯是不必要的。这是kmp最基本最关键的思想和目标。
阅读全文

Python 代码性能优化技巧

选择了脚本语言就要忍受其速度,这句话在某种程度上说明了 python 作为脚本的一个不足之处,那就是执行效率和性能不够理想,特别是在 performance 较差的机器上,因此有必要进行一定的代码优化来提高程序的执行效率。如何进行 Python 性能优化,是本文探讨的主要问题。本文会涉及常见的代码优化方法,性能优化工具的使用以及如何诊断代码的性能瓶颈等内容,希望可以给 Python 开发人员一定的参考。

Python 代码优化常见技巧

代码优化能够让程序运行更快,它是在不改变程序运行结果的情况下使得程序的运行效率更高,根据 80/20 原则,实现程序的重构、优化、扩展以及文档相关的事情通常需要消耗 80% 的工作量。优化通常包含两方面的内容:减小代码的体积,提高代码的运行效率。
阅读全文

从MVC框架看MVC架构的设计

尽管MVC早已不是什么新鲜话题了,但是从近些年一些优秀MVC框架的设计上,我们还是会发现MVC在架构设计上的一些新亮点。本文将对传统MVC架构中的一些弊病进行解读,了解一些优秀MVC框架是如何化解这些问题的,揭示其中所折射出的设计思想与设计理念。

 

MVC回顾

 

作为一种经典到不能再经典的架构模式,MVC的成功有其必然的道理,这个道理不同的人会有不同的解读,笔者最认同的一种观点是:通过把职责、性质相近的成分归结在一起,不相近的进行隔离,MVC将系统分解为模型、视图、控制器三部分,每一部分都相对独立,职责单一,在实现过程中可以专注于自身的核心逻辑。MVC是对系统复杂性的一种合理的梳理与切分,它的思想实质就是“关注点分离”。至于MVC三元素的职责划分与相互关系,这里不再赘述,下图给出了非常细致的说明。

a1

 

图1:MVC组件的功能和关系

View与Controller的解耦:mediator+二次事件委派

 

笔者早年开发基于swing的GUI应用时,在架构MVC的实践过程中深刻体会到了view与controller之间的紧密耦合问题。在很多事件驱动的GUI框架里,如swing,用户对view的任何操作都会触发一个事件,然后在listener的响应方法里进行处理。如果让view自己注册成为事件的listener,则必须要在view中加入对controller的引用,这不是MVC希望看到的,因为这样view和controller就形成了紧密的耦合关系。若将controller注册为listener,则事件响应将由controller承担,这又会导致controller处理其不该涉及的展现逻辑,造成view和controller难以解耦的原因在于:多数的用户请求都包含一定成分的展现逻辑和一定成分的业务逻辑,两种逻辑揉合在一个请求里,在处理的时候,view与controller很难合理地分工。解决这一问题的关键是要在view与controller之间建立一种可以将展现逻辑与业务逻辑进行有效分割的机制,在这方面,PureMVC[ii]的设计非常值得参考,它通过引入mediator+二次事件委派机制很好的解决了view与controller之间的紧耦合问题。

 

Mediator是一种设计模式,这种模式在组件化的图形界面框架中似乎有着普遍的应用场景,即使是在四人帮的《设计模式》一书中,也使用了一个图形界面程序的示例来讲解mediator。mediator的设计用意在于通过一个媒介对象,完成一组对象的交互,避免对象间相互引用,产生复杂的依赖关系。mediator应用于图形界面程序时,往往作为一组关系紧密的图形组件的交互媒介,完成组件间的协调工作(比如点选某一按钮,其他组件将不可用)。在PureMVC中,mediator被广泛应用,其定位也发生了微妙的变化,它不再只是图形组件间的媒介,同时也成为了图形组件与command之间的媒介,这使得它不再是可选的,而是成为了架构中的必需设施。对应到传统MVC架构中,mediator就是view与controller之间的媒介(当然,也依然是view之间的媒介),所有从view发出的用户请求都经过了mediator再传递给controller,它的出现在一定程度上缓解了view与controller的紧密耦合问题。
阅读全文