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 < n; index++) {
            Instance instance = instances.instance(index);
            double value = svm.classifyInstance(instance);
            if (value < 0.5) {
                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。

转自：http://hi.baidu.com/xuqingyang/blog/item/a52e6be752b9252ab838204b.html