基于SVM的用戶輸入推薦模型研究

司明

摘要：在現(xiàn)代計(jì)算機(jī)接口中用戶輸入任務(wù)是非常普遍的：我們經(jīng)常需要在一個(gè)給定的輸入框中輸入一些字符串。雖然當(dāng)前用戶會(huì)采用一些簡(jiǎn)捷策略來幫助用戶端，但這往往是不夠的。該文描述了一個(gè)可以預(yù)測(cè)用戶輸入行為的新穎模型，即基于SVM的用戶輸入推薦模型，該模型提出的依據(jù)是用戶輸入行為雖然各不相同，但在動(dòng)作序列中通常伴隨著一些可識(shí)別的潛在模式。該文引入用戶輸入推薦模型的動(dòng)機(jī)在于發(fā)現(xiàn)這些隱含的用戶輸入模式并利用這些模式來做輸入預(yù)測(cè)。我們的模型理念包括兩大核心部分：用于發(fā)現(xiàn)用戶輸入模式的模式挖掘和用于預(yù)測(cè)輸入值的預(yù)測(cè)分類。

關(guān)鍵詞：用戶輸入任務(wù)；可發(fā)現(xiàn)模式；模式挖掘；預(yù)測(cè)分類

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）05-0203-03

1 引言

用戶的輸入內(nèi)容是千變?nèi)f化的，很難發(fā)現(xiàn)隱藏在其中的用戶輸入模式。例如，當(dāng)用戶打開一個(gè)文檔時(shí)，無法預(yù)測(cè)到他將要輸入的內(nèi)容。盡管如此，在許多情況下，還是存在一些有跡可循的用戶輸入的模式和規(guī)律，尤其是對(duì)于用戶界面的單行輸入框。現(xiàn)有的一些方法僅能在某種特殊情況下使用，局限性很大，不能適應(yīng)一般情況。目前，相關(guān)的研究有很多[1-6】。但是這些技術(shù)都存在一些問題，比如：內(nèi)容分析受限、有效上下文選擇和推薦范圍過窄等問題，因此，為了滿足用戶自動(dòng)化輸入要求，本文提出了基于SVM的用戶輸入推薦模型。

2 基于SVM的用戶輸入推薦模型

在用戶操作界面上，用戶的操作行為可以看作是一個(gè)個(gè)動(dòng)作組成的序列。每一個(gè)動(dòng)作包含若干參數(shù)，當(dāng)用戶在界面的輸入框內(nèi)輸入內(nèi)容時(shí)，利用相關(guān)的信息來預(yù)測(cè)用戶的輸入值，這些相關(guān)信息包括的內(nèi)容有當(dāng)前參數(shù)和歷史數(shù)據(jù)。

基于以上的思路，本文提出了基于SVM的用戶輸入推薦模型，如圖1所示。

由上圖所示，該模型主要包括兩部分，預(yù)測(cè)分類和模式挖掘。預(yù)測(cè)分類器是依據(jù)用戶輸入的實(shí)例的當(dāng)前上下文信息來預(yù)測(cè)輸出與某模式對(duì)應(yīng)的模式標(biāo)簽。模式挖掘器的主要的功能是找出潛在的動(dòng)作序列模式，從而可以對(duì)樣例輸入模式起到篩選作用。實(shí)例在經(jīng)預(yù)測(cè)分類后器處理后進(jìn)入模式挖掘器，模式挖掘器則會(huì)依據(jù)用戶輸入的歷史記錄挖掘出用戶的輸入模式，并且向用戶給出預(yù)測(cè)推薦值。在特定的用戶輸入界面下，為了規(guī)范化模式挖掘算法，引入了文獻(xiàn)[7] 以提供模式挖掘的相關(guān)定義。模式挖掘的相關(guān)算法如時(shí)間序列模式挖掘[8]、頻繁模式挖掘[9]、聚類模式挖掘[10]的研究文獻(xiàn)以及各算法應(yīng)用的研究文獻(xiàn)[11-13]都表明模式挖掘技術(shù)的研究也是數(shù)據(jù)挖掘領(lǐng)域內(nèi)的熱點(diǎn)。

3 預(yù)測(cè)分類算法

根據(jù)用戶輸入推薦模型可以看出，新實(shí)例首先進(jìn)入預(yù)測(cè)分類器，根據(jù)實(shí)例的特征信息輸出模式標(biāo)簽，模式標(biāo)簽對(duì)應(yīng)于模式，模式挖掘器根據(jù)模式類型生成預(yù)測(cè)推薦值，該預(yù)測(cè)分類算法流程如圖2所示。

支持向量機(jī)（Support Vector Machine， SVM）[14]是一種傳統(tǒng)的機(jī)器學(xué)習(xí)方法[15]。它將輸入的樣本特征向量集合變換到高維空間，在高維空間中構(gòu)造最優(yōu)分類超平面來使樣本進(jìn)行分離。SVM算法的分類函數(shù)在形式上類似神經(jīng)網(wǎng)絡(luò)，輸出是中間節(jié)點(diǎn)的線性組合，每個(gè)中間節(jié)點(diǎn)對(duì)應(yīng)一個(gè)支持向量，向量之間只進(jìn)行點(diǎn)積運(yùn)算。SVM用于分類的表達(dá)式為：

如果采用核函數(shù)，就可以避免在高維特征空間進(jìn)行復(fù)雜的運(yùn)算。該過程可以這樣描述：首先將輸入向量x通過映射：Rn->H映射到高維Hibert空間H中。該函數(shù)K滿足，顯然不同的核函數(shù)決定了不同的決策曲面（即支持不同的向量機(jī)）。核函數(shù)的形式是多種多樣的，例如以下幾種常用的核函數(shù)：

多項(xiàng)式核函數(shù)：

徑向基核函數(shù)：

神經(jīng)網(wǎng)絡(luò)核函數(shù)：

實(shí)際上，SVM的核心思想是利用核函數(shù)將輸入樣本空間映射到高維特征空間，在這個(gè)空間中求一個(gè)最優(yōu)分類面f（x）=wT·x+b=0，根據(jù)f（x）構(gòu)造新的符號(hào)函數(shù)g（x），根據(jù)g（x）的取值將數(shù)據(jù)點(diǎn)即樣本進(jìn)行分類。簡(jiǎn)言之，SVM算法的原理就是給分類對(duì)象找到合適的核函數(shù)以構(gòu)造最優(yōu)分類決策平面，達(dá)到對(duì)輸入樣本進(jìn)行分類的目的。

由于SVM分類器是一個(gè)兩類分類器，只能實(shí)現(xiàn)兩類劃分，在解決多類劃分的問題時(shí)則需要作進(jìn)一步處理。通常通過組合多個(gè)SVM分類器來實(shí)現(xiàn)多類劃分問題。對(duì)于本課題的用戶輸入推薦模型中用戶動(dòng)作序列模式可以構(gòu)造一對(duì)多型分類器，構(gòu)造N個(gè)兩類分類器，通過比較分類器的輸出來判定分類結(jié)果。

SVM決策樹是將SVM分類算法和二叉決策樹[16]結(jié)合起來構(gòu)成的分類算法。針對(duì)本文用戶輸入推薦模型中的動(dòng)作序列， [A1（P11，P12…P1j…P1k），A2（P21，P22…P2j…P2k）……Ai（Pi1，Pi2…Pij…Pik）……AN（PN1，PN2…PNj…PNk）] （其中，Ai是動(dòng)作序列中的一個(gè)動(dòng)作，Pij是動(dòng)作中的一個(gè)參數(shù)）設(shè)計(jì)SVM決策樹[15] 算法。該算法的基本思想是：先將所有的動(dòng)作合成兩大類，再將每一大類分成兩個(gè)子類，如此進(jìn)行下去，直到得到最基本的所有單個(gè)動(dòng)作類別為止，這樣就形成了一棵二叉樹，在每棵樹非葉子節(jié)點(diǎn)都使用一個(gè)SVM分類器，葉子結(jié)點(diǎn)代表類別。一個(gè)N類可分的SVM決策樹共需要構(gòu)造N-1個(gè)SVM分類器。簡(jiǎn)單假設(shè)有動(dòng)作A、B、C、D，可以構(gòu)造SVM決策樹如圖：

為了構(gòu)造一個(gè)SVM分類器，需要確定決策樹的結(jié)構(gòu)以及每一個(gè)非葉子結(jié)點(diǎn)的類劃分方案，即采用不同的數(shù)組作為結(jié)點(diǎn)SVM分類器的正例類集合和反例類集合。各個(gè)分類器的性能取決于正反例類集合之間的可分性，類集合的可分性取決于構(gòu)成這兩個(gè)類集合的各類之間的相互可分性。各類間的可分性越好，則分類器的性能越好。

4 基于SVM決策樹的用戶輸入值推薦詳細(xì)步驟

根據(jù)上文提及的動(dòng)作序列進(jìn)行分析：

[A1（P11，P12…P1j…P1k），A2（P21，P22…P2j…P2k）……Ai（Pi1，Pi2…Pij…Pik）……AN（PN1，PN2…PNj…PNk）]

由此可以看出用戶動(dòng)作是很多的，與其對(duì)應(yīng)的動(dòng)作參數(shù)也是很多的，這樣諸多的動(dòng)作和與之對(duì)應(yīng)的參數(shù)之間的交涉就形成了一系列的動(dòng)作序列，而經(jīng)過訓(xùn)練后在這些動(dòng)作序列中發(fā)現(xiàn)的特征和規(guī)律就形成了規(guī)范化的動(dòng)作序列模式。每個(gè)動(dòng)作模式對(duì)應(yīng)一個(gè)模式標(biāo)簽。

用戶輸入推薦模型中預(yù)測(cè)分類與模式挖掘的具體步驟如下所示：

（1）當(dāng)用戶進(jìn)入用戶操作界面，首先做出一個(gè)引發(fā)動(dòng)作A，例如該動(dòng)作可定義為界面點(diǎn)擊。

（2）用戶動(dòng)作涉及相關(guān)動(dòng)作參數(shù)p，如選定對(duì)象的標(biāo)題、窗體界面上的按鈕等。

（3）用A（p0）表示動(dòng)作事件的觸發(fā)實(shí)例，構(gòu)造該實(shí)例所引發(fā)的個(gè)各關(guān)聯(lián)動(dòng)作及其參數(shù)之間的動(dòng)作序列：（A（p0）->A（p11）->A（p12）···A（p1i），A（p0）->A（p21）-> A（p22）···A（p2i），···A（p0）-> A（pk1）-> A（pk2）···A（pki））。用點(diǎn)擊動(dòng)作描述這一序列就是用戶在進(jìn)行點(diǎn)擊操作時(shí)由于所選參數(shù)不同而執(zhí)行不同的操作路徑。

（4）記錄數(shù)據(jù)

1）記錄數(shù)據(jù)：用戶動(dòng)作A（pki）被執(zhí)行的次數(shù)Num。

2）記錄數(shù)據(jù)：動(dòng)作序列中前后關(guān)聯(lián)動(dòng)A（pk（i-1）） ---> A（pki）之間的用戶輸入值Value，作為歷史記錄。

（5）以Num和Value作為支撐數(shù)據(jù)對(duì)用戶輸入值進(jìn)行預(yù)測(cè)分析，過程如下：

當(dāng)用戶做出觸發(fā)動(dòng)作事件A（p0）時(shí)，首先在模式庫中找出A（p0）引發(fā)的動(dòng)作序列中發(fā)生次數(shù)最多的路徑作為首要預(yù)測(cè)模式；然后系統(tǒng)將預(yù)測(cè)模式推薦給模式挖掘器，模式挖掘器結(jié)合相應(yīng)歷史記錄和用戶輸入過程的關(guān)鍵字產(chǎn)生最優(yōu)推薦值Value1給用戶。

1） 當(dāng)用戶接受推薦值Value1時(shí)則說明預(yù)測(cè)分類器成功，可以將該實(shí)例增加到訓(xùn)練樣本中，作為訓(xùn)練記錄的增加量。

2） 當(dāng)用戶沒有接受推薦值Value1時(shí)，即用戶的輸入值為Value2 ，則應(yīng)該將Value2與其他模式產(chǎn)生的預(yù)測(cè)值進(jìn)行比較。

① 當(dāng)在其他模式下產(chǎn)生的預(yù)測(cè)值和Value2 相同時(shí)，說明原預(yù)測(cè)分類是失敗的，然后將新的實(shí)例添加到訓(xùn)練樣本中。

② 當(dāng)在其他模式中未發(fā)現(xiàn)未能發(fā)現(xiàn)產(chǎn)生的預(yù)測(cè)值與Value2相同時(shí)， 模式挖掘器將會(huì)以Value2 作為關(guān)鍵字，分析特征值和歷史數(shù)據(jù)，建立一個(gè)新的模式Npattern，（Value2 ，Npattern）則構(gòu)成新模式Npattern下的實(shí)例，定義其對(duì)應(yīng)的模式標(biāo)簽作為該模式的唯一標(biāo)識(shí)。

5 總結(jié)

（1） 就挖掘效果而言，采用傳統(tǒng)算法挖掘潛在的用戶動(dòng)作序列模式代價(jià)是很高的，是因?yàn)橛脩舻牟僮髁?xí)慣的不同導(dǎo)致動(dòng)作序列的千差萬別，因此從大量的動(dòng)作序列中去發(fā)現(xiàn)有跡可循的動(dòng)作序列模式是很復(fù)雜的?？v使預(yù)測(cè)值的精度可以達(dá)到很高，但是挖掘模式的效果不夠理想，為用戶提供的幫助具有很大的局限性。該模型根據(jù)經(jīng)過訓(xùn)練的歷史數(shù)據(jù)來挖掘用戶的輸入模式，在用戶輸入操作特定的情況下，生成最優(yōu)預(yù)測(cè)推薦值。經(jīng)過大量的訓(xùn)練、特征查詢則會(huì)發(fā)現(xiàn)隱藏在其中的序列模式，此過程則實(shí)現(xiàn)了模式序列挖掘工作。

