羅恩韜王國(guó)軍（中南大學(xué)信息科學(xué)與工程學(xué)院 長(zhǎng)沙 410083）（湖南科技學(xué)院電子與信息學(xué)院 永州 425006）

大數(shù)據(jù)中一種基于語(yǔ)義特征閾值的層次聚類方法

羅恩韜*①②王國(guó)軍①
①（中南大學(xué)信息科學(xué)與工程學(xué)院 長(zhǎng)沙 410083）②（湖南科技學(xué)院電子與信息學(xué)院 永州 425006）

云計(jì)算、健康醫(yī)療、街景地圖服務(wù)、推薦系統(tǒng)等新興服務(wù)促使數(shù)據(jù)的種類和規(guī)模以前所未有的速度增長(zhǎng)，數(shù)據(jù)量的激增會(huì)導(dǎo)致很多共性問(wèn)題。例如數(shù)據(jù)的可表示，可處理和可靠性問(wèn)題。如何有效處理和分析數(shù)據(jù)之間的關(guān)系，提高數(shù)據(jù)的劃分效率，建立數(shù)據(jù)的聚類分析模型，已經(jīng)成為學(xué)術(shù)界和企業(yè)界共同亟待解決的問(wèn)題。該文提出一種基于語(yǔ)義特征的層次聚類方法，首先根據(jù)數(shù)據(jù)的語(yǔ)義特征進(jìn)行訓(xùn)練，然后在每個(gè)子集上利用訓(xùn)練結(jié)果進(jìn)行層次聚類，最終產(chǎn)生整體數(shù)據(jù)的密度中心點(diǎn)，提高了數(shù)據(jù)聚類效率和準(zhǔn)確性。此方法采樣復(fù)雜度低，數(shù)據(jù)分析準(zhǔn)確，易于實(shí)現(xiàn)，具有良好的判定性。

大數(shù)據(jù)；數(shù)據(jù)抽??；層次聚類；聚類分析

1 引言

云計(jì)算、健康醫(yī)療、推薦系統(tǒng)、社交網(wǎng)絡(luò)等新興服務(wù)促使人類社會(huì)的數(shù)據(jù)種類和規(guī)模正以前所未有的速度增長(zhǎng)。而在以上服務(wù)中，為了讓商品更具有吸引力，讓購(gòu)買客戶更快地找到自己所需要的商品、讓社交網(wǎng)絡(luò)個(gè)人信息更加個(gè)性化等，產(chǎn)生了大規(guī)模的、具有特定特征的、離散的詞匯來(lái)描述數(shù)據(jù)原型的基本形狀特征和結(jié)構(gòu)細(xì)節(jié)。而這些龐大的數(shù)據(jù)信息在大數(shù)據(jù)環(huán)境中由于受本身特性影響，往往造成信息過(guò)載，這使得數(shù)據(jù)的后續(xù)存儲(chǔ)，分類非常不便。因此，如何有效地對(duì)這些具有某種特定特征的數(shù)據(jù)進(jìn)行分析，挖掘數(shù)據(jù)之間的關(guān)系，建立可靠的數(shù)據(jù)聚類模型，從而為新型數(shù)據(jù)計(jì)算提供更個(gè)性化的決策支持和信息服務(wù)就顯得尤為必要。

