李琳

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

關鍵詞： 圖書分類; 大數(shù)據(jù); 熵加權; 聚類方法; 數(shù)據(jù)維度降低; 矩陣計算

中圖分類號： TN911.1?34; TP309 ? ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? 文章編號： 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）時代的來臨，社會各個行業(yè)都掀起了數(shù)字化、數(shù)據(jù)化的浪潮。圖書館領域也隨著信息化程度的不斷加深，產(chǎn)生了海量的書籍信息。但是如何有效對如此大規(guī)模的數(shù)據(jù)進行處理，從而挖掘出有價值、有關聯(lián)的信息成為難題[1?3]。

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

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

1 ?熵加權聚類原理分析

熵是一種對不確定性的測量，其起源于物理熱力學系統(tǒng)的“無序”度量[7]。在傳統(tǒng)熵加權算法中，聚類的目標函數(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]。此外，假設被聚類的對象為[X={x1，x2，…，xN}?RD]，聚類個數(shù)為[C]，迭代次數(shù)為[M]。

首先初始化[wik（0）]，然后進行重復迭代，其中，通過最小聚類算法目標函數(shù)[8]評估當前集合的隸屬表述程度[uij]：

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

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

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

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

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

根據(jù)式（3）計算的結果推導聚類中心距離[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）

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

[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 ?提出的熵加權聚類改進

2.1 ?初始聚類中心選取

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

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

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

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

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

將式（11）與目標聚類函數(shù)式（1）兩者結合得到：

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

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

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

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

結合式（13）和式（14），可得：

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

2.2 ?合并策略

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

[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ù)據(jù)分類結果實驗。第一部分的實驗采用的數(shù)據(jù)集為簡單的人工數(shù)據(jù)集KDS1，第二部分的實驗采用的是某省會城市的市級圖書館數(shù)據(jù)集，從中隨機選取了10個種類的2 073本書籍信息。兩個數(shù)據(jù)集參數(shù)如表1所示。實驗平臺主要配置為：2.6 GHz CPU，8 GB內(nèi)存，500 GB硬盤，Matlab 2010。

3.1 ?聚類效果分析

如表1所示，數(shù)據(jù)集KDS1的維數(shù)為2，類別數(shù)為3。采用改進熵加權聚類算法對上述兩個數(shù)據(jù)集進行聚類，得到聚類結果如圖1所示?？梢钥闯觯岢龅母倪M熵加權聚類算法能夠得到正確的聚類數(shù)量，驗證了其可行性。

3.2 ?書籍分類效果分析

采用[F1?measure]度量指標[12]來評價分類的性能：

[F1=2PRP+R] （20）

式中：[P]表示查準率;[R]表示查全率。

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

4 ?結 ?語

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

參考文獻

[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] 田磊，任國恒，王偉.基于聚類優(yōu)化的協(xié)同過濾個性化圖書推薦[J].圖書館學研究，2017（8）：77?82.

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

[6] 馬亞玲.云環(huán)境下多載體圖書信息自動分類方法仿真[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] 高翠芳，黃珊維，沈莞薔，等.基于信息熵加權的協(xié)同聚類改進算法[J].計算機應用研究，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.

作者簡介：李 ?琳（1975—），女，河南鄭州人，圖書館館員，研究方向為圖書館學。