基于Web 電子商務平臺的食用菌產品共詞聚類算法*

紀 琳

（浙江經濟職業技術學院商貿流通學院，浙江 杭州 310018）

食用菌產品電子商務網站一般都包含有大量的信息。用戶在對食用菌產品進行購買銷售時，信息以檢索或提交的方式傳遞給Web 后臺數據庫[1]，數據庫進行查詢、插入等操作。除交易信息外，Web頁面也包含有大量其它的信息，如用戶的登錄次數、搜索產品的名稱、查詢所用的關鍵詞或主題。這些信息對電子平臺來說，是十分重要的信息。從中可以發現一些高影響力和高頻檢索的主題，將其中有共同特征的主題詞進行分組，從而形成一組較高相似度的主題，這一過程即是稱為聚類，采用的算法即為聚類算法。

1 共詞聚類算法基本概念

對于食用菌產品電子商務平臺來說，電子商務平臺的Html 語言都以標簽的形式來定義標題、主體等文檔信息[2]。每一個標簽都有其屬性，屬性提供了有關Html 標簽的更多的信息，其中大多數Html 標簽共同使用的標準屬性有Class、Id 和Style。Class用來對信息進行歸類，代表具有共同性質的數據信息，在同一頁面中同一類信息可以多次出現。

1.1 聚類算法

聚類算法主要應用在主題和關鍵詞的搜索以及它們之間關系的分析上[3]。這一組主題的集合稱為“簇”，簇的特點是內部的數據對象之間有較高的相似度，而與簇外的數據有較高的相異度。對象間的相異度一般采用兩對象間的距離來度量，常用的距離函數有歐幾里得距離、切比雪夫距離、曼哈頓距離、明可夫斯基距離等。

以明可夫斯基距離為例[4]，如式（1） 所示。

式中：n表示n維空間，k為任意常數，x和y為n維空間兩點坐標。

可以看出，距離越近相似度越高。在聚類算法中，相似系數是與距離相反的一種度量方法，相似系數大，說明對象間的相似性高。常用的夾角余弦法、數量積法、指數相似法等表示相似系數。

以數量積法為例，當i=j時，相似系數Sij=1；當i≠j時，相似系數計算如式（2） 所示。

式中：M為正數，且

1.2 共詞聚類算法

共詞聚類也是一種聚類算法，是一種無中心的網狀聚類，沒有明確的中心主題特征，并不關心其它主題與中心主題間的距離。共詞聚類研究的是主題之間的關系，即主題與主題之間的距離，將距離比較近的主題歸為一類，形成一個相對獨立的小類，在這一小類中各主題的相似度很高，但每個小類之間的相異度較高。也就是將一個大類分成各個相對獨立、互不干擾的小類。共詞聚類算法常用在對文檔中高頻主題詞之間關聯性的評價上，主題詞關系越緊密，則聚類效果越好，比較符合文檔關鍵詞的分布形態研究[5]。由于共詞聚類描述的是主題詞或關鍵詞之間關系的緊密程度，因此主題與主題間的相互依賴關系十分重要，一旦一個主題屬性變化，就會傳遞到其它主題，從而引起連鎖反應，使聚類方式發生變化，影響聚類結果，所以共詞聚類是不穩定的網狀聚類方式[6]。

2 食用菌電子商務平臺的共詞聚類算法設計

食用菌電子商務平臺是一個以銷售各類食用菌的電子交易平臺，大量的信息在給用戶帶來便利的同時，也帶來了信息爆炸和信息過載的問題，數據分析處理越來越難，面對信息時的選擇無所適從。用戶無法快速鎖定想要購買的產品，商家無法針對性營銷，結果就造成了用戶體驗變差，潛在用戶流失。

因此，急需將大量食用菌電子商務平臺的數據、信息進行挖掘，對用戶進行畫像、分類找到潛在消費群體、挖掘爆款食用菌產品，實施精準營銷。就食用菌電子商務平臺的數據挖掘來說，共詞聚類算法是一個比較好的選擇，可以用于對電子商務網站Web 頁面的文檔主題和關鍵詞進行挖掘，從而找到潛在用戶的分類。

2.1 基于密度的共詞聚類算法原理

常用的聚類算法有對于發現任意形狀的聚類存在困難。對于共詞聚類來說，更適合用密度來描述聚類。該算法按照給定的閾值，與劃定聚類區域內所有的點個數進行比較，如果大于閾值則將其歸為一類，從而實現相近小類的聚類。該聚類區域中點的個數用密度來表示。常見的密度聚類算法有OPTICS、DBSCAN 算法等。DBSCAN 算法就是利用密度連通性實現聚類。其基本思想是對于類中的每個對象都必須是核心對象。但由于該算法和數據的輸入順序無關，因此數據處理量較大，易產生高維數據。因此又有了基于網格的算法，將空間數據離散化，形成一個網結構，從而解決高維數據的處理速度問題，如CLIQUE 算法、Wave Cluster 算法等。

