技术手记

12306 和火车票那点事

每年春运时铁道部和 12306 都要被喷死, 自己也和 12306 斗智斗勇了两三年, 这个冬天跟着 @scat 君折腾了很久, 随手写点什么说说这事.

提前说明我只是火车迷, 不是铁道部的人, 用不着帮铁道部把黑的说成白的, 我自己也有各种怨气要喷, 只是希望能提供一个相对客观的事实供大家来参考参考. 前半段跟喷子对喷和对 12306 的吐槽的会多点, 后面有一些胡思乱想的一些可能称得上是建议的东西.

喷子和不那么容易的 12306

然后以一个标准喷子的口气对那些说 12306 做的很烂随便找个本科生就能写的人骂一句, 去你大爷的什么时候国内的学生素质这么高你有多少我要多少; 再对一些所谓业内人士说的这种负荷找淘宝什么的能轻松解决的观点说句很抱歉, 这两个虽然在规模和突发性上有不少相似点, 但是还是有很多不一样的地方, 比如淘宝上一件商品如果有多件是无区别的, 而火车票一张就是一张, 有人买到上铺还不干非得换下铺, 而且这里面一张票就是一个锁, 而且淘宝超售了最多补货或退款, 火车可不是说加床或加位子就能加上去的, 而且要是先跟你说买到票了然后说不好意思超售了我们退钱给你, 不知道有多少人想直接穿过显示器把那边的服务器给砸了; 最后说说 12306NG 那帮人, 最近没关注, 一年前看了下那个论坛和所谓的发起人, 很可惜里面大部分都只是夸夸其谈一些自称砖家的喷子, 很多人估计都没做过百万规模的系统就敢各种意气风发指点江山, 这种人都能说出靠谱的整体解决方案和细节注意点来那就见鬼了.

喷爽了咱们来摆事实讲道理说说 12306 的各种不容易, 先说我们是怎么搞他的:

> 最早的 12306 基本上就是一个高校实验室的产品, 空闲时段可用, 用的也还凑合. 据说有收钱不出票的情况, 不过我还没遇到过, 所以不好评论. 退票的钱不是实时到账的, 快的几天慢的一个月我也都遇到过

> 等到了高峰期的时候, 开始各种登陆不上, 各种刷不开页面, 或提交不成功. 这时候最大的问题是带宽和前端服务器不够, 压根抢不到一个有效连接.

> 等把带宽问题基本解决后, 发现每一次页面加载都需要做太多次 GET 操作, 而且很多页面数据不优化不压缩, 虽然系统还用了 jQuery 什么的至少看起来算是跟上先进生产力的技术, 但是整体还是比较糙, 据说是用 CDN 和大量加机器来算扛住. // 不过到现在一次页面加载需要获取的资源还是太多, 而且一开始没做内部的负载均衡, 容易出现一个 ISP 解析过去都在少数几台机器, 所以同一地区不同 ISP 接入的速度会有明显差异 (比如北京联通用户多, 基本就卡成幻灯片, 用用户少的电信线路就相对靠谱点), 而且个人认为不少机器加的很浪费

> 有了缓存机制后发现一个巨坑爹的地方, 12306 似乎把后台实时数据和 CDN cache 在某些地方用反了, 比如余票等实时性非常强的数据反倒在前端有一个 cache, 平时还好, 但是高峰期放票瞬间这个 cache 就要命了, 如果你赶巧碰上一个更新较慢的 CDN, 估计等你刷到数据时票都被别人买完了 // 这个问题现在还是没有解决, 所以才有使用一些专线 CDN (比如传说中的海外线路) 可能会保证网络比较通畅 cache 更新也比较快的说法

> 等机器, 带宽, 缓存什么的搞差不多后, 开始有技术流的 hack 手段出现, 曾经有这样的刷票方法: 要买 2.3 的票, 但是还有几分钟才放票, 不确定自己是否一定能命中更新较及时的 CDN, 于是可以先查 2.2 的票找到对应车次的任意席位的票, 在填写乘车人信息时改 POST 请求中的参数, 把时间改成 2.3, 席位改成自己想要的 (比如硬卧), 然后强制提交, 只要到了放票时间, 不管自己连的前端服务器是否更新余票缓存, 都可以把这个请求提到后端进行处理. 这方法我用过, 很爽, 可惜现在被封了. // 封的手段是在提交订单时加了一个加密串, 发到站, 时间和车次必须和加密串对应才能提交. 不过这个加密串在同样条件下每次查询都可能不一样, 但是同一个验证码可以用无数次 (或者是一个比较长时间段内都可用, 没确认), 所以可以用大量的机器密集轮询 12306 不同的前端服务器获得对应的加密串, 一旦有这个数据就可以构建数据强制提交了. 此方法目前还可用且有人在用, 不过需要考虑 12306 现在开始限 IP 或限同 IP 的连接数了

