蔣 麗，薛善良

(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211106)

0 引 言

互聯(lián)網(wǎng)的快速發(fā)展帶動(dòng)著電子商務(wù)的發(fā)展，電子商務(wù)會(huì)產(chǎn)生大量的數(shù)據(jù)，合理分析這些數(shù)據(jù)，從中挖掘出客戶感興趣的信息，將會(huì)給企業(yè)帶來(lái)巨大的利潤(rùn)。在電子商務(wù)平臺(tái)上進(jìn)行數(shù)據(jù)挖掘已經(jīng)成為研究的熱點(diǎn)問(wèn)題，而電子商務(wù)網(wǎng)站中存儲(chǔ)的大多是非結(jié)構(gòu)化數(shù)據(jù)，比如文本[1]，因此，文本挖掘是面向電子商務(wù)進(jìn)行數(shù)據(jù)挖掘重要的研究角度之一。

首先，與傳統(tǒng)的數(shù)據(jù)挖掘相比，文本挖掘最大的特點(diǎn)是文本是非結(jié)構(gòu)化的數(shù)據(jù)，為了把數(shù)據(jù)挖掘的算法應(yīng)用在文本對(duì)象上，必須對(duì)文本進(jìn)行處理，使文本最終表示為一種結(jié)構(gòu)化形式[2]。傳統(tǒng)的文本表示模型是以統(tǒng)計(jì)詞頻得出特征的權(quán)重形成向量，但這種方法忽略了詞和詞之間的語(yǔ)義性從而降低了聚類精度。其次，原始k-means算法在簇密集且簇與簇之間區(qū)別明顯的數(shù)據(jù)中聚類效果較好，對(duì)文本聚類具有一定的局限性[3]。

1 k-means算法及Word2vec

1.1 k-means算法思想

1967年，MacQueen提出了k-means算法，它是一種基于劃分的經(jīng)典聚類算法[4]。該算法隨機(jī)選擇k個(gè)數(shù)據(jù)樣本作為初始聚類中心，在每次迭代過(guò)程中，根據(jù)計(jì)算相似度將每個(gè)數(shù)據(jù)樣本分配到最近的簇中，然后，重新計(jì)算簇的中心，也就是每個(gè)簇中所有數(shù)據(jù)的平均值。該算法結(jié)束的條件為聚類準(zhǔn)則函數(shù)達(dá)到最優(yōu)即收斂，從而使生成的每個(gè)聚類內(nèi)緊湊，類間獨(dú)立[5]。

1.2 k-means聚類算法步驟

Input：包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集合D以及聚類數(shù)k。

Output：滿足聚類準(zhǔn)則函數(shù)收斂的k個(gè)聚類簇。

Step1從數(shù)據(jù)集合D中隨機(jī)選擇k個(gè)數(shù)據(jù)對(duì)象作為初始聚類中心cj,j=1,2,…,k。

Step2求出每個(gè)數(shù)據(jù)對(duì)象與聚類中心的距離d(xi,cj),i=1,2,…,n;j=1,2,…,k。

Step3根據(jù)求出的距離，將每個(gè)數(shù)據(jù)對(duì)象劃分到最相似的簇中，即若滿足d(xi,cj)=min{d(xi,cj′),j′=1,2,…,k}，則xi∈Yj,Yj表示聚類中心為cj的簇。

1.3 Word2vec分析

傳統(tǒng)的具有代表性的文本表示方法有向量空間模型(Vector Space Model, VSM)[6]、布爾模型(Boolean Model, BM)[7]以及概率模型(Probabilistic Model, PM)[8]等。這些模型從不同的角度出發(fā)，使用不同的方法處理特征加權(quán)、類別學(xué)習(xí)和相似計(jì)算等問(wèn)題。但是，它們各具缺點(diǎn)，比如基于VSM的聚類方法是按詞頻統(tǒng)計(jì)信息，得出特征的權(quán)重形成向量，而忽略了詞和詞之間，以及文檔和文檔之間的語(yǔ)義相關(guān)性，從而導(dǎo)致聚類的質(zhì)量不高?；诖?，本文采用Word2vec[9],Word2vec是Google在2013年開(kāi)源的一款將詞表征為詞向量[10]的高效工具[11]，Word2vec可以考慮上下文的語(yǔ)義，能在一定程度上提高聚類的準(zhǔn)確性。

