應(yīng)用于圖書(shū)館書(shū)籍分類(lèi)的熵加權(quán)聚類(lèi)算法

李琳

摘 ?要： 目前很多圖書(shū)館都更加信息化和數(shù)字化，館藏書(shū)籍?dāng)?shù)量也因此不斷提高。如何通過(guò)聚類(lèi)算法做出海量圖書(shū)類(lèi)目的精確分類(lèi)，以便用戶(hù)更加方便快捷地篩選，成為亟需解決的問(wèn)題。提出的熵加權(quán)聚類(lèi)改進(jìn)算法是以傳統(tǒng)熵加權(quán)聚類(lèi)算法為基礎(chǔ)所設(shè)計(jì)的新的聚類(lèi)中心矩陣計(jì)算方法。通過(guò)選取具有代表性的樣本點(diǎn)作為初始聚類(lèi)中心，降低數(shù)據(jù)維度和冗余。此外，通過(guò)合并策略對(duì)信息熵加權(quán)隸屬表示進(jìn)行修改，從而避免聚類(lèi)過(guò)程中的局部最優(yōu)。實(shí)驗(yàn)結(jié)果表明，提出的聚類(lèi)方法在處理書(shū)籍大數(shù)據(jù)分類(lèi)任務(wù)時(shí)具有較高的精度和穩(wěn)定度。

關(guān)鍵詞： 圖書(shū)分類(lèi); 大數(shù)據(jù); 熵加權(quán); 聚類(lèi)方法; 數(shù)據(jù)維度降低; 矩陣計(jì)算

中圖分類(lèi)號(hào)： TN911.1?34; TP309 ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? 文章編號(hào)： 1004?373X（2020）01?0119?03

Entropy weighted clustering algorithm for classification of library books

LI Lin

Abstract： At present， many libraries are more informationized and digitized， so the number of books in the library is constantly increasing. How to accurately classify a large number of books by clustering algorithm has become an urgent problem to be solved， so that users can screen more conveniently and quickly. The new clustering center matrix calculation method is designed on the basis of traditional entropy?weighted clustering algorithm. By selecting representative sample points as initial clustering centers， data dimensionality and redundancy are reduced. In addition， the weighted membership representation of information entropy is modified by merging strategy to avoid local optimum in clustering process. The experimental results show that the proposed clustering method has high accuracy and stability in dealing with large data classification of books.

Keywords： book classification; big data; entropy weighting; clustering method; data dimension reduction; matrix calculation

0 ?引 ?言

隨著大數(shù)據(jù)（Big Data）時(shí)代的來(lái)臨，社會(huì)各個(gè)行業(yè)都掀起了數(shù)字化、數(shù)據(jù)化的浪潮。圖書(shū)館領(lǐng)域也隨著信息化程度的不斷加深，產(chǎn)生了海量的書(shū)籍信息。但是如何有效對(duì)如此大規(guī)模的數(shù)據(jù)進(jìn)行處理，從而挖掘出有價(jià)值、有關(guān)聯(lián)的信息成為難題[1?3]。

目前，聚類(lèi)分析作為大數(shù)據(jù)挖掘常用的方法，表現(xiàn)出良好的劃分判別效果，能夠在劃分類(lèi)未知的情況下，進(jìn)行不同類(lèi)或者簇的數(shù)據(jù)分類(lèi)。因此，許多聚類(lèi)算法被應(yīng)用于圖書(shū)館管理行業(yè)。文獻(xiàn)[4]提出基于聚類(lèi)優(yōu)化的協(xié)同過(guò)濾個(gè)性化圖書(shū)推薦方法。文獻(xiàn)[5]提出一種基于混合聚類(lèi)算法的圖書(shū)館管理系統(tǒng)，利用WEKA混合聚類(lèi)算法進(jìn)行圖書(shū)館的數(shù)據(jù)挖掘任務(wù)。文獻(xiàn)[6]采用核聚類(lèi)的方法實(shí)現(xiàn)圖書(shū)信息自動(dòng)分類(lèi)，通過(guò)結(jié)合TF?IDF計(jì)算表現(xiàn)出較好的邏輯性，且信息類(lèi)別劃分性能良好。

