如何使用基于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值。
