Nov 16
与某供应商对接的时候,要求用他们的RSA公钥加密,抛过来一个 RSAUtil.java ,核心代码大概是这样的:

public byte[] encrypt(byte[] data, PublicKey pk) throws Exception {
    Cipher cipher = Cipher.getInstance("RSA", new org.bouncycastle.jce.provider.BouncyCastleProvider());
    cipher.init(Cipher.ENCRYPT_MODE, pk);
    byte[] raw = new byte[128]; //cipher.getBlockSize() = 128
    cipher.doFinal(data, 0, data.length, raw, 0);
    return raw;
}


RSA什么的,用php来做不要太简单,顺手就能写出来:

function rsa_encrypt($plain_text, $public_key_path)
{
    $public_key = openssl_pkey_get_public(file_get_contents($public_key_path));
    openssl_public_encrypt($plain_text, $encrypted, $public_key);
    return bin2hex($encrypted);
}

function rsa_decrypt($encrypted, $private_key_path)
{
    $private_key = openssl_pkey_get_private(file_get_contents($private_key_path));
    openssl_private_decrypt(hex2bin($encrypted), $plain_text, $private_key);
    return $plain_text;
}


结果果然不行,发过去以后,对方表示无法解密,而我没有对方的私钥,不好验证,没办法,只能自己动手,造一对rsa密钥:

引用
$ openssl genrsa -out test.pem 1024
$ openssl rsa -in test.pem -pubout -out test_public.pem


试了下,确实和 java 的结果不互通。不过在测试过程中发现一个现象:java生成的加密串总是一样的,而php生成的加密串总是不一样的。google搜了一下"php openssl_public_encrypt different everytime", Stack Overflow 的解释是,PHP的 openssl_public_encrypt 默认使用 PKCS#1 算法,引入随机数,用于防止流量探测(频率分析、密文匹配什么的,我就不懂了)。

所以很显然,Bouncy Castle 没有使用 PKCS#1 算法,放狗搜到官方文档说,Cipher.getInstance("RSA", "BC") ,第一个参数 RSA 相当于 "RSA/NONE/NoPadding" (当然也可以指定 RSA/NONE/PKCS1Padding )。

看了下 php的openssl_public_encrypt文档,可以给第四个参数“padding”指定不同的值,例如 OPENSSL_NO_PADDING ,但是试了下,发现直接失败了,只好再放狗,竟然搜到了 php的bugreport,还好第一个回复就说明了原因:需要手动用 ASCII 0 填充到 blocksize 才行(当然rsa并不禁止使用其他value,主要是加解密双方要约定好)。

验证了一下,用 OPENSSL_NO_PADDING  能够正常解密 java 生成的密文,并且在明文前面填充了若干 ASCII 0 ,补全到128字节,就此解决问题:

function rsa_encrypt($plain_text, $public_key_path)
{
    $public_key = openssl_pkey_get_public(file_get_contents($public_key_path));
    openssl_public_encrypt(str_pad($plain_text, 128, "\0", STR_PAD_LEFT), $encrypted, $public_key, OPENSSL_NO_PADDING);
    return bin2hex($encrypted);
}

function rsa_decrypt($encrypted, $private_key_path)
{
    $private_key = openssl_pkey_get_private(file_get_contents($private_key_path));
    openssl_private_decrypt(hex2bin($encrypted), $plain_text, $private_key, OPENSSL_NO_PADDING);
    return ltrim($plain_text, "\0");
}


Jul 1

ucloud体验报告 不指定

felix021 @ 2013-7-1 02:02 [IT » 其他] 评论(3) , 引用(0) , 阅读(21786) | Via 本站原创
UPDATE@2013.08.04 搞到了一批折扣邀请码,有兴趣的同学(最好是带项目的团队、公司等)可以联系我。

最近弄了一台 ucloud.cn 的vps。准确地说应该是云主机,跟我在别处买的vps的确是有些不同的地方。

首先是注册,ucloud对密码的安全性要求太高了。其实很早之前就拿到邀请码试用过三天,但是由于对密码的要求过于复杂,刚开始几次,每次登陆之前都得重置密码,比较蛋疼;后来终于记住了,相当不容易。

