只有你帮助别人，别人才会帮助你

:)

诗经·国风·郑风·子衿

　　青青子衿，悠悠我心。纵我不往，子宁不嗣音？
　　青青子佩，悠悠我思。纵我不往，子宁不来？
　　挑兮达兮，在城阙兮。一日不见，如三月兮。

如何使用基于Suffix Array的String Kernel

String Kernel是这样一种Kernel方法，它根据两个字符串的所有公共子串计算它们的相似度，最简单的方法是用Dynamic Programming的办法，但复杂度较高，是N的平方。通过使用Suffix Tree或Suffix Array可以成功地把复杂度降为线性的，参见论文：eprints.pascal-network.org/archive/00002056/01/VisSmo04.pdf
我对String Kernel很感兴趣的原因是它有广泛的用处，比如可以利用它仅通过链接的URL和Anchor Text对它的主题进行分类（Focused Crawling的关键技术）。自己先是从网上下到了libSVM网站上提供的一个C语言的String Kernel源码(http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/string/libsvm-2.84-string.zip)，利用它对以前下过的数据集进行了尝试，结果很令人兴奋。自己昨天晚上利用BestFirst方法共下载了近万个网页，其中有74％是与主题“Linux" 相关的。自己把这些下载的URL中的三分之二交给String Kernel SVM进行学习，然后对剩下的三分之一个URL进行分类，结果如下：
Precision = 84%, Recall = 92%
自己花了一天的时间又找到了两个提供String Kernel的SVM包：一个是Weka的最新版中提供了一个基于Dynamic Programming的平方复杂度的Java类包(http://www.cs.waikato.ac.nz/ml/weka/里的Developer Verstion)，自己花了一个下午的时间终于让它在自己的数据集上运行了起来，但已经过去两个小时了，程序还是没有结束，自己为了备查它的使用方法，把自己的Java程序开列如下：
import java.io.File;

import weka.classifiers.functions.SMO;
import weka.classifiers.functions.supportVector.StringKernel;
import weka.core.Instance;
import weka.core.Instances;
import weka.core.converters.ArffLoader;


public class Test {
public static void main(String[] args) throws Exception {
ArffLoader loader = new ArffLoader();
loader.setFile(new File("train"));
Instances instances = loader.getDataSet();
instances.setClassIndex(0);

SMO svm = new SMO();
StringKernel kernel = new StringKernel();
kernel.setOptions(new String[] { "-D", "-P", "1" });
svm.setKernel(kernel);

System.out.println("Starting classifying...");
svm.buildClassifier(instances);
System.out.println("Done");

loader.setFile(new File("test"));
instances = loader.getDataSet();
instances.setClassIndex(0);

int n = instances.numInstances();
int TP = 0, FP = 0, TN = 0, FN = 0;
for (int index = 0; index <>
Instance instance = instances.instance(index);
double value = svm.classifyInstance(instance);
if (value <>
if (instance.stringValue(0).equals("yes")) {
TP++;
} else {
FP++;
}
} else {
if (instance.stringValue(0).equals("no")) {
TN++;
} else {
FN++;
}
}
}
double precision = 1.0 * TP / (TP + FP);
double recall = 1.0 * TP / (TP + FN);
double F1 = 2 * precision * recall * 1.0 / (precision + recall);

System.out.printf("TP = %d, FP = %d, TN = %d, FN = %d\n", TP, FP, TN, FN);
System.out.printf("precision = %%%.2f, recall = %%%.2f, F1 = %%%.2f\n", precision, recall, F1);
}
}

另一个是SVMSequel软件包(http://www.cs.utah.edu/~hal/SVMsequel/)，它最大的优势之一是它提供了一种基于SuffixTree的线性复杂度的String Kernel和Tree Kernel，可惜它的下载网址打不开，另外它的全部代码由Caml语言编写。后来自己在Google Code Search里通过查找间接下载了它的源码，自己打算以后有时间学学Caml语言再把它的源码改写成Java。
String Kernel目前最快的算法是基于Suffix Tree或Suffix Array的方法。目前网上能够找到的源码实现除了SVMSequel(现在源码好象无法下载得到，而且是基于OCaml语言)外，能够找到的并且可用的非常少。SASK(http://users.rsise.anu.edu.au/~chteo/SASK.html)是最新的基于Suffix Array的实现，它基于Linux下的C＋＋实现，但仅提供String Kernel的计算功能，如何与SVM结合起来直接使用并没有给出说明。自己在和它的作者进行了第14次通信后终于弄懂了利用它进行SVM分类的详尽过程，现在写在这里留给将来备忘：
首先下载http://users.rsise.anu.edu.au/~chteo/SASK.html上的两个压缩包sask-1.1（http://users.rsise.anu.edu.au/~chteo/src/sask-1.1.tgz）和SASK experiments（http://users.rsise.anu.edu.au/~chteo/src/sask_icml06_expt.tgz）。然后分别将它们解压缩并且执行make命令。假设解压缩后的根目录分别为sask-1.1和sask_icml06_expt。
再到libsvm网站上下载最新的libsvm，要求是2.84版本之后的，这样它具有利用Precomputed Kernel Matrix的输入数据格式的功能。
运行sask-1.1/src目录下面生成的line-libsvmkm可执行文件，将提供的文本训练集转化成libsvm可以接受的Kernel Matrix格式。
将生成的基于Kernel Matrix格式的libsvm训练文件交给libsvm里的svm-train可执行文件，得到对应的svm-model文件。这个文件里有rho值和各个Support Vector的序号和它们的alpha值。
利用这些Support Vector及对应的alpha值构建一个与训练集对应的StringKernel对象，具体代码参见sask_icml06_expt/Code里面的 ltp-sa-sl.cpp文件，大致过程如下：
将各个Support Vector每个后面加一个'\n'的SENTINAL字符后串接一起，形成一个Master String，假设这个字符串保存在data这个std::string里，然后：

//swf和swfParam是调节weight的参数
StringKernel sk(data.size(), (SYMBOL*)data.c_str(), swf, swfParam);

//alphas保存各个Support Vector的alpha值的数组，data_len保存各个Support Vector的长度, n是Support Vector的数目
sk.Set_Lvs(&alphas[0], &data_len[0], n);

sk.PrecomputeVal();

至此，一个分类器已经创建成功，如果对一个字符串pattern进行分类，通过如下语句计算它对应的svm值(保存在kval这个变量里），减去rho后的符号即为它的label：
sk.Compute_K((SYMBOL*)pattern.c_str(), pattern.length(), kval);

使用起来其实真的很简单。如果训练数目巨大，还可以考虑用SVM-light取代libsvm以得到Support Vector及它们的alpha值。

Tips

针对不同的Boss：
学校的老师：Boss就是权威，容不得你一点挑战(对Boss说话永远要毕恭毕敬，注意语气，能少说尽量少说)

高调做事，低调做人

遇到尊重自己的人时，只要他愿意，一定要与之结婚，不要找任何的借口，没钱，可以不办婚礼，一个百年不变的承诺，一张结婚证，一张结婚照既可。钱可以随时挣，感情却是可遇不可求；有时候一时的错过 ，就是一生的错过，或者，一生的遗憾。
爱一个人要付出很大代价，但不爱任何人，代价会更大；所以，不管你受过多少的伤，承受了多少的痛,都不能用冷漠来对待人生。道理很简单，你给人以热情，对方未毕还你热情，但你给人以冷漠，对方肯定会还你冷漠，甚至是加倍。
纵情的结束便是后悔的开始，因此，无论多沮丧多绝望都不要去体味放纵。
遇到曾背叛你的人时，要跟他好好聊聊，因为是他教你读懂了这世界；遇到曾爱过你的人时，记得感激他，因为他让你明白了爱；遇到你曾误会过的朋友时，要及时说声对不起；因为你亵渎过他对你的信任。我爱你三个字不要轻意说出口，这三个字只能对三个人说，一是那个给你生命的人，二是第一个你爱的人,三是与你结婚的那个人。
不要轻意相信诺言，更不能相信明知无法兑现的诺言。
学会忍耐，更要明白，忍耐不是懦弱，它不过是暂时把带剌的东西攥在手里，准备将来当做武器抛出。
做事要先有冷静的头脑，再有清析的思路；遇到无法控制的事时，尽量学会控制自己的情绪，以免造成无法收拾的结果。
为人子者，最大的不幸莫过于：子欲孝而亲不在，切记，及时行孝。
不要总是为过去犯过的错而后悔愧疚，想明白为什么会犯错，学会如何不再犯同样的错以及怎么样去弥补犯下的错才是你该深思的。
不要常在人前提起自己过去的辉煌，总盯着了不起的过去，就不会有了不起的将来。
人生是一份没有满分的的试卷，因为有些题根本就没有答案；再者，九十九分和一百分在绝大多数情况下是没什么区别的，所以，不要过份地追求完美。
往高处爬之前，先衡量一下自己的力气；而在跳入一个深坑之前，更要先弄清它有多深；做任何事都要量力而行。
快乐是一天，悲伤也是一天；轻松是一天，沉重也是一天；抱怨是一天，感恩也是一天，有什么理由选择后者？
生命的长度你可能无法把握，但你能把握生命的质量，不要虚度生命中的每一天，尽量充实自己。
当你伤心时，有人比你更伤心，更沮丧，更绝望，其实生活是没有极端的，关键在于你的心态。
在人之上，视人为人，在人之下，视已为人；任何时候，自尊都不能丢，别人的自尊更不能夺。
遇到困难时，不要指望奇迹会出现在你身上，自救才是摆脱厄运唯一的出路。
现实中的你也许要经历许多挫折，但千万不要灰心，因为最因难的时候你往往受益最深。
做错事时要敢于承担责任，对便是对，错就是错，不能自欺欺人，圣人孔子都有犯错的时候，更何况你？要学会道歉，学会反省自己，学会为自己的言行负责。
能用钱解决的问题，都不是什么问题，但不能偏激的认为金钱万能，至少有：金钱治不好艾滋病；金钱买不到朋友的真心；金钱买不到安安稳稳的睡眠，金钱买不到快乐。
不要为自己的相貌或者身高过分担心和自卑。人的心灵远胜于相貌，请相信这点。人就像一本书，相貌和身高就像书皮，而一本书光书皮做得漂亮是没有用的，真正耐人寻味的还是书的内容。
任何时刻都要保持自信，一个连自己都信不过的人，是没人会信任，没人敢信任的。
受到再大的打击，只要生命还在，就有希望，因为每一天的太阳都是新的。
不要因为寂寞而去恋爱，要将寂寞暂时关押，要学会品味寂寞。
女人一定要珍爱自己，只有把自己保护好了，才有机会去爱别人或别人来爱你。
人生中有很多无奈，要学会善待自己；接受自己不能改变的一切，改变自己能改变的一切。逃不掉的，改变不了就选择接受，去习惯，当伤与痛，成为一种习惯时，犹如生活中的一日三餐，那便不叫伤，不叫痛了，也无所谓伤，无所谓痛了。慢慢将伤痛与无奈一点一点地化解于生活当中，省去不必要的挣扎和煎熬，才能换取遇事不惊，坦然处世之心境；就算世界再灰暗，时间也不会抛弃你，它可以让你从容地成长和遗忘…
还是那句话:世上无难事,只怕有心人!这是我永远坚信的