1、2.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 机
2、器学习模型对于LCS模糊查询的优化 165.5 机器学习模型的自动优化 176结论 19参考文献 19致谢 19作者 苏家辉 指导教师 蔡广基副教授 （湛江师范学院信息科学与技术学院，湛江 524048）摘 要：本文研究机器学习的基本原理和实现方法，对一个使用动态规划实现的英汉字典模糊查询系统构建一个机器学习模型。该模型实现了对用户的检索习惯进行分析，提取用户检索数据中的有趣模式，并通过统计频度对模式集进行自动优化，为用户的模糊查询提供智能化的查询结果。关键词：机器学习模型，动态规划，模糊查询 Fuzzy query of an English-Chinese dictionary based
3、 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
4、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 use
5、r, providing intelligent solutions for the fuzzy query.Key words: Machine learning; dynamic programming algorithm; fuzzy query;1引言1.1研究背景及其意义机器学习是现代人工智能研究、发展的重要领域，它通过研究计算机如何模拟或实现人类的学习行为，通过分析、归纳、综合建立人类学习过程的计算模型或认识模型，基于已有数据识别复杂模式，做出智能化的决策，并将其应用于实际问题中，为解决问题提供可行决策和方案支持1。自1980年在卡内基梅隆大学召开第一届机器学习研讨会以来，机器学习
6、的研究工作发展迅猛，已成为人工智能领域研究的中心课题之一。随着机器学习的蓬勃发展，人们在工作中累积了大量可供测试算法的数据集或者超大数据集，机器学习工作者在此基础上可以进行更精准的研究。目前机器学习已经广泛应用于智能搜索、数据分析等领域，如许多大型的搜索引擎网站的智能化的用户体验都是基于机器学习等研究成果实现的。在大数据时代，机器学习研究将会得到更大的发展。1.2研究内容和目标研究机器学习模型的生成过程，构建机器学习的模型，将其应用到英汉字典模糊查询中。第2节介绍机器学习和模糊查询中的基本思路和实现方法，第3节具体介绍算法实现的设计和数据的处理，第4节编码实现构想，第5节通过一些测试用例验证、
7、完善算法的基本功能，最后一节对本研究做出总结并提出新展望。2研究与实现中的关键技术2.1机器学习的基本原理 机器学习是从已有或动态的数据中提取有用的新知识2，并将其应用到问题的决策中，其基本过程为： 1. 收集学习材料，即获取的数据； 2. 分析数据，从中提取有趣的模式； 3. 基于数据分析获取有趣的模式，生成知识库，制定决策； 4. 通过学习新知识检验知识库数据的有效性，修改、完善知识库。在步骤1中获取的知识是原始的数据或材料，他们看起来可能是杂乱无章的，因此在步骤2需要对数据进行分析，挖掘复杂的隐藏的模式，使用朴素的贝叶斯分类、噪声处理等方法对数据进行分离、提取，然后在将来的决策（步骤3）
8、中使用这些模式去提供方案。但是提取出来的模式也可能是无效的，这就需要步骤4不断地学习新的知识，判定模式是否有效，修改完善知识库。2.2有趣模式的提取如何从原始数据中提取有用的模式，挖掘那些隐藏的有趣知识？分类是数据分析的一种重要的形式，通过它可以提取重要的数据类型。分类首先要基于现有数据建立一个分类模型，然后根据模型对数据进行分类。分类模型有决策树分类器、贝叶斯分类器和基于规则的分类器等3。在英汉字典模糊查询系统，使用的是基于规则的分类器-形如IF-THEN的分类器。规则的IF部分是前提条件，THEN部分是结论。假如用户的某些输入满足特定的条件则可认为是有趣模式。一般情况下，如果用户本次输入的
9、数据在上一次模糊查询的结果集中，则可认为上一次为用户提供的结果集中的对应项是有趣的。如果不满足这一条件则可认为上一次的模糊结果集对用户没有帮助，即为无效数据，丢弃之。英汉字典模糊查询系统的规则分类器实现大体如下： 本次是否为精确查询？ YES NO 上一次是否有模糊结果集？ 非有趣模式 YES NO 本次输入在上一次模糊结果集中？YES NO 有趣模式 非有趣模式 图2.1规则分类器的实现 2.3有趣模式集的优化 有趣模式集中的记录都是用户感兴趣的，但是对于一个非精确的输入可能存在多个用户感兴趣的选择项，如何确定最优的选择项呢？在统计学上，使用概率表示一件事情在大量测试下发生的可能性4。假设A
10、代表用户的一个模糊输入，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采用自底向上的递推求值，把中
11、间的结果存储起来并用于后面的计算，对于改善蛮力搜索的时间复杂度是比较有效的，假设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
12、为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. 精确查询 在字典的索引文件中查找查看是否存在，如果存在，则去词库的译
13、义文件中读取，并将结果输出给用户。 3. 一般模糊查询 如果通过精确查找无法查出该单词/词组，这种可能是由于单词的单复数，动词过去式，现在分词的ing形式类等造成，因此一般模糊查询就是对以上形式的单词进行简单的处理，如去掉词尾的s、d等，然后再对处理之后的单词进行精确查询。 4. 基于最长公共子序列的模糊查询（以下简称lcs查询） 如果基于一般模糊查询仍无法查出，则使用lcs查询，该查询是基于全文的检索，找出与输入单词最为相近的单词，即与输入单词的最长公共子序列是在全文中的最大值的单词，并将其作为选择项输出给用户。 5. 机器学习的模块开始时候，用户的使用记录为空。在一次lcs查询之后，可以将
14、lcs模糊查询的结果集记录起来，如果用户下一次查询的输入与lcs模糊查询的结果集记录有匹配项，则认为它们是一个有趣模式，并把其加入到有趣模式集中。每一次模糊查询给用户输出的结果集都会与模式结果集中的结果进行匹配，如果找到，则把模式结果集中的匹配数据与模糊结果集，匹配数据优先放到结果集前，去除重复的项，生成最终结果集（决策），最后输出给用户。3.2 业务流程设计系统的业务流程如下： 图3.1业务流程图 是 3.3 数据结构设计 3.3.1 宏定义宏定义含义#define WORDCOUNT 59372词库中单词的个数#define WORDLEN 24单词的最大长度#define Error（m
15、sg） 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 struct int count;Preference;其中word表示用户偏好的单词，count是该单词的的支持度计数，即在用户的输入中该单词被选中的频数。 3. 模式
16、记录集 char inputWORDLEN;/用户输入的单词 Preference presMAXPRES;/最多记录5个偏好 Record;其中input是用户的非精确单词，pres是该单词对应的用户偏好单词数组，最多5个记录。3.3.3 文件1. 单词的索引文件star.ndx 存放的是一个个Node类型的数据，每个单词/词组都有一个对应的Node，这些数据按照单词的英文次序升序排列，因此在查找单词时可使用二分查找快速检索。2. 词库文件star.dict存放单词的释义3. 用户输入记录文件search.dat存放用户输入的非精确单词，及该单词对应的lcs模糊查询结果集4. 模式记录文件r
17、ecord.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工
18、具的安装2vim的基本配置 在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+）
19、 if（flag|（ai=b0） Li0=1; flag=1; else Li0=0; flag=0; for（j=0;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 string.hstdio.h#define MAXPRES 5/用户偏好的最大个数#define WORDLEN 24/单词最大长度#define PRENUM 5 /有效模式的个数/用户偏好/次数/用户选择项
20、/最多记录5个偏好/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 voi
21、d * 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 代表用
22、户的输入，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+;node_len,sizeof（int）,1,fd）; fwrite（nodes,sizeof（Node）,node_len,fd）; fclose（fd）;in
23、t 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,ch
24、ar* match_word）./record.data+b int RecordCount=0; Record* matched=NULL; char ch; fseek（fd,0,SEEK_SET）; fread（&ch,1,1,fd）; if（ch=EOF）/即初始状态，空文件 RecordCount=1;RecordCount,sizeof（int）,1,fd）; Record newRcd=0; strcpy（newRcd.input,word）; strcpy（newRcd.pres0.word,match_word）; newRcd.pres0.count=1;newRcd,si
25、zeof（Record）,1,fd）; /check the first record return; else Record* records=（Record*）malloc（RecordCount+1）*Recordsize）; fread（records,Recordsize,RecordCount,fd）; /a+模式从文件头读，从文件尾写 matched=（Record*）bsearch（word,records,RecordCount,Recordsize,Recordcmp）; /是已有记录 if（matched!=NULL） int num=0,i;/用于标识是否找到 whil
26、e（strlen（matched-presnum.word） num+;/计算当前用户偏好的数目num; if（!strcmp（match_word,matched-presi.word） matched-presi.count+; qsort（matched-pres,num,sizeof（Preference）,Prescmp）; break; （inum）/匹配项不在偏好数组中 Preference newPre=0; strcpy（newPre.word,match_word）; newPre.count=1; if（ipresi-1=newPre; /新记录 RecordCount+; newRcd.pres0