當(dāng)人們?cè)谡f(shuō)Word2vec算法或模型的時(shí)候，其實(shí)指的是其背后用于計(jì)算的2種語(yǔ)言模型，分別為CBOW和Skip-gram模型(如圖1所示)。從圖1可以看出，2個(gè)模型都包含輸入層、投影層以及輸出層。CBOW模型是在已知當(dāng)前詞wt的上下文wt-2,wt-1,wt+1,wt+2的前提下預(yù)測(cè)當(dāng)前詞wt；而Skip-gram模型是在已知當(dāng)前詞wt的前提下，預(yù)測(cè)其上下文wt-2,wt-1,wt+1,wt+2[12]。

(a) CBOW模型

(b) Skip-gram模型

對(duì)于CBOW和Skip-gram模型，Word2vec給出了2套框架，它們分別基于Hierarchical Softmax和Negative Sampling來(lái)進(jìn)行設(shè)計(jì)(如表1所示)[13]。

表1 Word2vec詞向量訓(xùn)練框架

框架模型CBOWSkip-gramHierarchicalSoftmaxCBOW+HSSkip-gram+HSNegativeSamplingCBOW+NSSkip-gram+NS

1.4 Word2vec訓(xùn)練詞向量的原理(CBOW+HS)

在模型的訓(xùn)練過(guò)程中，梯度是訓(xùn)練參數(shù)更新的依據(jù)[12]。為了獲得梯度公式，需要構(gòu)造訓(xùn)練模型的目標(biāo)函數(shù)，該訓(xùn)練框架優(yōu)化的目標(biāo)函數(shù)通常取為如下對(duì)數(shù)似然函數(shù)：

(1)

其中，C表示語(yǔ)料，Context(w)表示詞w的上下文，即w周邊的詞的集合。條件概率P(w|Context(w))的公式可寫為：

(2)

其中：

(3)

將式(2)代入式(1)中得到CBOW模型的目標(biāo)函數(shù)即：

(4)

(5)

最后將求出的詞向量用于聚類算法中。

Word2vec訓(xùn)練出來(lái)的詞向量形式如圖2所示。

圖2 Word2vec訓(xùn)練出來(lái)的詞向量形式

詞向量的維度常常介于50～200維，維度越高詞的特征表現(xiàn)越豐富，但訓(xùn)練時(shí)間和使用時(shí)的計(jì)算時(shí)間也會(huì)相應(yīng)增加，本文使用較為常用的100維來(lái)進(jìn)行Word2vec的訓(xùn)練。

2 改進(jìn)后的k-means算法思想

原始的k-means算法對(duì)聚類數(shù)k的選取十分敏感，不同的初始值可能會(huì)導(dǎo)致不同的聚類結(jié)果。聚類的結(jié)果對(duì)聚類數(shù)k的依賴性導(dǎo)致聚類結(jié)果不穩(wěn)定，且原始的k-means算法適用于簇密集但簇與簇之間區(qū)別較明顯的數(shù)據(jù)，但在文本聚類上具有一定的局限性。文本之間的區(qū)別沒(méi)有數(shù)據(jù)之間那么明顯，文本之間存在很多近似詞。原始的k-means算法隨機(jī)輸入聚類數(shù)k，如果文本的類別不符合聚類數(shù)k的值，不同類別的文本將被強(qiáng)行聚類到同一個(gè)類簇中。假設(shè)文本有7個(gè)類別，原始k-means算法將k設(shè)置為4，那么有3類將被強(qiáng)行劃分到這4個(gè)類別中。這樣的聚類結(jié)果是不太合理的?；诖耍疚奶岢鲆环N改進(jìn)的k-means算法，該算法首先根據(jù)相似性將數(shù)據(jù)劃分為k+x個(gè)簇，其中x為未知數(shù)，對(duì)于某個(gè)未知新樣本，如果與現(xiàn)有的k(假設(shè)k=4)個(gè)初始聚類中心足夠相似，那么就放入k個(gè)聚類中心中的某一個(gè)類中，否則就新增加一類(這時(shí)k+1=5)。將所有數(shù)據(jù)劃分為k+x類后再根據(jù)類與用戶的相似性使用k-means算法，改進(jìn)后的k-means算法減少了結(jié)果對(duì)參數(shù)的依賴且聚類結(jié)果更準(zhǔn)確。

2.1 基于共現(xiàn)詞的相似度

