許丹青，劉奕群，岑榮偉，馬少平，茹立云，楊 磊

(智能技術(shù)與系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，清華信息科學(xué)與技術(shù)國(guó)家實(shí)驗(yàn)室(籌)，清華大學(xué)計(jì)算機(jī)系，北京 100084)

1 前言

隨著互聯(lián)網(wǎng)在中國(guó)的蓬勃發(fā)展，中國(guó)網(wǎng)民的比例越來(lái)越大，據(jù)統(tǒng)計(jì)，直至2010年初，中國(guó)網(wǎng)民已達(dá)到了3.84億，位于全球首位[1]。中文輸入法作為中國(guó)網(wǎng)民在互聯(lián)網(wǎng)上必不可少的輸入工具，其作用也變得越來(lái)越重要。與英文輸入不同，中文的很多候選詞條所對(duì)應(yīng)的拼音輸入相同，如果對(duì)于一個(gè)拼音輸入而言，大多數(shù)用戶都選擇了某個(gè)詞條作為最終的結(jié)果，那么我們就將這個(gè)詞條排在越靠前的位置。這也是當(dāng)前的很多輸入法所采用的排序策略的主要思路。由于數(shù)據(jù)收集和分析的困難，以前對(duì)輸入法的研究主要集中用自然語(yǔ)言處理的方法，將現(xiàn)有的一些分詞算法和排序算法進(jìn)行一些優(yōu)化和改進(jìn)[2-3],而對(duì)目前輸入法的用戶行為研究并不多見。我們主要對(duì)經(jīng)過用戶許可收集的某中文輸入法一天的數(shù)據(jù)進(jìn)行分析，希望可以從中得到輸入法用戶行為的一些普適特征，為當(dāng)前的輸入法日后的改進(jìn)提供幫助。由于日志數(shù)據(jù)規(guī)模較大，所以結(jié)論具有一般性，能反映大多數(shù)用戶的行為特征。

本文后續(xù)的內(nèi)容組織如下：第2節(jié)是對(duì)前人相關(guān)工作的一些概述，第3節(jié)簡(jiǎn)單描述了我們采用的輸入法格式，第4節(jié)從三個(gè)不同方面對(duì)輸入法日志的用戶行為進(jìn)行分析，第5節(jié)從分析的結(jié)果中嘗試得出一些對(duì)當(dāng)前輸入法改進(jìn)有用的啟示和結(jié)論，第6節(jié)是參考文獻(xiàn)說明。

2 相關(guān)工作概述

由于Web數(shù)據(jù)規(guī)模龐大且數(shù)據(jù)格式等比較雜亂，因此，現(xiàn)有的輸入法必須經(jīng)過分詞、過濾、排序等操作才能得到能夠供用戶使用的詞條。同時(shí)由于與用戶體驗(yàn)聯(lián)系緊密，這部分的工作主要集中在產(chǎn)業(yè)界，目前研究界使用較多的是用戶查詢?cè)~日志，前人多次使用查詢?nèi)罩緦?duì)用戶需求進(jìn)行分析[4]，最典型的使用就是查詢推薦和查詢糾錯(cuò)。而目前的產(chǎn)業(yè)界的輸入法分析改進(jìn)主要集中在全局的詞庫(kù)生成算法和詞條排序算法，通過詞庫(kù)生成算法生成格式規(guī)整的詞庫(kù)，然后再通過詞頻等一系列的特征進(jìn)行權(quán)重計(jì)算，對(duì)候選詞條進(jìn)行最終的排序。

