基于海量數(shù)據(jù)的用戶點(diǎn)擊模式識(shí)別

林湘粵　北京郵電大學(xué)信息與通信工程學(xué)院碩士研究生張昕宇　北京郵電大學(xué)信息與通信工程學(xué)院碩士研究生

?

基于海量數(shù)據(jù)的用戶點(diǎn)擊模式識(shí)別

林湘粵北京郵電大學(xué)信息與通信工程學(xué)院碩士研究生
張昕宇北京郵電大學(xué)信息與通信工程學(xué)院碩士研究生

移動(dòng)互聯(lián)網(wǎng)的高速發(fā)展，產(chǎn)生了大量的話單數(shù)據(jù)，其中蘊(yùn)含的用戶行為模式為移動(dòng)運(yùn)營(yíng)商和人類信息社會(huì)的發(fā)展帶來了機(jī)遇和挑戰(zhàn)。本文介紹了基于云計(jì)算的海量數(shù)據(jù)挖掘技術(shù)下用戶點(diǎn)擊模式挖掘的過程，并分析了點(diǎn)擊模式挖掘的結(jié)果及其帶來的價(jià)值。

移動(dòng)互聯(lián)網(wǎng)；用戶行為模式；先驗(yàn)算法；云計(jì)算；模式挖掘

1　引言

移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展，帶領(lǐng)中國(guó)走向了信息化時(shí)代。用戶利用智能設(shè)備隨時(shí)隨地連接著移動(dòng)互聯(lián)網(wǎng)，并通過其產(chǎn)生了大量話單數(shù)據(jù)，大數(shù)據(jù)時(shí)代已經(jīng)到來。移動(dòng)互聯(lián)網(wǎng)中的海量數(shù)據(jù)，反映著人們?nèi)粘Ｐ袨榈姆椒矫婷?，在大?guī)模的用戶通過智能手機(jī)產(chǎn)生的上億規(guī)模流量的話單數(shù)據(jù)當(dāng)中，如何從中挖掘出用戶的行為特點(diǎn)，將用戶的行為總結(jié)成行為模式用以描述用戶的特征，是當(dāng)前大數(shù)據(jù)應(yīng)用的一個(gè)熱點(diǎn)。

移動(dòng)互聯(lián)網(wǎng)用戶的點(diǎn)擊行為模式挖掘是將用戶主動(dòng)點(diǎn)擊的網(wǎng)址鏈接總結(jié)成點(diǎn)擊模式的過程。這些總結(jié)的點(diǎn)擊模式能夠反映用戶真實(shí)的上網(wǎng)意圖，反映用戶真實(shí)的上網(wǎng)點(diǎn)擊行為。用戶點(diǎn)擊模式的挖掘能夠有助于理解用戶真實(shí)的網(wǎng)站訪問偏好，可以有助于商家對(duì)用戶的有效推送，同時(shí)也能夠利用識(shí)別的結(jié)果進(jìn)行網(wǎng)頁質(zhì)量的分析。將移動(dòng)互聯(lián)網(wǎng)的點(diǎn)擊信息采用處理、清洗和挖掘的方式，可以發(fā)現(xiàn)點(diǎn)擊者的點(diǎn)擊模式，提取出點(diǎn)擊使用者的個(gè)人特點(diǎn)和喜好，為不同喜好類別的用戶設(shè)計(jì)不同的網(wǎng)頁頁面，在恰當(dāng)?shù)木W(wǎng)頁頁面為用戶提供用戶自己所喜歡的特定廣告，并為用戶推送和用戶特點(diǎn)相匹配的商業(yè)資訊和新聞，從而增強(qiáng)商家的競(jìng)爭(zhēng)力。用戶點(diǎn)擊模式挖掘具有極其高的商業(yè)價(jià)值和現(xiàn)實(shí)意義。

2　點(diǎn)擊模式挖掘

隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)的發(fā)展和智能終端在市場(chǎng)上的擴(kuò)張，越來越多的人們通過智能終端連接到移動(dòng)互聯(lián)網(wǎng)，人們?cè)L問移動(dòng)互聯(lián)網(wǎng)的相關(guān)信息蘊(yùn)含著用戶的相關(guān)喜好、用戶的行為等，同時(shí)也蘊(yùn)含著移動(dòng)互聯(lián)網(wǎng)本身的一些特征。所以越來越多的研究者采用原始的數(shù)據(jù)挖掘技術(shù)去挖掘移動(dòng)互聯(lián)網(wǎng)背后的潛在信息。然而大多數(shù)移動(dòng)互聯(lián)網(wǎng)數(shù)據(jù)挖掘的技術(shù)都是基于網(wǎng)頁本身，只關(guān)注一些特殊文本和網(wǎng)頁關(guān)鍵字，基于用戶訪問的URL本身的研究和挖掘很少。

首先，基于點(diǎn)擊識(shí)別的算法，從大量的流記錄話單中識(shí)別出了點(diǎn)擊URL。為了進(jìn)一步對(duì)URL的內(nèi)部規(guī)律進(jìn)行挖掘和研究，將點(diǎn)擊URL的規(guī)則進(jìn)行提取，用這些提取出來的點(diǎn)擊URL規(guī)則代替點(diǎn)擊URL，從而極大地縮小點(diǎn)擊URL數(shù)據(jù)表的數(shù)量，節(jié)省存儲(chǔ)空間，同時(shí)發(fā)現(xiàn)點(diǎn)擊URL規(guī)則的內(nèi)部規(guī)律。

2.1點(diǎn)擊模式挖掘創(chuàng)新點(diǎn)

本文基于Apriori算法，并對(duì)其進(jìn)行了改進(jìn)，以適應(yīng)點(diǎn)擊模式挖掘算法。傳統(tǒng)的利用Apriori算法的挖掘當(dāng)中，最終展現(xiàn)序列的形式包含有序性、可重復(fù)性。在此方法中，為適應(yīng)URL有序的且具有層級(jí)關(guān)系的數(shù)據(jù)結(jié)構(gòu)，最終展示的序列還具有固定位置特性。即 與不是同一個(gè)序列，*在算法中扮演著重要角色，它并不是一個(gè)元素（不是一個(gè)項(xiàng)），不占長(zhǎng)度，但是占一個(gè)層級(jí)，并且在候選項(xiàng)產(chǎn)生的時(shí)候可以被其它項(xiàng)代替。此外，最終模式的內(nèi)容只取極大頻繁項(xiàng)，極大頻繁項(xiàng)的子集將不在最終模式發(fā)現(xiàn)結(jié)果當(dāng)中。

原始Apriori算法包括兩個(gè)部分：頻繁項(xiàng)的產(chǎn)生和規(guī)則的發(fā)現(xiàn)。用戶點(diǎn)擊模式挖掘算法，只要產(chǎn)生了頻繁序列項(xiàng)即是產(chǎn)生了規(guī)則，沒有單獨(dú)的規(guī)則發(fā)現(xiàn)階段。

另外，對(duì)于候選項(xiàng)的產(chǎn)生方法中，和原始算法也有所不同。候選項(xiàng)的產(chǎn)生原則應(yīng)當(dāng)避免產(chǎn)生太多不必要的候選，同時(shí)必須確保候選項(xiàng)集的集合是完備的，此外還不應(yīng)該產(chǎn)生太多重復(fù)候選項(xiàng)集。

在原始算法候選項(xiàng)的產(chǎn)生方法中，F(xiàn)k-1*Fk-1方法：與合并產(chǎn)生。在點(diǎn)擊URL識(shí)別算法中，由于序列中的每一個(gè)元素是具有固定位置的，所以在模式當(dāng)中與合并產(chǎn)生顯然是不正確的，所以采用Fk-1*F2的方法產(chǎn)生Fk，為了避免重復(fù)產(chǎn)生候選項(xiàng)，在Fk-1*F2產(chǎn)生Fk當(dāng)中，要求保證F2的層級(jí)大于Fk-1的層級(jí)。