從直觀上來(lái)說(shuō)，2個(gè)句子出現(xiàn)的共同詞匯越多說(shuō)明其相似度越大[16]。相似度不僅受到共同詞匯的影響，同時(shí)還要結(jié)合句子的總數(shù)來(lái)進(jìn)行度量，可以用如下公式直觀地表達(dá)該思想：

(6)

其中，cos (A,B)>0.03表示輸入句子A和B之間共現(xiàn)的詞匯數(shù)目，考慮到詞匯“連衣裙”和“裙子”雖不是共現(xiàn)詞，但它們屬于相似物品，故采用該公式。A和B代表搜索記錄，利用第1章中訓(xùn)練出來(lái)的詞向量直接進(jìn)行計(jì)算。

(7)

2.2 改進(jìn)后的k-means算法步驟

Input：包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集合D，k個(gè)初始聚類中心。

Output：滿足聚類準(zhǔn)則函數(shù)收斂的k+x個(gè)聚類簇。

Step1取一部分?jǐn)?shù)據(jù)，讓它們互相作相似性比較，得出相似度的閾值判定。

Step2從數(shù)據(jù)集合D中隨機(jī)選擇k個(gè)數(shù)據(jù)對(duì)象作為初始聚類中心并保證k個(gè)數(shù)據(jù)對(duì)象不重復(fù)(通過(guò)比較它們之間相似性，如果高于相似閾值則重新選擇)。

Step3求出每個(gè)數(shù)據(jù)對(duì)象與聚類中心的相似度并將數(shù)據(jù)集合劃為k+x類(通過(guò)基于共現(xiàn)詞的相似度計(jì)算，2個(gè)記錄的相似度大于等于相似閾值，則認(rèn)為這2個(gè)記錄為一類，如果小于相似閾值，則新增一類，從而更新聚類中心)。計(jì)算出的用戶和類簇的相似度可以用矩陣來(lái)表示，矩陣的行代表類簇的個(gè)數(shù)，矩陣的列代表用戶的個(gè)數(shù)。

Step4重新計(jì)算簇的聚類中心，取k+x個(gè)簇中相似度的中心值。

Step5計(jì)算相似度矩陣中數(shù)據(jù)與聚類中心的距離，將每個(gè)數(shù)據(jù)聚類到離該點(diǎn)最近的聚類中。

Step6反復(fù)執(zhí)行Step4和Step5，直到聚類中心點(diǎn)不再發(fā)生變化。

2.3 改進(jìn)后的算法流程圖

改進(jìn)后的算法流程如圖3所示。

圖3 改進(jìn)后的k-means流程圖

3 仿真實(shí)驗(yàn)分析

為了檢驗(yàn)改進(jìn)算法的有效性，對(duì)原始算法和改進(jìn)算法進(jìn)行對(duì)比實(shí)驗(yàn)，用于實(shí)驗(yàn)的CPU是Intel(R) Core(TM) i5-3210M CPU@2.50 GHz，內(nèi)存為4 GB，實(shí)驗(yàn)軟件環(huán)境：操作系統(tǒng)為64位Win7，編程軟件用Eclipse。實(shí)驗(yàn)所采用的數(shù)據(jù)是從ofbiz網(wǎng)站上獲取的用戶的點(diǎn)擊記錄，該記錄是通過(guò)用戶在電商網(wǎng)站中點(diǎn)擊商品時(shí)，調(diào)用商品詳情接口里添加的存放用戶瀏覽記錄的代碼，將用戶的瀏覽記錄存入一個(gè)對(duì)應(yīng)的文本文檔中就得到了如圖4所示的部分用戶瀏覽記錄(因?yàn)闉g覽記錄過(guò)多，所以只截取了前面30位用戶的瀏覽記錄)。為了縮短用戶id的顯示，將用戶名改為用戶a1、用戶a2等(聚類結(jié)果的好壞以及正確與否都將有評(píng)判標(biāo)準(zhǔn)，在數(shù)據(jù)量少的情況下，聚類結(jié)果的正確以及好壞是可以通過(guò)觀察得知，如多次聚類效果理想，則可以用于多用戶的瀏覽記錄中)。采用“結(jié)巴”分詞工具對(duì)記錄進(jìn)行分詞，將分詞的結(jié)果用Word2vec訓(xùn)練出詞向量，再利用原始的k-means算法和改進(jìn)后的k-means算法分別做實(shí)驗(yàn)進(jìn)行對(duì)比觀察結(jié)果。實(shí)驗(yàn)的數(shù)據(jù)被分為7類，原始的k-means算法輸入聚類數(shù)k=4，很多數(shù)據(jù)被聚類到不正確的類簇中，但改進(jìn)后的k-means算法會(huì)根據(jù)相似度自動(dòng)將類簇劃分為k+x個(gè)簇(k=4，x=3)，減少了聚類數(shù)k的誤差。

