应用于图书馆书籍分类的熵加权聚类算法

来源:用户上传      作者:

　　摘  要： 目前很多图书馆都更加信息化和数字化，馆藏书籍数量也因此不断提高。如何通过聚类算法做出海量图书类目的精确分类，以便用户更加方便快捷地筛选，成为亟需解决的问题。提出的熵加权聚类改进算法是以传统熵加权聚类算法为基础所设计的新的聚类中心矩阵计算方法。通过选取具有代表性的样本点作为初始聚类中心，降低数据维度和冗余。此外，通过合并策略对信息熵加权隶属表示进行修改，从而避免聚类过程中的局部最优。实验结果表明，提出的聚类方法在处理书籍大数据分类任务时具有较高的精度和稳定度。
　　关键词： 图书分类; 大数据; 熵加权; 聚类方法; 数据维度降低; 矩阵计算
　　中图分类号： 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—），女，河南郑州人，图书馆馆员，研究方向为图书馆学。
转载注明来源:https://www.xzbu.com/8/view-15122176.htm