基于用戶興趣域的混合數(shù)據(jù)聚類標(biāo)簽算法

李德玉，翁小奎，李艷紅

（1.山西大學(xué) 計算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006；2.山西大學(xué) 計算智能與中文信息處理教育部重點實驗室，山西 太原 030006）

0 引言

聚類是將物理或抽象的對象集合分為由類似對象組成的多個類的過程［1］，在聚類中形成同一個簇中的對象具有較高的相似度，不同簇中的對象具有較低的相似度.從應(yīng)用的角度，人們可通過聚類分析探索數(shù)據(jù)的分布、數(shù)據(jù)的抱團(tuán)性等特征，并利用這些結(jié)果了解和把握生產(chǎn)經(jīng)營活動的規(guī)律，設(shè)計新的產(chǎn)品，科學(xué)決策.混合數(shù)據(jù)是指描述對象的屬性具有符號型、數(shù)值型等多種形式的數(shù)據(jù)集，它是現(xiàn)實世界，特別是商業(yè)金融數(shù)據(jù)庫中最普遍的數(shù)據(jù)類型.然而，對于處理單一類型的數(shù)據(jù)（數(shù)值型數(shù)據(jù)或符號型數(shù)據(jù)）的聚類算法，在處理混合數(shù)據(jù)時，需要進(jìn)行相關(guān)轉(zhuǎn)換，即將符號型屬性轉(zhuǎn)換成數(shù)值型，或者將數(shù)值型屬性通過離散化轉(zhuǎn)換成符號型.研究表明聚類精度會在數(shù)據(jù)類型轉(zhuǎn)換時受到影響［2-5］.發(fā)展針對混合數(shù)據(jù)的聚類理論與方法具有重要的理論價值和實際意義.

1997年，Zhexue Huang提出了 K-prototypes算法［6］，它改進(jìn) K-means算法，來處理混合型數(shù)據(jù)的聚類.K-prototypes算法將符號型屬性與數(shù)值型屬性分開，以便使用適合符號型屬性的相似性度量和適合數(shù)值型屬性的距離度量，然后將兩者結(jié)合起來表示混合型數(shù)據(jù)間的相似性.它和k-means算法一樣具有高效率的優(yōu)點，但聚類結(jié)果同樣也受初始類中心的影響［7］.2002年，Cen Li和Gautan Biswas提出了SBAC算法（Similarity-Based Agglomerative Clustering）［8］.SBAC算法是一種凝聚型層次聚類算法，在度量對象間和類間相似性時，采用了Goodall相似性度量［9］.Goodall相似性度量賦予不經(jīng)常出現(xiàn)的屬性值匹配更大的權(quán)值.對于數(shù)值型屬性，相似性度量不僅考慮特征值的差別大小，而且還考慮值對出現(xiàn)的獨特性.值對出現(xiàn)的獨特性通過位于此值對區(qū)間內(nèi)的數(shù)據(jù)點來度量.2005年，He Zengyou等人提出數(shù)值型屬性聚類和概念型屬性聚類，然后將這些聚類結(jié)果看成是概念型數(shù)據(jù)，在其上應(yīng)用概念型數(shù)據(jù)聚類算法進(jìn)行聚類，并得到最終聚類結(jié)果［10］.2010年，羅會蘭等人提出了一種基于集成技術(shù)和譜聚類技術(shù)的混合數(shù)據(jù)聚類算法（CBEST）［11］，它利用聚類集成技術(shù)產(chǎn)生混合數(shù)據(jù)間的相似性，基于此相似性度量得到的待聚類數(shù)據(jù)的相似性矩陣，然后應(yīng)用譜聚類算法得到混合數(shù)據(jù)聚類結(jié)果.

