命令模式算是我在过往项目中除了单例模式、模版模式等简单的模式以外用的最频繁的一个设计模式。

个人感觉命令模式的魅力就在于把一个个request封装成一个个的object，非常方便扩展。命令模式类似Javascript中的回调函数一样，可以进行callback处理。当然最大的缺点就是当request过多时，Command类也会膨胀的厉害。

最近编码时想用命令模式，看书复习了下，却总感觉书上讲的没有我以前设计的一个命名模式框架好用。经过翻箱倒柜终于找出了以前设计的命令模式，这里记录下，方便以后使用。

Command接口

不再使用抽象类，改用接口。同样只有一个execute(..)方法，但需要传递一个Context上下文类。

Context类

Context类可以处理很多事情，比如类似SpringContext，比如结合策略模式和状态模式等，可以根据具体的需求来实现不同的Context类。

阅读全文>>

长假过后的第一天，突然看到一篇让我十分有共鸣的文章——最糟糕的编程面试题。这篇博文主要吐槽了面试题中最常犯的2个问题：太过困难或不切实际。而文中举的例子：如何检测链表是否存在环路，也恰巧是我曾经被面试过的一道题目。而那次面试也堪称我面试经历中最让人难（dan）忘（teng）的一次。

第一个故事——最难忘的面试

背景：校招，笔试通过后连续三轮面试，每轮都会刷一部分人，具体是那个公司就不说了，相信去过的同学基本都能猜出来。第一面，自我感觉表现一般，等结果时一直在想会不会一轮跪。结果这个岗位19个面试者刷了13个，我有幸留下了。第二轮，自我感觉十分良好。面试官问了很多这样的问题，如：如何判断两个链表是否有共同的尾巴、字符串相似度、链表中两元素交换等等。

后来他问到如何检测链表是否是环形链表，也就是首尾相连的链表，我当时想了想就答道，用2个指针，开始同时指向一个节点，然后一个指针移动，另外一个不动，若它们再次指向同一个节点，则是环形的。面试官笑道，用2个指针的想法不错，能否继续改进？我想了想，时间复杂度已经是O(n)了，难道要变成O(lgn)？那岂不是要借助于树之类的方法？这貌似有点太难了，短时间之内无法搞定。面试官看我犹豫了很久，提示到，还是使用2个指针，你再想想有没有其它的方法。然后我纠结了半天后，尝试的说了个当时觉得很粗（cao）糙（dan）的方法：一个指针走2步，一个指针走1步。没想到这尽然真是面试官的“标准答案”。面试官笑呵呵的说，不错不错。于是我心里一阵阵小激动，看来不用多久，我就会升职加薪，当上总经理，出任CEO，迎娶白富美，走上人生巅峰，想想还有点小激动呢。

阅读全文>>

问题

一个同事发来的题目：学校有三种人员，第一种为教师，属性包括名字、教工号、电话、地址；第二种为学生，属性包括名字、学号、电话、地址、平均成绩；第三种为辅工，属性包括名字、辅工号、电话、地址、工种。使用你学到的面向对象设计的方法，实现这三种人员的类表示，并实现三种人员的添加、修改、删除，可在内存进行增删改的操作，不需要永久保存。

注，可使用List保存人员，如没有使用OO设计方法，本期作业不通过，仅使用类不是OO设计。

答案v1

大致扫了一眼题目，是一个简单的OO设计问题。于是第一版答案很快出来了。

抽象父类Staff

阅读全文>>

最近有些迷茫，不知道自己的未来会怎样。感觉每个月总有那么几天会不由自主的思考人生、思考未来，然而关于这种没有结果的思考往往会让我很迷（dan）茫（teng）。迷茫的主要原因，仔细的想想，可能还是害怕现在走的路无法在未来达到自己预想的效果。

现在对自己的规划是：希望自己成为一个靠谱的编程+大数据+机器学习的人。但是现在却又有点担心成为一个四不像了，编程不靠谱、大数据也不精通、机器学习更是半调子。

之前看到一篇文章“程序员生存定律-打造属于自己的稀缺性”，里面说到技术向程序员，有两种方向来提升自己的价值：一是达到一定高度横向展开；二是彻底的专家型道路。当时想，我采用的方式应该是第一种。但是现在想想，在这个分工越来越细化的社会里，专家型的道路是否更合适些。这也是全栈程序员充满争论的原因之一：到底是博百家之长还是贪多嚼不烂？

其实感觉自己完全没有必要蛋疼。因为就我目前这所谓的三个方向：编程+大数据+机器学习，比起“百”而言，还差的多了去了。要是三个就搞不定，是不是太废柴了点。可是令人充满挫折感的机器学习确实很打击士气，花费的时间最多，但收获的效果却感觉最差。