層次聚類最終會(huì)產(chǎn)生一棵聚類樹(shù)，這樣就更方便了解聚類過(guò)程，因此有益于大數(shù)據(jù)使用者作出決策。目前，國(guó)內(nèi)外學(xué)者對(duì)大數(shù)據(jù)的聚類進(jìn)行了大量研究，現(xiàn)有的方法較多的是將數(shù)據(jù)抽樣方法、矩陣分解同經(jīng)典聚類算法等進(jìn)行結(jié)合來(lái)處理大數(shù)據(jù)的數(shù)據(jù)樣本。例如：文獻(xiàn)［1］提出了計(jì)算用戶權(quán)重，從而抽取用戶特征的思想。文獻(xiàn)［2，3］提出了指數(shù)機(jī)制，該機(jī)制主要是設(shè)計(jì)一些打分函數(shù)來(lái)對(duì)數(shù)據(jù)處理，打分越高，數(shù)據(jù)的特性就越接近。文獻(xiàn)［4-7］利用了數(shù)據(jù)抽樣方式對(duì)數(shù)據(jù)進(jìn)行聚類分析。文獻(xiàn)［8，9］利用分布式計(jì)算來(lái)進(jìn)行譜聚類。文獻(xiàn)［10］利用了矩陣分解的思想來(lái)求得特征值。文獻(xiàn)［11］利用了TOP-K的方法對(duì)大數(shù)據(jù)進(jìn)行查詢。但是以上方法因?yàn)閷?duì)樣本抽取的隨意性，沒(méi)有綜合考慮數(shù)據(jù)本來(lái)的特征值，因此很有可能丟失數(shù)據(jù)的關(guān)鍵特性，而利用矩陣分解思想求得的特征值對(duì)聚類分析的幫助較為有限。因此，將上述思想或者算法運(yùn)用到大數(shù)據(jù)的聚類分析上并不能取得良好的效果。

基于以上分析，本文結(jié)合了大數(shù)據(jù)環(huán)境中的語(yǔ)義文本數(shù)據(jù)的相似度、凝聚度特征，利用潛在概率語(yǔ)義分析（Probabilistic Latent Semantic Analysis，PLSA）算法的奇異值分解對(duì)大數(shù)據(jù)環(huán)境中的語(yǔ)義文本重新建模，結(jié)合數(shù)據(jù)樣本抽樣，抽取具有相似語(yǔ)義特征的文本來(lái)獲得詞語(yǔ)間的語(yǔ)義關(guān)系，再根據(jù)樣本特征，利用N-game統(tǒng)計(jì)語(yǔ)言模型和聯(lián)合解碼算法進(jìn)行分詞，最后通過(guò)期望最大化算法（EM）在數(shù)據(jù)挖掘中的優(yōu)勢(shì)來(lái)訓(xùn)練目標(biāo)簇類（潛在類），從而求解最佳閾值。

利用這個(gè)求得的閾值，結(jié)合層次聚類能夠在不同聚類層次視角下獲取不均勻聚類結(jié)果的優(yōu)勢(shì)，來(lái)控制聚類的聚類層次，在壓縮訓(xùn)練集規(guī)模的同時(shí)盡可能地保證分類精度和泛化性能，從而獲得相對(duì)合適的聚類結(jié)果。

本文的創(chuàng)新點(diǎn)如下：（1）利用N-game統(tǒng)計(jì)語(yǔ)言模型和聯(lián)合解碼分詞算法對(duì)大數(shù)據(jù)文本數(shù)據(jù)進(jìn)行解析。（2）提出一種大數(shù)據(jù)環(huán)境下面向語(yǔ)義特征相似性的閾值求解模型。（3）基于語(yǔ)義特征閾值，構(gòu)建合適的聚類層次，提出了一種新的處理大數(shù)據(jù)聚類的層次聚類方法。

2 相關(guān)定義

2.1層次聚類定義

聚類分析是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要方法，主要用于發(fā)現(xiàn)數(shù)據(jù)中的不同類別及從數(shù)據(jù)中識(shí)別出特定的分布或模式［12］。目前在電子商務(wù)、電影、音樂(lè)、社交網(wǎng)絡(luò)（如微信、微博）中得到了廣泛的應(yīng)用，其中的特征信息也廣泛用于群體的特征劃分，見(jiàn)表1，相對(duì)其他聚類算法，傳統(tǒng)領(lǐng)域?qū)哟尉垲惙椒▽?duì)所有數(shù)據(jù)采用相同的度量，所得到的最終聚類結(jié)果是一棵聚類樹(shù)［13］，實(shí)現(xiàn)了數(shù)據(jù)間基于分布的均勻劃分，數(shù)據(jù)構(gòu)成也比較單一。這樣，最終形成的聚類層次之間的各個(gè)節(jié)點(diǎn)就不能顯示彼此的特征關(guān)系。