在大數(shù)據(jù)時代，用戶興趣正在成為數(shù)據(jù)挖掘的一個新的研究視角.2005年，康海燕等人設(shè)計了基于最大生成樹的聚類算法和用戶興趣挖掘算法［12］，結(jié)合用戶興趣對文檔進(jìn)行相關(guān)分析，設(shè)計了個性化信息檢索策略.2008年，陳冬玲等人在語義空間上基于PLSA方法對用戶興趣進(jìn)行聚類［13］，挖掘用戶的信息需求.2011年，龔衛(wèi)華提出了基于主題的用戶興趣聚類算法［14］，在個性化推薦服務(wù)中表現(xiàn)出較高的推薦質(zhì)量和效率.2012年，王微微等人提出的基于用戶行為的興趣度模型，結(jié)合用戶興趣，用期望最大化算法實現(xiàn)用戶聚類，創(chuàng)建用戶興趣度模型，從而向用戶進(jìn)行個性化推薦［15］.趙妍和趙學(xué)民在基于CURE的用戶聚類算法研究的論文中，根據(jù)用戶興趣的顯著特征，提取元素的主要屬性進(jìn)行預(yù)聚類，為小類合并提供合理的初始類集，有較好的聚類效果［16］.

本文在對數(shù)據(jù)聚類分析處理中引入用戶興趣，提出一種基于用戶興趣域的混合數(shù)據(jù)聚類標(biāo)簽算法UIMCL（User’s Interest Mixed Data Clustering Label）.該算法以用戶興趣為基點，對用戶興趣信息進(jìn)行聚類，然后構(gòu)造用戶的興趣域，建立用戶興趣域和混合數(shù)據(jù)的關(guān)聯(lián)關(guān)系，最后對混合數(shù)據(jù)進(jìn)行標(biāo)簽聚類處理.實驗結(jié)果表明，引入用戶興趣信息在混合數(shù)據(jù)集上進(jìn)行UIMCL算法的聚類標(biāo)簽操作，能夠提升直接使用K-prototypes聚類算法對混合數(shù)據(jù)的聚類效果，也改變了聚類對象“非此即彼”的硬劃分方式，同時針對用戶興趣信息的聚類標(biāo)記結(jié)果有助于信息的推薦與用戶的行為決策.

1 用戶興趣聚類

本文在數(shù)據(jù)處理中引入用戶興趣，對用戶興趣信息采用K-prototypes算法［17］對其進(jìn)行聚類處理.K-prototypes算法中定義了一種融合數(shù)值型屬性和符號型屬性的相似性度量，并以其為基礎(chǔ)構(gòu)造聚類的目標(biāo)函數(shù)，通過迭代更新聚類原型來優(yōu)化目標(biāo)函數(shù)，獲得最優(yōu)聚類效果.假定待聚類對象集合為X＝｛X1，X2，X3，…，Xn｝，由n個觀測對象組成，每個觀測對象Xi＝｛xi1，xi2，…，xim｝由m 個屬性A1，A2，…，Am表示，其中，A1，A2，…，Ap為數(shù)值型屬性，Ap＋1，Ap＋2，…，Am為符號型屬性，Dom（Aj）表示屬性Aj的值域.對于符號型屬性Aj（j＞p），令Dom（Aj）＝｝，其中n指屬性Aj取值的數(shù)目.聚類中心用Z表示，相應(yīng)的，簡單記作Za＝（za1，za2，…，zam）.

K-prototypes算法的距離函數(shù)d由數(shù)值型和可分類型兩部分組成：

當(dāng)xij≠zaj時δ（xij，zaj）＝0，當(dāng)xij＝zaj時δ（xij，zaj）＝1，其中γ∈［0，1］為分類屬性的權(quán)重參數(shù).

K-prototypes算法的目標(biāo)函數(shù)為：

其中：uij＝1時，表示樣本Xi在類C1中，uij＝0則表示樣本Xi不屬于類C1中.

K-prototypes聚類算法：

Step 1 初始化初始聚類數(shù)k和聚類中心Z，即從數(shù)據(jù)集中隨機(jī)選取k個初始聚類原型；

Step 2 按照（2）式定義的目標(biāo)函數(shù)最小化原則，將數(shù)據(jù)集中的各個對象劃分到離它最近的聚類原型所代表的類中；

Step 3 對于每個類，重新計算新的聚類原型；