长期给自己打气：没事的，看一次不懂就看两次，看两次不懂就看三次，直到看懂为止。可是一想到效率这个词，就又立马纠结起来了：有这么多时间是不是可以干成很多其它事情了。

算了，不纠结了，车到山前必有路，船到桥头自然直，选择了就坚持走下去不要后悔就行。就好像骑车一样，选择上路，就必须面对汗水和孤独。

阅读全文>>

奇异值分解

奇异值分解，singular value decomposition（SVD）是线性代数中一种重要的矩阵分解。

记得大学时学习线性代数中的特征值和特征向量时，我就一直思考这个玩意算出来到底有啥用，难不成就是一群热（xian）爱（de）专（dan）研（teng）的人弄出来的数学小把戏？然后随着时间的推移，这些纯理论的东西就基本忘光了。大学的知识往往都这样的，和实际不接轨，学的时候不知道有啥用，等用的时候就忘的差不多了。

现在，在我学习线性代数后的第8年，我终于知道特征值这个玩意有啥用了。首先，先回忆下什么是特征值和特征向量吧。

特征值

对于一个方阵，其特征值和特征向量满足：

$A\nu=\lambda\nu$

求出所有的特征值和特征向量后，就得出了方阵A的特征值分解：

$A=Q\Sigma Q^{-1}$

其中 $Q$ 是特征向量按照与特征值的对应顺序组合而成 $(\nu_1,\nu_2,..)$ ， $\Sigma$ 是由特征值组成的一个对角矩阵。那么对于方阵A的特征值分解的意义又何在呢？先看下面这个例子，对于矩阵A（为了简单起见，设为对角矩阵）：

$A=\left(\begin{array}{ccc}100 & 0 & 0 \\0 & 10 & 0 \\0 & 0 & 1 \\\end{array}\right)$

阅读全文>>

Hypothesis testing

Hypothesis testing，假设检验。Spark目前支持皮尔森卡方检测（Pearson’s chi-squared tests），包括适配度检定和独立性检定。

皮尔森卡方检测

皮尔森卡方检测是最著名的卡方检测方法之一，一般提到卡方检测时若无特殊说明则代表使用的是皮尔森卡方检测。皮尔森卡方检测可以用来进行适配度检测和独立性检测。

适配度检测

适配度检测，Goodness of Fit test，验证一组观察值的次数分配是否异于理论上的分配。其 $H_0$ 假设（虚无假设，null hypothesis）为一个样本中已发生事件的次数分配会服从某个特定的理论分配。通常情况下这个特定的理论分配指的是均匀分配，目前Spark默认的是均匀分配。

独立性检测

独立性检测，independence test，验证从两个变量抽出的配对观察值组是否互相独立。其虚无假设是：两个变量呈统计独立性。

检测三个步骤

1. 计算卡方检定的统计值“ $\chi^2$ ”：把每一个观察值和理论值的差做平方后、除以理论值、再加总
2. 计算 $\chi^2$ 统计值的自由度“df”
3. 依据研究者设定的置信水平，查出自由度为df的卡方分配临界值，比较它与第1步骤得出的 $\chi^2$ 统计值，推论能否拒绝虚无假设

适配度检测示例

场景

将五角星的5个角分别标记为1,2,3,4,5。现在旋转若干次五角星，记录每个角指向自己的次数。

第一个的结果为(1,7,2,3,18)，第二个五角星的结果为(7,8,6,7,9)。现做出虚无假设：五角星的每个角指向自己的概率是相同的。

阅读全文>>

Spark 1.1.0于2014年9月11日发布，此次的版本将mllib完善了不少，如添加了Basic Statistics、添加了决策树的Java实现等等。现对1.1.0的新功能进行一次初步探索。

Summary statistics

Summary statistics主要提供基于列的统计信息，包括6个统计量：均值、方差、非零统计量个数、总数、最小值、最大值。

测试数据

测试代码

阅读全文>>

Boosting（提升）方法是一种常用的统计学习方法，其中最具有代表性的算法是AdaBoost。AdaBoost起源于PAC可学习性（probably approximately correct learnability）的研究。历史上，Valiant和Kearns首先提出了强可学习（strongly learnable）和弱可学习（weakly learnable）。在PAC框架下，若一个算法的识别准确率很高并能在多项式时间内完成则为强可学习；若一个算法的错误率仅仅比随机猜测略低，则称之为弱可学习。后来Schapire证明强可学习和弱可学习是等价的：在PAC学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。如此，问题就变成了：如果已经发现了一个弱学习算法，是否能够将其提升（boosting）为一个强学习算法。