表1 數(shù)據(jù)語(yǔ)義特征聚類信息

2.2 凝聚度的定義

對(duì)基于余弦相似度度量的簇的凝聚度可用簇內(nèi)相似度均值來(lái)度量［14］， 即

其中Ck為第k個(gè)簇，uij為Ck類第i個(gè)對(duì)象和第j個(gè)對(duì)象的余弦相似度，m = n × （n - 1）/2， n為簇類對(duì)象數(shù)。

2.3 相似度定義

相似度的定義是聚類分析的基礎(chǔ)［15］，本文相似度的定義采用余弦相似度，如果兩個(gè)向量的相似度為1，則表示兩個(gè)向量完全相同，0 則表示兩個(gè)向量沒(méi)有相似之處。定義余弦相似度的公式為

其中 uij表示 ui和 uj的相似度，表示數(shù)據(jù)簇，表示樣本點(diǎn) di在歐式空間的長(zhǎng)度。

2.4 N-game統(tǒng)計(jì)語(yǔ)言模型和聯(lián)合解碼分詞算法

在數(shù)據(jù)文本分詞時(shí)首先利用 N-game統(tǒng)計(jì)語(yǔ)言模型反映詞和詞之間的轉(zhuǎn)移關(guān)系［16］，當(dāng)兩個(gè)最近的詞（或字）相同時(shí)，映射兩個(gè)詞到同一個(gè)等價(jià)類。根據(jù)最大似然估計(jì)，語(yǔ)言模型的參數(shù)：

其中，C （w1w2… wi）表示樣本 w1w2… wi-1在訓(xùn)練數(shù)據(jù)中出現(xiàn)的次數(shù)。

其次，將它們的切分詞分別作為候選結(jié)果加入到一個(gè)統(tǒng)一的概率空間，通過(guò)求解聯(lián)合概率空間最大概率下的切分路徑，得到最終的切分結(jié)果的聯(lián)合概率分布。

Pci為每個(gè)字的信息概率模型， Pwj為每個(gè)詞的信息概率模型；而字模型和詞模型則利用最大熵模型，進(jìn)行共同決策。如果輸出結(jié)果為k，那么結(jié)合式（4）可以表示為

對(duì)于一個(gè)數(shù)據(jù)文本的分詞集合，通常需要計(jì)算它對(duì)于所有可能輸出k的條件概率，其中選擇最大概率的這個(gè)過(guò)程通常稱為解碼，因此，根據(jù)式（4），式（5）對(duì)聯(lián)合概率空間的字詞聯(lián)合解碼可以表示為

而字詞的聯(lián)合概率模型可以按照所有概率模型的共同作用選擇最終的輸出結(jié)果。字詞聯(lián)合概率模型可以表示為

3 基于潛在語(yǔ)義層次聚類算法

3.1 潛在概率語(yǔ)義分析（PLSA）閾值求解過(guò)程

假設(shè)大數(shù)據(jù)測(cè)試環(huán)境中存在一組具有相似對(duì)象的集合 D = （d1， d2， …， dn）和對(duì)象之中關(guān)鍵字的集合W = （w1， w2， …， wn）。且同時(shí)存在一組具有某種特征的集合 Z = （z1， z2， …， zk），假設(shè)對(duì)象中的關(guān)鍵字呈均勻分布，那么文檔和詞的聯(lián)合分布概率可以表示為

式（8）中，p（di）表示第j個(gè)數(shù)據(jù)對(duì)象概率，p（wi|zk）表示為特征語(yǔ)義發(fā)生條件下關(guān)鍵字發(fā)生的條件概率，p（zk|dj）為數(shù)據(jù)對(duì)象中存在某種特征的條件概率。模型參數(shù)則可以利用極大似然函數(shù)來(lái)進(jìn)行EM（Expectation Maximization）算法迭代，從而估計(jì)閾值L的最優(yōu)解。