Step 4 計算每個數(shù)據(jù)對象對新的數(shù)據(jù)原型的差異度，如果離一個數(shù)據(jù)對象最近的聚類原型不是當(dāng)前數(shù)據(jù)對象所屬聚類原型，則重新分配這兩個聚類的對象：

Step 5 重復(fù)Step 3和Step 4直到各個聚類中不再有數(shù)據(jù)對象發(fā)生變化.

2 用戶興趣域構(gòu)建

在Fα，β（Ci）中，參數(shù)α是針對數(shù)值屬性的.α越大，表示對數(shù)據(jù)的數(shù)值屬性值是否屬于該用戶興趣域容忍度越大，反之越小.參數(shù)0＜β≤1是針對符號值屬性的，它是一個比例，表示將符號類型屬性的值按其在一個簇中出現(xiàn)頻次由高到低的比例歸入興趣域.用戶興趣域?qū)嵸|(zhì)上是用戶興趣數(shù)據(jù)聚合模式的抽象，就屬性取值而言，不同興趣域的在某個屬性下的取值可以是交叉的.因此，同一個數(shù)據(jù)可能會關(guān)聯(lián)于多個不同的興趣域.

3 數(shù)據(jù)聚類標(biāo)簽

數(shù)據(jù)聚類標(biāo)簽是按照一定的方法，根據(jù)已有的聚類結(jié)果信息，如簇中心、簇原型等為無標(biāo)記數(shù)據(jù)賦以標(biāo)記的過程.與以往的數(shù)據(jù)標(biāo)簽需要賦予無標(biāo)記數(shù)據(jù)一個簇標(biāo)簽不同，本文關(guān)注的是對無標(biāo)記數(shù)據(jù)標(biāo)記一個興趣域.

根據(jù)用戶興趣域中各個屬性的范圍可以建立用戶興趣域與混合數(shù)據(jù)的關(guān)聯(lián)圖，它表示用戶興趣域Dj與混合數(shù)據(jù)樣本Si的關(guān)聯(lián)，如圖1所示.在Dj中每個屬性Vi取值都有一個范圍［ViD，ViU］，其中ViD表示屬性值Vi的下界，ViU表示屬性值Vi的上界.混合數(shù)據(jù)樣本Si中每個屬性Ai與興趣域Dj中對應(yīng)的屬性值Vi的關(guān)聯(lián)用dij表示，當(dāng)Ai∈［ViD，ViU］時，dij＝1，否則，dij＝0.則混合數(shù)據(jù)樣本Si與用戶興趣域Dj的關(guān)聯(lián)度的權(quán)值可用Dij表示，Dij的值由公式（3）獲得，

稱Vij為數(shù)據(jù)Si關(guān)于用戶興趣域Dj的隸屬度，其中M為數(shù)據(jù)樣本的屬性個數(shù).

圖1 數(shù)據(jù)與興趣域的關(guān)聯(lián)關(guān)系圖Fig.1 Relationship diagram of data and an interest domain

由公式（4）可知，Vij的取值范圍為［0，1］，Vij值越大則表示混合型數(shù)據(jù)中數(shù)據(jù)Si歸屬于用戶興趣域Dj的集成度越高，否則，Vij的值越小，表示數(shù)據(jù)Si聚類于Dj的集成度越低.但數(shù)據(jù)Si可能與多個用戶興趣域有聯(lián)系，因此，設(shè)參數(shù)λ控制聚類標(biāo)簽閥值，當(dāng)Vij≥λ時，把Si歸類于Dj，λ的取值根據(jù)聚類的效果進(jìn)行調(diào)節(jié).

我們設(shè)計了數(shù)據(jù)標(biāo)簽算法UIMCL，算法的具體步驟如下：

Step 1：對輸入的用戶興趣信息數(shù)據(jù)集U＝｛U1，U2，U3，…，Un｝，使用聚類算法聚為k個類，即C＝｛C1，C2，…，Ck｝；

Step 2：根據(jù)用戶興趣信息的聚類結(jié)果C＝｛C1，C2，…，Ck｝的類中心屬性值的信息，構(gòu)建用戶興趣域D＝｛D1，D2，D3，…，Dk｝；