圖4 部分用戶瀏覽數(shù)據(jù)

原始k-means算法聚類結(jié)果如圖5所示，改進(jìn)后的k-mean算法聚類結(jié)果如圖6所示。

圖5 原始k-means算法聚類結(jié)果

圖6 改進(jìn)后的k-means算法聚類結(jié)果

數(shù)據(jù)集相同的情況下，原始k-means聚類算法針對(duì)文本聚類準(zhǔn)確率只有70%，聚類質(zhì)量不優(yōu)，聚類結(jié)果沒(méi)有多大的參考意義，改進(jìn)后的k-means聚類算法準(zhǔn)確率達(dá)到97%，聚類結(jié)果更具有參考價(jià)值。如表2所示。

表2 原始k-means與改進(jìn)的k-means聚類算法的準(zhǔn)確率對(duì)比/%

原始k-means算法改進(jìn)的k-means算法7097

4 結(jié)束語(yǔ)

k-means聚類算法是一種被廣泛應(yīng)用的算法，但k-means聚類算法對(duì)有些特殊的數(shù)據(jù)無(wú)法進(jìn)行較精確的聚類。因此，需要根據(jù)特定的情況改進(jìn)k-means算法中的某些地方。實(shí)驗(yàn)結(jié)果顯示，本文提出的算法確實(shí)是有效的，當(dāng)然在實(shí)驗(yàn)過(guò)程中也發(fā)現(xiàn)存在的一些不足，比如實(shí)驗(yàn)所需的時(shí)間復(fù)雜度比較高。下一步將考慮如何降低改進(jìn)k-means算法的時(shí)間復(fù)雜度。

參考文獻(xiàn)：

[1] 張宏兵. Web文本挖掘技術(shù)在網(wǎng)頁(yè)推薦中的應(yīng)用研究[D]. 南京:南京理工大學(xué), 2013.

[2] 于寬. 改進(jìn)K-means算法在文本聚類中的應(yīng)用[D]. 大連:大連交通大學(xué), 2007.

[3] 鄧海. 降維多核K-Means算法在文本聚類中的研究[D]. 南寧:廣西大學(xué), 2013.

[4] 程楊. 中文短文本聚類算法的研究[D]. 長(zhǎng)春:吉林大學(xué), 2016.

[5] 楊河彬. 基于詞向量的搜索詞分類、聚類研究[D]. 上海:華東師范大學(xué), 2015.

[6] Wu Xindong, Kumar V, Quinlan J R, et al. Top 10 algorithms in data mining[J]. Knowledge and Information Systems, 2008,14(1):1-37.

[7] 朱明. 數(shù)據(jù)挖掘[M]. 合肥:中國(guó)科學(xué)技術(shù)大學(xué)出版社, 2002.

[8] Salton G. Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer[M]. Addison-Wesley, 1989.

[9] Baeza-Yates R, Ribeiro-Neto B. Modern Information Retrieval[M]. Addison-Wesley, 1999.

[10] Mikolov T. Word2vec Project[EB/OL]. https://code.google.com/p/word2vec/, 2014-09-18.

[11] Turian J, Ratinov L, Bengio Y. Word representations: A simple and general method for semi-supervised learning[C]// Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics. 2010:384-394.

[12] 周練. Word2vec的工作原理及應(yīng)用探究[J]. 科技情報(bào)開(kāi)發(fā)與經(jīng)濟(jì), 2015,25(2):145-148.

[13] 熊富林,鄧怡豪,唐曉晟. Word2vec的核心架構(gòu)及其應(yīng)用[J]. 南京師范大學(xué)學(xué)報(bào)(工程技術(shù)版), 2015,15(1):43-48.

[14] 唐明,朱磊,鄒顯春. 基于Word2vec的一種文檔向量表示[J]. 計(jì)算機(jī)科學(xué), 2016,43(6):214-217.

[15] 董文. 基于LDA和Word2vec的推薦算法研究[D]. 北京:北京郵電大學(xué), 2015.

[16] 劉敏. 基于詞向量的句子相似度計(jì)算及其在基于實(shí)例的機(jī)器翻譯中的應(yīng)用[D]. 北京:北京理工大學(xué), 2015.