其中 n（wi，di）是關(guān)鍵字w在數(shù)據(jù)對(duì)象中d中出現(xiàn)的次數(shù)，相對(duì)于潛在語(yǔ)義分析中的SVD分解，EM算法具有線性收斂速度，可以使似然函數(shù)達(dá)到局部最優(yōu)。

對(duì)于抽取出來(lái)的小數(shù)據(jù)集，希望它能和大數(shù)據(jù)集一樣包含了所有的自然簇（設(shè)總數(shù)為T）。估算樣本大小的方法如下：

式中k為抽取數(shù)據(jù)簇的比例（0 1）k＜ ≤ ，n為數(shù)據(jù)總量， ni為數(shù)據(jù)空間里的預(yù)計(jì)簇類個(gè)數(shù)，式（10）表示按照概率k從簇類中抽取 k × ni個(gè)數(shù)據(jù)樣本 s 的大小。

3.2 基于潛在語(yǔ)義層次聚類算法

在本文算法中，主要考慮合并條件下的層次聚類，聚類產(chǎn)生的結(jié)果來(lái)自于上一次的兩個(gè)聚類的合并，從而來(lái)減少聚類中心的數(shù)量。當(dāng)兩個(gè)類的距離少于設(shè)定的閾值時(shí)，則將兩個(gè)類進(jìn)行合并；否則，進(jìn)入下一步的探測(cè)。

經(jīng)過(guò)歐式距離進(jìn)行計(jì)算，可以得到其相應(yīng)矩陣為

定義為 D，ij數(shù)據(jù)類中 Ni所有樣品和 Nj類中所有樣本間的最小距離，即

利用歐式空間的兩點(diǎn)間的距離公式可以得到

表2 通用合并算法的偽碼

3.3 新聚類算法的復(fù)雜度分析

對(duì)于新算法在運(yùn)行上的空間開(kāi)銷，可以考慮的因素是等待聚類的大數(shù)據(jù)抽樣的特征樣本為k個(gè)，假設(shè)聚類采用單鏈接的聚類方法，每個(gè)待聚類的簇按照串行的實(shí)現(xiàn)方式進(jìn)行擺放，那么聚類的總時(shí)間開(kāi)銷為 O（n3），同時(shí)又假設(shè)抽取樣本所花費(fèi)開(kāi)銷為m，那么算法總的空間復(fù)雜度 S（n）可以表示為

根據(jù)前文所提到的計(jì)算方法特征詞的提取規(guī)則，具有相同或者相似特征的樣本規(guī)模非常小，因此新算法的空間復(fù)雜度為 O（n）。同時(shí)，數(shù)據(jù)樣本的分詞算法的時(shí)間復(fù)雜度為 O（n）。因此算法的時(shí)間復(fù)雜度主要與前文的提取特征，分詞，層次聚類有關(guān)。抽樣數(shù)據(jù)如果采用線性排列，假設(shè)分詞所需時(shí)間為t，提取特征的時(shí)間為l，那么k個(gè)樣本分詞的總時(shí)間為k t× ，提取特征的總時(shí)間為k l× ，聚類的時(shí)間復(fù)雜度3

k n× ，那么算法的總時(shí)間復(fù)雜度可以表示為

可見(jiàn)新算法的時(shí)間開(kāi)銷是線性的，為 O（n）。

4 實(shí)驗(yàn)分析

