基于SVM的用户输入推荐模型研究

摘要：在现代计算机接口中用户输入任务是非常普遍的：我们经常需要在一个给定的输入框中输入一些字符串。虽然当前用户会采用一些简捷策略来帮助用户端，但这往往是不够的。该文描述了一个可以预测用户输入行为的新颖模型，即基于SVM的用户输入推荐模型，该模型提出的依据是用户输入行为虽然各不相同，但在动作序列中通常伴随着一些可识别的潜在模式。该文引入用户输入推荐模型的动机在于发现这些隐含的用户输入模式并利用这些模式来做输入预测。我们的模型理念包括两大核心部分：用于发现用户输入模式的模式挖掘和用于预测输入值的预测分类。

关键词：用户输入任务；可发现模式；模式挖掘；预测分类

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）05-0203-03

1 引言

用户的输入内容是千变万化的，很难发现隐藏在其中的用户输入模式。例如，当用户打开一个文档时，无法预测到他将要输入的内容。尽管如此，在许多情况下，还是存在一些有迹可循的用户输入的模式和规律，尤其是对于用户界面的单行输入框。现有的一些方法仅能在某种特殊情况下使用，局限性很大，不能适应一般情况。目前，相关的研究有很多[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） 就挖掘效果而言，采用传统算法挖掘潜在的用户动作序列模式代价是很高的，是因为用户的操作习惯的不同导致动作序列的千差万别，因此从大量的动作序列中去发现有迹可循的动作序列模式是很复杂的。纵使预测值的精度可以达到很高，但是挖掘模式的效果不够理想，为用户提供的帮助具有很大的局限性。该模型根据经过训练的历史数据来挖掘用户的输入模式，在用户输入操作特定的情况下，生成最优预测推荐值。经过大量的训练、特征查询则会发现隐藏在其中的序列模式，此过程则实现了模式序列挖掘工作。

（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 InclusionCExclusion 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.