然后是选配置。ucloud的最低配置是单核、2G内存、2mbps单线,显然不是面向个人vps玩家了,不过对于创业公司什么的倒是很合适。对比了一下国内另外两家云主机的同样配置,价格上也还是挺有优势的。选配置的时候有个“高性能磁盘”选项很有意思,目测是为了数据库之类对磁盘IOPS要求比较高的场合设置的,勾上了价格也没多大变化。

最终我选择的配置是双核、2G、20GB数据盘、4M双线,2700/yr。

开通主机以后就是选择系统。我图省事选了个ubuntu 12.04 64bit的。本来还做好准备像我的个人vps那样,vnc连上去在命令行下通过mount上去的iso安装,结果发现等了一会儿直接就可以开始用了,看起来应该是像openvz方案一样事先准备好了对应的template改改配置就能上。而且非常贴心的一点是,apt的默认源是ucloud自建的同步源,apt-get update和install的时候就很爽~其他的OS没试过,不过去mirror看了下,除了ubuntu,还有debian、fedora、centos等发行版的源,甚至还有个10gen(也就是mongodb他们家)的源。

进入后台管理看了下,一眼就能认出浓浓的bootstrap的味道,感觉挺无趣的,好歹用个Flat UI什么的换换小清新的口味嘛-。-  不过后台功能还是挺赞的,尤其是与 upyun、dnspod 的战略合作,可以绑定他们两家帐号,方便管理。至于upyun/dnspod的牛逼之处就不用多说了,这三家能合力打造这样的平台,前景我非常看好。

开通的时候我选择的是华东双线机房,所以给分配了2个ip,一个电信一个联通,因为域名是托管在dnspod,可以为不同请求线路返回合适的ip,很给力。ping了一下,延迟只有11ms,相当不错。ssh登上去看了下,ifconfig只看到了个内网ip,还觉得挺神奇的。后来在ucloud的主页看到,这是他们的“弹性IP”解决方案,ip不是直接绑定在vps的网卡上。设想,对于线上4台年付费的web机器进行负载均衡,某一台down了,可以马上把另一个按小时付费的备机开起来,把ip切过去,这样即减少了故障时间,又相当节省,貌似不错。

所谓“云主机”,我觉得跟传统vps/服务器的主要区别有2个:一个是可以按需选择合适的配置,并且此后还可以不断调整升级且代价很小;另一个就是底层存储是基于网络的,所在服务器挂掉也不用担心,换个地方再启动起来就好了。

去年12月在杭州参加SegmentFault举办的Hackathon的时候曾经试用过XX云的主机,他们家的特色是有自建的BGP骨干网,网络比较给力;但问题是,XX云主机的磁盘IO烂到一定境界,实在是……后来听说他们是直接用NFS作为底层存储,以及看到各种吐槽他们家IO的……

所以这次用ucloud的时候就特意关注了下磁盘性能,跑点数据列出来附在后面供参考,可以看出性能相当不错,已fio的数据为参考,顺序读取697M,顺序写入419M,随机读取 6245 IOPS,随机写入 309 IOPS。其中随机写入偏弱,可能是多备份网络延迟的原因吧,不知道选择“高性能磁盘”效果会怎样,但是就算是309 IOPS,也比服务器用的机械硬盘快多了,跟别说被甩开n条街的XX云了……很好奇他们家这个是怎么实现的,真希望ucloud的技术团队可以分享一下经验~

至于ucloud的其他方面,因为用的时间还比较短,体验不多,没什么可说的,就是总体感觉良好。ucloud提供的这项服务,对于创业团队什么的来说,的确可以算是最合适的选择了。


下附磁盘测试数据:

TEST#1 dd写入
引用
$ dd if=/dev/zero bs=1M count=4096 of=test
4096+0 records in
4096+0 records out
4294967296 bytes (4.3 GB) copied, 15.1328 s, 284 MB/s


TEST#2 hdparm -tT
引用
$ for i in 1 2 3; do sudo hdparm -tT /dev/vdb; done