為驗(yàn)證經(jīng)過(guò)提取特征值判定的層次聚類算法在處理不規(guī)則形狀簇的正確性和有效性，比較本文所給出的語(yǔ)義特征算法模型在給定數(shù)據(jù)區(qū)間獲得聚類的能力。本節(jié)構(gòu)建了具有不規(guī)則形狀的數(shù)據(jù)集，并在該數(shù)據(jù)集上檢驗(yàn)算法的聚類正確率。實(shí)驗(yàn)數(shù)據(jù)來(lái)自芬蘭大學(xué)（http://cs.joensuu.fi/sipu/datasets/）上的聚類測(cè)試集。我們選取一組樣本點(diǎn)進(jìn)行了人工數(shù)據(jù)合成，共包括65536個(gè)特征值元組，使用MATLAB2014搭建實(shí)驗(yàn)環(huán)境，硬件配置為，CPU：I5-4590 CPU3.3 GHz， RAM 4 GB進(jìn)行試驗(yàn)仿真。

圖1 測(cè)試數(shù)據(jù)集1

4.1 數(shù)據(jù)集測(cè)試

在本實(shí)驗(yàn)中，聚類最終輸出是根據(jù)語(yǔ)義特征求的閾值L在該L層獲得較合適的聚類結(jié)果，也就是說(shuō)在該層上基本可以體現(xiàn)語(yǔ)義特征的區(qū)分群體，根據(jù)式（9）求得的特征閾值分別比較了不同特征值產(chǎn)生等價(jià)類的計(jì)算時(shí)間及存儲(chǔ)空間，實(shí)驗(yàn)數(shù)據(jù)是通過(guò)投影在3維空間的樣本向量進(jìn)行表示。參數(shù)L決定了最終聚類樹(shù)的大小，由于本實(shí)驗(yàn)主要觀測(cè)聚類樹(shù)的構(gòu)建過(guò)程，因此為了避免超過(guò)閾值L而形成完全聚類樹(shù)的構(gòu)建，本實(shí)驗(yàn)將先通過(guò)遞增法來(lái)表示聚類樹(shù)的形成過(guò)程。3次實(shí)驗(yàn)中L的取值分別為500， 1000，2000。

4.2 數(shù)據(jù)聚類仿真

實(shí)驗(yàn)結(jié)果見(jiàn)圖2，圖2（a）表示對(duì)數(shù)據(jù)集的初始化，可以看到數(shù)據(jù)是無(wú)序散列的，圖2（b）表示進(jìn)行了一定的聚類，但是沒(méi)有得到具體的聚類期望，圖2（d）表示根據(jù)特征閾值獲得了目標(biāo)聚類，算法終止。可見(jiàn)利用特征值進(jìn)行干擾下的層次聚類算法，可以利用語(yǔ)義特征的提取減少聚類次數(shù)，這樣明顯減少了讀寫磁盤的次數(shù)，從而節(jié)約了運(yùn)算空間和提高了計(jì)算效率。在這里值得一提的是，我們也可以選取圖2（c）的聚類結(jié)果作為最終聚類，因?yàn)樵搱D已經(jīng)基本體現(xiàn)了了特征分類，而且計(jì)算時(shí)間要比圖2（d）小一倍，當(dāng)然這主要是根據(jù)用戶的具體需要進(jìn)行判定。

4.3 算法效率分析

圖2 語(yǔ)義特征聚類仿真結(jié)果

目前針對(duì)于大數(shù)據(jù)算法分析的研究方法主要有模糊信息?；植诩?，多維數(shù)據(jù)去重法，每一種數(shù)據(jù)的處理方法針對(duì)不同數(shù)據(jù)的特征有自身特征的應(yīng)用場(chǎng)合，其算法的時(shí)間復(fù)雜性比較見(jiàn)表3。

為驗(yàn)證語(yǔ)義特征閾值算法的正確性和有效性，我們選取了芬蘭大學(xué)的測(cè)試數(shù)據(jù)集（http://cs. joensuu.fi/sipu/datasets/）進(jìn)行了對(duì)比實(shí)驗(yàn)測(cè)試，數(shù)據(jù)集見(jiàn)圖3。

實(shí)驗(yàn)結(jié)果表明，本文所提出的基于語(yǔ)義特征閾值的層次聚類方法在不同數(shù)據(jù)集上均可以得到正確的聚類數(shù)，并且能夠在相對(duì)較短的時(shí)間完成響應(yīng)。我們選取了Toy Problem， R15， Flame， Aggregation實(shí)驗(yàn)結(jié)果進(jìn)行說(shuō)明，見(jiàn)圖4。