（2） 就挖掘效率而言。本文采用基于SVM決策樹的分類算法，把原動(dòng)作序列映射到高維空間，通過在高維空間構(gòu)造分類函數(shù)來實(shí)現(xiàn)原動(dòng)作序列的模式劃分，解決了維數(shù)災(zāi)難問題，此外該算法有效地降低了在線計(jì)算時(shí)間，進(jìn)行預(yù)測(cè)分類的效率較高。

（3） 就應(yīng)用前景而言。隨著計(jì)算機(jī)領(lǐng)域技術(shù)的飛速發(fā)展，人機(jī)交互成為了人們處理工作的主流模式，人機(jī)交互技術(shù)的發(fā)展則成為研究領(lǐng)域內(nèi)炙手可熱的焦點(diǎn)。用戶輸入推薦模型作為一種智能的人機(jī)交互處理技術(shù)，理論上為用戶解決日常繁瑣的輸入任務(wù)提供便捷高效的服務(wù)，無疑是人機(jī)交互技術(shù)中的一大突破，因此，用戶輸入推薦技術(shù)的應(yīng)用前景十分廣闊。

（4） 本文結(jié)合SVM算法提出輔助用戶輸入的新模型——用戶輸入推薦模型，該模型提供了輔助用戶自動(dòng)化輸入的新思路，并以模式挖掘和預(yù)測(cè)分類作為本模型的兩大核心模塊。文中詳細(xì)介紹了SVM預(yù)測(cè)分類方法，并結(jié)合用戶輸入的動(dòng)作序列設(shè)計(jì)了基于SVM決策樹的分類方法，以通過訓(xùn)練得到可支撐數(shù)據(jù)模型作為預(yù)測(cè)分類的依據(jù)。該算法可以同時(shí)最小化經(jīng)驗(yàn)誤差與最大幾何邊緣區(qū)。SVM作為數(shù)據(jù)挖掘中分類方法與其他算法比較時(shí)，總能表現(xiàn)出更好的性能和效果，這是因?yàn)镾VM在分類原理和方法上是一個(gè)根本性的解決方案，其給出的是全局最優(yōu)解，所以該算法極大提高了預(yù)測(cè)分類的正確率。