但是，上述聚類(lèi)算法均解決的是低維數(shù)據(jù)問(wèn)題，當(dāng)面對(duì)高維數(shù)據(jù)和大型數(shù)據(jù)的聚類(lèi)問(wèn)題時(shí)，會(huì)表現(xiàn)出精度差和失效的現(xiàn)象。然而，熵加權(quán)聚類(lèi)算法在處理高維數(shù)據(jù)集合時(shí)具有較強(qiáng)的適應(yīng)性。因此，本文將熵加權(quán)聚類(lèi)算法應(yīng)用于書(shū)籍大數(shù)據(jù)集合的聚類(lèi)問(wèn)題，并在原有熵加權(quán)算法的基礎(chǔ)上進(jìn)行改進(jìn)，降低了數(shù)據(jù)維度和冗余，避免聚類(lèi)過(guò)程中的局部最優(yōu)問(wèn)題，提升聚類(lèi)效果從而提高書(shū)籍信息分類(lèi)的準(zhǔn)確度。

1 ?熵加權(quán)聚類(lèi)原理分析

熵是一種對(duì)不確定性的測(cè)量，其起源于物理熱力學(xué)系統(tǒng)的“無(wú)序”度量[7]。在傳統(tǒng)熵加權(quán)算法中，聚類(lèi)的目標(biāo)函數(shù)定義如下：

[J（t）=j=1Ni=1Cumijk=1Dwik（xjk-vik）2+γi=1Ck=1Dwiklog wik] （1）

式中：[0≤uij≤1]，[i=1Cuij=1]，[0≤wik≤1]，[k=1Dwik=1]。此外，假設(shè)被聚類(lèi)的對(duì)象為[X={x1，x2，…，xN}?RD]，聚類(lèi)個(gè)數(shù)為[C]，迭代次數(shù)為[M]。

首先初始化[wik（0）]，然后進(jìn)行重復(fù)迭代，其中，通過(guò)最小聚類(lèi)算法目標(biāo)函數(shù)[8]評(píng)估當(dāng)前集合的隸屬表述程度[uij]：

[uij=（dij）-1/m-1s=1C（dsj）-1/m-1] （2）

該數(shù)據(jù)集合的特征系數(shù)為：

[vik=j=1Numijxikj=1Numij] ? （3）

根據(jù)目標(biāo)函數(shù)及式（2）來(lái)推斷隸屬迭代[ui（Nt）]，如下所示：

[ui（Nt）=（di（Nt））-1m-1s=1C（ds（Nt））-1m-1] （4）

根據(jù)式（3）計(jì)算的結(jié)果推導(dǎo)聚類(lèi)中心距離[9]：

[di（Nt）=k=1Dwik（t-1）（x（Nt）k-vik）2] （5）

其中：

[vik（t）=vik（t-1）-η（t）?umi（Nt）?（vik（t-1）-x（Nt）k）] （6）

[η（t）=η0（ηfη0）tNM] （7）

計(jì)算熵加權(quán)系數(shù)[10]，計(jì)算方法如下：

[wik（t）=exp（-qik（t）γ）s=1Dexp（-qis（t）γ）] （8）

其中：

[qik（t）=qik（t-1）-umi（Nt）（vik（t）-x（Nt）k）2] （9）

2 ?提出的熵加權(quán)聚類(lèi)改進(jìn)

2.1 ?初始聚類(lèi)中心選取

通過(guò)上述熵加權(quán)聚類(lèi)原理分析可以看出，其初始聚類(lèi)中心是從整體范圍中進(jìn)行選取，導(dǎo)致數(shù)據(jù)冗余較大。因此，在現(xiàn)有熵加權(quán)算法的基礎(chǔ)上，設(shè)計(jì)新的聚類(lèi)中心矩陣計(jì)算方法，以便選取具有代表性的樣本點(diǎn)作為初始聚類(lèi)中心，降低數(shù)據(jù)維度。

首先在完成初始化設(shè)置后，包括隸屬表述程度[u（1）ij]，開(kāi)始計(jì)算聚類(lèi)中心矩陣，具體方法如下：

[vik=j=1nu2ijxjkj=1nu2ij] （10）

給定數(shù)據(jù)集合[U=[u1，u2，…，un]]和[V=[v1，v2，…，vn]]，并設(shè)定[wik]的計(jì)算方式如下：

[wik=exp-j=1nu2ij（xjk-vik）2γs=1dexp-j=1nu2ij（xjs-vis）2γ] （11）