前不久，中國(guó)科學(xué)院研究生院的張瑋[5]等人提出了一種結(jié)合分類模型的中文輸入法，他們針對(duì)現(xiàn)有輸入法很少用的候選詞本身的特性，將輸入法詞庫(kù)進(jìn)行了類別標(biāo)注，同時(shí)根據(jù)用戶當(dāng)前輸入串的上下文判定當(dāng)前的輸入語(yǔ)境類別，提高屬于當(dāng)前類別詞庫(kù)的詞條在整個(gè)詞庫(kù)中對(duì)應(yīng)權(quán)重，這樣符合上下文語(yǔ)境的詞條就會(huì)排在相對(duì)靠前的位置。這種對(duì)輸入法詞庫(kù)進(jìn)行類別標(biāo)注并在輸入法系統(tǒng)中集成分類引擎的方法，可以在一定程度上提高用戶的輸入效率和體驗(yàn)度的，然而，其工作缺乏大規(guī)模數(shù)據(jù)集的訓(xùn)練和測(cè)試。

此外，輸入法的用戶交互行為也很重要。之前，我們就某中文輸入法某一天的日志進(jìn)行了簡(jiǎn)單的分析[6]，主要從用戶使用的應(yīng)用程序的相對(duì)熵值和用戶半徑這兩個(gè)特征簡(jiǎn)單分析了各個(gè)應(yīng)用程序類別的用戶行為，研究結(jié)果顯示有著相同用戶需求的應(yīng)用程序之間有著相似的屬性。基于之前的工作，本文將從其他多個(gè)方面對(duì)輸入法的用戶行為進(jìn)行詳細(xì)分析。

3 輸入法日志格式說明

該實(shí)驗(yàn)中所采用的日志是來(lái)自于某中文輸入法“用戶體驗(yàn)提升計(jì)劃”記錄的用戶行為日志，該部分日志得到了行為信息收集對(duì)象的同意，完全為匿名記錄。我們選取了2009年11月1日當(dāng)天的日志數(shù)據(jù)，其涵蓋了4.1億條用戶輸入條目，417萬(wàn)個(gè)獨(dú)立用戶和8 232個(gè)應(yīng)用程序。其中每條用戶輸入條目包含的信息如表1所示。

表1 輸入法日志格式

4 基于輸入法日志的用戶行為分析

4.1 詞頻與應(yīng)用程序使用頻度的分析

該實(shí)驗(yàn)中，我們對(duì)日志中的所有詞條以及所有應(yīng)用程序按照其使用頻度進(jìn)行了排序，并分析了使用頻度和其對(duì)應(yīng)的排序之間的關(guān)系，如圖1所示。

圖1 詞條和應(yīng)用程序的使用頻度與對(duì)應(yīng)排名的關(guān)系

圖1顯示，應(yīng)用程序和詞條的使用頻度是符合冪律分布的，即極少數(shù)的應(yīng)用程序和詞條的使用頻度占了所有應(yīng)用程序頻度的絕大多數(shù)。統(tǒng)計(jì)發(fā)現(xiàn)，排名前10的應(yīng)用程序的頻度占了輸入法總數(shù)的77.4%，而排名第1的應(yīng)用程序—— 騰訊QQ聊天程序的使用頻度占了總使用頻度的44.2%。這里，為了更加方便的對(duì)排名前10的應(yīng)用程序進(jìn)行深入的研究和分析，我們?cè)诒?列出了使用頻度排名前10的應(yīng)用程序的名稱。

從表2可以看出，使用頻度排名前10的應(yīng)用程序主要分為四類：即時(shí)通信類、游戲類、瀏覽器類和辦公編輯類。本文中， 我們將針對(duì)這四個(gè)主要類別和這10個(gè)應(yīng)用程序的詞頻等特征展開分析。

表2 排名前10對(duì)應(yīng)的應(yīng)用程序

4.2 各個(gè)主要應(yīng)用程序間一元，二元詞頻相似度分析

在這些主要應(yīng)用程序的基礎(chǔ)上，我們還分別對(duì)它們的一元與二元高頻詞進(jìn)行統(tǒng)計(jì)，根據(jù)兩個(gè)應(yīng)用程序之間的一元(或是二元)詞頻的前200個(gè)詞中所包含的相同詞的個(gè)數(shù)，從而計(jì)算兩個(gè)應(yīng)用程序之間的相似度。假設(shè)應(yīng)用程序a一元(或是二元)詞頻的前200個(gè)詞的集合為Va,應(yīng)用程序b的一元(或是二元)詞頻的前200個(gè)詞的集合為Vb,我們定義a與b的相似度計(jì)算公式如公式(1)。

