String核负实例语法特征提取算法

Grammatical Feature Extraction Algorithm for String Kernel False Instance

通过String核方法把语法数据库中的负实例转化成核矩阵,采用Kmeans聚类算法对核矩阵进行聚类,将原始负实例数据库分成多个容量较小的特征数据表,使大规模O(n3)核矩阵转换为n/s×O(s3)(s<<n)矩阵,以减少运算量。分析语法检查精度随Kmeans聚类参数的变化规律。实验结果表明,该算法在不降低语法检查精度的前提下提高了语法检查速度。

This paper translates false instance in grammatical database to kernel matrix through String kernel method, uses Kmeans clustering method to cluster the kernel matrix and separate the original false instance database into many characteristic tables with small capacitance. It transforms large scale O（n^3） kernel matrix into n/s×O（s^3）（s〈〈n） matrix to decrease calculation amount, and analyzes the rule of the grammatical check accuracy with the change of Kmeans clustering parameters. Experimental results show that this algorithm can enhance the running speed without decreasing the accuracy of grammatical check.