應用于圖書館書籍分類的熵加權聚類算法

李琳

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

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

中圖分類號： 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 ?引 ?言

隨著大數據（Big Data）時代的來臨，社會各個行業都掀起了數字化、數據化的浪潮。圖書館領域也隨著信息化程度的不斷加深，產生了海量的書籍信息。但是如何有效對如此大規模的數據進行處理，從而挖掘出有價值、有關聯的信息成為難題[1?3]。

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

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

1 ?熵加權聚類原理分析

熵是一種對不確定性的測量，其起源于物理熱力學系統的“無序”度量[7]。在傳統熵加權算法中，聚類的目標函數定義如下：

[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]，聚類個數為[C]，迭代次數為[M]。

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

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

該數據集合的特征系數為：

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

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

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

根據式（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）

計算熵加權系數[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 ?初始聚類中心選取

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

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

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

給定數據集合[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）與目標聚類函數式（1）兩者結合得到：

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

在式（12）中分別對[wik]和[λwi]求偏導數，并令結果等于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 ?合并策略

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

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

式中[η]表示合并系數。

[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 ?實驗結果與分析

本實驗分為兩部分：對改進熵加權聚類算法的聚類效果實驗;采用提出聚類算法的書籍大數據分類結果實驗。第一部分的實驗采用的數據集為簡單的人工數據集KDS1，第二部分的實驗采用的是某省會城市的市級圖書館數據集，從中隨機選取了10個種類的2 073本書籍信息。兩個數據集參數如表1所示。實驗平臺主要配置為：2.6 GHz CPU，8 GB內存，500 GB硬盤，Matlab 2010。

3.1 ?聚類效果分析

如表1所示，數據集KDS1的維數為2，類別數為3。采用改進熵加權聚類算法對上述兩個數據集進行聚類，得到聚類結果如圖1所示。可以看出，提出的改進熵加權聚類算法能夠得到正確的聚類數量，驗證了其可行性。

3.2 ?書籍分類效果分析

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

[F1=2PRP+R] （20）

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

分別利用傳統K?均值聚類[13]、傳統熵加權聚類[14]和改進的熵加權聚類對圖書館數據集進行分類實驗，并在[F1?measure]指標方面進行比較分析。為了合理有效性，在數據集上對每種算法重復運行10 次取平均值。3種算法的分類結果對比如表2所示。可以看出，改進的熵加權算法在[F1?measure]指標的性能統計明顯優于傳統K?均值聚類和傳統熵加權聚類，表現出更佳的準確度。同時迭代次數也有所降低，穩定性較好。

4 ?結 ?語

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

參考文獻

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

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

[6] 馬亞玲.云環境下多載體圖書信息自動分類方法仿真[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] 高翠芳，黃珊維，沈莞薔，等.基于信息熵加權的協同聚類改進算法[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—），女，河南鄭州人，圖書館館員，研究方向為圖書館學。