> 12306 注册帐号需要提供证件号, 不能坑别人, 所以默认大家一人就是一个帐号, 同帐号只要有订单没完成, 就不能去下别的订单, 如果一次要买不同车的票, 那就疯了, 还好 12306 允许护照/港澳通行证什么的也可以注册, 谢天谢地又多几个帐号可以一起刷了, 果然办个护照什么的还是没坏处的. // 这个限制其实也能绕过去, 你收集一堆朋友的帐号给你抢一张票不就行了. 还有个更 ws 方法能很容易搞到成百上千的帐号, 个人使用怎么着也都够了, 具体方法还是不说了, 免得被封

> 能搞到提交所需数据, 也有足够的帐号去刷, 那接下来的问题就是怎么把能自动化的地方自动化. 各种抢票助手的原理大致都是做一个浏览器插件, 自动重试查询, 并且监控对应的票额, 然后把一些能自动完成的步骤自动完成 (比如点下一步什么的) // 这里还是有带宽的问题, 其实并不是每次都要把所有的流程都走完, 获取的数据也只要核心数据, 不少插件应该没考虑好这个, 还是对用户的网络有比较高要求. 另外 12306 也做了一些限制, 比如连续两次重试时间不能小于五秒, 偶尔也改一下 URL, 做个 302 跳转什么的. 不过整体而言这个封不了, 完全模拟用户行为, 后面的一些 hack 也基本是这个思路

> 一直到上一步, 应该说已经能将大部分操作自动化完成, 唯一的麻烦就是验证码. 12306 一直到 2013/01/25 用的都还是用一套非常弱的验证码, 字迹清晰颜色差异明显, 最关键的是字体似乎只有两种, 随便找个学过基本的图形学的本科生应该就可以搞定, 先做二值化提取出有字的部分, 然后做水平和垂直方向的投影, 按区块直接跟已知的单个验证码特征库最对比就可以了. 死猫君和其同伙用 C/C++ 实现, 能做到 1ms 一个验证码, 99%+ 的准确率, 12306 在这样的识别效率面前已经完全不设防, 想怎么搞就怎么搞. // 但是超简单的验证码已经从 2013/01/26 开始变成了一个相对复杂的, 原来的方法需要做一些优化才能用, 且识别率可能不那么高

> 就算验证码的识别率下降, 但哪怕只有一两成的成功率, 机器还是比人快的. 12306 的对策一开始是加浏览器参数校验, 如果是裸的 POST 请求就拒绝掉, 但是 http header 这种东西, 自己人肉走一遍流程把对应的数据扒下来让机器模拟还是毫无压力. 接下来 12306 是不停的改接口 URL, 虽然最后还是落到同一个处理接口上, 但是加上了跳转判断, 直接提到最终接口的会被拒绝, 到这就变成猫鼠游戏, 12306 改一次 URL 对应的机器行为就要跟着改一次. 估计是今年各种机器行为搞 12306 搞的比较疼, 虽然他们已经提供了超过一千个对外 IP, 也还是怕被这么搞, 接下来的一招是加了更严格的间隔时间限制, 这时候机器行为的成功率就很重要了, 一旦重试最少五秒就过去了, 而且有一些步骤加了很猥琐的隐藏等待时间, 机器提交太快会报错, 而慢一点接近人的速度就没事. // 最后那个限制真心无解, 不过对手快的人也是很伤的, 别人眼尖手快你还能不让别人买? 跟 @scat 吐槽说看来 12306 对他们的网络很有信心, 正常人五秒内是刷不开第二次或能提交上请求的. 另外机器重试时加个随机附加时间, 可以对人的行为模仿的更像, 这个 12306 没法做特征库来判断是人的行为还是被机器刷

> 攻防到这阶段, 两边基本就没什么办法了, 不过 12306 干了件更 NB 且 WS 的事情: 同 IP 限制登陆人数和封 IP. // 不知道 12306 怎么判断的, 反正 jike 他们那种抢法绝逼是要被封 IP 的, 但是很多企业对外出口就一个, 要赶上员工集体抢票, 结局就是集体悲剧, 反正我在公司悲剧过几次 -.-|

目前拉锯战就到此, 如果是真的搞技术的人, 要是自己的产品成天都在被一群这么蛋疼的人这么玩, 估计早就疯了, 所以说 12306 今年系统一直还可用 (虽然还是会卡还是没有票), 且一直在增强防御, 还是挺不容易的