/dev/vdb:
Timing cached reads:  9574 MB in  2.00 seconds = 4790.56 MB/sec
Timing buffered disk reads: 1714 MB in  3.02 seconds = 568.37 MB/sec

/dev/vdb:
Timing cached reads:  10018 MB in  2.00 seconds = 5013.55 MB/sec
Timing buffered disk reads: 1840 MB in  3.01 seconds = 611.33 MB/sec

/dev/vdb:
Timing cached reads:  9574 MB in  2.00 seconds = 4792.34 MB/sec
Timing buffered disk reads: 1908 MB in  3.00 seconds = 635.80 MB/sec


TEST #3 fio random-read
引用
$ cat random-read-test.fio   
[random-read]
rw=randread
size=1g
directory=/home/felix021/test/

$ fio random-read-test.fio
random-read: (g=0): rw=randread, bs=4K-4K/4K-4K, ioengine=sync, iodepth=1
fio 1.59
Starting 1 process
random-read: Laying out IO file(s) (1 file(s) / 1024MB)
Jobs: 1 (f=1): [r] [100.0% done] [26789K/0K /s] [6540 /0  iops] [eta 00m:00s]
random-read: (groupid=0, jobs=1): err= 0: pid=10676
  read : io=1024.0MB, bw=24980KB/s, iops=6245 , runt= 41976msec
    clat (usec): min=77 , max=35439 , avg=155.44, stdev=237.39
    lat (usec): min=78 , max=35440 , avg=155.82, stdev=237.39
    bw (KB/s) : min=18384, max=28256, per=100.22%, avg=25035.02, stdev=1702.27
  cpu          : usr=3.42%, sys=23.48%, ctx=262433, majf=0, minf=24
  IO depths    : 1=100.0%, 2=0.0%, 4=0.0%, 8=0.0%, 16=0.0%, 32=0.0%, >=64=0.0%
    submit    : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
    complete  : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
    issued r/w/d: total=262144/0/0, short=0/0/0
    lat (usec): 100=3.05%, 250=93.84%, 500=2.44%, 750=0.22%, 1000=0.10%
    lat (msec): 2=0.23%, 4=0.07%, 10=0.05%, 20=0.01%, 50=0.01%

Run status group 0 (all jobs):
  READ: io=1024.0MB, aggrb=24980KB/s, minb=25579KB/s, maxb=25579KB/s, mint=41976msec, maxt=41976msec

Disk stats (read/write):
  vdb: ios=260955/11, merge=0/10, ticks=25956/396, in_queue=25972, util=61.22%


TEST #4 fio random-write
$ cat random-write-test.fio
[random-write]
rw=randwrite
size=1G
directory=/home/felix021/test/

$ fio random-write-test.fio
random-write: (g=0): rw=randwrite, bs=4K-4K/4K-4K, ioengine=sync, iodepth=1
fio 1.59
Starting 1 process
random-write: Laying out IO file(s) (1 file(s) / 1024MB)
Jobs: 1 (f=1): [w] [92.5% done] [0K/1429K /s] [0 /348  iops] [eta 01m:09s]
random-write: (groupid=0, jobs=1): err= 0: pid=10733
  write: io=1024.0MB, bw=1236.3KB/s, iops=309 , runt=848202msec
    clat (usec): min=1 , max=1101.4K, avg=3231.07, stdev=10586.16
    lat (usec): min=1 , max=1101.4K, avg=3231.53, stdev=10586.42
    bw (KB/s) : min=  14, max=397248, per=95.34%, avg=1178.40, stdev=9976.63
  cpu          : usr=0.19%, sys=0.75%, ctx=49240, majf=0, minf=24
  IO depths    : 1=100.0%, 2=0.0%, 4=0.0%, 8=0.0%, 16=0.0%, 32=0.0%, >=64=0.0%
    submit    : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
    complete  : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
    issued r/w/d: total=0/262144/0, short=0/0/0
    lat (usec): 2=0.01%, 4=0.06%, 10=54.82%, 20=25.75%, 50=2.45%
    lat (usec): 100=1.28%, 250=0.84%, 500=0.36%, 750=0.08%, 1000=0.02%
    lat (msec): 2=0.04%, 4=0.05%, 10=0.29%, 20=8.87%, 50=4.58%
    lat (msec): 100=0.47%, 250=0.02%, 500=0.01%, 750=0.01%, 1000=0.01%
    lat (msec): 2000=0.01%