參考文獻(xiàn)：

[1]Anne Tomes， Peter Armstrong， Murray Clark .User groups in action： The management of user inputs in the NPD process[J].Technovation， 1996， 16 （10）：541-551.

[2]S. Fukushima A L. Ralescu.Improved retrieval in a fuzzy database from adjusted user input[J].Journal of Intelligent Information Systems， 1995， 5 （3）：249-274.

[3] Kartic Subr， Sylvain Paris， Cyril Soler， Jan Kautz.Accurate Binary Image Selection from Inaccurate User Input[J].Computer Graphics Forum， 2013， 32 （2pt1）：41-50.

[4] Morrill C S， Goodwin N C， Smith S L .User input mode and computer-aided instruction[J].Human factors， 1968， 10 （3）.

[5] Fangju Wang， Kyle Swegles.Modeling user behavior online for disambiguating user input in a spoken dialogue system[J].Speech Communication， 2013.

[6] Lex van Velsen， Corrie Huijs， Thea van der Geest .Eliciting User Input for Requirements on Personalization： The Case of a Dutch ERP System[J].International Journal of Enterprise Information Systems （IJEIS）， 2008， 4 .

[7] AGRAWAL R， IMIELINSKI T， WAMI A.S.Mining association rules between sets of items in large databases[C].Proceedings of the ACM SIGMOD Conference on Management of data， 1993.

