王輝 趙瑋 祁 薇

摘要：隨著電子商務(wù)的快速發(fā)展，用戶數(shù)量與日俱增，商品數(shù)量龐大。在海量商品中，如何快速地得到自己想要的商品。基于這個(gè)問(wèn)題，該文利用了用戶的個(gè)人信息，將用戶的個(gè)人性格特征、所屬職業(yè)，以層次樹(shù)的方式進(jìn)行量化表示，并采用K-means算法將用戶進(jìn)行聚類，具有相似特征的用戶在同一個(gè)類別中，將查詢最近鄰時(shí)間降低。最后針對(duì)K-means聚類算法初始中心的選擇問(wèn)題，采用kruskal算法構(gòu)造最小生成樹(shù)的思想進(jìn)行改進(jìn)，解決了k中心點(diǎn)的選擇問(wèn)題。

關(guān)鍵詞：個(gè)人特征;次樹(shù);k-means算法;Kruskal最小生成樹(shù)

中圖分類號(hào)：TP391? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? 文章編號(hào)：1009-3044（2018）35-0017-03

1? 背景

中國(guó)電子商務(wù)研究中心2018年統(tǒng)計(jì)數(shù)據(jù)表明[1]，我國(guó)電子商務(wù)全局保持了快速發(fā)展的勢(shì)頭，成為我國(guó)經(jīng)濟(jì)發(fā)展的主力軍。個(gè)性化推薦技術(shù)是電子商務(wù)領(lǐng)域核心技術(shù)，它能根據(jù)不同的用戶推薦符合個(gè)人需求的商品。個(gè)性化推薦系統(tǒng)的可以劃分為三個(gè)模塊：第一個(gè)模塊用來(lái)提取用戶特征，第二個(gè)模塊進(jìn)行相關(guān)物品檢索，最后一個(gè)模塊用于推薦結(jié)果。聚類是用戶特征提取模塊的重要算法，屬于數(shù)據(jù)挖掘技術(shù)之一，能夠幫助市場(chǎng)分析人員區(qū)分出不同的消費(fèi)群體來(lái)。聚類分析算法有很多，有基于密度的聚類、基于模型的聚類、基于層次的聚類、基于劃分的聚類，我們通常使用基于劃分中的k-means聚類算法[2]。

該文利用了用戶的個(gè)人信息，將不同用戶的性格特征、從事的行業(yè)，通過(guò)層次樹(shù)的方法進(jìn)行量化表示，之后，利用K-means算法將用戶進(jìn)行聚類，使具有相似個(gè)人特征的用戶在同一個(gè)簇中，降低了搜索最近鄰的時(shí)間。

2 K-means聚類算法

K-means是一種常見(jiàn)的數(shù)據(jù)聚類算法，基本思想是：算法接收參數(shù)k，然后將事先輸入的n個(gè)數(shù)據(jù)對(duì)象劃分為k個(gè)聚類以便使得所獲得的聚類滿足：同一聚類中的對(duì)象相似度較高，不同聚類中的對(duì)象相似度較小。通過(guò)不斷的迭代，逐次更新各聚類中心的值，直至得到最好的聚類結(jié)果。

K-means聚類算法步驟：

1） 先從沒(méi)有標(biāo)簽的元素集合A中隨機(jī)抽取k個(gè)元素，作為k個(gè)子集各自的重心;

2） 分別計(jì)算剩下的元素到k個(gè)子集重心的距離，根據(jù)距離將這些元素分別劃歸到最近的子集;

3） 根據(jù)聚類結(jié)果，重新計(jì)算重心：

4） 判斷聚類函數(shù)是否收斂，收斂則結(jié)束，不收斂轉(zhuǎn)向2）進(jìn)一步迭代：[E=i=1kx∈cix-xi2] （2）

K-means聚類算法簡(jiǎn)單高效，適用于海量數(shù)據(jù)的處理的特性，但是k值的選擇是隨機(jī)的，對(duì)于初始質(zhì)心點(diǎn)的選取的好壞容易影響最終聚類結(jié)果，容易陷入局部最優(yōu)解。

針對(duì)k-means聚類算法的缺陷，該文采用kruskal算法構(gòu)造最小生成樹(shù)的思想優(yōu)化初始聚類質(zhì)心數(shù)目k的選擇，避免局部最優(yōu)解的產(chǎn)生。

