機器學習的英漢字典模糊查詢研究與設計開發(fā)

機器學習的英漢字典模糊查詢研究與設計開發(fā)○○A基礎理論●B應用研究○C調查報告○D其他本科生畢業(yè)論基于機器學習的英漢字典模糊查詢二級學院：信息科學與技術學院專業(yè)：計算機科學與技術年級：2010級學號：2010344369作者姓名：蘇家輝指導教師：蔡廣基副教授完成日期：2014年5月24日基于機器學習的英漢字典模糊查詢專業(yè)名稱：計算機科學與技術作者姓名：蘇家輝指導教師：蔡廣基論文答辯小組組長：蔡廣基成員：王曉曄關心論文成績：given.Themodelanalysestheuser’sfuzzyquerydataandfindsouttheconnectionsbetweenthedata,recordingtheminingmodels,appliesthemtothefuzzyquerysetduringanon-accuratesearching,andautomaticallyimprovestheminingmodelssetaccordingtothestatisticsatfrequenciesofuser,providingintelligentsolutionsforthefuzzyquery.Keywords:Machinelearning。dynamicprogrammingalgorithm。fuzzyquery。1引言1.1研究背景及其意義機器學習是現代人工智能研究、發(fā)展的重要領域，它通過研究計算機如何模擬或實現人類的學習行為，通過分析、歸納、綜合建立人類學習過程的計算模型或認識模型，基于已有數據識別復雜模式，做出智能化的決策，并將其應用于實際問題中，為解決問題提供可行決策和方案支持[1]。自1980年在卡內基梅隆大學召開第一屆機器學習研討會以來，機器學習的研究工作發(fā)展迅猛，已成為人工智能領域研究的中心課題之一。隨著機器學習的蓬勃發(fā)展，人們在工作中累積了大量可供測試算法的數據集或者超大數據集，機器學習工作者在此基礎上可以進行更精準的研究。目前機器學習已經廣泛應用于智能搜索、數據分析等領域，如許多大型的搜索引擎網站的智能化的用戶體驗都是基于機器學習等研究成果實現的。在大數據時代，機器學習研究將會得到更大的發(fā)展。1.2研究內容和目標研究機器學習模型的生成過程，構建機器學習的模型，將其應用到英漢字典模糊查詢中。第2節(jié)介紹機器學習和模糊查詢中的基本思路和實現方法，第3節(jié)具體介紹算法實現的設計和數據的處理，第4節(jié)編碼實現構想，第5節(jié)通過一些測試用例驗證、完善算法的基本功能，最后一節(jié)對本研究做出總結并提出新展望。2研究與實現中的關鍵技術2.1機器學習的基本原理機器學習是從已有或動態(tài)的數據中提取有用的新知識[2]，并將其應用到問題的決策中，其基本過程為：1.收集學習材料，即獲取的數據；2.分析數據，從中提取有趣的模式；3.基于數據分析獲取有趣的模式，生成知識庫，制定決策；4.通過學習新知識檢驗知識庫數據的有效性，修改、完善知識庫。在步驟1中獲取的知識是原始的數據或材料，他們看起來可能是雜亂無章的，因此在步驟2需要對數據進行分析，挖掘復雜的隱藏的模式，使用樸素的貝葉斯分類、噪聲處理等方法對數據進行分離、提取，然后在將來的決策（步驟3）中使用這些模式去提供方案。但是提取出來的模式也可能是無效的，這就需要步驟4不斷地學習新的知識，判定模式是否有效，修改完善知識庫。2.2有趣模式的提取如何從原始數據中提取有用的模式，挖掘那些隱藏的有趣知識？分類是數據分析的一種重要的形式，通過它可以提取重要的數據類型。分類首先要基于現有數據建立一個分類模型，然后根據模型對數據進行分類。分類模型有決策樹分類器、貝葉斯分類器和基于規(guī)則的分類器等[3]。在英漢字典模糊查詢系統，使用的是基于規(guī)則的分類器--形如IF-THEN的分類器。規(guī)則的IF部分是前提條件，THEN部分是結論。假如用戶的某些輸入滿足特定的條件則可認為是有趣模式。一般情況下，如果用戶本次輸入的數據在上一次模糊查詢的結果集中，則可認為上一次為用戶提供的結果集中的對應項是有趣的。如果不滿足這一條件則可認為上一次的模糊結果集對用戶沒有幫助，即為無效數據，丟棄之。英漢字典模糊查詢系統的規(guī)則分類器實現大體如下：本次是否為精確查詢？YESNO上一次是否有模糊結果集？非有趣模式YESNO本次輸入在上一次模糊結果集中？非有趣模式YESNO有趣模式非有趣模式圖2.1規(guī)則分類器的實現2.3有趣模式集的優(yōu)化有趣模式集中的記錄都是用戶感興趣的，但是對于一個非精確的輸入可能存在多個用戶感興趣的選擇項，如何確定最優(yōu)的選擇項呢？在統計學上，使用概率表示一件事情在大量測試下發(fā)生的可能性[4]。假設A代表用戶的一個模糊輸入，X1，…，Xi代表A輸入所對應的用戶感興趣的選擇項，設p(A|Xi)為用戶輸入A后選擇Xi的概率，分別計每一個選擇項Xi的p(A|Xi),將具有最大值的選擇項排在最前面，即為最優(yōu)的選擇項。用戶每次輸入A后選擇Xi都是對A—Xi模式的一次強化。p(A|Xi)=n(Xi)/n(A),在該式中n(Xi)表示Xi被選擇的次數，n(A)表示輸入A的總次數，對于計算A的所有選擇項的p(A|Xi)，分母都是相同的，因此在具體的實現中，只需要為每一個選擇項項添加一個頻度計數，這樣具有最大頻度計數的選擇項即為最優(yōu)的選擇項。2.4使用動態(tài)規(guī)劃的最長公共子序列動態(tài)規(guī)劃[5]采用自底向上的遞推求值，把中間的結果存儲起來并用于后面的計算，對于改善蠻力搜索的時間復雜度是比較有效的，假設a[n]，b[m]分別表示長度為n,m的兩個字符串，則a[0],…,a[n-1]中的任意組合表示a的子序列，b[0]…b[m-1中的任意組合表示b的子序列,如果要求這兩個字符串的最長公共子序列，采用簡單的線性規(guī)劃的方法是：列舉a的所有所有2的n次方個子序列，察看它與b[m]的最長公共子序列長度，采用這種方法的時間復雜度是指數級的Ο(n^2)，如果采用動態(tài)規(guī)劃的方法可以使解決最初公共子序列問題優(yōu)化到Ο（nlogn）。假設L[n][m]表示a的前n個字符與b的前m個字符之間的最長公共子序列長度，則L[n][m]的遞推公式如下：LCSflag初始值為0，用于標記當n或m為0時，前面是否有a的子序列與b的子序列相等的情況。對于n=0或m=0,若a[n]=a[m],則L[n][m]=LCSflag=1,如果a[n]!=a[m],若LCSflag=1則，L[n][m]=1，否則L[n][m]=0；對于n和m都不等于0的情況：若a[n]=b[m]則L[n][m]=L[n-1][m-1]+1；若a[n]!=b[m]則L[n][m]={L[n-1][m]和L[n][m-1]中的最大值}。3系統設計3.1總體結構系統的主要功能包括以下部分1.用戶輸入接收用戶輸入的單詞或詞組，它們可能是精確的輸入，也可能是存在拼寫錯誤的單詞或詞組，如“department”和“deparmen”等。2.精確查詢在字典的索引文件中查找查看是否存在，如果存在，則去詞庫的譯義文件中讀取，并將結果輸出給用戶。3.一般模糊查詢如果通過精確查找無法查出該單詞/詞組，這種可能是由于單詞的單復數，動詞過去式，現在分詞的ing形式類等造成，因此一般模糊查詢就是對以上形式的單詞進行簡單的處理，如去掉詞尾的‘s’、‘d’等，然后再對處理之后的單詞進行精確查詢。4.基于最長公共子序列的模糊查詢（以下簡稱lcs查詢）如果基于一般模糊查詢仍無法查出，則使用lcs查詢，該查詢是基于全文的檢索，找出與輸入單詞最為相近的單詞，即與輸入單詞的最長公共子序列是在全文中的最大值的單詞，并將其作為選擇項輸出給用戶。5.機器學習的模塊開始時候，用戶的使用記錄為空。在一次lcs查詢之后，可以將lcs模糊查詢的結果集記錄起來，如果用戶下一次查詢的輸入與lcs模糊查詢的結果集記錄有匹配項，則認為它們是一個有趣模式，并把其加入到有趣模式集中。每一次模糊查詢給用戶輸出的結果集都會與模式結果集中的結果進行匹配，如果找到，則把模式結果集中的匹配數據與模糊結果集，匹配數據優(yōu)先放到結果集前，去除重復的項，生成最終結果集（決策），最后輸出給用戶。3.2業(yè)務流程設計系統的業(yè)務流程如下：圖3.1業(yè)務流程圖是是3.3數據結構設計3.3.1宏定義宏定義含義#defineWORDCOUNT59372詞庫中單詞的個數#defineWORDLEN24單詞的最大長度#defineError(msg){perror(msg)。eXit(1)。}出錯處理#definePRENUM5對于每個用戶輸入可以提取的有效模式的最大個數3.3.2結構體1.單詞索引記錄typedefstruct{ charword[WORDLEN]。 intoffset。 intlength。 }Node。其中word表示單詞，offset是該單詞在詞庫文件中的索引，length是該單詞的釋義的長度2.用戶的偏好記錄typedefstruct{ charword[WORDLEN]。 intcount。}Preference。其中word表示用戶偏好的單詞，count是該單詞的的支持度計數，即在用戶的輸入中該單詞被選中的頻數。3.模式記錄集typedefstruct{ charinput[WORDLEN]。//用戶輸入的單詞 Preferencepres[MAXPRES]。//最多記錄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開發(fā)環(huán)境4.1.1硬件平臺CPU：i5-4200h2.8GHz；內存：256MB及以上。4.1.2軟件平臺操作系統：Windows虛擬機VMware10.0下的ubuntulinux。開發(fā)工具：gcc,vim4.2開發(fā)環(huán)境的搭建和配置安裝vim在linux終端輸入

sudoapt-getinstallvim-gtk，然后輸入root用戶密碼等待完成vim工具的安裝vim的基本配置在linux終端輸入vi~/.vimrc按如下方式配置setnusetts=4setsw=4setcindentsetautoident3．環(huán)境變量的設置在終端輸入vi~/.bashrc添加以下行：exportPATH="$PATH:./"保存之后在命令行輸入source.bashrc4.3編寫代碼4.3.1最長公共子序列長度核心代碼intLCS(char*a,char*b){intn,m,i,j。intflag=0。n=strlen(a)-1。m=strlen(b)-1。intL[100][100]={0}。for(i=0。i<=n。i++){ if(flag||(a[i]==b[0])) { L[i][0]=1。 flag=1。 } elseL[i][0]=0。 }flag=0。for(j=0。j<=m。j++){ if(flag||(a[0]==b[j])) { L[0][j]=1。 flag=1。 } elseL[0][j]=0。}//chara[100],b[100]。for(i=1。i<=n。i++)for(j=1。j<=m。j++){if(a[i]==b[j])L[i][j]=L[i-1][j-1]+1。elseif(L[i][j-1]>=L[i-1][j])L[i][j]=L[i][j-1]。else L[i][j]=L[i-1][j]。}returnL[n][m]。}4.3.2機器學習模型的c語言實現1.在learn.h中的定義#ifndef_LEARN_H#define_LEARN_H#include"dict.h"#include<stdlib.h>#include<string.h>#include<stdio.h>#defineMAXPRES5//用戶偏好的最大個數#defineWORDLEN24//單詞最大長度#definePRENUM5//有效模式的個數typedefstruct{ charword[WORDLEN]。//用戶偏好 intcount。//次數}Preference。typedefstruct{ charinput[WORDLEN]。//用戶選擇項 Preferencepres[MAXPRES]。//最多記錄5個偏好}Record。//intRecordsize=sizeof(Record)。//一個記錄的大小voidRecordData(char*word,Node*nodes)。voidNewRecord(char*word,char*match_word)。voidAnalyse(char*word)。voidSolution(char*newData,Node*nodes)。voidDecision(Node*dst_node,Node*src_node)。//用于快速查找查詢記錄或對記錄快排intRecordcmp(constvoid*dst,constvoid*src)。intPrescmp(constvoid*dst,constvoid*src)。#endif主要函數解釋：RecordData：用于記錄用戶每次輸入的非精確單詞及其使用lcs模糊查詢得到的結果集。Analyse：分析用戶的輸入和lcs模糊結果集間的關系，提取有趣模式。NewRecord:記錄有趣模式。Solution：提取與用戶輸入的非精確單詞相關的模式記錄。Decision：根據歷史模式記錄，生成最終的決策方案。2.在learn.c中主要函數的實現voidRecordData(char*word,Node*nodes){//word代表用戶的輸入，nodes是模糊查詢的結果集 FILE*fd=fopen("./search.dat","w+b")。//打開并清空上一次的結果 if(!fd) return。 intnode_len=0。 intlen=strlen(word)。 fwrite(&len,sizeof(int),1,fd)。 fwrite(word,1,len,fd)。while(strlen(nodes[node_len].word)>0) node_len++。 fwrite(&node_len,sizeof(int),1,fd)。 fwrite(nodes,sizeof(Node),node_len,fd)。 fclose(fd)。}intRecordcmp(constvoid*dst,constvoid*src){ Record*d=(Record*)dst。 Record*s=(Record*)src。 returnstrcmp(d->input,s->input)。}//對用戶偏好按降序排序intPrescmp(constvoid*dst,constvoid*src){ Preference*d=(Preference*)dst。 Preference*s=(Preference*)src。 return(d->count)<(s->count)。}voidNewRecord(char*word,char*match_word){FILE*fd=fopen("./record.dat","a+b")。 if(!fd) return。intRecordCount=0。。Record*matched=NULL。charch。fseek(fd,0,SEEK_SET)。fread(&ch,1,1,fd)。if(ch==EOF)//即初始狀態(tài)，空文件{ RecordCount=1。 fseek(fd,0,SEEK_SET)。 fwrite(&RecordCount,sizeof(int),1,fd)。 RecordnewRcd={0}。 strcpy(newRcd.input,word)。 strcpy(newRcd.pres[0].word,match_word)。 newRcd.pres[0].count=1。fwrite(&newRcd,sizeof(Record),1,fd)。 //checkthefirstrecord 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){ intnum=0,i。//用于標識是否找到 while(strlen(matched->pres[num].word)>0) num++。//計算當前用戶偏好的數目 for(i=0。i<num。i++) { if(!strcmp(match_word,matched->pres[i].word)){ matched->pres[i].count++。 qsort(matched->pres,num,sizeof(Preference),Prescmp)。 break。 } } if(!(i<num))//匹配項不在偏好數組中 { PreferencenewPre={0}。 strcpy(newPre.word,match_word)。 newPre.count=1。 if(i<MAXPRES) matched->pres[i]=newPre。 elsematched->pres[i-1]=newPre。 }}//新記錄else{RecordCount++。 RecordnewRcd={0}。 strcpy(newRcd.input,word)。 strcpy(newRcd.pres[0].word,match_word)。 newRcd.pres[0].count=1。 records[RecordCount-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)。}}voidAnalyse(char*match_word){FILE*fd=fopen("./search.dat","rb")。 if(!fd) return。intlen=0。fread(&len,sizeof(int),1,fd)。charword[len+1]。fread(word,1,len,fd)。word[len]='\0'。//printf("valueinAnalyse:%s\n,%d",word,len)。intnode_len=0。fread(&node_len,sizeof(int),1,fd)。Nodenodes[node_len]。fread(nodes,sizeof(Node),node_len,fd)。fclose(fd)。inti=0。//判斷是否為有趣模式for(i=0。i<node_len。i++){ if(!strcmp(nodes[i].word,match_word)) { NewRecord(word,match_word)。 break。 }}}voidSolution(char*newData,Node*nodes){FILE*fd=fopen("./record.dat","rb")。 if(!fd) return。intRecordCount=0。charch。fseek(fd,0,SEEK_SET)。fread(&ch,1,1,fd)。if(ch==EOF){ fclose(fd)。 return。}fseek(fd,0,SEEK_SET)。fread(&RecordCount,sizeof(int),1,fd)。Record*records=(Record*)malloc(RecordCount*Recordsize)。fread(records,Recordsize,RecordCount,fd)。fclose(fd)。Record*matched=(Record*)bsearch(newData,records,RecordCount,Recordsize,Recordcmp)。if(!matched){//無歷史記錄 free(records)。 //printf("Solutioncalledailues\n")。 return。}//讀出有效模式，最多5個intnum=0。while(strlen(matched->pres[num].word)){ //printf("presvalue:%s\n",matched->pres[num].word)。 num++。}//printf("匹配記錄中的pres:%d\n",num)。if(num>PRENUM) num=PRENUM。inti。for(i=0。i<num。i++) strcpy(nodes[i].word,matched->pres[i].word)。free(records)。}//計算結點數目intNodenum(Node*nodes){ inti=0。while(strlen(nodes[i].word)) i++。returni。}//結點數組拷貝voidNodecpy(Node*dst_node,Node*src_node){ intsrc_count=Nodenum(src_node)。 inti=0。 for(i=0。i<src_count。i++) {strcpy(dst_node[i].word,src_node[i].word)。}}//結點查找intFindNode(char*word,Node*nodes,intnum){ inti=0。 for(i=0。i<num。i++) if(!strcasecmp(word,nodes[i].word))//找到 return1。 return0。}//src_node:nodesfromrecordfile,des_node:finalnodesarraytodualsearchvoidDecision(Node*dst_node,Node*src_node){//src_node表示從歷史數據中獲取的數據，des_node本次模糊匹配結果 intsrc_count=Nodenum(src_node)。intdst_count=Nodenum(dst_node)。 Nodetemp[dst_count]。 NodenilNode={0}。//用于結點初始化 Nodecpy(temp,dst_node)。 NodenewNodes[src_count+dst_count]。//合并 intj=0。 for(j=0。j<(src_count+dst_count)。j++) newNodes[j]=nilNode。// Nodecpy(newNodes,src_node)。 intnewCount=Nodenum(newNodes)。 inti=0。 for(i=0。i<dst_count。i++) {if(!FindNode(temp[i].word,src_node,src_count)) {newNodes[newCount]=temp[i]。 newCount++。 } } Nodecpy(dst_node,newNodes)。}5測試與分析在編寫好所有的代碼之后，在終端輸入命令gcc*.c即可編譯生成可執(zhí)行文件，然后在終端輸入./a.out按以下用例測試。5.1精確查詢的實現測試用例1：word:mopmopn.拖把,鬼臉亂蓬蓬的頭發(fā)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形式的規(guī)則，再去掉詞尾的一個字符，再次進行精確查找，輸出單詞“jump”的釋義。測試用例6：word:flowersflowern.花,精華,盛時vi.開花,旺盛,成熟vt.使開花測試結果分析：同上，flowers并不在詞庫中，是flower的復數形式，采用一般模糊查詢，輸出flower的釋義。5.3基于動態(tài)規(guī)劃的模糊查詢實現測試用例7：word:loto您是否要搜索：lotsofplotoutblotoutalotofpilotboat測試結果分析：用戶輸入“l(fā)otof”，由于詞庫中不存在該單詞，也不是由于詞尾如動名詞、單復數、過去式等原因造成的錯誤，使用一般模糊查找也無法確定出單詞的釋義。解決思路之一：使用基于全文的最長公共子序列搜索，遍歷單詞索引文件中的所有單詞，找出與“l(fā)oto”具有最長公共子序列最大值的5個單詞或詞組。但是由于基于動態(tài)規(guī)劃算法得出的最長公共子序列長度并不是基于連續(xù)子序列的（盡管它在算法的效率上是較優(yōu)的），因此還要使用機器學習模型對查詢結果集作進一步優(yōu)化。5.4機器學習模型對于LCS模糊查詢的優(yōu)化測試用例8：（由于機器學習的過程是連續(xù)，以下測試結果是緊密關聯的）1.word:departmen您是否要搜索：departeddepartureapartmentdepartmentdeportment2.word:departmentdepartmentn.部,部門。學部,系。司,局,處,科3.word:departmen您是否要搜索：departmentdeparteddepartureapartmentdeportment4.word:deportmentdeportmentn.行為,舉止5.word:departmen您是否要搜索：departmentdeportmentdeparteddepartureapartment測試結果分析：步驟1開始時不存在模式文件，輸入“departmen”查找，會進入到LCS查找，得出來的模糊結果集是：{departed,departure,apartment,department,deportment},不夠精確。步驟2用戶根據提示輸入了“department”得到釋義，并且“department”在上一次LCS查找的模糊結果集中，因此“departmen”和“department”將會作為一個有趣模式被提取出來并記錄到模式文件中。步驟3再次輸入“departmen”查詢，這時已存在記錄“department”，會優(yōu)先輸出“department”，得到優(yōu)化的模糊結果集：{department，departed,departure,apartment,deportment}。步驟4接著用戶選擇輸了“deportm