為了驗(yàn)證本文方法在計(jì)算時(shí)間和算法開(kāi)銷上的有效性，本文方法和多維數(shù)據(jù)去重聚類方法在Flame框架數(shù)據(jù)集進(jìn)行了運(yùn)算時(shí)間的比較測(cè)試，經(jīng)過(guò)比較可以看出，本算法在數(shù)據(jù)的計(jì)算效率上優(yōu)于多維數(shù)據(jù)去重聚類算法，并且這種時(shí)間優(yōu)勢(shì)隨數(shù)據(jù)量規(guī)模的遞增而增加。實(shí)驗(yàn)結(jié)果見(jiàn)表4和圖5。

實(shí)驗(yàn)結(jié)果證明，基于語(yǔ)義特征閾值的層次聚類方法所產(chǎn)生的等價(jià)類查詢時(shí)間比在一般意義上的層次聚類算法進(jìn)行查詢響應(yīng)時(shí)間要快，這是因?yàn)橐缘葍r(jià)類方式保存的存儲(chǔ)空間比傳統(tǒng)意義的層次聚類算法要?。煌瑫r(shí)，它對(duì)任意形狀的數(shù)據(jù)集均有效，對(duì)輸入?yún)?shù)具有弱依賴性，并且具有處理噪聲的能力，能夠找到滿足特定的聚類的約束。經(jīng)過(guò)試驗(yàn)測(cè)試，通過(guò)對(duì)數(shù)據(jù)集進(jìn)行特征劃分，然后利用概率估計(jì)計(jì)算出來(lái)的閾值，可以較快地獲得聚類的最佳層數(shù)。

5 結(jié)束語(yǔ)

表3 大數(shù)據(jù)典型分析方法適應(yīng)性比較

目前大數(shù)據(jù)的應(yīng)用非常廣泛，特別是在商業(yè)智能、政府決策、公共服務(wù)、醫(yī)療健康等領(lǐng)域已經(jīng)成為研究熱點(diǎn)。以醫(yī)療健康領(lǐng)域?yàn)槔?，?dāng)前醫(yī)療與健康服務(wù)的數(shù)據(jù)分析面臨了前所未有的挑戰(zhàn)，具體表現(xiàn)有，醫(yī)療患者診療方案的數(shù)據(jù)冗余，因?yàn)閷?duì)于相同的病情，不同的醫(yī)生描述有相當(dāng)大的差別，這導(dǎo)致醫(yī)療系統(tǒng)中數(shù)據(jù)冗余非常離散和龐大，而如此大規(guī)模的不規(guī)則數(shù)據(jù)為數(shù)據(jù)分析和處理帶來(lái)了不便，因此開(kāi)展研究數(shù)據(jù)的價(jià)值挖掘和數(shù)據(jù)分析就顯得尤為必要。本模型著重關(guān)注數(shù)據(jù)的語(yǔ)義特征，通過(guò)算法將數(shù)據(jù)進(jìn)行處理和分析，最后對(duì)相似語(yǔ)義的數(shù)據(jù)進(jìn)行聚類，減少數(shù)據(jù)在計(jì)算和分析過(guò)程中的計(jì)算開(kāi)銷和存儲(chǔ)開(kāi)銷，對(duì)于大數(shù)據(jù)分析具有研究意義，為推動(dòng)新型醫(yī)療健康服務(wù)和其他領(lǐng)域的信息化變革，具有重要的參考價(jià)值。

圖3 測(cè)試數(shù)據(jù)集2

圖4 不同數(shù)據(jù)集的語(yǔ)義特征聚類時(shí)間圖

圖5 語(yǔ)義特征閾值方法和多維數(shù)據(jù)去重方法時(shí)間對(duì)比

表4 不同數(shù)據(jù)量計(jì)算時(shí)間比較