在每?jī)蓚€(gè)頻繁項(xiàng)合并產(chǎn)生新的候選項(xiàng)的時(shí)候，對(duì)產(chǎn)生的候選項(xiàng)直接篩選，原始算法只根據(jù)支持度計(jì)數(shù)方法過濾，點(diǎn)擊URL識(shí)別算法不僅根據(jù)支持度計(jì)數(shù)方法過濾，還根據(jù)置信度進(jìn)行過濾，而且根據(jù)兩方面的置信度進(jìn)行過濾。

2.2點(diǎn)擊模式挖掘相關(guān)定義

點(diǎn)擊URL規(guī)則的提取，采用數(shù)據(jù)挖掘理論當(dāng)中關(guān)聯(lián)分析和頻繁項(xiàng)集產(chǎn)生的方法進(jìn)行提取和逐層發(fā)現(xiàn)。并沒有完全照搬關(guān)聯(lián)分析和頻繁項(xiàng)集產(chǎn)生的Apriori算法，而是將算法進(jìn)行了改進(jìn)，研究出有層級(jí)順序的規(guī)則提取算法，以適應(yīng)URL當(dāng)中每一項(xiàng)之間有特定順序這一主要特點(diǎn)。同時(shí)，最終采取的URL規(guī)則是極大頻繁項(xiàng)集。

首先，定義序列這個(gè)概念，它具有如下4個(gè)性質(zhì)：

性質(zhì)一：序列中的元素是有層級(jí)的。一個(gè)序列中的元素從前到后依次是第0，1，2，3……層級(jí)，一個(gè)元素在不同層級(jí)上代表著不同的序列，如和是不同的序列。

性質(zhì)二：序列中的某一個(gè)層級(jí)的元素允許為空。如果某一個(gè)層級(jí)的元素為空，則用*代替。

性質(zhì)三：序列中的元素是有序的，調(diào)換順序，即產(chǎn)生新的一個(gè)序列，如和是不同的序列。

性質(zhì)四：序列中的元素允許相同，如也是一個(gè)序列。為將問題闡述清楚，還有如下幾個(gè)定義需要說明：

（1）項(xiàng)（i）：將URL以“/”分割，一個(gè)URL分割后的每一個(gè)元素，都是一個(gè)項(xiàng)。

（2）項(xiàng)集（iSets）：由若干個(gè)項(xiàng)組成集合為一個(gè)項(xiàng)集。

（3）事務(wù)（t）：每一個(gè)URL為一個(gè)事務(wù)。

（4）事務(wù)集（tSets）：具有0個(gè)或多個(gè)事務(wù)的集合為一個(gè)事務(wù)集。

（5）層級(jí)（level）：將URL以“/”分割，一個(gè)URL分割后的第i個(gè)元素，即是第i層級(jí)。層級(jí)針對(duì)一個(gè)項(xiàng)而言。

（6）長(zhǎng)度（length）：一個(gè)URL規(guī)則當(dāng)中含有非空項(xiàng)的個(gè)數(shù)，即是該URL規(guī)則的長(zhǎng)度。長(zhǎng)度針對(duì)一個(gè)URL規(guī)則而言。

（7）支持度計(jì)數(shù)（σ）：規(guī)則在事務(wù)集當(dāng)中的出現(xiàn)次數(shù)。

（8）支持度。

（9）置信度（Confidence）：確定新規(guī)則在包含原規(guī)則的事務(wù)集當(dāng)中出現(xiàn)的頻繁程度。

基于以上定義，序列中的每個(gè)元素就是項(xiàng)，每個(gè)URL抽象成的序列就是事務(wù)，項(xiàng)的位置序號(hào)代表著這個(gè)項(xiàng)的層級(jí)，一個(gè)序列中非空元素的個(gè)數(shù)是一個(gè)序列的長(zhǎng)度，k-序列是長(zhǎng)度為k的序列。序列中的元素的個(gè)數(shù)和序列的長(zhǎng)度可以是不同的，如中元素的個(gè)數(shù)是4，但是序列的長(zhǎng)度是2。