(1)

另外，除了對(duì)應(yīng)用程序之間進(jìn)行了詞頻相似度的計(jì)算外，我們還對(duì)兩個(gè)類別之間的應(yīng)用程序進(jìn)行了平均相似度的計(jì)算。假設(shè)有k個(gè)程序?qū)儆谀骋活悇eA(i=1…k)，n個(gè)程序?qū)儆谀骋活悇eB(j=1…n)，類別A和類別B之間的一元(二元)詞頻的平均相似度計(jì)算公式如公式(2)。

(2)

我們對(duì)輸入法中的主要應(yīng)用程序(見表2)的一元詞頻的top200進(jìn)行了提取，并分別根據(jù)公式(1)和公式(2)進(jìn)行了一元相似度和二元相似度的計(jì)算，表3 顯示了各個(gè)程序之間的相似度結(jié)果，其中上三角表示的是一元相似度的計(jì)算結(jié)果，而下三角表示的是二元相似度的對(duì)應(yīng)的計(jì)算結(jié)果。

通過表3的詞頻相似度結(jié)果的對(duì)比， 我們可以很明顯的看出： 有著相同的用戶需求的應(yīng)用程序的詞頻相似度要明顯高于其他不同需求的程序。如程序“qq”與“fetion”的之間的相似度明顯高于其和“dnf”，“winword”等程序。在本節(jié)中，我們主要就高頻詞條的相似度作為衡量應(yīng)用程序的用戶行為的一個(gè)特征。表3的結(jié)果顯示，相同類別的應(yīng)用程序之間的高頻相似度很高，即相同類別的應(yīng)用程序有著相似的用戶行為。為了進(jìn)一步深入探索用戶需求與應(yīng)用程序的關(guān)系，接下來(lái)我們對(duì)主要應(yīng)用程序類別之間的一元平均相似度和二元平均相似度分類別進(jìn)行觀察比較。

表3 主要應(yīng)用程序的詞頻相似度

表3顯示了相同類別的應(yīng)用程序的詞頻相似度很高，因此，我們將各個(gè)主要應(yīng)用程序根據(jù)其用戶需求的不同進(jìn)行了類別分類，并且對(duì)類別之間和類別之內(nèi)的平均相似度按照公式(2)進(jìn)行計(jì)算。類別內(nèi)部的平均相似度是所有這個(gè)類別內(nèi)部的應(yīng)用程序相似度的平均值，與此類似，類別之間的平均相似度是分屬于兩個(gè)類別的應(yīng)用程序相似度的平均值。圖2顯示了類別之間的一元詞頻的平均相似度的結(jié)果。

圖2 不同類別之間的一元詞頻相似度

圖2顯示，不同類別內(nèi)部的平均相似度也是不同的。其中，瀏覽器類的高頻詞條的相似度最高，達(dá)到了0.85。瀏覽器類的詞頻分布相對(duì)集中，需求比較明確，而辦公和游戲類用戶群體差異較大，需求比較分散，這也在一定程度上解釋了瀏覽器內(nèi)部的平均相似度最高，而辦公和游戲類相似度較低的結(jié)果。另外，我們還發(fā)現(xiàn)，不同類別之間的相似度也是不同的，聊天程序和瀏覽器的相似度達(dá)到了0.5左右，而和辦公編輯類的只有0.1。這表明了聊天類和瀏覽器類之間有著一定的相似度。為了進(jìn)一步的對(duì)進(jìn)行類別之間的比較，我們也按照類似的方法對(duì)二元詞頻相似度進(jìn)行了統(tǒng)計(jì)，統(tǒng)計(jì)結(jié)果見圖3。