同時(shí)，本文利用實(shí)際數(shù)據(jù)進(jìn)行大量的實(shí)驗(yàn)分析，試驗(yàn)結(jié)果表明本方法可以通過(guò)數(shù)據(jù)出現(xiàn)的特征選擇進(jìn)行降噪和數(shù)據(jù)簡(jiǎn)約降低數(shù)據(jù)的復(fù)雜度，根據(jù)數(shù)據(jù)關(guān)鍵字的出現(xiàn)頻率來(lái)確定聚類特征。在聚類階段，利用似然估計(jì)所計(jì)算出來(lái)的閾值進(jìn)行聚類終止。實(shí)踐證明，該算法比傳統(tǒng)的數(shù)據(jù)層次聚類分析算法具有更好的數(shù)據(jù)分析性能，能更好地提高數(shù)據(jù)分析的可視化，為求解數(shù)據(jù)的多維度之間的映射關(guān)系提供了一種新的思路。當(dāng)然這個(gè)方法還有改進(jìn)的地方，例如數(shù)據(jù)去重的精確度還不太高，數(shù)據(jù)的聚類分析的擴(kuò)展度不夠，而這方面的工作是下一步的研究重點(diǎn)。

［1］ 程學(xué)旗， 靳小龍， 王元卓， 等. 大數(shù)據(jù)系統(tǒng)和分析技術(shù)綜述［J］.軟件學(xué)報(bào)， 2014， 25（9）: 1889-1909. Cheng Xue-qi， Jin Xiao-long， Wang Yuan-zhuo， et al.. Survey on big data system and analytic technology［J］. Journal of Software， 2014， 25（9）: 1889-1909.

［2］ Du Y， He Y， Tian Y， et al.. Microblog bursty topic detection based on user relationship［C］. IEEE 6th Joint International Information Technology and Artificial Intelligence Conference （ITAIC）， Chongqing， China， 2011， 1: 260-263.

［3］ 孫吉貴， 劉杰， 趙連宇. 聚類算法研究［J］. 軟件學(xué)報(bào)， 2008，19（1）: 48-61. Sun Ji-gui， Liu Jie， and Zhao Lian-yu. Clustering algorithms research［J］. Journal of Software， 2008， 19（1）: 48-61.

［4］ Choromanska A， Jebara T， Kim H， et al.. Fast spectral clustering via the nystr?m method［C］. Proceedings of the 24th International Conference， Algorithmic Learning Theory 2013， Singapore， 2013: 367-381.

［5］ Hearn T A and Reichel L. Fast computation of convolution operations via low-rank approximation［J］. Applied Numerical Mathematics， 2014， （75）: 136-153.

［6］ Gajjar M R， Sreenivas T V， and Govindarajan R. Fast computation of Gaussian likelihoods using low-rank matrix approximations［C］. 2011 IEEE Workshop on Signal Processing Systems （SiPS）， Beirut， Lebanon， 2011: 322-327.

［7］ 崔穎安， 李雪， 王志曉， 等. 社會(huì)化媒體大數(shù)據(jù)多階段整群抽樣方法［J］. 軟件學(xué)報(bào)， 2014， 25（4）: 781-796. Cui Ying-an， Li Xue， Wang Zhi-xiao， et al.. Sampling online social media big data based multi stage cluster method［J］. Journal of Software， 2014， 25（4）: 781-796.

［8］ Chen W Y， Song Y， Bai H， et al.. Parallel spectral clustering in distributed systems［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33（3）: 568-586.

［9］ 丁世飛， 賈洪杰， 史忠植. 基于自適應(yīng) Nystr?m 采樣的大數(shù)據(jù)譜聚類算法［J］. 軟件學(xué)報(bào)， 2014， 25（9）: 2037-2049. Ding Shi-fei， Jia Hong-jie， and Shi Zhong-zhi. Spectral clustering algorithm based on adaptive Nystr?m sampling for big data analysis［J］. Journal of Software， 2014， 25（9）: 2037-2049.