Run status group 0 (all jobs):
  WRITE: io=1024.0MB, aggrb=1236KB/s, minb=1265KB/s, maxb=1265KB/s, mint=848202msec, maxt=848202msec

Disk stats (read/write):
  vdb: ios=1/145156, merge=0/13152, ticks=12/3297360, in_queue=3297220, util=99.78%

TEST #5 fio sequence-read
引用
$ cat read-test.fio
[random-read]
rw=read
size=1g
directory=/home/felix021/test/

$ fio read-test.fio
random-read: (g=0): rw=read, bs=4K-4K/4K-4K, ioengine=sync, iodepth=1
fio 1.59
Starting 1 process
random-read: Laying out IO file(s) (1 file(s) / 1024MB)
Jobs: 1 (f=1)
random-read: (groupid=0, jobs=1): err= 0: pid=10798
  read : io=1024.0MB, bw=697191KB/s, iops=174297 , runt=  1504msec
    clat (usec): min=0 , max=16300 , avg= 4.73, stdev=97.89
    lat (usec): min=1 , max=16300 , avg= 4.95, stdev=97.89
    bw (KB/s) : min=615400, max=779152, per=99.97%, avg=696994.67, stdev=81877.45
  cpu          : usr=11.44%, sys=57.75%, ctx=3787, majf=0, minf=26
  IO depths    : 1=100.0%, 2=0.0%, 4=0.0%, 8=0.0%, 16=0.0%, 32=0.0%, >=64=0.0%
    submit    : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
    complete  : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
    issued r/w/d: total=262144/0/0, short=0/0/0
    lat (usec): 2=66.20%, 4=31.16%, 10=0.58%, 20=0.15%, 50=0.28%
    lat (usec): 100=0.63%, 250=0.89%, 500=0.07%, 750=0.01%, 1000=0.01%
    lat (msec): 2=0.01%, 4=0.01%, 10=0.01%, 20=0.01%

Run status group 0 (all jobs):
  READ: io=1024.0MB, aggrb=697191KB/s, minb=713924KB/s, maxb=713924KB/s, mint=1504msec, maxt=1504msec

Disk stats (read/write):
  vdb: ios=3697/0, merge=0/0, ticks=1280/0, in_queue=1268, util=74.56%


TEST #6 fio sequence-write
引用
$ cat write-test.fio
[random-read]
rw=write
size=1g
directory=/home/felix021/test/

$ fio write-test.fio
random-read: (g=0): rw=write, bs=4K-4K/4K-4K, ioengine=sync, iodepth=1
fio 1.59
Starting 1 process
Jobs: 1 (f=1): [W] [-.-% done] [0K/409.3M /s] [0 /102K iops] [eta 00m:00s]
random-read: (groupid=0, jobs=1): err= 0: pid=10816
  write: io=1024.0MB, bw=419934KB/s, iops=104983 , runt=  2497msec
    clat (usec): min=0 , max=10136 , avg= 7.71, stdev=123.62
    lat (usec): min=0 , max=10136 , avg= 7.98, stdev=123.64
    bw (KB/s) : min=177498, max=650096, per=110.68%, avg=464776.50, stdev=202324.17
  cpu          : usr=14.74%, sys=57.69%, ctx=199, majf=0, minf=27
  IO depths    : 1=100.0%, 2=0.0%, 4=0.0%, 8=0.0%, 16=0.0%, 32=0.0%, >=64=0.0%
    submit    : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
    complete  : 0=0.0%, 4=100.0%, 8=0.0%, 16=0.0%, 32=0.0%, 64=0.0%, >=64=0.0%
    issued r/w/d: total=0/262144/0, short=0/0/0
    lat (usec): 2=0.08%, 4=36.39%, 10=58.08%, 20=4.91%, 50=0.38%
    lat (usec): 100=0.07%, 250=0.01%, 500=0.01%, 750=0.01%, 1000=0.01%
    lat (msec): 2=0.01%, 4=0.01%, 10=0.04%, 20=0.01%

