基于Web 電子商務(wù)平臺(tái)的食用菌產(chǎn)品共詞聚類算法*

紀(jì) 琳

（浙江經(jīng)濟(jì)職業(yè)技術(shù)學(xué)院商貿(mào)流通學(xué)院，浙江 杭州 310018）

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

1 共詞聚類算法基本概念

對(duì)于食用菌產(chǎn)品電子商務(wù)平臺(tái)來說，電子商務(wù)平臺(tái)的Html 語言都以標(biāo)簽的形式來定義標(biāo)題、主體等文檔信息[2]。每一個(gè)標(biāo)簽都有其屬性，屬性提供了有關(guān)Html 標(biāo)簽的更多的信息，其中大多數(shù)Html 標(biāo)簽共同使用的標(biāo)準(zhǔn)屬性有Class、Id 和Style。Class用來對(duì)信息進(jìn)行歸類，代表具有共同性質(zhì)的數(shù)據(jù)信息，在同一頁(yè)面中同一類信息可以多次出現(xiàn)。

1.1 聚類算法

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

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

式中：n表示n維空間，k為任意常數(shù)，x和y為n維空間兩點(diǎn)坐標(biāo)。

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

以數(shù)量積法為例，當(dāng)i=j時(shí)，相似系數(shù)Sij=1；當(dāng)i≠j時(shí)，相似系數(shù)計(jì)算如式（2） 所示。

式中：M為正數(shù)，且

1.2 共詞聚類算法

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

2 食用菌電子商務(wù)平臺(tái)的共詞聚類算法設(shè)計(jì)

食用菌電子商務(wù)平臺(tái)是一個(gè)以銷售各類食用菌的電子交易平臺(tái)，大量的信息在給用戶帶來便利的同時(shí)，也帶來了信息爆炸和信息過載的問題，數(shù)據(jù)分析處理越來越難，面對(duì)信息時(shí)的選擇無所適從。用戶無法快速鎖定想要購(gòu)買的產(chǎn)品，商家無法針對(duì)性營(yíng)銷，結(jié)果就造成了用戶體驗(yàn)變差，潛在用戶流失。

因此，急需將大量食用菌電子商務(wù)平臺(tái)的數(shù)據(jù)、信息進(jìn)行挖掘，對(duì)用戶進(jìn)行畫像、分類找到潛在消費(fèi)群體、挖掘爆款食用菌產(chǎn)品，實(shí)施精準(zhǔn)營(yíng)銷。就食用菌電子商務(wù)平臺(tái)的數(shù)據(jù)挖掘來說，共詞聚類算法是一個(gè)比較好的選擇，可以用于對(duì)電子商務(wù)網(wǎng)站W(wǎng)eb 頁(yè)面的文檔主題和關(guān)鍵詞進(jìn)行挖掘，從而找到潛在用戶的分類。

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

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

2.2 共詞聚類算的實(shí)現(xiàn)

共詞聚類算法實(shí)現(xiàn)主要步驟如下。

第一，找出含有聚類的密集子空間。在算法的實(shí)現(xiàn)過程中，由于是由k 維的密集單元格集合Dk生成k+1 維的密集的候選單元格集合Ck+1，因此數(shù)據(jù)結(jié)構(gòu)應(yīng)設(shè)計(jì)成樹形。

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

式中：couny（ui）是ui中含有的數(shù)據(jù)點(diǎn)的數(shù)目。

對(duì)子空間進(jìn)行覆蓋的降序排序，子空間被分成兩個(gè)集合，一個(gè)是被選中集合R，一個(gè)是被裁剪掉的單元的集合P。分別計(jì)算這兩個(gè)集合區(qū)域覆蓋的平均值，以及該平均值和集合中每個(gè)子空間的差；然后把存儲(chǔ)這些值需要的數(shù)位進(jìn)行相加，得到的結(jié)果就是我們想要的目標(biāo)編碼函數(shù)：

找到一個(gè)能使目標(biāo)函數(shù)TL（i） 的值最小的i值，這個(gè)i值也就是被選中區(qū)域和被裁減區(qū)域的分界點(diǎn)。由于使用了MDL 裁剪技術(shù)進(jìn)行了裁剪，這樣可以降低時(shí)間復(fù)雜度，但同時(shí)也會(huì)導(dǎo)致一些密集單元被漏掉，降低了聚類的效果。

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

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

輸入：經(jīng)移動(dòng)處理后的數(shù)據(jù)單元；

FindCluster (u,clusterno) {

Cellnumber=oldCellnumber+addCellnumber;

For (i=0;i

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

輸出：生成的聚類以及它們的編號(hào)clusterno。

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

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

3 結(jié)論

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