2.3點(diǎn)擊模式挖掘方法

首先，頻繁項(xiàng)集的產(chǎn)生主要依靠支持度計(jì)數(shù)原則。在此頻繁項(xiàng)集產(chǎn)生階段，只產(chǎn)生長(zhǎng)度為2的序列，并且此序列的第0個(gè)元素一定不為空。初始規(guī)則的產(chǎn)生分兩個(gè)步驟：

（1）初始候選項(xiàng)的產(chǎn)生：產(chǎn)生每一個(gè)長(zhǎng)度為2的子序列。

（2）初始候選項(xiàng)的篩選：設(shè)子序列的支持度為δ，該規(guī)則為頻繁項(xiàng)的判斷原則為：δ>δs。

然后，對(duì)點(diǎn)擊模式進(jìn)行擴(kuò)展。長(zhǎng)度為j+1的序列由長(zhǎng)度為j的序列和長(zhǎng)度為2的序列構(gòu)成，一旦產(chǎn)生新的序列，產(chǎn)生它的兩個(gè)父序列就可以由新的序列替代，即最后取得是極大頻繁項(xiàng)。URL規(guī)則的擴(kuò)展過程，采用邊產(chǎn)生新規(guī)則邊篩選的方法。假設(shè)規(guī)則G1層級(jí)為L(zhǎng)evel1，長(zhǎng)度為L(zhǎng)ength1（Length1=j）；規(guī)則G2層級(jí)為L(zhǎng)evel2，長(zhǎng)度為L(zhǎng)ength2（Length2=2）。規(guī)則的擴(kuò)展包括兩個(gè)步驟：

（1）候選項(xiàng)的產(chǎn)生：G1與G2兩個(gè)規(guī)則合并產(chǎn)生候選G3，且有如下原則：Level2>Level1。

（2）候選項(xiàng)的篩選：G3是新產(chǎn)生的規(guī)則，它被判別為頻繁項(xiàng)的原則：（a）δG3>δs；（b）δG3/δG1>δc；（c）δG3/δG2>δc。

由之前的算法步驟產(chǎn)生了不同長(zhǎng)度的序列，即不同長(zhǎng)度的規(guī)則，由于一旦產(chǎn)生新的序列，產(chǎn)生它的兩個(gè)父序列就可以由新的序列替代，即最后取得是極大頻繁項(xiàng)，所以要對(duì)最后的所有規(guī)則進(jìn)行篩選，篩選出極大頻繁項(xiàng)，即極大長(zhǎng)度的規(guī)則。

至此，點(diǎn)擊url模式挖掘算法得以實(shí)現(xiàn)。

3　點(diǎn)擊模式挖掘結(jié)果

3.1數(shù)據(jù)說明

所采集到的流量數(shù)據(jù)來自運(yùn)營(yíng)商，數(shù)據(jù)的采集地理位置在中國(guó)一個(gè)大型城市。該城市的人口數(shù)量有400萬人左右，一天的數(shù)據(jù)量在1T左右。數(shù)據(jù)所采集的移動(dòng)互聯(lián)網(wǎng)骨干網(wǎng)的網(wǎng)絡(luò)結(jié)構(gòu)圖如圖1所示。在移動(dòng)互聯(lián)網(wǎng)當(dāng)中，有3個(gè)主要的組成部分，即移動(dòng)設(shè)備、接入網(wǎng)絡(luò)、骨干網(wǎng)絡(luò)。

研究所使用的數(shù)據(jù)集通過流量監(jiān)控系統(tǒng)TMS設(shè)備進(jìn)行采集，TMS設(shè)備連接著圖中所示的Gn接口。將報(bào)文按照五元組｛源IP，目的IP，源端口號(hào)，目的端口號(hào)，傳輸協(xié)議｝的規(guī)則進(jìn)行解析，流是一段時(shí)間內(nèi)具有相同五元組的一系列報(bào)文的集合。由于數(shù)據(jù)量的巨大，解析好的流記錄，會(huì)上傳到Hadoop集群的分布式存儲(chǔ)文件系統(tǒng)HDFS當(dāng)中。