关于提升方法的研究很多，例如：boostrapping，将多个弱分类器分配不同的权值来组成强分类器；bagging，根据多个弱分类器的投票结果来确定最后的分类结果。这些提升方法中，最有效最具有代表性的则是AdaBoost。

AdaBoost算法过程

AdaBoost通过每一轮的分类结果来改变每个样本的权值，使得分类错误的样本权值变大，分类正确的样本权值变小，这样使得没有正确分类的数据获得更高的关注。对于多个弱分类器，AdaBoost通过加权多数表决来组合，误差率小的分类器权值大，反之，则权值小。具体算法如下：

1. 初始化训练数据的权值分布
   $D_1=(w_{11},w_{12},..,w_{1N}), {w_{iN}={1\over N}}, i=1,2,..,N$
2. 对m=1, 2, .., M
   1. 使用具有权值 $D_m$ 的训练数据集学习，得到基本分类器 $G_m(x)$
   2. 计算 $G_m(x)$ 在数据集上的分类误差率， $e_m=P(G_m(x_i)\neq y_i)=\sum_i^N{w_{mi}I(G_m(x_i)\neq y_i)}$
   3. 计算 $G_m(x)$ 的系数 $\alpha_m={1\over 2}ln{{1-e_m}\over e_m}$
   4. 更新数据集的权值分布 $D_{m+1}=(w_{m+1,1},w_{m+1,2},..,w_{m_1,N})$ ，其中 $w_{m+1,i}={w_{mi}\over Z_m}e^{-\alpha_my_iG_m(x_i)}$ ， $Z_m=\sum_i^N{w_{mi}e^{-\alpha_my_iG_m(x_i)}}$
   5. 构建基本分类器的线性组合 $f(x)=\sum_m^M \alpha_mG_m(x)$
3. 得到最终的分类器 $G(x)=sign(f(x))$

阅读全文>>

什么是协同过滤

协同过滤(Collaborative Filtering, 简称CF)，wiki上的定义是：简单来说是利用某兴趣相投、拥有共同经验之群体的喜好来推荐使用者感兴趣的资讯，个人透过合作的机制给予资讯相当程度的回应（如评分）并记录下来以达到过滤的目的进而帮助别人筛选资讯，回应不一定局限于特别感兴趣的，特别不感兴趣资讯的纪录也相当重要。

以上定义太拗口，举个简单的例子：我现在多年不看日本anime的新番了，最近突然又想看几部新番，但又不知道这么多新番中看哪些比较好，于是我就找几个同样喜欢日本动漫的朋友来咨询。我第一个想咨询的朋友是和我口味最像的，我们都特别喜欢看《虫师》、《黑之契约者》、《寒蝉》这样的小众动画；我问的第二个朋友和我口味差不多，他特别喜欢看《钢炼》《无头骑士异闻录》这样的动画，我虽然喜欢，但不像他那么喜欢；由于身边喜欢日本动画的朋友不多，剩下第三个可以咨询的是一个宅女，平常经常看腐、宅、基的动漫，完全跟我不是一路人，于是问了下她推荐的片子，并将这些片子打上的黑名单的标签。然后我就开始看第一个朋友推荐的片子了，要是时间特别多又很无聊我可能会看第二个朋友推荐的，但打死我也不会看第三个朋友推荐的。这就是协同过滤的一个简化、小众版。

如何进行相似度度量

接着上面的例子，我可以通过我和其它朋友共同喜欢某个或某类动漫来确定我们的口味是否一样，那么如何以数学或者机器的形式来表示这个“口味一样”呢？通常，是通过“距离”来表示，例如：欧几里得距离、皮尔逊相关度、曼哈顿距离、Jaccard系数等等。

欧几里得距离

欧几里德距离（Euclidean Distance），最初用于计算欧几里得空间中两个点的距离，在二维空间中，就是我们熟悉的两点间的距离，x、y表示两点，维度为n：

$d(x,y)=\sqrt {(\sum_i^n (x_i-y_i)^2)}$

相似度：

$sim(x,y)={1\over {1+d(x,y)}}$

阅读全文>>

FieldSelection

FieldSelection包含FieldSelectionMapper、FieldSelectionReducer和FieldSelectionHelper，根据字面意思就可以了解其作用：用于选择field。直接上示例：

测试数据

代码示例

其中第三行用于选择输出的field。冒号之前的为key的field，之后为value的field。"0,3:1,2,4-"的意思为：选择第1、4列为key，选择第2、3、5及其以后的列为value。此外还可以使用类似“4-7”这样的方式来选择一个范围。为了直观的区分key和value，第五行将key和value的分隔符设置为“|”。

阅读全文>>