利用分类算法实现图书分类管理

发布时间：2022-10-04 09:29 热度：

利用分类算法实现图书分类管理

张超

一．背景知识介绍

随着计算机技术的快速发展，计算机在企业管理中的应用普及，利用计算机实现图书信息分类管理势在必行。目前部分小型图书馆的借阅工作大部分还是手工管理，工作效率偏低，而且不能及时了解图书的种类以及用户们极力需求的图书类型等，不能更好的适应大多数用户的借阅要求。

计算机信息化管理有着储存量大，查询速度快等许多优点，提供及时快捷的信息处理。因此，利用计算机提供给我们的信息对学生们的借阅过程形成一整套动态的分类管理系统能够极大地提高图书管理的效率。将图书分文别类地管理，不仅能够提高管理员的工作效率，而且用户可以快速地查询到自己需要的类型的图书，也提高了查询的效率。

二．分类算法介绍

涉及到图书信息的分类，当然要对分类算法做进一步的介绍。分类算法被用来预测数据对象的离散类别，其应用非常普遍，对于图书馆管理系统，要涉及到对图书种类的分类，出版日期的分类以及不同作者的分类查询等等。

分类算法经常表现为树的表示和遍历问题。那么，就涉及到以下6个问题：

•如果用数据库中的一个表来表达树型分类，应该有几个字段；

•如何快速地从这个表恢复出一棵树；

•如何判断某个分类是否是另一个分类的子类；

•如何查找某个分类的所有产品；

•如何生成分类所在的路径；

•如何新增分类。

下面我们重点以决策树算法为例来介绍图书分类管理的基本核心思想。

三．决策树分类算法核心思想介绍

决策树表示方法是应用最广泛的逻辑方法之一，具有分类的精度较高，成的模式相对简单，对噪声数据有相对较强的健壮性等优点，因而是目前应用比较广泛的归纳推理算法之一，受到数据挖掘研究者的广泛关注。

决策树归纳是经典的分类算法。它采用自顶向下递归，各个击破的方式构造决策树。树的每一个结点使用信息增益度量来选择测试逻辑判断（即属性）。可以从生成的决策树中提取规则。

决策树构造的输入是一组带有类别标记的例子，构造的结果一般是一棵二叉树或多叉树。二叉树的内部节点，即非叶子节点一般表示成为一个逻辑判断，树的边是逻辑判断的分支结果。多叉树的内部节点是属性，边是该属性的所有取值，树的叶子节点一般都定义为类别标记。构造决策树的方法是采用自顶向下的递归方法，其思路是：

•以代表训练样本的单个结点开始建树。

•如果样本都在同一个类，则该结点成为树叶，并用该类标记。

•否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最好地将样本分类的逻辑判断。该逻辑判断称为该结点的“测试”或“判定”属性。值得注意的是，在这类算法中，所有的逻辑判断都是取离散值的，连续值逻辑判断必须离散化。

•对测试属性的每个已知的值，创建一个分支，并据此划分样本。

•算法使用同样的过程，递归地形成每个划分上的样本决策树。一旦一个属性出现在一个结点上，就不必考虑该结点的任何后代。

•递归划分步骤，当下列条件之一成立时停止：

给定结点的所有样本属于同一类。

没有剩余属性可以用来进一步划分样本。

构造好的决策树关键就在于如何选择最优的逻辑判断，对于同样一组例子，犹豫选择的逻辑判断不同，可以生成很多不同的决策树。下面利用ID3算法举例说明如何构建一棵决策树来实现对图书的分类管理。

对于ID3算法，首先要考虑如何选取合适的逻辑判断来产生分支，这就需要介绍信息论的一系列概念：

假设属于第i类的训练实例Ci，X中总的训练实例个数为|X|，若一个实例属于第i类的概率为p(Ci)，则：

p(Ci)=|Ci|/|X|

•信息熵H(X)：用来度量整个信息源X整体的不确定性。

H(X)=-∑p(ai)log(p(ai)) (i=1,2,..n)

•条件熵H(X|Y)：如果信息源X受随机变量Y的约束，用条件熵H(X|Y)来表示在收到随机变量Y之后，对随机变量X的不确定性。

H(X|Y)=-∑∑p(ai|bj)log(p(ai|bj)) (i=1,2,..n, j=1,2,…m)

•平均互信息量I(X|Y)：用它来表示信号Y所能提供的关于X的信息量的大小，其中I(X|Y)=H(X)-H(X|Y)。

建立决策树的过程就是将不确定度逐渐减小的过程，利用I(X|Y)表示的信息增益量选择信息增益最大的属性进行优先分类，下面举例来说明如何利用决策树分类算法实现图书分类。

表1给出了一个简单的图书样本数据集，假设图书的属性有四个：种类，出版日期，出版社，作者。样本数据集合被分为类别1和类别2，通过ID3算法构造决策树将数据进行分类。

通过对每个属性的信息熵和条件熵的计算，得到H(X|种类) <H(X|出版日期)< H(X|出版社) <H(X|作者)，所以I(X|种类) >I(X|出版日期)> I(X|出版社) >I(X|作者)。可见应该选择“种类”属性作为优先测试属性。重复此类操作，在决策树每一层选择优先测试属性，生成的决策树如图1所示。