Step 3：調(diào)用公式（3）計算混合數(shù)據(jù)集X＝｛X1，X2，X3，…，Xn｝中各個數(shù)據(jù)值與各個用戶興趣域D＝｛D1，D2，D3，…，Dk｝的關(guān)聯(lián)度Dij；

Step 4：用公式（4）計算混合數(shù)據(jù)集中各個數(shù)據(jù)值歸屬于用戶興趣域D＝｛D1，D2，D3，…，Dk｝的隸屬度Vij；

Step 5：根據(jù)設(shè)置的隸屬度控制值λ，對混合數(shù)據(jù)集數(shù)值聚類標(biāo)簽輸出.

在UIMCL算法中，對混合數(shù)據(jù)集聚類時，需要輸入混合型數(shù)據(jù)集X＝｛X1，X2，X3，…，Xn｝和用戶興趣信息數(shù)據(jù)集U＝｛U1，U2，U3，…，Un｝.同時，要給出聚類的個數(shù)k、聚類核大小σ、用戶興趣域容忍度α和β以及聚類標(biāo)簽控制值λ.通過UIMCL算法對混合數(shù)據(jù)集進(jìn)行聚類標(biāo)簽處理，可將輸出歸屬于各個不同用戶興趣域的數(shù)據(jù)樣本值.

4 實驗結(jié)果及分析

4.1 數(shù)據(jù)集與算法精確率

為了驗證UIMCL算法的有效性，本文從UCI真實數(shù)據(jù)集中挑選了三組數(shù)據(jù)集進(jìn)行實驗，這三組數(shù)據(jù)集都是混合型數(shù)據(jù)，數(shù)據(jù)集的具體信息描述如表1所示.

表1 實驗數(shù)據(jù)集Table 1 Experiment datasets

聚類算法的精確率μ，定義如下：

公式中，k是聚類數(shù)目，n是數(shù)據(jù)集中樣本數(shù)，αi是第i個類中被準(zhǔn)確聚類的樣本個數(shù).

4.2 實驗結(jié)果與分析

（1）UIMCL算法中用戶興趣域容忍度的控制值α和β對聚類效果的影響

對應(yīng)數(shù)據(jù)集Heart、Credit和CMC，聚類類別數(shù)k取值為2、2和3，聚類標(biāo)簽控制參數(shù)λ取值為0.8，用戶興趣信息數(shù)目為30%實驗數(shù)據(jù)對象數(shù)目的情況下，可以通過調(diào)節(jié)α和β對聚類效果進(jìn)行控制.α和β對聚類結(jié)果的影響如圖2和圖3所示.

圖2 不同α值的聚類效果Fig.2 Differentαvalue clustering effect

圖3 不同β值的聚類效果Fig.3 Differentβvalue clustering effect

在圖2中可知，隨著α值的增長，數(shù)據(jù)聚類的效果也將隨之提升，當(dāng)α取值大于2時，聚類效果的提升不再明顯.

在圖3中可知，隨著β值的增長，數(shù)據(jù)聚類的效果會也隨著提升，當(dāng)β取值大于0.4時，聚類結(jié)果的提升不再明顯.

由此可知在使用UIMCL算法數(shù)據(jù)聚類處理時，α和β分別取值2和0.4得到了較好的聚類效果.

（2）用戶興趣信息數(shù)目的大小對UIMCL算法聚類效果的影響

在相同實驗數(shù)據(jù)集Heart、Credit和CMC下使用UIMCL算法數(shù)據(jù)聚類處理，聚類類別控制值k分別取2、2和3，用戶興趣域的控制值α和β分別取值為2和0.4，聚類標(biāo)簽控制參數(shù)λ取值為0.8.不同用戶興趣信息的數(shù)目大小對算法的聚類影響如圖4所示.