圖3 不同類別之間的二元詞頻相似度

將二元詞頻的相似度和一元詞頻相似度進(jìn)行對(duì)比，各類程序之間的相似度趨勢(shì)幾乎沒有發(fā)生變化。瀏覽器類內(nèi)部的相似度依然最高，而辦公類和游戲類之間的平均相似度幾乎為0，即辦公類的高頻詞和游戲類的高頻詞幾乎沒有重合，這與辦公類和游戲類用戶需求相差較大的原因有一定的關(guān)系。通過上述的一元詞頻和二元詞頻相似度的分析，我們可以假設(shè)，如果對(duì)現(xiàn)有輸入法詞庫(kù)和排序策略按照應(yīng)用程序的類別屬性進(jìn)行更新和改進(jìn)，應(yīng)該可以在一定程度上提高用戶的滿意度。

4.3 各個(gè)主要應(yīng)用程序之間的KL距離分析

上一節(jié)中，我們從高頻詞頻的相似度對(duì)不同應(yīng)用程序類別的用戶行為習(xí)慣進(jìn)行了分析，下面我們將選定相對(duì)熵和用戶半徑這兩個(gè)指標(biāo)作為另一種衡量應(yīng)用程序之間的差異的特征[7]。首先，相對(duì)熵的定義如下：

其中p(w)代表某個(gè)詞w的概率分布，Entropy代表的是整個(gè)應(yīng)用程序的相對(duì)熵。如果某個(gè)應(yīng)用程序的相對(duì)熵很小，表示其對(duì)應(yīng)的用戶行為相對(duì)較為集中。

用戶半徑衡量的是應(yīng)用程序中的每個(gè)用戶到該應(yīng)用程序總體詞頻分布的中心點(diǎn)的距離，每個(gè)單獨(dú)的用戶半徑作為一個(gè)獨(dú)立的點(diǎn)，沒有統(tǒng)計(jì)意義，因而我們將應(yīng)用程序的用戶半徑定義為此應(yīng)用程序中所有用戶半徑的平均值，其是衡量用戶行為另一個(gè)重要的指標(biāo)。用戶半徑越小，代表此應(yīng)用程序的用戶群的行為特征有著較高的相似性。應(yīng)用程序?qū)?yīng)的用戶半徑定義如下：

表4 主要應(yīng)用程序的熵值與半徑

4.4 其他用戶行為分析

首詞條命中率，即排在第一位的候選詞條被命中的比例，翻頁(yè)率則是用戶在輸入法提供的候選結(jié)果中進(jìn)行翻頁(yè)的比例。首詞條命中率和翻頁(yè)率一直被認(rèn)為是衡量輸入法效率很主要的兩個(gè)指標(biāo)，因此，我們將對(duì)各個(gè)類別對(duì)應(yīng)的首詞條命中類別和翻頁(yè)率進(jìn)行了統(tǒng)計(jì)，統(tǒng)計(jì)結(jié)果如圖4。

圖4 各種應(yīng)用程序的首詞條命中率和翻頁(yè)率對(duì)比

上述的圖表顯示，即時(shí)通信類兩者的質(zhì)量評(píng)估總體是最好的，而游戲類的則相對(duì)較差。同時(shí)，首條命中率和翻頁(yè)率隨不同的應(yīng)用程序類別也是不同的。究其原因，可能是因?yàn)椴煌钠匆舸诓煌膽?yīng)用程序類別中，用戶所需要的中文候選詞條互不相同。這樣可能導(dǎo)致在一些類別的應(yīng)用程序中首次命中率下降，翻頁(yè)率上升，從而導(dǎo)致用戶體驗(yàn)度下降。

5 結(jié)果與討論