3.2點(diǎn)擊模式挖掘結(jié)果評(píng)價(jià)

基于點(diǎn)擊URL的識(shí)別結(jié)果，進(jìn)行點(diǎn)擊模式的挖掘。在支持度和置信度的選擇上，選擇在模式挖掘結(jié)果的F1值最大的時(shí)候所對(duì)應(yīng)的支持度和置信度。所以，在本文中，點(diǎn)擊URL的模式挖掘的支持度為0.1，置信度為0.5。在這個(gè)閾值設(shè)定下，點(diǎn)擊的模式挖掘結(jié)果如表1～6所示。

表1　社交網(wǎng)站A點(diǎn)擊模式識(shí)別結(jié)果

表2　某社區(qū)網(wǎng)站點(diǎn)擊模式識(shí)別結(jié)果

表3　社交網(wǎng)站B點(diǎn)擊模式識(shí)別結(jié)果

表4　新聞網(wǎng)站C點(diǎn)擊模式識(shí)別結(jié)果

圖1　2G和3G網(wǎng)絡(luò)數(shù)據(jù)采集網(wǎng)絡(luò)結(jié)構(gòu)圖

表5　新聞網(wǎng)站D點(diǎn)擊模式識(shí)別結(jié)果

表6　新聞網(wǎng)站E點(diǎn)擊模式識(shí)別結(jié)果

從試驗(yàn)結(jié)果可以看出某社交網(wǎng)站A的F1值平均為0.8451，某社交網(wǎng)站B的F1值平均為0.8500，某社區(qū)網(wǎng)站的F1值平均為0.8424，新聞網(wǎng)站C的F1值平均為0.8549，新聞網(wǎng)站D的F1值平均為0.8588，新聞網(wǎng)站E 的F1值平均為0.8945?？梢钥闯觯蠬ost對(duì)應(yīng)的F1值的平均值均在0.85左右，識(shí)別的結(jié)果較好。

4　結(jié)束語

隨著移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展和互聯(lián)網(wǎng)上信息的爆炸式增長(zhǎng)，網(wǎng)站和網(wǎng)頁越來越成為人們?cè)谌粘Ｉ钪蟹窒硇畔?，交流想法，休閑娛樂的重要平臺(tái)。通過用戶的行為規(guī)律為用戶構(gòu)建用戶畫像，發(fā)現(xiàn)他獨(dú)特的喜好，改善商家所給出的業(yè)務(wù)和應(yīng)用，具有極高的商業(yè)價(jià)值和現(xiàn)實(shí)意義。而用戶上網(wǎng)的點(diǎn)擊行為是移動(dòng)互聯(lián)網(wǎng)用戶行為模式挖掘中相當(dāng)重要的部分。

本文提供的點(diǎn)擊URL模式挖掘方法改進(jìn)了原有的Apriori算法，使新的方法能夠適應(yīng)URL的有序的同時(shí)是帶有層級(jí)關(guān)系的數(shù)據(jù)結(jié)構(gòu)。利用挖掘的點(diǎn)擊模式，可以發(fā)現(xiàn)用戶點(diǎn)擊網(wǎng)頁的真實(shí)意圖，為移動(dòng)運(yùn)營(yíng)商提供隱形的有意義的用戶上網(wǎng)點(diǎn)擊行為的信息和用戶點(diǎn)擊網(wǎng)頁的興趣點(diǎn)，對(duì)提升網(wǎng)頁的質(zhì)量有著至關(guān)重要的作用。

User click pattern recognition for massive data

LIN Xiangyue，ZHAN GXinyu

With the rapid development of the Mobile Internet，massive user data has been produced，in which the user behavior model has brought both challenges and opportunities.This paper details the process of user click pattern mining based on cloud computing.By the way，the result and the commercial valueit would brought have been given as well.

mobile internet；user behavior model；apriori algorithm；cloud computing；pattern mining

2016-04-10）