本科毕业论文---基于机器学习的英汉字典模糊查询论文正文.doc

A 基础理论 B 应用研究 C 调查报告 D 其他本科生毕业设计（论文）基于机器学习的英汉字典模糊查询二级学院：信息科学与技术学院专 业：计算机科学与技术年 级：2010级学 号：2010344369作者姓名：苏家辉指导教师：蔡广基 副教授完成日期：2014年5月24日基于机器学习的英汉字典模糊查询专业名称：计算机科学与技术作者姓名：苏家辉指导教师：蔡广基论文答辩小组组 长： 蔡广基 成 员： 王晓晔 关 心 论文成绩： 目 录1引言21.1研究背景及其意义21.2研究内容和目标22研究与实现中的关键技术22.1机器学习的基本原理22.2有趣模式的提取22.3有趣模式集的优化32.4使用动态规划的最长公共子序列33系统设计43.1总体结构43.2 业务流程设计43.3 数据结构设计53.3.1 宏定义53.3.2 结构体53.3.3 文件64实施应用64.1 开发环境64.1.1 硬件平台64.1.2 软件平台64.2 开发环境的搭建和配置64.3 编写代码74.3.1最长公共子序列长度核心代码74.3.2机器学习模型的c语言实现85测试与分析145.1 精确查询的实现145.2 一般模糊查询的实现155.3 基于动态规划的模糊查询实现165.4 机器学习模型对于LCS模糊查询的优化165.5 机器学习模型的自动优化176结论19参考文献19致谢19基于机器学习的英汉字典模糊查询作者 苏家辉 指导教师 蔡广基副教授 （湛江师范学院信息科学与技术学院，湛江 524048）摘 要：本文研究机器学习的基本原理和实现方法，对一个使用动态规划实现的英汉字典模糊查询系统构建一个机器学习模型。该模型实现了对用户的检索习惯进行分析，提取用户检索数据中的有趣模式，并通过统计频度对模式集进行自动优化，为用户的模糊查询提供智能化的查询结果。关键词：机器学习模型，动态规划，模糊查询 Fuzzy query of an English-Chinese dictionary based on machine learningSu JiahuiSchool of information science and technology, Zhanjiang Normal University, Zhanjiang, 524048 ChinaAbstract： Based on the machine learning theory , a model of the fuzzy query of an English-Chinese dictionary system, which is fulfilled by the dynamic programming algorithm is given. The model analyses the users fuzzy query data and finds out the connections between the data, recording the mining models, applies them to the fuzzy query set during a non-accurate searching, and automatically improves the mining models set according to the statistics at frequencies of user, providing intelligent solutions for the fuzzy query.Key words: Machine learning; dynamic programming algorithm; fuzzy query;1引言1.1研究背景及其意义机器学习是现代人工智能研究、发展的重要领域，它通过研究计算机如何模拟或实现人类的学习行为，通过分析、归纳、综合建立人类学习过程的计算模型或认识模型，基于已有数据识别复杂模式，做出智能化的决策，并将其应用于实际问题中，为解决问题提供可行决策和方案支持1。自1980年在卡内基梅隆大学召开第一届机器学习研讨会以来，机器学习的研究工作发展迅猛，已成为人工智能领域研究的中心课题之一。随着机器学习的蓬勃发展，人们在工作中累积了大量可供测试算法的数据集或者超大数据集，机器学习工作者在此基础上可以进行更精准的研究。目前机器学习已经广泛应用于智能搜索、数据分析等领域，如许多大型的搜索引擎网站的智能化的用户体验都是基于机器学习等研究成果实现的。在大数据时代，机器学习研究将会得到更大的发展。1.2研究内容和目标研究机器学习模型的生成过程，构建机器学习的模型，将其应用到英汉字典模糊查询中。第2节介绍机器学习和模糊查询中的基本思路和实现方法，第3节具体介绍算法实现的设计和数据的处理，第4节编码实现构想，第5节通过一些测试用例验证、完善算法的基本功能，最后一节对本研究做出总结并提出新展望。2研究与实现中的关键技术2.1机器学习的基本原理 机器学习是从已有或动态的数据中提取有用的新知识2，并将其应用到问题的决策中，其基本过程为： 1. 收集学习材料，即获取的数据； 2. 分析数据，从中提取有趣的模式； 3. 基于数据分析获取有趣的模式，生成知识库，制定决策； 4. 通过学习新知识检验知识库数据的有效性，修改、完善知识库。在步骤1中获取的知识是原始的数据或材料，他们看起来可能是杂乱无章的，因此在步骤2需要对数据进行分析，挖掘复杂的隐藏的模式，使用朴素的贝叶斯分类、噪声处理等方法对数据进行分离、提取，然后在将来的决策（步骤3）中使用这些模式去提供方案。但是提取出来的模式也可能是无效的，这就需要步骤4不断地学习新的知识，判定模式是否有效，修改完善知识库。2.2有趣模式的提取如何从原始数据中提取有用的模式，挖掘那些隐藏的有趣知识？分类是数据分析的一种重要的形式，通过它可以提取重要的数据类型。分类首先要基于现有数据建立一个分类模型，然后根据模型对数据进行分类。分类模型有决策树分类器、贝叶斯分类器和基于规则的分类器等3。在英汉字典模糊查询系统，使用的是基于规则的分类器-形如IF-THEN的分类器。规则的IF部分是前提条件，THEN部分是结论。假如用户的某些输入满足特定的条件则可认为是有趣模式。一般情况下，如果用户本次输入的数据在上一次模糊查询的结果集中，则可认为上一次为用户提供的结果集中的对应项是有趣的。如果不满足这一条件则可认为上一次的模糊结果集对用户没有帮助，即为无效数据，丢弃之。英汉字典模糊查询系统的规则分类器实现大体如下： 本次是否为精确查询？ YES NO 上一次是否有模糊结果集？ 非有趣模式 YES NO 本次输入在上一次模糊结果集中？ 非有趣模式 YES NO 有趣模式 非有趣模式 图2.1规则分类器的实现 2.3有趣模式集的优化 有趣模式集中的记录都是用户感兴趣的，但是对于一个非精确的输入可能存在多个用户感兴趣的选择项，如何确定最优的选择项呢？在统计学上，使用概率表示一件事情在大量测试下发生的可能性4。假设A代表用户的一个模糊输入，X1，Xi代表A输入所对应的用户感兴趣的选择项，设p(A|Xi)为用户输入A后选择Xi的概率，分别计每一个选择项Xi的p(A|Xi),将具有最大值的选择项排在最前面，即为最优的选择项。用户每次输入A后选择Xi都是对AXi模式的一次强化。p(A|Xi)=n(Xi)/n(A),在该式中n(Xi)表示Xi被选择的次数，n(A)表示输入A的总次数，对于计算A的所有选择项的p(A|Xi)，分母都是相同的，因此在具体的实现中，只需要为每一个选择项项添加一个频度计数，这样具有最大频度计数的选择项即为最优的选择项。2.4使用动态规划的最长公共子序列动态规划5采用自底向上的递推求值，把中间的结果存储起来并用于后面的计算，对于改善蛮力搜索的时间复杂度是比较有效的，假设an，bm分别表示长度为n,m的两个字符串，则a0,an-1中的任意组合表示a的子序列，b0bm-1中的任意组合表示b的子序列,如果要求这两个字符串的最长公共子序列，采用简单的线性规划的方法是：列举a的所有所有2的n次方个子序列，察看它与bm的最长公共子序列长度，采用这种方法的时间复杂度是指数级的(n2)，如果采用动态规划的方法可以使解决最初公共子序列问题优化到（n log n）。假设Lnm表示a的前n个字符与b的前m个字符之间的最长公共子序列长度，则Lnm的递推公式如下：LCSflag初始值为0，用于标记当n或m为0时，前面是否有a的子序列与b的子序列相等的情况。对于n=0或m=0,若an=am,则Lnm=LCSflag=1,如果an!=am,若LCSflag=1则，Lnm=1，否则Lnm=0； 对于n和m都不等于0的情况：若an=bm则Lnm= Ln-1m-1+1；若an!=bm则Lnm= Ln-1m和Lnm-1中的最大值。3系统设计3.1总体结构 系统的主要功能包括以下部分 1. 用户输入 接收用户输入的单词或词组，它们可能是精确的输入，也可能是存在拼写错误的单词或词组，如“department”和“deparmen”等。 2. 精确查询 在字典的索引文件中查找查看是否存在，如果存在，则去词库的译义文件中读取，并将结果输出给用户。 3. 一般模糊查询 如果通过精确查找无法查出该单词/词组，这种可能是由于单词的单复数，动词过去式，现在分词的ing形式类等造成，因此一般模糊查询就是对以上形式的单词进行简单的处理，如去掉词尾的s、d等，然后再对处理之后的单词进行精确查询。 4. 基于最长公共子序列的模糊查询（以下简称lcs查询） 如果基于一般模糊查询仍无法查出，则使用lcs查询，该查询是基于全文的检索，找出与输入单词最为相近的单词，即与输入单词的最长公共子序列是在全文中的最大值的单词，并将其作为选择项输出给用户。 5. 机器学习的模块开始时候，用户的使用记录为空。在一次lcs查询之后，可以将lcs模糊查询的结果集记录起来，如果用户下一次查询的输入与lcs模糊查询的结果集记录有匹配项，则认为它们是一个有趣模式，并把其加入到有趣模式集中。每一次模糊查询给用户输出的结果集都会与模式结果集中的结果进行匹配，如果找到，则把模式结果集中的匹配数据与模糊结果集，匹配数据优先放到结果集前，去除重复的项，生成最终结果集（决策），最后输出给用户。3.2 业务流程设计系统的业务流程如下： 图3.1业务流程图 是 3.3 数据结构设计 3.3.1 宏定义宏定义含义#define WORDCOUNT 59372词库中单词的个数#define WORDLEN 24单词的最大长度#define Error(msg) perror(msg); eXit(1);出错处理#define PRENUM 5对于每个用户输入可以提取的有效模式的最大个数3.3.2 结构体 1. 单词索引记录 typedef struct char wordWORDLEN; int offset; int length; Node;其中word表示单词，offset是该单词在词库文件中的索引，length是该单词的释义的长度 2. 用户的偏好记录typedef structchar wordWORDLEN;int count;Preference;其中word表示用户偏好的单词，count是该单词的的支持度计数，即在用户的输入中该单词被选中的频数。 3. 模式记录集typedef structchar inputWORDLEN;/用户输入的单词Preference presMAXPRES;/最多记录5个偏好Record;其中input是用户的非精确单词，pres是该单词对应的用户偏好单词数组，最多5个记录。3.3.3 文件1. 单词的索引文件star.ndx 存放的是一个个Node类型的数据，每个单词/词组都有一个对应的Node，这些数据按照单词的英文次序升序排列，因此在查找单词时可使用二分查找快速检索。2. 词库文件star.dict存放单词的释义3. 用户输入记录文件search.dat存放用户输入的非精确单词，及该单词对应的lcs模糊查询结果集4. 模式记录文件record.dat存放的是有趣模式记录，这些记录也是按用户的输入非精确单词升序排序，这样方便在进行记录查找时使用二分查找，快速的查询某一记录是否存在，在记录的内部是按照模式的有效次数降序按序的。 4实施应用4.1 开发环境4.1.1 硬件平台 CPU：i5-4200h 2.8GHz； 内存：256MB及以上。4.1.2 软件平台 操作系统：Windows虚拟机VMware 10.0下的ubuntu linux。 开发工具：gcc ,vim4.2 开发环境的搭建和配置1 安装vim 在linux终端输入sudo apt-get install vim-gtk，然后输入root用户密码等待完成vim工具的安装2 vim的基本配置 在linux终端输入vi /.vimrc按如下方式配置set nuset ts=4set sw=4set cindentset autoident3环境变量的设置在终端输入 vi /.bashrc添加以下行：export PATH=$PATH:./ 保存之后在命令行输入source .bashrc 4.3 编写代码4.3.1最长公共子序列长度核心代码int LCS(char* a,char* b) int n,m,i,j; int flag=0; n=strlen(a)-1; m=strlen(b)-1; int L100100=0; for(i=0;i=n;i+) if(flag|(ai=b0) Li0=1; flag=1; else Li0=0; flag=0; for(j=0;j=m;j+) if(flag|(a0=bj) L0j=1; flag=1; else L0j=0; /char a100,b100;for(i=1;i=n;i+) for(j=1;j=Li-1j) Lij=Lij-1; else Lij=Li-1j;return Lnm;4.3.2机器学习模型的c语言实现 1.在learn.h中的定义#ifndef _LEARN_H#define _LEARN_H#include dict.h#include #include #include #define MAXPRES 5/用户偏好的最大个数#define WORDLEN 24/单词最大长度#define PRENUM 5 /有效模式的个数typedef structchar wordWORDLEN;/用户偏好int count;/次数Preference;typedef structchar inputWORDLEN;/用户选择项Preference presMAXPRES;/最多记录5个偏好Record;/int Recordsize=sizeof(Record);/一个记录的大小void RecordData(char* word,Node* nodes);void NewRecord(char* word,char* match_word);void Analyse(char* word);void Solution(char* newData,Node* nodes);void Decision(Node* dst_node,Node* src_node);/用于快速查找查询记录或对记录快排int Recordcmp(const void * dst,const void * src);int Prescmp(const void * dst,const void * src);#endif 主要函数解释： RecordData：用于记录用户每次输入的非精确单词及其使用lcs模糊查询得到的结果集。 Analyse：分析用户的输入和lcs模糊结果集间的关系，提取有趣模式。 NewRecord:记录有趣模式。 Solution：提取与用户输入的非精确单词相关的模式记录。 Decision：根据历史模式记录，生成最终的决策方案。 2. 在learn.c中主要函数的实现 void RecordData(char* word,Node* nodes)/word 代表用户的输入，nodes是模糊查询的结果集FILE* fd=fopen(./search.dat,w+b);/打开并清空上一次的结果if(!fd)return;int node_len=0;int len=strlen(word);fwrite(&len,sizeof(int),1,fd);fwrite(word,1,len,fd); while(strlen(nodesnode_len.word)0)node_len+;fwrite(&node_len,sizeof(int),1,fd);fwrite(nodes,sizeof(Node),node_len,fd);fclose(fd);int Recordcmp(const void * dst,const void * src)Record* d=(Record*)dst;Record* s=(Record*)src;return strcmp(d-input,s-input);/对用户偏好按降序排序int Prescmp(const void * dst,const void * src)Preference* d=(Preference*)dst;Preference* s=(Preference*)src;return (d-count) count);void NewRecord(char* word,char* match_word) FILE* fd=fopen(./record.dat,a+b);if(!fd)return; int RecordCount=0; Record* matched=NULL; char ch; fseek(fd,0,SEEK_SET); fread(&ch,1,1,fd); if(ch=EOF)/即初始状态，空文件 RecordCount=1; fseek(fd,0,SEEK_SET); fwrite(&RecordCount,sizeof(int),1,fd); Record newRcd=0; strcpy(newRcd.input,word); strcpy(newRcd.pres0.word,match_word); newRcd.pres0.count=1; fwrite(&newRcd,sizeof(Record),1,fd); /check the first record fclose(fd); return; else fseek(fd,0,SEEK_SET); fread(&RecordCount,sizeof(int),1,fd); Record* records=(Record*)malloc(RecordCount+1)*Recordsize); fread(records,Recordsize,RecordCount,fd); fclose(fd); /a+模式从文件头读，从文件尾写 matched=(Record*)bsearch(word,records,RecordCount,Recordsize,Recordcmp); /是已有记录 if(matched!=NULL) int num=0,i;/用于标识是否找到while(strlen(matched-presnum.word)0)num+;/计算当前用户偏好的数目 for(i=0;ipresi.word) matched-presi.count+;qsort(matched-pres,num,sizeof(Preference),Prescmp);break; if(!(inum)/匹配项不在偏好数组中 Preference newPre=0; strcpy(newPre.word,match_word); newPre.count=1; if(ipresi=newPre; else matched-presi-1=newPre; /新记录 else RecordCount+; Record newRcd=0; strcpy(newRcd.input,word); strcpy(newRcd.pres0.word,match_word); newRcd.pres0.count=1; recordsRecordCount-1=newRcd; /对record数组重新排序 qsort(records,RecordCount,sizeof(Record),Recordcmp); /写回记录文件 FILE* fw=fopen(./record.dat,r+b); fseek(fw,0,SEEK_SET); fwrite(&RecordCount,sizeof(int),1,fw); fwrite(records,sizeof(Record),RecordCount,fw); free(records); fclose(fw); void Analyse(char* match_word) FILE* fd=fopen(./search.dat,rb);if(!fd)return; int len=0; fread(&len,sizeof(int),1,fd); char wordlen+1; fread(word,1,len,fd); wordlen=0; /printf(value in Analyse:%sn,%d,word,len); int node_len=0; fread(&node_len,sizeof(int),1,fd); Node nodesnode_len; fread(nodes,sizeof(Node),node_len,fd); fclose(fd); int i=0; /判断是否为有趣模式 for(i=0;ipresnum.word) /printf(pres value:%sn,matched-presnum.word); num+; /printf(匹配记录中的pres:%dn,num); if(num PRENUM) num=PRENUM; int i; for(i=0;ipresi.word); free(records);/计算结点数目int Nodenum(Node* nodes)int i=0; while(strlen(nodesi.word) i+; return i;/结点数组拷贝void Nodecpy(Node* dst_node,Node* src_node)int src_count=Nodenum(src_node);int i=0;for(i=0;isrc_count;i+) strcpy(dst_nodei.word,src_nodei.word); /结点查找int FindNode(char* word,Node* nodes,int num)int i=0;for(i=0;inum;i+)if(!strcasecmp(word,nodesi.word)/找到return 1;return 0;/src_node: nodes from record file,des_node: final nodes array to dual searchvoid Decision(Node* dst_node,Node* src_node)/src_node表示从历史数据中获取的数据，des_node本次模糊匹配结果int src_count=Nodenum(src_node); int dst_count=Nodenum(dst_node);Node tempdst_count;Node nilNode=0;/用于结点初始化Nodecpy(temp,dst_node);Node newNodessrc_count+dst_count;/合并int j=0;for(j=0;j(src_count+dst_count);j+)newNodesj=nilNode;/Nodecpy(newNodes,src_node);int newCount=Nodenum(newNodes);int i=0;for(i=0;idst_count;i+) if(!FindNode(tempi.word,src_node,src_count) newNodesnewCount=tempi; newCount+; Nodecpy(dst_node,newNodes);5测试与分析在编写好所有的代码之后，在终端输入命令gcc *.c 即可编译生成可执行文件，然后在终端输入./a.out按以下用例测试。5.1 精确查询的实现 测试用例1：word:mopmopn. 拖把,鬼脸乱蓬蓬的头发vt. 用拖把洗擦,擦,拭vi. 做鬼脸测试结果分析：用户输入“mop”进行搜索，该单词在索引文件中找到，则从词库中读取其释义并输出。 测试用例2：word:youyoupron. 你,你们;一个人,任何人测试结果分析：用户输入“you”进行搜索，该单词在索引文件中找到，则从词库中读取其释义并输出 测试用例3：word:movemoven. 移动,迁居,步骤vt. 移动,开动,感动,鼓动vi. 移动,离开,运行,迁移,行动测试结果分析：同上，可以精确查出“move”的释义。查询的限制：用户检索的英文单词长度不能超过24个有效字符，无法对空输入进行查询。5.2 一般模糊查询的实现 测试用例4：word:movedmoven. 移动,迁居,步骤vt. 移动,开动,感动,鼓动vi. 移动,离开,运行,迁移,行动测试结果分析，在第一次精确查询时，由于词库中并没有“moved”，这是由于用户的拼写错误照成的，本例中用户输入的是单词的过去式，可进行一般的处理，去掉词尾的“d”,再进行精确查询，可输出“move”对应的英译汉释义。 测试用例5：word:jumppingjumpn. 跳跃,跳动,上涨,惊跳vt. 跳越,跃过,突升,使跳跃vi. 跳跃,跳,跳动,暴涨测试结果分析：用户输入的是“jumpping”,这个单词也无法使用精确查询，该单词为ing形式，可以先去掉词尾的“ing”查看是否可以找不到，若找不到再尝试由于元音+辅音结尾的形如mop-mopping形式的规则，再去掉词尾的一个字符，再次进行精确查找，输出单词“jump”的释义。 测试用例6：word:flowersflowern. 花,精华,盛时vi. 开花,旺盛,成熟vt. 使开花测试结果分析：同上，flowers并不在词库中，是flower的复数形式，采用一般模糊查询，输出flower的释义。5.3 基于动态规划的模糊查询实现 测试用例7：word:lot o您是否要搜索： lots of plot out blot out a lot of pilot boat测试结果分析：用户输入“lot of”，由于词库中不存在该单词，也不是由于词尾如动名词、单复数、过去式等原因造成的错误，使用一般模糊查找也无法确定出单词的释义。解决思路之一：使用基于全文的最长公共子序列搜索，遍历单词索引文件中的所有单词，找出与“lot o”具有最长公共子序列最大值的5个单词或词