2.2 共詞聚類算的實現

共詞聚類算法實現主要步驟如下。

第一，找出含有聚類的密集子空間。在算法的實現過程中，由于是由k 維的密集單元格集合Dk生成k+1 維的密集的候選單元格集合Ck+1，因此數據結構應設計成樹形。

從時間復雜度可以看出，時間復雜度和密集單元格最高維子空間稱指數關系，維數的增加將導致時間復雜度的快速增長；這種算法在處理高維數據時效率仍不高[7]。密集單元會隨著子空間維數的增長快速增長，對于密集單元不一定都是我們想要的，因此在實現過程中可以采用MDL 的裁剪，剪去一些不合格的候選集，只保留我們感興趣的密集單元，從而降低時間復雜度。MDL 中心思想就是為了使代碼最短，按照一定的模式對輸入的數據進行編碼。假設存在一個子空間集合{D1,D2, …,Dn}，MDL 方法計算各個子空間含有的記錄數公式為：

式中：couny（ui）是ui中含有的數據點的數目。

對子空間進行覆蓋的降序排序，子空間被分成兩個集合，一個是被選中集合R，一個是被裁剪掉的單元的集合P。分別計算這兩個集合區域覆蓋的平均值，以及該平均值和集合中每個子空間的差；然后把存儲這些值需要的數位進行相加，得到的結果就是我們想要的目標編碼函數：

找到一個能使目標函數TL（i） 的值最小的i值，這個i值也就是被選中區域和被裁減區域的分界點。由于使用了MDL 裁剪技術進行了裁剪，這樣可以降低時間復雜度，但同時也會導致一些密集單元被漏掉，降低了聚類的效果。

第二，非密集單元的移動處理。針對MDL 裁剪技術有遺漏的問題，在處理非密集單元時不能簡單裁剪，而應將其移動處理。即如果某個單元格的中心點與重心點不在同一位置，即重心點偏向于鄰近的密集單元，以該單元的重心為中心，重新畫一個單元，使該單元中的數據點盡可能分布均勻，也就是說使它的中心和重心重合。本質上來看，新的單元就是原來的單元向密集單元移動了。最重要達到的目標就是使包含屬于同一個簇中的數據點的單元靠的緊密一些。

非密集單元的移動處理目標是對于給定的數據集合找出它的簇，找出每一個對象所屬的cluster 并進行標識，算法主要通過數據空間的劃分將密集單元找出，而對于非密集單元，將其向密集單元移動。從而聚類生成cluster，cluster 中的每一個數據點都被標記一個clusterID，即聚類編號。和Step 1 中的步驟一樣，采用深度優先算法來找出密集的連通的子空間。通過FindCluster (u,clusterno) 函數來實現，clusterno 是密集單元的cluster 編號。FindCluster (u,clusterno) 函數的偽代碼如下：

輸入：經移動處理后的數據單元；

FindCluster (u,clusterno) {

Cellnumber=oldCellnumber+addCellnumber;

For (i=0;i

If ( ui 是密集單元&&ui 不屬于任何一個聚類&&ui 和u 是連通的) {

輸出：生成的聚類以及它們的編號clusterno。

第三，找出給定的子空間的聚類。在這一步中，需要輸入的是一個處在同一個子空間中的密集單元格集合D，輸出是{D1,D2, …Dn} 即D的一個劃分。

第四，產生聚類的描述。即輸入同一個子空間中的一個密集單元格集合，這個集合中的單元在k維空間中本應該是連接在一起的，操作把它們分開了，這些單元組成一個聚類P。找出構成聚類的所有單元，這些單元包含的連通單元的數目最少，這樣做的目的就是使每個聚類的描述達到最小。

3 結論

將共詞聚類應用在食用菌電子商務平臺的數據挖掘上，也是一種新的嘗試和探索。但在實際的電子商務數據分析中，如果得到的聚類用戶難于理解，那么就難把它應用到實際的電子交易中。聚類結果必須易于理解、方便平臺用戶的使用，需要把聚類結果和特定的解釋與電子商務的應用相聯系。共詞聚類算法，克服了原有密度聚類算法的精度受方格大小影響、以及由于裁剪造成的聚類結果精確度不高等缺點，在電子商務平臺的應用上表示出了良好的性能。后續還需要通過仿真實驗驗證算法有效性，進一步改進算法提高聚類精度。