3 k-means聚類算法的改進(jìn)

該文借鑒了最小生成樹(shù)的原來(lái)，提出了一種改進(jìn)的k-means聚類算法。將系統(tǒng)中的用戶作為數(shù)據(jù)空間的頂點(diǎn)，用戶之間的距離，看作是一條邊，根據(jù)kruskal[4]算法來(lái)用點(diǎn)和邊構(gòu)造最小生成樹(shù)。

改進(jìn)的k-means聚類算法步驟：

1） 所有用戶表示成連通網(wǎng)N=（V，{E}），其中V是頂點(diǎn)的集合，每一個(gè)頂點(diǎn)代表一個(gè)用戶，E是全部邊的集合，每一條邊代表用戶之間的距離。

2） 使用具有n個(gè)頂點(diǎn)且無(wú)邊的非連通圖T=（V，{ }）表示初始狀態(tài)，把每個(gè)頂點(diǎn)看成一個(gè)連通分量。

3） 在E中選擇邊長(zhǎng)最小的邊，如果該邊對(duì)應(yīng)的頂點(diǎn)處于T中不同的連通分量上，則將此邊加入T中，否則，去掉該邊，重新選擇一條邊長(zhǎng)最小的邊。重復(fù)以上步驟，直到某些頂點(diǎn)的連線構(gòu)成了環(huán)，則將這些頂點(diǎn)加入同一個(gè)集合k中，然后把這些頂點(diǎn)在T中刪除。

4） 重復(fù)第3）步，直到所有的頂點(diǎn)都分配到k個(gè)集合中。

5） 計(jì)算每個(gè)集合的中心，以此作為k個(gè)初始的聚類中心。

6） 應(yīng)用傳統(tǒng)的k-means聚類算法完成聚類。

求解過(guò)程演示如圖1。

4 基于用戶個(gè)人特征的聚類算法實(shí)現(xiàn)

該文將用戶的個(gè)人特征分為六個(gè)屬性：年齡，性別，學(xué)歷，職業(yè)，性格特點(diǎn)，個(gè)人偏好，按照用戶個(gè)人特征的不同對(duì)其進(jìn)行聚類。

首先將用戶的個(gè)人信息進(jìn)行量化表示。年齡是一個(gè)數(shù)值屬性，使用用戶注冊(cè)信息時(shí)填寫(xiě)的年齡值，性別是個(gè)二元屬性，男性用0表示，女性用1表示，學(xué)歷劃分為小學(xué)，中學(xué)，大學(xué)，碩士，博士五種類型，分別用數(shù)字1到5來(lái)表示，職業(yè)和性格特征將其以層次樹(shù)的形式進(jìn)行表示。

美國(guó)霍普金斯大學(xué)心理學(xué)教授、著名的職業(yè)指導(dǎo)專家約翰.L.霍蘭德（John L.Holland）[3]將職業(yè)劃分為實(shí)際型、研究型、藝術(shù)型、社會(huì)型、企業(yè)型、傳統(tǒng)型六大基本類型。參照約翰.L.霍蘭德的分類方法，該文將用戶職業(yè)以層次樹(shù)的形式進(jìn)行表示。如圖2所示：

六個(gè)基本類型內(nèi)部還有具體的職業(yè)劃分，例如歌唱舞蹈分為：歌唱家，舞蹈家，歌唱家還分為民族，通俗，美聲等等。自然科學(xué)分為天文學(xué)工作者，物理學(xué)工作者，化學(xué)工作者等等。自頂向下，從左到右，將每一層進(jìn)行編號(hào)從0開(kāi)始標(biāo)號(hào)，0為職業(yè)，1為實(shí)際型，2為研究型，3為藝術(shù)型…011為手工操作，012為技術(shù)操作，0111為木匠，0112為鎖匠…以此類推。

用戶的性格特征也可以分為以下幾類：嚴(yán)肅型，嚴(yán)謹(jǐn)型，幽默型（冷幽默，搞笑型），熱情型，內(nèi)向型，外向型，綜合型…那么將用戶性格特征表示成性格層次樹(shù)，如圖3所示。