［10］ Chen X and Cai D. Large scale spectral clustering with landmark-based representation［C］. Proceedings of the 25th AAAI Conference on Artificaial Inteligence， San Francisco，USA， 2011: 313-318.

［11］ 慈祥， 馬友忠， 孟小峰. 一種云環(huán)境下的大數(shù)據(jù) Top-K查詢方法［J］. 軟件學(xué)報(bào)， 2014， 25（4）: 813-825. Ci Xiang， Ma You-zhong， and Meng Xiao-feng. Method for Top-K query on big data in cloud［J］. Journal of Software，2014， 25（4）: 813-825.

［12］ Horng S J， Su M Y， Chen Y H， et al.. A novel intrusion detection system based on hierarchical clustering and support vector machines［J］. Expert Systems with Applications， 2011，38（1）: 306-313.

［13］ Bahmani B， Moseley B， Vattani A， et al.. Scalable kmeans++［J］. Proceedings of the VLDB Endowment， 2012，5（7）: 622-633.

［14］ Zhang X and You Q. Clusterability analysis and incremental sampling for Nystr?m extension based spectral clustering［C］. IEEE 11th International Conference on Data Mining （ICDM），Vancouver， Canada， 2011: 942-951.

［15］ Zhang K and Kwok J T. Clustered Nystr?m method for large scale manifold learning and dimension reduction［J］. IEEE Transactions on Neural Networks， 2010， 21（10）: 1576-1587.

［16］ Vlachou A， Doulkeridis C， Kotidis Y， et al.. Monochromatic and bichromatic reverse top-k queries［J］. IEEE Transactions on Knowledge and Data Engineering， 2011， 23（8）: 1215-1229.

羅恩韜： 1978年生，男，副教授，博士生，研究方向?yàn)樵瓢踩?、大?shù)據(jù)聚類分析、隱私保護(hù).

王國(guó)軍： 1970年生，男，教授，博士生導(dǎo)師，研究方向?yàn)榭尚庞?jì)算、大數(shù)據(jù)健康醫(yī)療、隱私保護(hù).

A Hierarchical Clustering Method Based on the Threshold of Semantic Feature in Big Data

Luo En-tao①②Wang Guo-jun①
①（School of Information Science and Engineering， Central South University， Changsha 410083， China）
②（School of Electronics and Information Engineering， Hunan University of Science and Engineering， Yongzhou 425006， China）

The type and scale of data has been promoted with a hitherto unknown speed by the emerging services including cloud computing， health care， street view services recommendation system and so on. However， the surge in the volume of data may lead to many common problems， such as the representability， reliability and handlability of data. Therefore， how to effectively handle the relationship between the data and the analysis to improve the efficiency of classification of the data and establish the data clustering analysis model has become an academic and business problem， which needs to be solved urgently. A hierarchical clustering method based on semantic feature is proposed. Firstly， the data should be trained according to the semantic features of data， and then is used the training result to process hierarchical clustering in each subset； finally， the density center point is produced. This method can improve the efficiency and accuracy of data clustering. This algorithm is of low complexity about sampling， high accuracy of data analysis and good judgment. Furthermore， the algorithm is easy to realize.

Big data； Data extraction； Hierarchical clustering； Clustering analysis

s: The National Natural Science Foundation of China （60173037， 6272496， 61272151）； The Hunan Provincial Education Departmant of China （2015C0589）； Key Discipline Project of Hunan University of Science and Engineering

TP393

A

1009-5896（2015）12-2795-07

10.11999/JEIT150422

2015-04-10；改回日期：2015-09-01；網(wǎng)絡(luò)出版：2015-11-01

*通信作者：羅恩韜 cs_entaoluo@csu.edu.cn

國(guó)家自然科學(xué)基金（60173037， 6272496， 61272151），湖南省教育廳科研項(xiàng)目（2015C0589）和湖南科技學(xué)院重點(diǎn)學(xué)科項(xiàng)目