基于IID3的电子商务信息挖掘研究，本文主要内容关键词为：商务信息论文,电子论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
中图分类号：O236文献标识码：A
在电子商务过程中，通常会产生大量的数据，数据挖掘就成为对这些数据进行分析的有效方法。电子商务中产生的数据有其自身的特点，把数据挖掘技术与电子商务进行有机的结合，再选用适合电子商务数据的挖掘方法，可以提高数据挖掘的效率，让数据挖掘更好地为电子商务服务。
在电子商务中进行数据挖掘具有一些有利的条件。首先，数据收集的可控制性大大提高。在电子商务环境下，可以设计一个系统专门收集数据，一般地，用计算机自动记录的数据比手工收集的数据出现的噪声和残缺要少。电子商务可以产生丰富的数据，可以是客户的购买行为，也可以是一些统计数据。其次，原来难以收集或不可能收集的数据，在电子商务环境下变得可能或容易收集。例如，一个网上购物电子商务系统可以记录下客户的行为，包括客户看了哪些商品，将哪些商品放入购物篮，哪些商品被放入购物篮但没有被最终购买等。还可以采取抽奖或赠送小礼品等方式来进行网上调查，收集客户数据。再次，因为电子商务已经自动化，因此在电子商务系统上构建的数据挖掘系统较为容易，而网络数据挖掘系统也容易和电子商务系统相结合。因此，有针对性地设计电子商务系统和网络数据挖掘系统，将两者有机结合，能更好地为组织或企业服务。
一、分类及其相关的研究
分类是进行数据挖掘的最实用技术之一，它包含预测给定样本的分类值。数据分类有两个连续的步骤，首先通过对预先知道分类值的一个样本集的学习构造一个分类模型，然后利用构造的分类模型来对新样本进行分类，如预测分类值等。分类问题在计算机科学和工程应用等诸多领域中都起着重要的作用，如图像处理以及数据挖掘等。许多计算手段，如神经网络[1]，演化算法[2]，模糊计算[3]以及决策树[4]等在分类问题中都有较多的应用。在这些手段中，决策树近年来受到了较多的关注，并且成为一个较为流行的分类问题。
决策树的经典算法是ID3，C4.5是ID3的后继版本。构造决策树的流行算法是利用剪枝方法处理“过分适应”的数据问题。通常，这种方法是使用统计量的办法剪去最不可靠的分支，这将导致较快的分类，提高决策树独立于测试数据分类的能力[5]。树剪枝用一个叶结点来代替一个完整的子树。与“事后”采用树剪枝不同，我们关注的是“事先”使用用于数据预处理的构造决策树方案。事实上，在电子商务的数据库中，某些样本往往是非常相似的。这是因为会有一些顾客购买的商品是非常类似的。还有，一个样本的某些属性也往往会具有较强的相关性。例如，购买个人计算机的用户通常也会购买一些电脑耗材。这样，在庞大的电子商务数据库中，数据之间显然是存在着较强的联系的。基于这一观点，我们设计了基于改进决策树算法(improved ID3,IID3)的电子商务信息挖掘系统。IID3算法有两个部分：第一部分是数据的维数约减。维数约减包含属性选择和样本减少，属性选择是在一些相关性较高的属性中选择部分属性，同时剔除掉其余的属性；样本减少就是将相似度高于某一阈值的两个相邻样本归为同一类，同时剔除掉这两个样本中的任何一个。第二个部分就是构造分类决策树。
下面，我们首先详细地介绍改进的决策树算法IID3中的维数约减方法，然后提出了基于维数约减的IID3算法，最后，在给出案例分析的基础上指出今后研究工作的方向。
二、改进的决策树算法IID3
（一）数据压缩
这一部分，我们关注下列问题：其一是选出最为相关的属性，即属性选择；其二是利用相似度判断准则剔除掉部分样本，即样本减少。
(1)属性选择
有许多的原因可以说明减少属性的数量至足够的少是必要的。计算的复杂性是明显的原因之一。尽管两个属性分别用于分类处理具有较好的分类信息，并且当他们组合在一个属性向量里时，会因其高相关性而使得它们的分类信息会减少则是原因之二。
显然，
。现在，相关属性的选择由下面的方案进行。即由
的值表示第i和第j个属性的相关性。我们比较属性间的相似性，如果某两个属性的相似性高于一个给定的阈值，我们就选择其中任何一个属性，然后去掉另外一个。这样就将样本的属性个数进行了约减。
(2)样本减少
设想要对一个数据对象的集合进行分析，在分类之前，聚类(clustering)就是将数据对象分成多个类或簇(cluster)，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别就较大。相似度是根据描述对象的属性值来计算的。距离是经常采用的度量方式。最为常用的距离度量方法是欧几里得距离，它的定义如下：
如果两个连续样本的相似度超过某一给定的阈值，我们就将这两个样本归为同一类，并同时剔除掉这两个样本中的任何一个。
（二）决策树
决策树是利用已知分类值的样本来构造特别的分类器，这些分类器可用于对各应用领域数据库中的新样本进行分类。树的每一个内部节点关联一个描述数据库小观测样本的属性，而且连接两个前后继节点的有向线段上用该节点的属性“测试”或“判定”值进行标识。每个叶节点都与我们希望预测的属性及其值（属性的分类值）相联系。基于决策树的学习算法通常采用的是划分——征服策略[7]，例如，它们通常利用递归的办法根据某一裂变准则将数据集划分为一些子集。这种裂变准则在构造决策树的过程中是非常重要的，因为裂变准则决定决策树的下一个元素是那一节点（或树叶）。大家熟悉的裂变技术是信息增益和信息增益率[8,9]。我们的处理方式是采用信息增益。使用信息增益来分割训练数据集可以尽可能的简化对给定样本的分类。
设S是s个数据样本的集合。假定类标号属性具有m个不同类
。设
是
类中样本。对一个给定的样本分类所需的期望信息由下式给出：
(4)if S中的某两个样本的相似度超过某一阈值户。则剔除掉这两个样本中任何一个样本，在决策树构造完毕后，将该剔除掉的样本归为那个保留下来的样本所属的节点；
(5)选择attribute_list中具有最大Gain(D)值的属性test_attribute；标记节点N为test_attribute；
(6)for each test_attribute中的已知值a
由节点N长出一个条件为test_attribute=a的分枝；
(7)设si是samples中test_attribute=a的样本的集合；
(8)if si为空then
加上一个树叶，标记为samples中最普通的类；
else
加上一个由IID3(si,attribute-list-test_attribute)返回的节点。
三、案例分析
假定我们有一个AllElectronics的邮寄清单数据库。邮寄清单用于分发介绍新产品和降价信息材料。数据库描述顾客的属性，如他们的姓名、性别、工作单位、通讯地址、年龄、收入、职业和信誉度。顾客就可以按他们是否在AllElectronics购买计算机进行分类。假定新的顾客添加到数据库中，你想将新计算机的销售信息通知顾客，而将促销材料分发给数据库中的每个新顾客的费用又可能很高。一个更有效的方法是只给那些可能买新计算机的顾客寄材料。为解决这些问题，就可以构造和使用决策树分类模型。
表1给出的是取自AllElectronics，并且经过数据压缩的顾客数据库数据元组训练集数据。即通过属性选择，删除了属性“性别、工作单位以及通讯地址”；通过样本减少，将属性的取值完全相同的两个属性向量归纳为同一类，然后去掉其中之一，保留一个属性向量用于构造决策树。从附录1的数据训练集可以知道，类标号属性buy_computer有两个不同值（即yes,no），因此有两个不同的类(m=2)。设类
对应yes，而类
对应no。那么类yes有9个样本，类no有5个样本。为计算每个属性的信息增益，我们首先使用(5)式，计算对给定样本分类所需的期望信息：
表1 AllElectronics顾客数据库训练数据元组
类似地，我们可以计算
Crain(income)=0.029，Gain(student)=0.151和Gain(credit__rating)=0.048。由于age在属性中具有最高信息增益，它被选作测试属性。创建一个节点，用age标记，并对于每一个属性，引出一个分枝。样本据此划分，如图1所示。注意，落在分区age=“31,…,40”的样本都属于同一类。由于它们都属于同一类，因此要在该分枝的端点创建一个树叶，并用yes标记。算法返回的最终判断树如图1所示。
从图1给出的顾客是否可能购买计算机的判断树，我们抽出的分类规则是：
IF age= "＜ = 30" AND student = "no"
THEN buy_ computer = "no"
IF age= "＜ = 30" AND student= "yes"
THEN buy_computer = "yes"
IF age= "31,…,40"
THEN buy_ computer= "yes"
IF age= "＞40" AND credit_rating= "excellent"
THEN buy_ computer="no"
IF age= "＞40" AND credit-rating="fair"
THEN buy_computer="yes"
图1 概念buy_computer的判断树
四、结论
我们知道，即使训练集的大小与准确性之间不存在着任何的联系，决策树的大小与训练集的大小之间通常还是存在着强烈关系的。此外，就内容丰富、蕴藏信息量大的顾客数据库数据元组训练集数据而言，以剔除训练集中的任意样本为手段来减少决策树的大小这一方案，对决策树分类的准确性没有或很少有影响[10]。这暗示我们，任何的数据压缩技术都将因为减少训练集的大小而得到决策树大小的减小。很明显，在电子商务的数据库中进行数据挖掘，我们希望知道通过数据压缩的方法能够使得决策树大小的减少程度是多少，对训练集中的样本采用什么样的剔除方法，以及决策树大小的减少在多大程度上取决于训练样本的减少等。算法IID3回答了所有的这些问题。与在构造决策树的过程中仅仅使用随机选择样本的方法不同，IID3是基干数据压缩技术的决策树算法，它适用于内容丰富，蕴藏信息量大的数据库。因此，该方案特别适用于在电子商务的数据库进行数据挖掘。IID3算法的数据压缩技术的先进性有两点：其一是对数据库中的数据进行了科学的属性选择。如我们分析的案例保留了属性“姓名”，剔除了属性“性别、工作单位、通讯地址”等。因为IID3的属性选择方法是基于属性间相关性的比较而做出的属性选择，因此，该属性选择方案是合理的。并且，由于样本属性的减少，我们所构造的决策树的深度也会相应地减小。其二是科学的样本压缩方法。在IID3中，如果相邻的两个样本的相似度高于某一给定的阈值，则将该两样本归为同一类，在构造决策树时仅选用这两个样本中的任何一个参与构造。这样既使得计算决策树每一个节点的计算量大大减少，同时，那个没参与决策树构造的样本的类标号也可以相应地被确定。今后，我们将进一步地改进IID3算法，使其适用于电子商务中的各种不同类型的数据库。