將式（11）與目標(biāo)聚類(lèi)函數(shù)式（1）兩者結(jié)合得到：

[ψ（wik）=i=1cj=1nu2ijk=1dwik（xjk-vik）2+γi=1cj=1nwiklog wik-i=1cλwik=1dwik-1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（12）]

在式（12）中分別對(duì)[wik]和[λwi]求偏導(dǎo)數(shù)，并令結(jié)果等于0， 則有：

[?ψ（wik）?wik=j=1nu2ij（xjk-vik）2+γ（log wik+1）-λwi=0] ?（13）

[?ψ（wik）?wik=k=1dwik-1=0] （14）

結(jié)合式（13）和式（14），可得：

[wik=exp-j=1nu2ij（xjk-vik）2γs=1dexp-j=1nu2ij（xjs-vis）2γ] （15）

2.2 ?合并策略

最后，通過(guò)合并策略對(duì)信息熵加權(quán)隸屬表示進(jìn)行修改，從而避免聚類(lèi)過(guò)程中的局部最優(yōu)[11]，定義合并策略熵加權(quán)的隸屬表示計(jì)算方法如下：

[uij=η?u+（1-η）?u″ij] ?（16）

式中[η]表示合并系數(shù)。

[u′ij=1s=1Ck=1dwik（xjk-vij）2k=1dwsk（xjk-vsk）2] （17）

[u″ij=αNi-Njk=1dwik（xjk-vik）2] ? ?（18）

[Nj=αs=1C1k=1dwsk（xjk-vsk）2Nss=1C1k=1dwsk（xjk-vsk）2] （19）

3 ?實(shí)驗(yàn)結(jié)果與分析

本實(shí)驗(yàn)分為兩部分：對(duì)改進(jìn)熵加權(quán)聚類(lèi)算法的聚類(lèi)效果實(shí)驗(yàn);采用提出聚類(lèi)算法的書(shū)籍大數(shù)據(jù)分類(lèi)結(jié)果實(shí)驗(yàn)。第一部分的實(shí)驗(yàn)采用的數(shù)據(jù)集為簡(jiǎn)單的人工數(shù)據(jù)集KDS1，第二部分的實(shí)驗(yàn)采用的是某省會(huì)城市的市級(jí)圖書(shū)館數(shù)據(jù)集，從中隨機(jī)選取了10個(gè)種類(lèi)的2 073本書(shū)籍信息。兩個(gè)數(shù)據(jù)集參數(shù)如表1所示。實(shí)驗(yàn)平臺(tái)主要配置為：2.6 GHz CPU，8 GB內(nèi)存，500 GB硬盤(pán)，Matlab 2010。

3.1 ?聚類(lèi)效果分析

如表1所示，數(shù)據(jù)集KDS1的維數(shù)為2，類(lèi)別數(shù)為3。采用改進(jìn)熵加權(quán)聚類(lèi)算法對(duì)上述兩個(gè)數(shù)據(jù)集進(jìn)行聚類(lèi)，得到聚類(lèi)結(jié)果如圖1所示?？梢钥闯?，提出的改進(jìn)熵加權(quán)聚類(lèi)算法能夠得到正確的聚類(lèi)數(shù)量，驗(yàn)證了其可行性。

3.2 ?書(shū)籍分類(lèi)效果分析

采用[F1?measure]度量指標(biāo)[12]來(lái)評(píng)價(jià)分類(lèi)的性能：

[F1=2PRP+R] （20）

式中：[P]表示查準(zhǔn)率;[R]表示查全率。

分別利用傳統(tǒng)K?均值聚類(lèi)[13]、傳統(tǒng)熵加權(quán)聚類(lèi)[14]和改進(jìn)的熵加權(quán)聚類(lèi)對(duì)圖書(shū)館數(shù)據(jù)集進(jìn)行分類(lèi)實(shí)驗(yàn)，并在[F1?measure]指標(biāo)方面進(jìn)行比較分析。為了合理有效性，在數(shù)據(jù)集上對(duì)每種算法重復(fù)運(yùn)行10 次取平均值。3種算法的分類(lèi)結(jié)果對(duì)比如表2所示。可以看出，改進(jìn)的熵加權(quán)算法在[F1?measure]指標(biāo)的性能統(tǒng)計(jì)明顯優(yōu)于傳統(tǒng)K?均值聚類(lèi)和傳統(tǒng)熵加權(quán)聚類(lèi)，表現(xiàn)出更佳的準(zhǔn)確度。同時(shí)迭代次數(shù)也有所降低，穩(wěn)定性較好。