关于 12306 和铁路客运的吐槽及建议

前面在同情了半天 12306 后还是吐槽没票这个现实, 没票的最大原因还是运力不足, 大家都想过年前一天到家, 那单日发送量必然爆表, 但车就那么多, 只能靠抢

运力不足有一些变通的方法, 比如加挂车厢, 动车重联等方式来提升已有运力, 这个大家都很爽; 比如卧代座 (硬卧车厢当硬座买, 一节车厢大概多卖 20 来张票), 这个大家也觉得还好, 遇上比较 nice 的车上铺还能爬上去轮流躺着睡觉; 比如开临客, 这个似乎就不那么灵光了, 大家对临客的印象还是又慢又破的绿皮车, 经常让车和晚点, 殊不知现在连高铁都有临客, 只是不挂 L 的车次, 临客最大的问题还是时间不好, 一般都半夜出发或到达, 除了这个其他都还好, 我坐过北京到南宁的临客, 空调车人也不多, 除了慢了点其他都巨爽; 比如提升车底周转率, 普速时代最多就是把长途车到终点后再开个短途, 把到下一次发车前的这段间隔用起来, 这个意义好像不大, 而且本来车还是要整备的, 但是动车和高铁时代提升周转率就很有意义了, 同样的北京到武汉 1225 公里, 一路不停按 250 的速度要至少五个小时, 但按 380 的速度跑就不到四个小时了, 同一列车底长短混跑, 一天可能就能多开一趟车, 可惜这个被现任铁道部的猪头领导以安全为由强制降速, 而且给动车组生产厂家的订单也不加, 导致需要车的时候没车, 单车底也还有检修里程限制, 不可能 7*24 连轴转, 坑爹啊这不是

另一个导致运力不足的问题是车票价格, 现行火车票价格已经十多年没变了, 期间还经历了六次大提速, 其他交通方式和物价已不知道涨了多少, 偏偏铁道部自己还涨不了价 (发改委什么的一堆流程要走), 所以只能绿皮改空调, 普速变快速 (虽然实际时间可能还慢了) 来曲线救国, 动车和高铁的票价是明显上了一个档次, 所以也能解释为什么有高铁后普速必然会少一堆, 大部分国人还是缺钱不缺时间的主, 特别是学生这种巨叽歪的群体. 造成同样结果的还因为人民群众的生活水平提高了, 也娇气了, 以前有硬座就很好, 现在很多人还非卧铺不坐, 最狠的是只要硬卧下铺的, 人家理由多充分: 软卧太贵硬座不爽上铺难爬, 需求就这样被密集化 (很多人都是只坐某趟特定车的某种特定铺)

在供给远小于需求的供需现状下怎么搞都无解, 那只能把问题退一步, 让大家怎样以一个 “公平” 的方式来搞. 我自己想过一个方案, 后面有一次问了 @cnberg 印度是怎么弄的, 发现跟我想的基本一样, 我先说说印度怎么订票:

1. 订票提前周期很长. 订票时
– 1.a 如果有票则付全款出票, 完成
– 1.b 如果没票则交押金 (大约 10 人民币) 进入一个排队队列
2. 排队过程中
– 2.a 可随时查询在队列里的位置, 当新票额放出或有人退票或退出排队, 你在队列里前进, 排到后付全款出票, 退押金, 完成
– 2.b 如果到开车时间还没排到有票的位置, 退押金, 完成
– 2.c 主动退出排队队列, 押金不退, 完成
3. 退票
– 3.a 退票收取大约 10% 的手续费, 完成

这里面最爽的是引入了排队机制和获知自己排队位置的查询接口, 让整个过程对乘客而言更透明. 但是当时我们讨论时也说到, 中国春运是刚需, 提前半年估计也会在订票的时候就把系统和队列压爆, 只是把现在提前 20 天的坑爹提前了而已, 而且对那些没法提前那么长时间确定行程的人是一种伤害. 而且估计印度网民远没中国多 (具体数据没查, 但是用脚也能想到), 所以系统压力没那么大

我的方案比这个更激进点, 不同的是
1. 排队时就可以先付全款, 这样一旦排到票马上就能出票, 不至于说排到票时自己不方便, 因为没法付款而导致被从队列里强制踢出去
2. 退票费按退票时间到开车时间的间隔依次递增, 越晚退票手续费越高, 这样也让那些买多张票备用但最后只用一张的人提前把资源让出来给有需要的人 // 现在就很多人买好几张票备着, 走之前才退, 结果其他有需要的人也来不及捡漏

这些都是比较大的系统性变化, 我们这些玩票也就吐吐槽, 如果有不妥或没考虑到的地方也欢迎讨论