由圖4可知，實驗數(shù)據(jù)集的聚類準(zhǔn)確率會隨著用戶興趣信息數(shù)目的增多而提升.當(dāng)用戶興趣信息數(shù)目為20%數(shù)據(jù)集數(shù)目時，數(shù)據(jù)集的聚類準(zhǔn)確率約為0.6.隨著用戶興趣信息數(shù)目增加大于數(shù)據(jù)集數(shù)目的40%時，聚類準(zhǔn)確率不再明顯提升.因此在有一定數(shù)目的用戶興趣信息時使用UIMCL算法數(shù)據(jù)聚類處理會得到較好的處理效果.

（3）聚類標(biāo)簽控制參數(shù)λ對數(shù)據(jù)聚類效果的影響

對應(yīng)實驗數(shù)據(jù)集Heart、Credit和CMC，聚類類別數(shù)k分別取值為2、2和3，用戶興趣信息數(shù)目為20%實驗數(shù)據(jù)數(shù)目的情況下，用戶興趣域的控制值α和β分別取值為2和0.4，通過調(diào)節(jié)聚類標(biāo)簽控制參數(shù)λ對聚類效果進(jìn)行控制.λ參數(shù)對聚類結(jié)果的影響如圖5中所示.

圖4 不同用戶興趣信息數(shù)目的聚類效果Fig.4 Different interested number clustering effect

圖5 控制參數(shù)λ對聚類結(jié)果的影響Fig.5 Parametersλvalue clustering effect

從實驗結(jié)果圖5中，不能明確統(tǒng)計聚類標(biāo)簽控制參數(shù)λ的取值對聚類效果影響的規(guī)律，但從實驗結(jié)果圖中可知，當(dāng)聚類標(biāo)簽控制參數(shù)λ取值為0.7時，實驗數(shù)據(jù)集的聚類準(zhǔn)確率最高，取值為0.8時次之.因此本文在對混合數(shù)據(jù)使用UIMCL算法聚類處理時，聚類標(biāo)簽控制參數(shù)λ取值為0.7.

（4）UIMCL算法與經(jīng)典K-prototypes算法比較

在相同數(shù)據(jù)集下，利用第4節(jié)的UIMCL算法與經(jīng)典K-prototypes算法在準(zhǔn)確率上進(jìn)行了對比.聚類類別數(shù)k＝2，3，4，5，6，用戶興趣域的控制值α和β分別取值為2和0.4，聚類標(biāo)簽控制參數(shù)λ取值為0.7.在用戶興趣信息數(shù)目為20%實驗數(shù)據(jù)對象數(shù)目的情況下，Heart、Credit和CMC三種數(shù)據(jù)集的聚類結(jié)果依次為圖6（P185）中（a）、（b）、（c）.

圖6的（a）中Heart數(shù)據(jù)集使用K-prototypes算法UIMCL算法聚類的平均準(zhǔn)確率μ分別為0.58和0.64.在（b）中Credit數(shù)據(jù)集使用K-prototypes算法UIMCL算法聚類的平均準(zhǔn)確率μ分別為0.60和0.65.在（c）中CMC數(shù)據(jù)集使用K-prototypes算法UIMCL算法聚類的平均準(zhǔn)確率μ分別為0.56和0.62.由此可知，在相同混合數(shù)據(jù)集，不同聚類類別數(shù)下對數(shù)據(jù)聚類處理，UIMCL算法的聚類準(zhǔn)確率μ均高于K-prototypes算法的聚類準(zhǔn)確率.

圖6 實驗數(shù)據(jù)集中兩種算法準(zhǔn)確率的比較Fig.6 Experiment data set two algorithm accuracy comparison

5 結(jié)論與展望