Run status group 0 (all jobs):
  WRITE: io=1024.0MB, aggrb=419934KB/s, minb=430012KB/s, maxb=430012KB/s, mint=2497msec, maxt=2497msec

Disk stats (read/write):
  vdb: ios=0/1382, merge=0/11, ticks=0/219176, in_queue=246612, util=77.43%

Mar 24
原文: Reed–Solomon codes for coders
参考: AN2407.pdf
WIKI: 里德-所罗门码
实现:Pypi ReedSolo

#译注:最近看到了RS码,发现还挺有意思的,找了一些资料学习了下,发现对于程序员来说,从这篇看起会比较容易。看完以后想着翻译一下试试,看看自己到底看懂了多少,于是就有了这篇。本文有部分错误,以及一些排版不对的地方,有兴趣的还是看原文更好:)

为程序员写的Reed-Solomon码解释

Reed-Solomon纠错码(以下简称RS码)广泛用于数据存储(如CD)和传输应用中。然而,在这些应用中,码字是藏在了电子设备里,所以无法一窥它们的模样以及它们是如何生效的。有些复杂的条形码设计也采用了RS码,能够暴露出所有的细节,对于想要获得这种技术如何生效的第一手技术的爱好者,这是一种很有趣的方式。

在这篇文章里,我是试图从程序员的视角(而不是数学家的视角)来介绍RS码的基本原理。我会用以当下流行的QR码作为例子来介绍。我选择了Python(主要是因为写出来的代码看起来整洁美观),但是我也会介绍一些不那么显而易见的Python特性,以便那些不熟悉Python的人也能看懂。里头涉及到的数学知识对读者有一定要求,并且一般是大学才教授的,但是应当能让对高中代数掌握较好的人看懂。

内容:
1 QR码结构
1.1 掩码
1.2 格式信息
1.3 数据
1.4 解码
2 BCH码
2.1 BCH错误检测
2.2 BCH纠错
3 有限域理论
3.1 乘法
3.2 基于对数的乘法
3.3 除法
3.4 多项式
4 RS码
4.1 RS生成多项式
4.2 RS编码
4.3 伴随式(Syndrome)计算
4.4 消除(erasure)纠正
4.5 错误(error)纠正
4.6 消除和错误纠正
Mar 23
#Update@3.23 23:05 早上9点之前密码重置功能被Apple暂停了,下午根据CNBETA的消息漏洞已经修复。

今天一个朋友的苹果帐号密码被修改,iMac、iPad、iPhone上的所有资料都被抹除,iMac被锁定无法登陆,几百GB的资料瞬间化为乌有,怀疑是同行恶意行为。悲剧详情可到v2ex的这个帖子凭吊。

根据提示这个帖子描述漏洞详情的两个连接 国外版 国内版 里提到的方法,我用自己的apple id和新注册的apple id验证,的确存在

重置密码过程异常简单(使用chrome):

1. 登录https://iforgot.apple.com/iForgot/iForgot.html,填写指定的apple id,点击下一步
2. 选择验证方法—— 回答安全提示问题,点击下一步
3. 填写apple id注册时填写的出生日期,先不提交
4. 打开开发者工具,在elements处搜索"security"字样(某个hidden的input的value),改成null
5. 提交,进入密码重置页面,输入新密码,重置完成。

因此强烈建议立即修改自己apple id的生日

修改流程:

1. 打开 https://appleid.apple.com ,登陆
2. 点击左边的“帐户和密码安全”
3. 填写安全提示问题的答案,并点击继续
4. 在新页面里修改生日。

应该朋友要求已将操作视频录像,有兴趣的可以在 优酷 观看,或者从 百度网盘微云 下载,瞧瞧看看苹果的服务有多么不堪。
Mar 5

记坑 不指定

felix021 @ 2013-3-5 15:39 [IT » 其他] 评论(4) , 引用(0) , 阅读(6691) | Via 本站原创
1. Python的除法