[8] Chieh-Yuan Tsai，Bo-Han Lai， J. Lu.A Location-Item-Time sequential pattern mining algorithm for route recommendation[J]. Knowledge-Based Systems，2014.

[9] Ke-Chung Lin， I-En Liao， Tsui-Ping Chang. A frequent itemset mining algorithm based on the Principle of Inclusion–Exclusion and transaction mapping[J]. Information Sciences， 2014.

[10] Swee Chuan Tan， Kai Ming Ting， Shyh Wei Teng. A general stochastic clustering method for automatic cluster discovery[J]. Pattern Recognition， 2011，44 （10）.

[11] Elsa Loekito， James Bailey， Jian Pei. A binary decision diagram based approach for mining frequent subsequences[J]. Knowledge and Information Systems， 2010， 24（2）.

[12] Aileen P Wright， Adam T Wright， Allison B. McCoy et al.. The use of sequential pattern mining to predict next prescribed medications[J]. Journal of Biomedical Informatics， 2014.

[13] Guo-Cheng Lan， Tzung-Pei Hong， Vincent S Tseng et al.. Applying the maximum utility measure in high utility sequential pattern mining[J]. Expert Systems With Applications， 2014.

[14] Yubo Yuan.Forecasting the movement direction of exchange rate with polynomial smooth support vector machine[J]. Mathematical and Computer Modelling， 2013， 57（3-4）.

[15] Haijun Zhai， Patrick Brady， Qi Li et al.. Developing and evaluating a machine learning based algorithm to predict the need of pediatric intensive care unit transfer for newly hospitalized children[J]. Resuscitation， 2014.

[16] Kemal Polat， Salih Güne?. The effect to diagnostic accuracy of decision tree classifier of fuzzy and k-NN based weighted pre-processing methods to diagnosis of erythemato-squamous diseases[J]. Digital Signal Processing， 2006， 16 （6）： 922-930.