本文通過引入用戶興趣信息對數(shù)據(jù)聚類處理進(jìn)行研究，將用戶興趣數(shù)據(jù)作為小規(guī)模數(shù)據(jù)，利用K-prototypes算法對其聚類，在此基礎(chǔ)上構(gòu)建用戶興趣域.利用擬標(biāo)簽數(shù)據(jù)的各屬性值與用戶興趣域分量的關(guān)系定義了數(shù)據(jù)關(guān)于用戶興趣域隸屬度.基于用戶興趣域和“數(shù)據(jù)-用戶興趣域”隸屬度的概念，提出了混合數(shù)據(jù)聚類標(biāo)簽算法UIMCL（User’s Interest Mixed Data Clustering Label）.該算法不僅能有效地處理混合型數(shù)據(jù)聚類，改變數(shù)據(jù)聚類時對象“非此即彼”的硬劃分方式，同時與傳統(tǒng)的K-prototypes算法相比，UIMCL算法數(shù)據(jù)聚類的效果更好，并且基于用戶的興趣信息的數(shù)據(jù)處理結(jié)果，有利于信息的推薦與用戶的行為決策.但本算法在對用戶興趣信息聚類時聚類中心的選取及數(shù)據(jù)類型的權(quán)重處理上欠佳，因此，在進(jìn)一步的研究中，將針對這些方面進(jìn)行更深入的研究，以期待獲得更好的，針對用戶興趣信息的數(shù)據(jù)處理效果.

［1］Xu Rui，Wunsch Donald.Survey of Clustering Algorithm［J］.IEEE Transactions on Neural Net works，2005，16（3）：645-678.

［2］Johannes Grabmeier，Andreas Rudolph.Techniques of Cluster Algorithms in Data Mining［J］.Data Mining and Knowledge Discovery，2002，6（4）：303-360.

［3］Ralambondrainy H.A Conceptual Version of the k-means Algorithm［J］.Pattern Recognition Letters，1995，16（11）：1147-1157.

［4］Wang Hui，Dubitzky Werner.A Flexible and Robust Similarity Measure Based on Contextual Probability［C］／／Proceedings of the International Joint Conference on Artificial Intelligence，2005.

［5］Ma Shuai，Wang Tao.A Fast Clustering Algorithm Based on Reference and Density［J］.Journal of Software，2003，14（6）：1089-1095.

［6］Huang Z X.Clustering Large Data Sets with Mixed Numeric and Categorical Values［C］／／Proceedings of the East Pacific-Asia Conference on Knowledge Discovery and Data Mining，1997.

［7］朱躍龍，李士進(jìn)，劉凈.一種基于 K-prototype的多層次聚類改進(jìn)算法［J］.河海大學(xué)學(xué)報：自然科學(xué)版，2007，3（1）：342-347.

［8］Li Cen，Biswas Gautan.Unsupervised Learning with Mixed Numeric and Nominal Data［J］.IEEE Transactions on Knowledge Data Engineering，2009，14（4）：673-682.

［9］Goodall D W.A New Similarity Index Based On Probability［J］.Biometrics，1996，22：882-892.

［10］He Z Y，Xu X.Clustering Mixed Numeric and Categorical Data：A Cluster Ensemble Approach ［J］.Computer Science Artificial Intelligence，2005，5（4）：255-268.

［11］羅會蘭，危輝.一種基于聚類集成技術(shù)的混合型數(shù)據(jù)聚類算法［J］.計算機(jī)科學(xué)，2010，37（11）：234-244.

［12］康海燕，王克儉.基于最大生成樹的文檔聚類及其在個性化信息檢索中的應(yīng)用［C］／／中國模糊邏輯與計算智能聯(lián)合學(xué)術(shù)會議論文集.2009：351-355.

［13］陳冬玲，王大玲.基于PLSA方法的用戶興趣聚類［J］.東北大學(xué)學(xué)報：自然科學(xué)版，2008，29（1）：53-56.

［14］龔衛(wèi)華，楊良懷，金蓉.基于主題的用戶興趣域算法［J］.通信學(xué)報，2011，32（1）：72-78.

［15］王微微，夏秀峰，李曉明.一種基于用戶行為的興趣度模型［J］.計算機(jī)工程與應(yīng)用，2012，48（8）：148-151.

［16］趙妍，趙學(xué)民.基于CURE的用戶聚類算法研究［J］.計算機(jī)工程與應(yīng)用，2012，48（11）：97-101.

［17］Huang Z X.Extension to the k-means Algorithm for Clustering Large Data Sets with Categorical Values［J］.Data Mining and Knowledge Discovery，1998（2）：283-304.