线上有一个简单的函数,运行一年多了,作用是把"分"表示的字符串转成"元":
def fen_to_yuan(str_fen):
    fen = int(str_fen)
    return '%d.%02d' % (int(fen / 100) , fen % 100)

看起来也的确是没有什么问题,但是就这么简单的一点代码,它还是错了,原因是fen_to_yuan("-270")居然返回了"-3.30"!坑爹啊。简单测试一下,原来是这样:
引用
>>> -270/100
-3
>>> -270%100
30

所以只好蛋疼地修改成这样:
def fen_to_yuan(str_fen):
    fen = int(str_fen)
    sign, fen = fen < 0 and ('-', -fen) or ('', fen)
    return sign + '%d.%02d' % (int(fen / 100) , fen % 100)


2. 线上有一个脚本,要得到上个月的月份,bash的实现就是
引用
date -d "-1 month $date" +%m

看起来也的确是没有什么问题,但是就这么简单的一点代码,它还是错了,原因是对于10月31号居然返回了10!坑爹啊。简单测试一下,原来是这样:
引用
$ date -d "-1 month 20121031" +%Y-%m-%d
20121001
$  date -d "-1 month 20130331" +%Y-%m-%d
20130303

也就是说,先把月份减一,然后检查日期,超过当前月,再向上修正月份,再向上修正年份。

所以只好蛋疼地修改成这样:
引用
date -d "-1 month ${date:0:6}01" +%m

#update: @whusnoopy补充说 向后查看1个月也会有这样的情况,总之记得用月来算是有坑的,千万注意。

3. crontab的小坑

crontab默认是不会读取.bashrc,需要自己去source一下.bashrc,并且不支持像bash一样用反引号来启动一个子命令(这个结论是错的,是因为%前面忘了加斜杠)。这个不展开细说了,有兴趣的试试吧。
Mar 3

常用find + grep查找封装 不指定

felix021 @ 2013-3-3 23:45 [IT » 其他] 评论(0) , 引用(0) , 阅读(1923) | Via 本站原创
看源码的时候经常要在某一类文件里面grep一些内容,用标准的find + grep写起来很辛苦:

$ find -name "*.c" -exec grep {} -Hne "hello world" \;

所以简单封装了下,保存成 ~/bin/xgrep 然后把 ~/bin 加入到 PATH 里去,以后就只需要

$ xgrep \*.c "hello world"    #注意这个 \*.c 里可以用的是*和?的通配符,不是正则

#!/bin/bash

if [ -z "$1" -o -z "$2" ]; then
    echo "Usage: xgrep FilePattern WordPattern"
    exit
fi

filepat="$1"
greppat="$2"

shift
shift

set -x

find -name "$filepat" -exec grep {} -Hne "$greppat" $* \;

#后来才想起grep其实有个--exclude=PATTERN(可以去掉find),但是已经这么用了挺久,习惯了。。。
Aug 22

windows下的批量重命名 不指定

felix021 @ 2012-8-22 22:23 [IT » 其他] 评论(2) , 引用(0) , 阅读(3913) | Via 本站原创
可能很多同学不知道Windows是自带这个功能的。至少从WinXP开始就有。操作要领:

0. 批量重命名的文件应该在一个文件夹内。

1. 选择所有需要被重命名的文件。全选(CTRL+A),或拖动/用shift选择选择一个区间,或按住CTRL一个一个点,都可以。

2. 使用鼠标右键选择你希望被重命名的第一个文件,输入新的文件名。注意,新的文件名如果不带编号(如a.txt),那么会按顺序改成 a.txt, a (1).txt ... a (5).txt,如果带编号(如 b (3).txt,注意编号只能用圆括号包起来),则编号会按顺序增加:b (3).txt, b (4).txt ... b (11).txt。

3. 回车,OVER。

