程序员的自我修养
Home » 文章归档 » 2014年九月

一个简单的OO问题

0条评论1,866次浏览

问题

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

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

答案v1

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

抽象父类Staff

阅读全文>>

标签:, ,

有些迷茫

5条评论6,540次浏览

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

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

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

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

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

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

阅读全文>>

分类:随想
标签:

SVD与PCA

4条评论16,074次浏览

奇异值分解

奇异值分解,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)\)

阅读全文>>

Spark 1.1.0 Basic Statistics(下)

2条评论6,179次浏览

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 Basic Statistics(上)

1条评论3,816次浏览

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

Summary statistics

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

测试数据

测试代码

阅读全文>>

分类:Apache Spark
标签:,

AdaBoost

2条评论5,693次浏览

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))\)

阅读全文>>

分类:机器学习

Spark MLlib之协同过滤

30条评论25,370次浏览

什么是协同过滤

协同过滤(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)}}\)

阅读全文>>

MapReduce库类

0条评论2,009次浏览

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的分隔符设置为“|”。

阅读全文>>

标签:,

Trie树

0条评论4,297次浏览

前几天与学弟聊到他最近的面试题中有一题需要计算两个字符串的最长公共子字符串。当时想到了KMP算法可能可以解决,但仔细想想可能是个比较复杂的任务。后来在网上看到有不少人说用trie树来解决。然后我就糊涂了,记忆中trie树貌似只能解决最长公共前缀的问题吧。于是复习一遍Trie树。

简介

Trie树百度百科解释如下:又称单词查找树,字典树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。

Trie树的直观结构如图所示:
trie tree

图中红色的点代表此处有字符串在此结束,上图中共有7个字符串:abc、abcd、abd、b、bcd、efg、hij(百科中的图,空白边就算作j好了)。

Trie树的使用场景

  • 字符串检索,词频统计,搜索引擎的热门查询。
  • 字符串最长公共前缀。
  • 字符串排序。
  • 作为其他数据结构和算法的辅助结构,如后缀树,AC自动机等。

至于“计算两个字符串的最长公共子字符串”这样的需求无法采用trie树实现,就算能实现也需要大量的改变。

阅读全文>>

标签:,
11
profile
  • 文章总数:81篇
  • 评论总数:241条
  • 分类总数:32个
  • 标签总数:45个
  • 运行时间:1254天

大家好,欢迎来到selfup.cn。

这不是一个只谈技术的博客,这里记录我成长的点点滴滴,coding、riding and everthing!

最新评论
  • Anonymous: :?: :razz: :sad:
  • Anonymous: 牛
  • Anonymous: 楼主你好,我偶尔也会 遇到Reconnect due to socket error: java.nio.channels.ClosedCha...
  • Anonymous: sdfs
  • Anonymous: :arrow: :neutral: :cry:
  • Anonymous: java.io.NotSerializableExcepti on: DStream checkpointing has been enabled but the DStreams with their...
  • wick: HI,请问一下,U,S,V得到 ,怎么得到近似矩阵 (用spark java),谢谢。
  • Michael Whitaker: Thank you for this blog, it was very helpful in troubleshooting my own issues. It seems that no...
  • Anonymous: :mad:
  • Anonymous: :???:
  • Anonymous: :mad: :mad: :mad:
  • 洋流: 哥们,我问个问题,你 把testOnborrow去掉了。。 如果得到的jedis资源...
  • 洋流: 哥们,我问个问题,你 把testOnborrow去掉了。。 如果得到的jedis资源...
  • Anonymous: :razz: :evil: :grin:
  • 张瑞昌: 有很多,比较常见的是 Jacob迭代法,一次迭代O (n^3),迭代次数不清楚 ...
  • Anonymous: :mrgreen:
  • lc277: 你好 我想问下一般删除节点 要多久,要删除的datano de大概用了1t,解除...
  • Anonymous: 你好 我想问下一般删除节点 要多久,要删除的datano de大概用了1t,解除...
  • Anonymous: :smile: :grin: :eek:
  • 李雪璇: 想要完整代码,可以帮 忙发给我吗