落到 12306 本身, 感觉可以提供一个精简版入口来满足订票需求, 像界面/退票/添加修改常用联系人之类的操作很少用到, 没必要每次都为了兼容这些操作而走那套有巨多图片和 .js 加载的系统, 刷票助手什么的其实就是在帮忙减轻网络压力, 反正大家只要能定到票, 直接做个纯文本界面也无不可

压缩 VirtualBox 下安装 Linux 的 .vdi 虚拟硬盘文件

之前虚拟机里装过一个 Ubuntu, 闲的蛋疼还装了 KDE 等一陀东西, 后来不想玩了折腾把不用的删掉 (主要是 KDE 及其相关, 还有升级内核留下的一堆 linux-image)

删除 KDE 我用的是 http://www.cnblogs.com/wangvsa/archive/2012/07/22/2603626.html 这个帖里提到的方法, 直接复制命令删除就行了, 不过粗看了一眼这一把应该也删掉了不少其他的依赖, 算了, 有要用到的时候再 apt-get install 好了, 另外也有类似 http://os.51cto.com/art/201001/176255.htm 这个帖里提到的用 apt-get --purge remove 移除某个核心库的方法, 但我没试.

删除多余 linux-image 用的是 http://blog.csdn.net/c9h8o4/article/details/6647220 这个帖里提到的方法, 简单实用. 用 dpkg --get-selections | grep linux-image 找到现在安装了哪些版本, 接着用 uname -a 看当前版本, 再通过 apt-get remove 的方式把不用的移除.

把多余的东西删掉后发现虚拟机对应的 .vdi 虚拟硬盘文件还是很大, 查了下说是在允许容量范围内, 动态扩展的 .vdi 容量会一直扩大而不会缩小, 必须手工做压缩. 搜了一堆方法后发现 http://www.kilobug.com/archives/624 这里说的最简单, 用了一下确实, 从之前的 14.1G 压缩到 5.67G (删了一陀东西也有帮助), 简单复述一遍:

1. 在虚拟机里把没用的磁盘空间置零 (这一步耗时比较长, 且没提示. 另外如果有权限问题记得前面加 sudo)

dd if=/dev/zero of=/zero.tmp
rm -f /zep.tmp

2. 关闭虚拟机

3. 执行压缩命令 (宿主机是 Win 或 Linux 都自行找 VboxManager 的路径)

VboxManager modifyhd /PATH_TO_VDI/name.vdi --compact

在搜索过程中发现其他几个看起来靠谱的链接, 记录供他人参考:
虚拟机是 Windows: http://city5.com/space/reannounce.asp?spaceid=344&announceid=517778
Linux 的复杂折腾法: http://cypromet.site90.net/blog/?p=41

读书笔记: 探索推荐引擎内部的秘密

看到别人推荐的, 在 IBM 发布的几篇推荐引擎的介绍, 不少干货, 先记录下

探索推荐引擎内部的秘密,第 1 部分: 推荐引擎初探
http://www.ibm.com/developerworks/cn/web/1103_zhaoct_recommstudy1/index.html?ca=drs-

探索推荐引擎内部的秘密,第 2 部分: 深入推荐引擎相关算法 – 协同过滤
http://www.ibm.com/developerworks/cn/web/1103_zhaoct_recommstudy2/index.html?ca=drs-

探索推荐引擎内部的秘密,第 3 部分: 深入推荐引擎相关算法 – 聚类
http://www.ibm.com/developerworks/cn/web/1103_zhaoct_recommstudy3/index.html?ca=drs-

// 现在写 blog 越来越不勤快了, 最近重看了一遍 Python 的官方文档, 又查漏补缺了好多点, 但是没做笔记, 怕是又会忘, 除了零散乱看还是要勤写, 自己重述一遍才算把看过的东西好好理解了, 之前写机器学习的东西又挖坑没填

为什么通过前端 .js 记用户日志会丢数据

在这个数据驱动的时代, 做什么事情没有数据光凭感觉是不可能了, 今年夏天开始接手新鲜事的策略, 先推日志的丰富化和标准化, 关于点击日志, 解决方法无外乎这么三种:

1. 在点击 url 串上带上丰富信息, 然后在后续处理的前端 (比如 nginx 或 apache) 上打印请求日志, 把请求日志汇总过滤得到想要的
2. 做点击跳转, 用户点击后先跳到自己服务器上, 然后由自己的服务器做重定向, 并记录这一次请求
3. 前端 JavaScript 监控用户鼠标行为, 并及时上报到服务器

这三种方法也分别有各自的优缺点, 当时分析的是