功能很贴心,但是半残,有时候不满足要求,在没有安装额外的语言的情况下,可以用类似如下的vbs来应急:
Set a= WScript.createObject("WScript.Shell")
WScript.sleep 1000
For i = 1 to 23
  j = i
  If i < 10 Then
    j = "0" & i
  End If
  a.sendkeys "{DOWN}{F2}"    '向下,F2(重命名)
  a.sendkeys "TBBTs02e" & j  '文件名, win7下就不用再  & ".rmvb" 了,但是xp需要
  a.sendkeys "~"            '回车
  WScript.sleep 200
Next
May 16

说说机器学习 不指定

felix021 @ 2012-5-16 00:29 [IT » 其他] 评论(0) , 引用(0) , 阅读(3984) | Via 本站原创
为了论文搞了把机器学习的东西,虽然了解得非常肤浅,但是窥探了一下这个领域也还是很有收获。

对于遇到的问题,传统的思路是通过建模,然后使用对应的算法予以解决。但是对于很多问题,建模本身是不实际的,例如语音识别、计算机视觉等等。而机器学习算法的思路则不同,通过对现有的数据进行分析和统计,得到一组参数来逼近真实的模型,从而能够处理未知的数据。

我的论文里主要是使用SVM来解决简单的二分类问题。SVM,Support Vector Machine的简写,也就是“支持向量机”,很早以前有“听说过”,但是之前完全没有概念。这次在yihong妹妹的推荐下,看了faruto大牛写的《SVM入门精品系列讲解》,能大致在原理上明白svm分类的机制。之所以称faruto为大牛,主要是因为这个讲解系列非常地浅显易懂,没有卖弄玄虚,即使是我这样没学好数学的人,也能够非常容易地弄懂。

由我来归纳的话,svm的基本思路应该是,将每个样本x当作一个N维向量(也就是N维空间中的一个点),通过某种方式找到该空间中的一个超平面w * x + b = 0,将样本分成两类。例如二维空间中的点,可以用一条直线分成两类,而三维空间的点,可以用一个平面来分。由于并不是所有问题中,样本在N维空间中都可以被超平面分为两类,因此通过使用引入核函数将样本映射到更高维的空间、并引入松弛变量以忽略噪音数据等方式,达到对数据进行分类的目的。

可能看起来有点抽象?没关系,把那个系列(并不是很长)看完就懂了,其实不难理解。在此基础上,svm方法还有许多扩充,例如对不平衡样本集的处理、One-Class SVM、在线SVM训练等等。

想要使用svm算法的话,非常幸运,台湾大学林智仁(Lin Chih-Jen)副教授主持的 libsvm 项目提供了c/java/python/matlab 的接口,直接拿来就能用了,非常方便。

在学习svm的过程中,也顺便看了一些其他的机器学习算法,这里也大致列一下。

HMM,隐马尔可夫模型。李开复的主要学术成就(之一?),就是使用了HMM开发出世界上第一个大词汇量连续语音识别系统 Sphinx。根据Google研究员吴军的数学之美 系列三 -- 隐含马尔可夫模型在语言处理中的应用,使用HMM来进行语音识别是李开复的师兄提出的。

HMM算法是基于贝叶斯公式的。贝叶斯公式在机器学习中是一个非常基础的理论。关于这个,推荐阅读《数学之美番外篇:平凡而又神奇的贝叶斯方法》

神经网络算法,通过模拟神经元的工作方式来对数据进行学习,使用多个神经元构成一个网络,并适当加入反馈机制。详情参考神经网络编程入门

遗传算法,通过模拟染色体复制、基因变异等机制,使状态不断”进化“,从而尽量逼近最优值。详情参考遗传算法入门

模拟退火,非常简洁、实用的一个算法,基于“爬山算法”(不断逼近离当前点最近的极值,贪心)改进而来,通过引入随机化以获得跳跃到其他极值区域的机会,从而尽可能获得更高的极值点。详情可参考《大白话解析模拟退火算法》

此外还看到了决策树、K-mean聚类等算法,不过没有细看,只是大致扫了一眼,就不扯了。

以上给出的链接大都是讲解得非常浅显易懂的文章,非常推荐阅读。
分页: 1/7 第一页 1 2 3 4 5 6 7 下页 最后页 [ 显示模式: 摘要 | 列表 ]