蔣 麗，薛善良

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

0 引 言

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

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

1 k-means算法及Word2vec

1.1 k-means算法思想

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

1.2 k-means聚類算法步驟

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

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

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

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

Step3根據(jù)求出的距離，將每個數(shù)據(jù)對象劃分到最相似的簇中，即若滿足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í)和相似計算等問題。但是，它們各具缺點，比如基于VSM的聚類方法是按詞頻統(tǒng)計信息，得出特征的權(quán)重形成向量，而忽略了詞和詞之間，以及文檔和文檔之間的語義相關(guān)性，從而導(dǎo)致聚類的質(zhì)量不高。基于此，本文采用Word2vec[9],Word2vec是Google在2013年開源的一款將詞表征為詞向量[10]的高效工具[11]，Word2vec可以考慮上下文的語義，能在一定程度上提高聚類的準(zhǔn)確性。

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

(a) CBOW模型

(b) Skip-gram模型

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

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

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

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

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

(1)

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

(2)

其中：

(3)

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

(4)

(5)

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

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

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

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

2 改進后的k-means算法思想

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

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

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

(6)

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

(7)

2.2 改進后的k-means算法步驟

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

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

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

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

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

Step4重新計算簇的聚類中心，取k+x個簇中相似度的中心值。

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

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

2.3 改進后的算法流程圖

改進后的算法流程如圖3所示。

圖3 改進后的k-means流程圖

3 仿真實驗分析

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

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

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

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

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

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

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

原始k-means算法改進的k-means算法7097

4 結(jié)束語

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

參考文獻：

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

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

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

[4] 程楊. 中文短文本聚類算法的研究[D]. 長春:吉林大學(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]. 合肥:中國科學(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]. 科技情報開發(fā)與經(jīng)濟, 2015,25(2):145-148.

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

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

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

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