1. 这个必须要保证点击后还是跳到自己的服务器上, 否则跳出去的点击无法跟踪. 不太可能丢日志, 只是过滤会多道工序. 目测 Facebook 曾经是这样干的
2. 绝对完整的记录. 不过需要新增服务器响应跳转请求, 并且如果跳转服务挂了会让用户压根到不了 url 指向的地方. 目前所有的广告服务都是这样 (而且点击串加密), Google 的网页搜索很早就是这样, 百度跟 360 干上后也换成了这种. 根据度厂员工在新浪微博上跟别人的讨论, 即使是百度网页搜索那么大的量, 算上灾备最多 50 台跳转服务器可以搞定 (根据公开资料, 百度每天网页搜索量在十亿这个量级, 按搜索引擎页面点击率 30% 算, 每天至少三亿次点击跳转请求)
3. 可记录的东西非常多, 不仅仅是点击, 而且还有一些页面上的其他 js 行为 (如悬浮, js 展开元素等), 但是会丢 15%~20% 的数据. 跟 360 干架前百度的网页搜索用的这种方式, 刚看了下 FB 也是这种了

其他的优缺点都比较容易明白, 但是 js 模式会丢 15%~20% 的数据这个非常难理解, 之前我只听到 20% 这个比例, 但是没人告诉我为什么, 昨天跟死猫君说日志的时候他也提到他们那边用 js 记的日志也有 15% 的丢失率, 但是他也只是听说这个比例而不明白原理.

今天跟前端同学讨论, 终于搞懂了为什么是这样. 后端的思维是每发生一次事件就打一条日志, 所以极难发生日志丢失的问题. 而前端不能每发生一次事件就向服务器发请求打一次日志, 这样会带来很大的网络开销并拖慢用户的浏览器, 所以前端都是把要纪录的行为在用户端先缓存, 等积累够若干条或过了若干秒后才向服务器汇总上报, 如果在这个上报条件触发前浏览器崩溃掉, 那日志就没了, 或者用户关掉浏览器也会丢掉这部分数据 (据说有一些方式可以响应关闭事件并上报日志, 但具体方式不了解, 另外前端同学反馈 IE6 下丢数据现象更严重). 所以丢数据这事其实是用户流畅度体验和数据完备性的一个平衡, 如果让用户卡一点那丢失比例就低一点. 另外接 js 汇报日志的服务器压力也是一个要考虑的点, 因为如果真用 js 汇报, 那一定就不止点击这点数据了, 鼠标滚轮, 悬停等事件显然是能有都有, 服务器不一定扛的过来.

机器学习手记系列 3: 线性回归和最小二乘法

好几个月没再继续, 挖坑不填是不对的, 还是继续写手记.

线性回归

线性回归一般用来学习一维自变量和一维因变量之间的线性关系. 如果存在一维自变量 x, 同时还有一维因变量 y = f(x), 如果有一堆对不同 x 下 y 的观测值, 即 的观测对, 且如果 x, y 之间存在较明显的线性关系, 可以用 f(x) = a*x + b 这样的方程表示, 则可以用线性回归的方法学习出 a 和 b 的值, 同时估计这个拟合方法的误差 r.

扩展一下, 线性回归也可以指 y = a1*x1 + a2*x2 + ... + ak*xk + b 这样多维自变量和一维因变量之间的线性关系 (多项式里自变量的最高幂次都是 1), 同样也可以用回归的方式学出来里面不同的系数和常数项的值. 只有一维自变量的称之为一元线性回归, 否则是多元线性回归.

判断线性回归好坏, 一般就用平方误差和来描述, 其表达为 (f(x1)-y1)2 + (f(x2)-y2)2 + ... + (f(xk)-yk)2), 此值如果为 0 则说明自变量和因变量存在完全的线性关系, 否则是近似线性, 越小近似的越好. 这个东西看着有没有一点面熟? 其实就是机器学习手记系列 2: 离线效果评估里最后提到的 MSE 的非平均版本.

解方程法

假如输入样本存在绝对的线性关系, 即最后的误差为 0, 则问题变为解二元一次方程 (一元线性回归里的系数加常数) 或 N+1 元一次方程 (多元线性回归里 N 个自变量的系数加常数). 这没什么好说的, 直接对原输入直接求解就行了, 类似计算方法这样的课本上有的是解法, 做梯度下降或牛顿法乃至矩阵分解都可以解.

梯度下降法

考虑到绝大部分情况下不存在绝对的线性关系, 则问题可以变成怎么求平方误差和的最小值点. 如果是一元线性回归, 目标函数变为 g(a, b) = (f(x1)-y1)2 + (f(x2)-y2)2 + ... + (f(xk)-yk)2

