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

Grammatical Feature Extraction Algorithm for String Kernel False Instance

作　　者：吕威[1,2] 林文昶[2] 李磊[2] 

机构地区：[1]北京师范大学珠海分校信息技术学院,珠海519085 [2]中山大学软件研究所,广州510275

出　　处：《计算机工程》2009年第23期12-14,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(10471156;10531040)

摘　　要：通过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.

关 键 词：Kmeans方法 聚类 String核 负实例 特征提取 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]