基于SVM的用戶輸入推薦模型研究
2015-10-24 05:25:57司明
電腦知識與技術 2015年5期
司明
摘要：在現代計算機接口中用戶輸入任務是非常普遍的：我們經常需要在一個給定的輸入框中輸入一些字符串。雖然當前用戶會采用一些簡捷策略來幫助用戶端，但這往往是不夠的。該文描述了一個可以預測用戶輸入行為的新穎模型，即基于SVM的用戶輸入推薦模型，該模型提出的依據是用戶輸入行為雖然各不相同，但在動作序列中通常伴隨著一些可識別的潛在模式。該文引入用戶輸入推薦模型的動機在于發現這些隱含的用戶輸入模式并利用這些模式來做輸入預測。我們的模型理念包括兩大核心部分：用于發現用戶輸入模式的模式挖掘和用于預測輸入值的預測分類。
關鍵詞：用戶輸入任務；可發現模式；模式挖掘；預測分類
中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2015）05-0203-03
1 引言
用戶的輸入內容是千變萬化的，很難發現隱藏在其中的用戶輸入模式。例如，當用戶打開一個文檔時，無法預測到他將要輸入的內容。盡管如此，在許多情況下，還是存在一些有跡可循的用戶輸入的模式和規律，尤其是對于用戶界面的單行輸入框?，F有的一些方法僅能在某種特殊情況下使用，局限性很大，不能適應一般情況。目前，相關的研究有很多[1-6】。但是這些技術都存在一些問題，比如：內容分析受限、有效上下文選擇和推薦范圍過窄等問題，因此，為了滿足用戶自動化輸入要求，本文提出了基于SVM的用戶輸入推薦模型。
2 基于SVM的用戶輸入推薦模型
在用戶操作界面上，用戶的操作行為可以看作是一個個動作組成的序列。每一個動作包含若干參數，當用戶在界面的輸入框內輸入內容時，利用相關的信息來預測用戶的輸入值，這些相關信息包括的內容有當前參數和歷史數據。
基于以上的思路，本文提出了基于SVM的用戶輸入推薦模型，如圖1所示。
由上圖所示，該模型主要包括兩部分，預測分類和模式挖掘。預測分類器是依據用戶輸入的實例的當前上下文信息來預測輸出與某模式對應的模式標簽。模式挖掘器的主要的功能是找出潛在的動作序列模式，從而可以對樣例輸入模式起到篩選作用。實例在經預測分類后器處理后進入模式挖掘器，模式挖掘器則會依據用戶輸入的歷史記錄挖掘出用戶的輸入模式，并且向用戶給出預測推薦值。在特定的用戶輸入界面下，為了規范化模式挖掘算法，引入了文獻[7] 以提供模式挖掘的相關定義。模式挖掘的相關算法如時間序列模式挖掘[8]、頻繁模式挖掘[9]、聚類模式挖掘[10]的研究文獻以及各算法應用的研究文獻[11-13]都表明模式挖掘技術的研究也是數據挖掘領域內的熱點。
3 預測分類算法
根據用戶輸入推薦模型可以看出，新實例首先進入預測分類器，根據實例的特征信息輸出模式標簽，模式標簽對應于模式，模式挖掘器根據模式類型生成預測推薦值，該預測分類算法流程如圖2所示。
支持向量機（Support Vector Machine， SVM）[14]是一種傳統的機器學習方法[15]。它將輸入的樣本特征向量集合變換到高維空間，在高維空間中構造最優分類超平面來使樣本進行分離。SVM算法的分類函數在形式上類似神經網絡，輸出是中間節點的線性組合，每個中間節點對應一個支持向量，向量之間只進行點積運算。SVM用于分類的表達式為：
如果采用核函數，就可以避免在高維特征空間進行復雜的運算。該過程可以這樣描述：首先將輸入向量x通過映射：Rn->H映射到高維Hibert空間H中。該函數K滿足
多項式核函數：
徑向基核函數：
神經網絡核函數：
實際上，SVM的核心思想是利用核函數將輸入樣本空間映射到高維特征空間，在這個空間中求一個最優分類面f（x）=wT·x+b=0，根據f（x）構造新的符號函數g（x），根據g（x）的取值將數據點即樣本進行分類。簡言之，SVM算法的原理就是給分類對象找到合適的核函數以構造最優分類決策平面，達到對輸入樣本進行分類的目的。
由于SVM分類器是一個兩類分類器，只能實現兩類劃分，在解決多類劃分的問題時則需要作進一步處理。通常通過組合多個SVM分類器來實現多類劃分問題。對于本課題的用戶輸入推薦模型中用戶動作序列模式可以構造一對多型分類器，構造N個兩類分類器，通過比較分類器的輸出來判定分類結果。
SVM決策樹是將SVM分類算法和二叉決策樹[16]結合起來構成的分類算法。針對本文用戶輸入推薦模型中的動作序列， [A1（P11，P12…P1j…P1k），A2（P21，P22…P2j…P2k）……Ai（Pi1，Pi2…Pij…Pik）……AN（PN1，PN2…PNj…PNk）] （其中，Ai是動作序列中的一個動作，Pij是動作中的一個參數）設計SVM決策樹[15] 算法。該算法的基本思想是：先將所有的動作合成兩大類，再將每一大類分成兩個子類，如此進行下去，直到得到最基本的所有單個動作類別為止，這樣就形成了一棵二叉樹，在每棵樹非葉子節點都使用一個SVM分類器，葉子結點代表類別。一個N類可分的SVM決策樹共需要構造N-1個SVM分類器。簡單假設有動作A、B、C、D，可以構造SVM決策樹如圖：
為了構造一個SVM分類器，需要確定決策樹的結構以及每一個非葉子結點的類劃分方案，即采用不同的數組作為結點SVM分類器的正例類集合和反例類集合。各個分類器的性能取決于正反例類集合之間的可分性，類集合的可分性取決于構成這兩個類集合的各類之間的相互可分性。各類間的可分性越好，則分類器的性能越好。
4 基于SVM決策樹的用戶輸入值推薦詳細步驟
根據上文提及的動作序列進行分析：
[A1（P11，P12…P1j…P1k），A2（P21，P22…P2j…P2k）……Ai（Pi1，Pi2…Pij…Pik）……AN（PN1，PN2…PNj…PNk）]
由此可以看出用戶動作是很多的，與其對應的動作參數也是很多的，這樣諸多的動作和與之對應的參數之間的交涉就形成了一系列的動作序列，而經過訓練后在這些動作序列中發現的特征和規律就形成了規范化的動作序列模式。每個動作模式對應一個模式標簽。
用戶輸入推薦模型中預測分類與模式挖掘的具體步驟如下所示：
（1）當用戶進入用戶操作界面，首先做出一個引發動作A，例如該動作可定義為界面點擊。
（2）用戶動作涉及相關動作參數p，如選定對象的標題、窗體界面上的按鈕等。
（3）用A（p0）表示動作事件的觸發實例，構造該實例所引發的個各關聯動作及其參數之間的動作序列：（A（p0）->A（p11）->A（p12）···A（p1i），A（p0）->A（p21）-> A（p22）···A（p2i），···A（p0）-> A（pk1）-> A（pk2）···A（pki））。用點擊動作描述這一序列就是用戶在進行點擊操作時由于所選參數不同而執行不同的操作路徑。
（4）記錄數據
1）記錄數據：用戶動作A（pki）被執行的次數Num。
2）記錄數據：動作序列中前后關聯動A（pk（i-1）） ---> A（pki）之間的用戶輸入值Value，作為歷史記錄。
（5）以Num和Value作為支撐數據對用戶輸入值進行預測分析，過程如下：
當用戶做出觸發動作事件A（p0）時，首先在模式庫中找出A（p0）引發的動作序列中發生次數最多的路徑作為首要預測模式；然后系統將預測模式推薦給模式挖掘器，模式挖掘器結合相應歷史記錄和用戶輸入過程的關鍵字產生最優推薦值Value1給用戶。
1） 當用戶接受推薦值Value1時則說明預測分類器成功，可以將該實例增加到訓練樣本中，作為訓練記錄的增加量。
2） 當用戶沒有接受推薦值Value1時，即用戶的輸入值為Value2 ，則應該將Value2與其他模式產生的預測值進行比較。
① 當在其他模式下產生的預測值和Value2 相同時，說明原預測分類是失敗的，然后將新的實例添加到訓練樣本中。
② 當在其他模式中未發現未能發現產生的預測值與Value2相同時， 模式挖掘器將會以Value2 作為關鍵字，分析特征值和歷史數據，建立一個新的模式Npattern，（Value2 ，Npattern）則構成新模式Npattern下的實例，定義其對應的模式標簽作為該模式的唯一標識。
5 總結
（1） 就挖掘效果而言，采用傳統算法挖掘潛在的用戶動作序列模式代價是很高的，是因為用戶的操作習慣的不同導致動作序列的千差萬別，因此從大量的動作序列中去發現有跡可循的動作序列模式是很復雜的?？v使預測值的精度可以達到很高，但是挖掘模式的效果不夠理想，為用戶提供的幫助具有很大的局限性。該模型根據經過訓練的歷史數據來挖掘用戶的輸入模式，在用戶輸入操作特定的情況下，生成最優預測推薦值。經過大量的訓練、特征查詢則會發現隱藏在其中的序列模式，此過程則實現了模式序列挖掘工作。
（2） 就挖掘效率而言。本文采用基于SVM決策樹的分類算法，把原動作序列映射到高維空間，通過在高維空間構造分類函數來實現原動作序列的模式劃分，解決了維數災難問題，此外該算法有效地降低了在線計算時間，進行預測分類的效率較高。
（3） 就應用前景而言。隨著計算機領域技術的飛速發展，人機交互成為了人們處理工作的主流模式，人機交互技術的發展則成為研究領域內炙手可熱的焦點。用戶輸入推薦模型作為一種智能的人機交互處理技術，理論上為用戶解決日常繁瑣的輸入任務提供便捷高效的服務，無疑是人機交互技術中的一大突破，因此，用戶輸入推薦技術的應用前景十分廣闊。
（4） 本文結合SVM算法提出輔助用戶輸入的新模型——用戶輸入推薦模型，該模型提供了輔助用戶自動化輸入的新思路，并以模式挖掘和預測分類作為本模型的兩大核心模塊。文中詳細介紹了SVM預測分類方法，并結合用戶輸入的動作序列設計了基于SVM決策樹的分類方法，以通過訓練得到可支撐數據模型作為預測分類的依據。該算法可以同時最小化經驗誤差與最大幾何邊緣區。SVM作為數據挖掘中分類方法與其他算法比較時，總能表現出更好的性能和效果，這是因為SVM在分類原理和方法上是一個根本性的解決方案，其給出的是全局最優解，所以該算法極大提高了預測分類的正確率。
參考文獻：
[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.