我们的目标就是让这个目标函数值最小, 选定一组 的初始值, 然后求其梯度方向, 每次前进一个小步长, 再求梯度前进, 直到目标函数值不再下降, 说明我们已经走到了一个极值点附近, 终止迭代. 对一元线性回归, 梯度方向是对函数求偏导得到的向量方向.

另外需要注意的是, 梯度下降不一定能找到最优解, 可能会在某个局部最优解那陷进去就出不来了.

这部分更详细的推导请见参考资料里 “机器学习中的数学(1)” 一篇, 里面的公式和图做的很赞, 思路也比我清晰.

牛顿法

梯度下降一般遇到的问题迭代步长不好选, 选太小到极值点太慢, 搞太大又会在极值点附近时因为步长太大跳过去了.

牛顿法最大的贡献就是同时给出了梯度方向和迭代步长, 几乎是一步到位的求解. 方法同解方程一样, 对新的损失目标函数求解, 只是一次解可能还不够好, 需要多做几次迭代. 一般梯度下降可能需要上千轮的迭代, 而牛顿法几次迭代就能到极值点了.

最小二乘法

伟大的高斯同学提出并证明了最小二乘法是最好解答, 证明过程略… 直接看维基或百度百科上的原文吧 (数学不好伤不起).

应用

虽然这个方法看起来很简单粗暴, 但是很多时候变化确实就是线性的. 比如在很多论文和工业实践中, 大家认为同等质量的广告或搜索结果, 放在从上到下不同的位置上, 其点击率和位置的关系符合线性关系, 即 ctr(rank) = a*rank + b.

在六月的一次随笔杂记里, 提到了这样的问题:

如下式子里不同的阿拉伯数字只是一个符号, 实际表示的可能是其他数字
967621 = 3
797321 = 1
378581 = 4
422151 = 0
535951 = 1
335771 = 0

根据上述式子, 判断下式等于?
565441 = ?

假设每个式子最后做的都是加法, 并把字符 0~9 映射到 x0~x9, 则统计不同字母出现的次数就可以列线性返程, 可以将第一个式子表示为

x0*0 + x1*1 + x2*1 + x3*0 + x4*0 + x5*0 + x6*2 + x7*1 + x8*0 + x9*1 = 3

其他类推. 对这堆式子求解就可以得到不同数字对应的真实数值, 可以得到 565441 = 1. // 具体代码和方法下次给出

参考资料

* Wiki Least squares: http://en.wikipedia.org/wiki/Least_squares
* Wiki Mean Squared Error: http://en.wikipedia.org/wiki/Mean_squared_error
* 中文维基 最小二乘法: http://zh.wikipedia.org/wiki/%E6%9C%80%E5%B0%8F%E4%BA%8C%E4%B9%98%E6%B3%95
* 百度百科 线性回归: http://baike.baidu.com/view/449540.htm
* 百度百科 最小二乘法: http://baike.baidu.com/view/139822.htm
* 人人上的日志 幼儿园的题目和机器学习的关系: http://blog.renren.com/share/30314/13432269197
* 机器学习中的数学(1): http://www.cnblogs.com/LeftNotEasy/archive/2010/12/05/mathmatic_in_machine_learning_1_regression_and_gradient_descent.html

// 本文开写于 9.24, 拖到 10.26 才马马虎虎完成, 最后那个题的解也没写, 各种错乱后续再修改或补充吧

Win7 图标异常解决

上周某次有程序运行到一半挂了, 强制退出终止进程后屏幕颜色异常, 继续杀 explorer 并重启后恢复正常, 但是有程序图标挂了, 类似这样:

(图片来自百度知道, 后续答案也来自百度知道: http://zhidao.baidu.com/question/197765345.html)

百思不得其解, 最后在上面那个知道问答的非最佳答案里找到解决方法:

0. 先关掉其他的东西避免误伤
1. 打开一个命令行窗口
2. 在任务管理器里杀掉 explorer 进程
3. 在命令行里干掉 iconcache.db
* 注: cd 的 /d 参数可以改变驱动器, del 的 /a 参数可删除隐藏文件
cd /d %userprofile%AppDataLocal
del IconCache.db /a
exit

4. 重启 explorer 进程, 恢复正常

无聊理工男在面对浪漫时干的二逼事

今天在 http://zhoucaiqi.com/emlog/guoke-website.html 上看到对一个网站的介绍:

这网站的域名相当伤感,内容也很伤感。
整个网站只有一张静态网页。这网页只有一张孤单的图片,以及冷寂的一两句话。

里面说的是这个 http://www.guoke.com/ 网站, 点过去看了下, 确实很孤单落寞的感觉.

前面是浪漫, 下面是无聊理工干的二逼事.

先是 NetMD 同学说多好的域名, 果壳没买下来, 然后死猫同学矫情了下后说这些历史图是怎么截到的, 接着我无聊去看了下 whois 的记录, 找到如下信息:

Domain name: guoke.com

Administrative Contact:
Hu Yanlin
Hu Yanlin (admin@doeasy.com)
+86.1068469837
Fax: +86.1068467228
2-1-2105, No.27 Zengguang Road
Haidian Dist.
Beijing, CN 100048
CN

继续看 doeasy.com 这是个什么网, 发现是域名贩子, 立马觉得 guoke.com 是不是也是域名贩子弄的, 然后一开始那个文章只是在给这个域名做推广. 不过要真是域名贩子, 能做到这样也挺不错了, 又仔细看了下一开始那个帖, 发现是在 Twitter 上 fo 的一个深圳的 IT 工作者的个人博客, 应该是真的默默关注了这么久, 还是一个温暖的故事吧.

事情还没完, 关于 guoke.com 拥有者的地址, 好奇看了下是海淀区, 那个 Zengguang Road 是个什么地方呢? 用拼音打了下居然第一反应是 增广路, 这… 我好像图论学的也没有那么好吧, 再找了下是 增光路, 死猫君表示难怪这么熟, 原来就在他现在住的地方旁边.

无聊理工 + 2B 完毕, 随手一记.

2012全球架构师峰会参会简记

8.10 ~ 8.12 在深圳参加全球架构师峰会 (http://www.archsummit.com/), 回来也十来天了, 先把回来后记在 evernote 里的简记发下, 详细的后面跟着幻灯片展开下


公司定的机票时间都太晚了, 走的时候上飞机没晚点, 起飞晚了一个多小时, 到深圳都晚上十一点, 到酒店也半夜一点
住的略偏, 在小梅沙, 这酒店算一般水平吧, 可以理解成规模大点的农家乐
吃的凑合, 会务的自助餐还是挺不错的, 就是人太多, 要么早点要么晚点, 不然排队排死人. 茶点我就第一天提前去偷吃了点, 剩下的都懒得排队了
会场是万科的总部, 很多地方设计的很精妙, 但是大梅沙离市区还是太远太远了


组织的还是挺不错的, 就是有时候几个分会场都想去, 无法分身
同声传译很赞, 也没有很外行翻出莫名其妙的句子来, 前面坚持听了几场英文的, 最后一场借了个传译器果然还是听中文要顺畅很多
腾讯是主赞助商, 发的东西很多, 公仔和衣服没抽到和领到, 其他的资料倒是都拿点, 腾讯在这方面的宣传做的挺好, 给的东西也比较下血本
其他有很多硬件 (比如 SanDisk 的企业用 SSD) 或平台型 (比如云存储) 的赞助商, 我不懂, 就随便看了看展台. 倒是有很多开发平台的赞助商, 比如天翼, 还有海豚浏览器也是赞助商, 我还没怎么弄明白开发平台这个生态圈怎么玩, 果然落伍了


大会场的几个 topic, Pinterest 那个没赶上, 老外吐槽中国网络状况倒是吐的挺狠也挺实在的, 包括多网不通, 还有 GFW, 只是八线机房是个什么情况, 电信/联通/移动/教育网/还有四个有啥?
搜索那个 session 讲的都比较虚, 扯了些概念, 搜狗的提出抓别人的搜索结果 (参考资料: 孟学一有关暗网数据挖掘的书), 一淘讲了些干货, 不过总感觉也没啥特别的, 是因为别的人都没做过或看过这么大的搜索引擎, 所以觉得有很爽的干货么?
大数据那个 session 干货比较多, EMC 上来介绍了一些基于 Hadoop 或 Map/Reduce 的框架, 都很赞, Yahoo 的 Nova 自动化调度数据和任务也做的很好, LinkedIn 对数据的处理方式也非常值得参考, Pinterest 最后讲那个数据库分片, 真的是把简单做到极致, 能不复杂绝不复杂, 能用钱搞定的事情没必要省那几台服务器钱结果把系统搞的巨麻烦


Day1
All: http://vdisk.weibo.com/s/ajLUe

Day2
上午: http://vdisk.weibo.com/s/au-u-
下午主会场 (海量数据): http://vdisk.weibo.com/s/av8ue
下午分会场 1 (移动互联网): http://vdisk.weibo.com/s/aveIJ
下午分会场 2 (安全): http://vdisk.weibo.com/s/av5bn

Day3
All: http://vdisk.weibo.com/s/aAaQ3/1345032030

Chrome 多用户分别建快捷方式

Chrome 从今年年初开始在 Dev 版支持多帐号, 当时用的很爽. 最近 Dev 版解析 .js 老出错, 导致无法正常上人人和看视频, 严重影响工作和娱乐, 响应大家号召改回 stable, 结果发现多帐号是支持的, 但是怎么也找不到如何建特定帐号的快捷方式, 网络上搜的方法都只对老版本的 dev 分支有效.

今天找了另一台机器, 上面有多用户且分开建了快捷方式的 Chrome Dev, 看了下快捷方式, 把快捷方式的目标改为下面这样就行了 (红色是要添加的)

C:\Users\snoopy\AppData\Local\Google\Chrome\Application\chrome.exe –profile-directory=”Default”
C:\Users\snoopy\AppData\Local\Google\Chrome\Application\chrome.exe –profile-directory=”Profile 1″

读完了数学之美

正如上一篇日志中提到的, 最近买了吴军博士数学之美并利用晚上的时间在看. 粗粗的过了一遍, 把以前很多没明白的东西给理顺了下, 具体的一些数学推导没来得及去验证. 书的后半部分感觉比较凌乱和随意, 不过还是值得购买去支持的, 如果大家都不买书, 那以后也会越来越难读到经典之作.

读的过程中用手机简单记了些简单的笔记, 现在回头想想, 再过一下:

方法论

1. 做事要简洁高效: 简单粗暴的方法, 只要是对的那就应该这么做, 与其花非常大的代价弄一个貌似完美的系统, 最后还不一定能保证结果, 还不如花很短的时间去做一个能达到 90% 性能的可用系统, 并用若干个 90% 性能的系统组合起来达到完美效果. 这一点也是我非常认可和坚持的, 在团队里也需要贯彻下去.

2. 凡事都需要可解释: 做策略做算法, 一定要对每个 case 给出合理的解释, 这样才能知道怎么去改进. 吴军在书里举的例子是说搜索, 一开始要用简单高效的系统和特征来保证鲁棒性和可调试性, 其实在计算广告和推荐系统里也是一样, 只是我们现在总会一上来就弄很多复杂的上去, 导致很难调试和追查, 最后就一把烂账怎么也算不清. 这点上自己一直做的不好, 要好好注意.

3. 真理应该拥有简单漂亮的描述: 自然真理的本质描述往往是很简单的很漂亮的, 如果搞的太复杂, 就不太对头, 多半是方向都错了. 书里的例子是说描述太阳系的行星运动, 地心说的模型需要用 40 层圆周修正, 日心说则可以降低到 8-10 个圆周修正, 但最后的真理却是一个椭圆方程就完美解释.

具体案例

1. 新闻/文本分类中的加权. 在做余弦相似度计算时, 需要考虑位置加权, 词性加权等影响. 对于位置加权, 一般的思路都是对树形结构做加权, 比如普通文章的标题/摘要等, 网页则一般是 HTML 语法树的加权, 实际上 Google 在很早之前就开始模拟网页渲染, 做物理位置的加权, 而这一套网页渲染的技术, 用来开发 Chrome 不是正好? 而且随着 Chrome 的市场占有率上升, 也可以逼迫高质量网站的网页代码会更标准, 至少是可以兼容 Chrome 的标准, 这样 Google 可以获得更准确的页面渲染效果并用于权重计算, 现在很多别的公司也开始关注浏览器, 但是不知道有没有想到这一层用法. 词性加权这又回到 NLP 的基础建设上, 果然做互联网, 要做精做深, NLP 是个绕不开的大坑, 就算数学模型如此优雅和有用, 但还是需要有基础数据才能去计算.

2. Logistic Regression 在工业界的广泛应用. 自己好像在生产环境中就用过这一种模型, 接触过线性回归和 Naive Bayes, 但是都没能去深入理解, 其他 boosting 和 SVM 等方法, 每次都是听了个大概, 一直没空去试. 根据自己的经验, 以及吴军的说法, LR 最大的优点是线性叠加, 皮实耐操以及水平扩展性好, 这几个都挺符合方法论的. 不过在点击率非常低的环境下, 要用好 LR 确实很难, 吴军说的是特征权重在 [-6, +6] 区间才有意义, 按 Sigmod 变换函数 1/(1+exp(-z)) 计算, -6 对应的也不过是 0.247%, 这个点击率在搜索广告以外的很多地方还是挺难达到的, 加上位置, beta0 等修正后可以让值很接近, 但是精度又受很大影响, 之前想过把某个小区间做放大处理, 但是一直没想清楚到底要怎么扩, 怎么能维持相对关系并可以还原, 求指点.