衡量中文輸入法產(chǎn)品的優(yōu)劣有很多指標(biāo)，其中包含首條詞條命中率、翻頁(yè)次數(shù)、內(nèi)存占用量、簡(jiǎn)拼詞使用率等，這些都直接影響著用戶的滿意度。本文主要從兩個(gè)方面對(duì)輸入法日志進(jìn)行了分析：首先，就一元、二元詞頻相似度分析而言，我們發(fā)現(xiàn)有著相似用戶需求的應(yīng)用程序(同一類別)之間的詞頻相似度要明顯高于不屬于同一類別的相似度；不同類別內(nèi)部的平均相似度也是不相同的。其中，瀏覽器類別內(nèi)部的相似度最高(達(dá)到0.85)，表明瀏覽器類的詞條需求較為集中。其次，我們對(duì)應(yīng)用程序的熵值與用戶半徑進(jìn)行了定義，并用其對(duì)各大主要應(yīng)用程序進(jìn)行分析。分析發(fā)現(xiàn)，用戶需求相似的應(yīng)用程序在熵值和用戶半徑有著相似的屬性。其中游戲軟件類和即時(shí)通信類的熵值和用戶半徑比較小，表明這兩類所對(duì)應(yīng)的用戶群相對(duì)較為集中。同時(shí)，我們發(fā)現(xiàn)，當(dāng)前的首詞條命中率和翻頁(yè)率也是隨著應(yīng)用程序類別發(fā)生變化的。即時(shí)通信類別的效果最好，而游戲類別相對(duì)較差。

詞庫(kù)和排序策略是整個(gè)輸入法的核心。目前輸入法對(duì)所有應(yīng)用程序均采用了同樣的詞庫(kù)和排序算法，然而很多情況下能夠達(dá)到全局最優(yōu)的條件未必會(huì)是局部最優(yōu)。目前即時(shí)通信類用戶占了整個(gè)輸入法用戶的50%左右，于是當(dāng)前的詞條排序大都是基于即時(shí)通信類用戶最優(yōu)的，而其他類用戶和即時(shí)通信類用戶需求之間有一定的差異，從而導(dǎo)致了當(dāng)前的詞條排序不能很好的滿足其他類用戶的輸入需求。通過我們的分析發(fā)現(xiàn)，如果我們可以對(duì)于不同用戶需求的應(yīng)用程序，選用不同的詞庫(kù)和排序算法，

則會(huì)使得不同應(yīng)用需求的用戶的滿意度都得到一定的提升。

用戶需求是輸入法最切實(shí)的質(zhì)量評(píng)估，然而也是最抽象的，有時(shí)可能一個(gè)應(yīng)用程序會(huì)對(duì)應(yīng)著不同的用戶需求，所以為應(yīng)用程序定位其對(duì)應(yīng)的用戶需求，從而進(jìn)行針對(duì)性改進(jìn)，是我們下一步研究的方向。

[1] 中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心(CNNIC)，第25次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告[EB/OL]，2010年1月,http://www.cnnic.net.cn/uploadfiles/pdf/2010/1/18/141029.pdf.

[2] Z. Chen and K. Lee. A new statistical approach to Chinese pinyin input[C]//The 38thAnnual Meeting of the Association for Computational Linguistics, 241-247, Hong Kong, 2000.

[3] CD Manning, H Schutze. Foundations of Statistical Natural Language Processing[M]. The MIT Press, Cambridge, Massachusetts, 1999.

[4] D Downey, et al. Understanding the relationship between searchers’ queries and information goals[C]//CIKM’08, 449-458, California, 2008.

[5] 張瑋,孫樂，馮元勇，等.一種結(jié)合分類模型的中文輸入法[C]//中國(guó)中文信息學(xué)會(huì)二十五周年學(xué)術(shù)會(huì)議，2006：586-593.

[6] R Cen, et al. Study Language Models with Specific User Goals[C]//The 19thinternational conference on World Wide Web, 1073-1074, USA, 2010.

[7] J Lin. Divergence measures based on the Shannon entropy[J]. IEEE Transactions on Information Theory, 1991， 37:145-151.