通過(guò)性格層次樹(shù)，用戶性格特征可以進(jìn)行量化，例如，某一用戶的性格特征是木訥型，可以量化為022，嚴(yán)謹(jǐn)型則量化為0211，以此類推，全部用戶特征都可以量化表示。

通過(guò)上面兩個(gè)操作，用戶信息全部進(jìn)行了量化，例如用戶甲：性別：男;年齡31，學(xué)歷：碩士，職業(yè)：物理學(xué)工作者，性格：嚴(yán)謹(jǐn)型，那么用戶甲個(gè)人信息量化的結(jié)果為{0，31，4，0212，0211}。

之后，采用改進(jìn)的k-means算法對(duì)用戶量化向量實(shí)行聚類操作，使具有相似個(gè)人信息的用戶能夠聚為一類，從而得到k個(gè)用戶簇，最近鄰的查找在同一個(gè)簇中進(jìn)行，節(jié)省了查找時(shí)間，提升了推薦精度。

5 試驗(yàn)結(jié)果及其分析

該文采用的實(shí)驗(yàn)數(shù)據(jù)來(lái)自movielens的數(shù)據(jù)集，分別利用傳統(tǒng)的k-means聚類算法以及改進(jìn)的基于用戶個(gè)人特征的聚類算法仿真實(shí)驗(yàn)，比較兩種算法的性能，以最小空間內(nèi)搜索到最近鄰的數(shù)目作為衡量標(biāo)準(zhǔn)。

隨機(jī)選取ID為16，121，317，608，912五位用戶，最近鄰閾值選取14，聚類數(shù)目分別選取2，3，4，5，（其中4為通過(guò)kruskal找到的最佳k值）對(duì)每一個(gè)活動(dòng)用戶只在其所在的簇中查找最近鄰居，查到的最近鄰居如表1、2所示：

傳統(tǒng)的聚類算法：

通過(guò)計(jì)算得出，聚類數(shù)目2，傳統(tǒng)的聚類算法搜索率為1.497，聚類數(shù)目3，搜索率為2.366，聚類數(shù)目4，搜索率為2.34…，平均搜索率為2.16。

改進(jìn)的聚類算法如表2所示。

通過(guò)計(jì)算得出，聚類數(shù)目2，改進(jìn)聚類算法搜索率為1.63，聚類數(shù)目3，搜索率為2.69，聚類數(shù)目是4（4是通過(guò)kruskal找到的最佳k值），搜索率為2.99…平均搜索率為2.37。

通過(guò)改進(jìn)的聚類算法和傳統(tǒng)聚類算法的對(duì)比，證明了該文改進(jìn)的聚類算法能夠合理地選擇k值，在比較小的用戶空間內(nèi)搜索到更多的鄰居，這種改進(jìn)方法提高了查找用戶最近鄰的效率和精度，能夠滿足推薦系統(tǒng)對(duì)實(shí)時(shí)性的要求。

6 總結(jié)

該文針對(duì)傳統(tǒng)的k-means聚類算法k值不確定問(wèn)題，采用了kruskal算法構(gòu)造最小生成樹(shù)的思想對(duì)其進(jìn)行改進(jìn)，解決了由于k的隨機(jī)性帶來(lái)的局部最優(yōu)解的問(wèn)題，并且按照用戶個(gè)人特征，采用職業(yè)層次樹(shù)和性格層次樹(shù)方式，對(duì)用戶個(gè)人特征進(jìn)行量化表示，節(jié)省了最近鄰的搜索時(shí)間，提高了推薦精度。

參考文獻(xiàn)：

[1] 朱明.數(shù)據(jù)挖掘[M].合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2008：37-38.

[2] Han J W， Kamber M. 數(shù)據(jù)挖掘：概念與技術(shù)[M].北京： 機(jī)械工業(yè)出版社，2001： 232-235.

[3] Nada Dabbagh， Brenda Bannan-Ritland. Online learning： concepts， strategies， and application[M]. New Jersey： Prentice Hall， 2004.

[4] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社， 2003：175-176.

[5] Sarwar B M.， KaryPis G， Konstan J A， et al. Item-based Collaborative filtering recommendationaglgorithm[C]. Proceedings of the Tenth International World Wide Web Conference， ACM Press， 2001：285-295.

[通聯(lián)編輯：謝媛媛]