4 ?結(jié) ?語(yǔ)

本文在原有熵加權(quán)算法的基礎(chǔ)上進(jìn)行改進(jìn)，降低了數(shù)據(jù)維度和冗余，避免了聚類(lèi)過(guò)程中的局部最優(yōu)問(wèn)題，提升聚類(lèi)效果。通過(guò)實(shí)驗(yàn)得出如下結(jié)論：人工數(shù)據(jù)集的聚類(lèi)實(shí)驗(yàn)驗(yàn)證了提出算法的有效性;相比其他兩種算法，提出聚類(lèi)算法在圖書(shū)館書(shū)籍?dāng)?shù)據(jù)集上具有更大的[F1?measure]分類(lèi)指標(biāo)數(shù)值。但是，對(duì)混合簇的聚類(lèi)效果仍有待提升，后續(xù)將對(duì)此進(jìn)行完善。

參考文獻(xiàn)

[1] YANG C W， HUANG Q Y， LI Z L， et al. Big data and cloud computing： innovation opportunities and challenges [J]. International journal of digital earth， 2017， 10（1）： 13?53.

[2] AKTER S， WAMBA S F. Big data and disaster management： a systematic review and agenda for future research [J]. Annals of operations research， 2017（9）： 1?21.

[3] HU H， WEN Y， CHUA T S， et al. Toward scalable systems for big data analytics： a technology tutorial [J]. IEEE access， 2017， 2（1）： 652?687.

[4] 田磊，任國(guó)恒，王偉.基于聚類(lèi)優(yōu)化的協(xié)同過(guò)濾個(gè)性化圖書(shū)推薦[J].圖書(shū)館學(xué)研究，2017（8）：77?82.

[5] 周運(yùn)麗.基于混合聚類(lèi)算法的圖書(shū)館管理系統(tǒng)研究[J].計(jì)算機(jī)與數(shù)字工程，2018，46（3）：504?507.

[6] 馬亞玲.云環(huán)境下多載體圖書(shū)信息自動(dòng)分類(lèi)方法仿真[J].計(jì)算機(jī)仿真，2018，35（11）：297?300.

[7] YANG M S， NATALIANI Y. A feature?reduction fuzzy clus?tering algorithm based on feature?weighted entropy [J]. IEEE transactions on fuzzy systems， 2018， 26（2）： 817?835.

[8] ?OMAK E. A modified particle swarm optimization algorithm using Renyi entropy?based clustering [J]. Neural computing & applications， 2016， 27（5）： 1381?1390.

[9] CHA H S， YOO S W， LEE T， et al. An entropy?based clus?tering algorithm for load balancing in WSN [J]. International journal of sensor networks， 2016， 22（3）： 188?196.

[10] 高翠芳，黃珊維，沈莞薔，等.基于信息熵加權(quán)的協(xié)同聚類(lèi)改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用研究，2015，32（4）：1016?1018.

[11] ZHAO W， LIU H， DAI W， et al. An entropy?based clustering ensemble method to support resource allocation in business process management [J]. Knowledge & information systems， 2016， 48（2）： 305?330.

[12] ZHANG H Y， PU J， WANG J Q， et al. An improved weighted correlation coefficient based on integrated weight for interval neutrosophic sets and its application in multi?criteria decision?making problems [J]. International journal of computational intelligence systems， 2015， 8（6）： 1027?1043.

[13] DUBEY A K， GUPTA U， JAIN S. Analysis of K?means clustering approach on the breast cancer wisconsin dataset [J]. International journal of computer assisted radiology & surgery， 2016（11）： 2033?2047.

[14] NGUYEN N， VO A P N， CHOI I， et al. A stationary wavelet entropy?based clustering approach accurately predicts gene expression [J]. Journal of computational biology， 2015， 22（3）： 236?249.

作者簡(jiǎn)介：李 ?琳（1975—），女，河南鄭州人，圖書(shū)館館員，研究方向?yàn)閳D書(shū)館學(xué)。