第一篇:数据挖掘与知识发现(讲稿7-神经网络挖掘)
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
第7章
基于神经网络的数据挖掘技术
人工神经网络ANN(Artificial Neural Network)是反映人脑结构及功能的一种数学模型,它是由大量的简单处理单元经广泛并行互连形成的一种网络系统。用以模拟人类进行知识的表示与存储以及利用知识进行推理的行为。它是对人脑系统的简化、抽象和模拟,具有人脑功能的许多特征。
目前,人工神经网络已在模式分类、机器视觉、机器听觉、智能计算、机器人控制、信号处理、组合优化问题求解、联想记忆、编码理论、医学诊断、金融决策、数据挖掘等领域得到广泛应用。
7.1 基于知识的神经网络(KBANN)
神经网络用于数据挖掘的困难之一是,对经过训练的神经网络的输出结果很难给出直观的解释。许多学者试图将专家系统和神经网络相结合,设计出兼有专家系统和神经网络优点的混合系统。其中,基于知识的神经网络就是其中最有代表性的一种系统。
基于知识的神经网络包含如下四个阶段:
① 规则库表示阶段:提取原始的领域知识并将其组织成规则库;(属人工智能内容)
② 映射阶段:将上述规则库中的每条规则映射成一个小的子网络,全体子网络就构成了一个原始网络结构;
③ 学习阶段:用训练样本对上述网络进行训练;(应用人工神经网络学习算法)④ 规则提取阶段:将上述训练好的神经网络再映射成规则库。
其典型结构图为:
图1 基于知识的神经网络的信息流程
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
1)原始规则库转化为神经网络结构
(1)合取规则
在与肯定条件相对应的网络连接权设置为,在与否定条件相对应的网络连接权设置为,在与结论相对应的神经元的阈值设置为(2P1)/2,其中P是肯定条件的个数。经验表明,在KBANN中,通常设置为4能取得较好的效果。如,规则
A:B,C,D,not(E)
图2 合取规则转化为神经网络示间图
(2)析取规则
KBANN对与每个析取条件相对应的连接权设置为,对与结论相对应的神经元阈值设置为/2。如,规则
图3 析取规则转化为神经网络示意图
2)知识库转化为神经网络示例
设(a)为规则库;(b)为规则的层次结构,其中,实线代表必要关系,虚线表示抑制关系;(c)为由规则库转化而来的神经网络,其中,为了处理析取规则而引入X和Y结点,实线连接代表权重均设置为,它代表规则库中的依赖关系;细线代表有待进一步学习的连接权,它反映知识的精化。
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
7.2 基于KBANN的规则提取方法
基于KBANN在数据挖掘中的作用集中体现在规则提取阶段,这一问题在神经网络研究领域十分活跃。这里,主要给出一些从前馈网络(如,多层感知器MLP)中提取规则的方法。几乎所有的规则提取方法都假设经过训练的神经网络的神经元,要么处于活跃状态,要么处于不活跃状态。
1.有代表性的规则提取方法
(1)LRE方法
用LRE方法对MLP进行规则提取主要两步:
每一步,对网络中的每个隐层结点和输出结点搜索不同的输入组合,使得输入加权和大于当前结点的阈值;
对每一个组合产生一条规则,其前件是各个输入条件的合取。如,Either、KT和Subset算法就是LRE方法中有代表性的三种方法。它们的特点:生成的规则均较容易理解,但这三种方法有如下缺点:① 搜索空间大,故搜索效率低;② 前后生成的规则有可能发生重复;③ 不能保证所有有用的规则均被产生出来。
针对Subset算法的缺点,Towell等提出了MofN方法,该算法的基本思想是将所有权值分成若干个等价类,在每个等价类中成员的作用基本相似,因而可以相互互换。MofN方法通过六个步骤,从训练好的神经网络中提取规则,它们分别是:
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
① 分类---即将连接权分成若干等价类; ②平均---即将每个等价类中的权值平均化; ③ 去除---即去除对神经元的作用较小的等价类;
④ 优化---即在去除了部分连接权后,对神经元的阈值进行优化; ⑤ 提取---即从经优化的神经网络中提取规则; ⑥ 简化---即将上述规则简化,使其更易于理解。
(2)黑箱方法
黑箱方法仅考虑从前馈神经网络的输入和输出的行为来提取规则。所以称之为黑箱是因为在提取规则时不考虑神经网络的类型和结构,主要关心输入和输出间的映射关系。
(3)提取模糊规则
在模糊神经网络和神经网络模糊系统的研究中,有些模糊神经网络和神经网络模糊系统中包含模糊规则的提取和精化方法。
(4)从递归网络中提取规则
该方法将递归网络的状态和有限自动机的状态相对应,可提高神经网络的泛化能力。
2.一些新规则的提取方法
本节主要介绍Taha和Ghosh的最新研究工作,其中包含三种规则提取方法:
(1)二值输入输出规则提取算法(BIO-RE)
该方法属于一种简单的黑箱方法,它对二值输入的神经网络进行规则提取,若原始输入不是二值的,则必须先将其二值化:
yi1ifxii
0otherwise其中,xi为原始输入;i为阈值;yi是与xi相对应的二值化输入。
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
图4 感知器模型
它的算法为:
输入:经训练好的神经网络
输出:规则(库)
步骤:
① 给出对应于各二值输入模式的神经网络输出O(Y){oj(Y)|oj{0,1}};
② 将二值输入和输出相对应,构成一个真值表;
③ 由上式真值表生成相应的布尔函数,即所需的规则(库)。
BIO-RE算法所提取的规则有如下一般形式:
IF [Not]输入变量 [[And] [Not]输入变量]* → 结论j 其中,[·]---表示任选项;[·]*---表示可重复0次或n次。
若最终提取的规则为
IfY1AndNoYt2ThenO1 则必须将其改写为
IfX11AndX22ThenO1
由此可见,一个“真”二值输入变量(如,Y1)表示“X11”;一个否定的二值输入变量(如,NotY2)表示“X22”
此法当输入输出本来就是二值的,或经二值化后不会显著影响其性能且输入变量不太大时,用BIO-RE算法是合适的,否则此方法就不太适用。
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
(2)部分规则提取算法(Partial-RE)
针对BIO-RE算法的不足,Partial-RE算法仅关心主要的连接权的组合,对每个隐层结点或输出层结点j,将输入结点j的正负连接权按降序排列,形成两个集合。然后从最大的正连接权开始,比如从第i个结点进入的连接权最大,该算法判断在不考虑其他结点输入的情况下,能否使结点j激活。若存在这样的结点j,则生成一条规则
cf
IfNodeiNodej
其中,cf表示该条规则的置信度:
1,若响应函数为Sigmoid型n_1exp(wjixij)i1n_
cfmin(1,wjixij),若响应函数为线性阈值函数
i11,若响应函数为阶跃函数这里,wji为输入xi与结点j间的连接权;j为结点j的阈值;称为置信参数,是一个小正数(0.10.3)。
若发现结点i足够强使得结点j被激活,则结点i即被标记,今后当考察结点j时,结点i将不被考虑。Partial-RE算法继续检查剩余的正连接权,直到发现一个带正连接权的结点不能单独激活结点j时为止。
必须注意:Partial-RE算法假定所有的输入均有相同的取值范围,这样它们对隐层结点的影响仅由权值决定。因此,必须对原始输入变量先进行量化:
zi_1.0xu1.0exp((i2i))2i
其中,zi是原始输入变量xi经量化后的值;i为输入X的标准均方差,ui是X的均值。
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
此外,该算法还寻找负权结点,在激活时,则产生如下规则:
IfcfNotNodegNodej
不仅如此,该算法还寻找正权和负权的组合,并激活隐层或输出层结点,则产生如下规则:
cf
IfNodeiAndNotNodegNodej
当所有的规则都生成后,将它们改写成如下形式:
IfXiicfAndXggConsequentj
实验结果表明,Partial-RE算法比较适合于规模较大的问题,因为此时提取所有规则是一个NP-完全问题,而提取一部分最重要的规则是切实可行的办法。
(3)全部规则提取算法(Full-RE)
Full-RE算法与Partial-RE算法相比,它可以从连续输入、归一化输入及二值化输入等各种神经网络中提取规则,具有较好的普适性。
对每个隐层结点j,Full-RE算法首先生成以下中间规则:
cf
If(wjiXij)Consequentj
_由于存在一组Xi满足中间规则,这样就必须知道Xi的取值范围。每个输入特征Xi(ai,bi)可以用k个小区间来离散化为
Di{di,0ai,di,1,,di,k1,di,kbi}
当Full-RE算法发现离散化存在多组解时,它将根据连接权的符号选择Xi的最大或最小离散化值。若wji是负的,则Full-RE算法选择Xi的最大离散化值,否则选择Xi的最小离散化值。离散化后形成下列线性规化问题:
Minimizewj1D1wj2D2wjnDn 使得
____
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
___
wj1D1wj2D2wjnDnj 且Di{di,0ai,di,1,,di,k1,di,kbi},1in。
可以用任何一种求解线性规划问题的工具来求解该线性规划问题,从而得到X的取值范围。假设一个可行解为x1e1和x2e2,从输入X1和X2到结点j的连接权分别是正数和负数,则Full-RE算法如下规则:
IfX1e1cfAndX2e2hj
其中,aieibi。隐层和输出层间提取的规则可以表示为
cf
Ifh1Andh2Ok
Full-RE算法将中间规则和隐层与输出层间提取的规则复合形成新的规则,复合的方法是对每个隐层结点hj,将hj替换为中间规则中后件为hj的前件,最终形成的规则的一般形式为
cf
If简单布尔表达式[And简单布尔表达式]*结论j
值得注意的是,由于由Full-RE算法提取的规则中对前提条件的个数不作限制,而仅对相邻层间规则中的前提条件个数作限制。所以,当输入特征是二值时,就不需要二值化过程。7.3 基于ANN的数据挖掘示例
《吴一帆,基于模糊神经网络的数据挖掘算法.caj,长沙电力学院学
报,2002(4)》
第二篇:数据挖掘与知识发现(讲稿9--遗传算法)
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
第九章
基于遗传算法的数据挖掘
面向属性的数据挖掘方法是基于逻辑的,神经网络挖掘方法是基于方程的,而本章要介绍的遗传算法,则是一种基于十字表的数据挖掘方法。它也是一种典型的知识发现方法。
遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的Holland教授提出,起源于60年代对自然和人工自适应系统的研究。70年代De Jong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。在此基础上,由Goldberg在80年代对其进行了归纳总结,形成了遗传算法的基本框架。9.1 遗传算法概要
对于一个求函数最大值的优化问题(最小值类同),一般可描述为如下的数学规划模型:
maxf(X)
s.t.XR
(9-1)
RU式中,X[x1,x2,,xn]T为决策变量;f(X)为目标函数(线性或非线性;离散或连续;单峰或多峰);U为基本空间;R为U上的一个子集。满足约束条件的解X称为可行解,集合R表示由所有满足约束条件的解组成的一个集合,叫做可行解集合。
图1 最优优问题的可行解及可行解集合
传统的求最优解或近似最优解的方法主要有:枚举法、分枝定界法、1
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
启发式算法和搜索算法。随着问题种类的不同,以及问题规模的扩大,要寻找到一种能以有限的代价来解决上述最优化问题的通用方法仍是一个难题。而遗传算法正好能为此类问题提供一个有效途径和通用框架,开创了一种新的全局优化搜索算法。
遗传算法是模拟生物进化过程的计算模型,它是自然遗传学和计算机科学相互结合渗透而形成的新的计算方法。
生物的进化过程主要是通过染色体之间的交叉和变异来完成的。在遗传算法中,将n维决策向量X用n个记号Xi,i1,2,,n所组成的符号串来表示X:
XX1X2XnX[X1,X2,,Xn]T
把每一个Xi,i1,2,,n看作一个遗传基因,它的所有可能取值称为等位基因。这样,X就可看作是由n个遗传基因所组成的一个染色体(或个体)。对于每个个体,要按照一定的规则确定出其适应度。个体的适应度与其对应的个体表现型X的目标函数值相关联,X越接近于目标函数的最优点,其适应度越大;反之适应度越小。所有染色体X就组成了问题的搜索空间。
生物的进化是以集团为主体的。与此对应,遗传算法的运算对象是由M个个体所组成的集合,称为群体。与生物一代一代的自然进化过程类似,遗传算法的运算过程也是一个反复迭代过程,第t代群体记为P(t),经过一代遗传和进化后,得到第t1代群体,也是由多个个体组成的集合,记为P(t1)。这个群体不断地经过遗传和进化操作,并且每次都按优胜劣汰的规则将适应度较高的个体更多的遗传到下一代,这样最终在群体中将会得到一个优良的个体X,它达到或接近于问题的最优解X*。
遗传算法中最优解的搜索过程也模仿生物的这种进化过程。使用所谓的遗传算子作用于群体P(t)中,进行下述的遗传操作,从而得到新一 2
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
代群体P(t1)。主要操作有:
选择:根据各个个体的适应度,按照一定的规则或方法,从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t1)中; 交叉:将群体P(t)内的各个个体随机搭配成对,对每一对个体,以某个概率(称为交叉概率)交换它们之间的部分染色体; 变异:对群体P(t)中的每一个个体,以某一概率(称为变异概率)改变某一个或某一些基因座上的基因值为其他的等位基因。遗传算法的运算步骤为:
(1)初始化:设置进化代数计数器t0;设置最大进化代数T;随机生成M个个体作为初始群体P(0);
(2)个体评价:计算群体P(t)中各个个体的适应度;(3)选择运算:将选择算子作用于群体;(4)交叉运算:将交叉算子作用于群体;
(5)变异运算:将变异算子作用于群体。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t1);
(6)终止条件判断:若tT,则tt1,转到步骤二;若tT,则以进化过程中所得到的具有最大适应度的个体作为最优解输出,终止计算。
遗传算法的执行过程如下图所示:
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
图1 遗传算法的执行过程
9.2 遗传算法的特点
与传统的优化算法:单纯形法、梯度法、动态规划法和分枝定界法相比,遗传算法是一类可用于复杂系统优化计算的鲁棒性搜索算法。其特点主要有:
遗传算法以决策变量的编码作为运算对象。而传统的优化算法往往是直接利用决策变量的实际值本身来进行优化计算; 遗传算法直接以目标函数值作为搜索信息。而传统的优化算法不仅需要利用目标函数值,而且往往需要目标函数的导数值等其他一些辅助信息才能确定搜索方向;
遗传算法同时使用多个搜索点的搜索信息。而传统的优化算法往往从解空间中的一个初始点开始最优解的迭代搜索过程; 遗传算法使用概率搜索技术。而传统的优化算法往往使用的是确定性的搜索方法,一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系,这种确定性往往也有可能使得搜索永远达不到最优点,因而限制了算法的应用范围。
9.3 遗传算法的应用
遗传算法提供了一种求解复杂系统优化问题的通用框架,它不依赖于问题的具体领域,对问题的种类有很强的鲁棒性,所以广泛应用于很
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
多学科。
(1)优化函数(2)组合优化(3)生产调度问题(4)自动控制(5)机器人学(6)图像处理(7)人工生命(8)遗传编码(9)机器学习
9.4 遗传算法的构成要素及形式定义
构成遗传算法的要素主要有:染色体编码方法、个体适应度评价、遗传算子、基本遗传算法的运行参数。
(1)染色体编码方法
在实现对一个问题用遗传算法进行求解之前,必须先对问题的解空间进行编码,以便于它能够由遗传算法进行操作。最常用的编码方法是二进制编码、浮点数编码、格雷码编码、符号编码等。
如,二进制编码方法是遗传算法中最常用的一种编码方法,它使用的编码符号集是由二进制符号集0和1所组成的二值符号集{0,1},它所构成的个体基因型是一个二进制编码符号串。
二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取值范围是[Umin,Umax],若用长度为l的二进制编码符号串来表示该参数,则它总共能够产生2l种不同的编码,即为:
00000000...00000000=0 ——> Umin 00000000...00000001=1 ——> Umin1
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
.....11111111...11111111=2*2*2…2-1——>Umax 则二进制编码的编码精度为:
sUmaxUmin l21假如,对于x∈[0,1023],若用10位长的二进制编码来表示该参数的话,则下述符号串:
X:
0 0 1 0 1 0 1 1 1 1
就可表示一个个体,它所对应的参数值为x=175。此时的编码精度s=1。
(2)适应度函数
在遗传算法中,模拟自然选择的过程主要通过评估函数和适应度函数来实现的。前者是用来评估一个染色体的优劣的绝对值,后者是用来评估一个染色体相对于整个群体的优劣的相对值的大小。
但在遗传算法中,评估函数和适应度函数的计算与应用比较相近,所以一般文献中常混为一谈。
(3)遗传算子
基本遗传算法使用下列三种遗传算子:
选择算子:按照某种策略从父代中挑选个体进入中间群体,如使用比例选择;
交叉算子:随机地从中间群体中抽取两个个体,并按照某种交叉策略使两个个体互相交换部分染色体码串,从而形成两个新的个体。如使用单点交叉;
变异算子:通常按照一定的概率(一般较小),改变染色体中某些基因的值。
(4)基本遗传算法的运行参数
基本遗传算法有下述4个运行参数需要提前设定:(目前无合理的理论依据)
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
M:群体大小:即群体中所含个体的数量,一般取20-100; T:遗传算法的终止进化代数,一般取为100-500; pc:交叉概率:一般取为0.4-0.99; pm:变异概率:一般取为0.0001-0.1。基本遗传算法的形式定义为:
SGA(C,E,P0,M,,,,T)
其中,C---个体的编码方法;
E---个体适应度评价函数;
P0---初始群体;
M---群体大小;
---选择算子;
---交叉算子;
---变异算子;
T---遗优越性运算终止条件。9.5 遗传算法的数学理论
1.模式
定义:模式表示一些相似的模块,它描述了在某些位置上具有相似结构特征的个体编码串的一个子集。
不失一般性,以二进制编码为例,个体是由二值字符集V={0,1}中的元素所组成的一个编码串,而模式却是由三值字符集V{0,1,*}中的元素所组成的一个编码串,其中“*”表示通配符,它既可被当作“1”,也可被当作“0”。如,H=1***001*就是一个模式,串A=10100011与B=10110010都是与模式H相匹配的字符串,称为两者相似。
定义:模式H的第一个和最后一个常量之间的距离称为模式的定义长度,记为(H)。
定义:模式中常量的个数称为模式的阶数,记为O(H)。
如上例中,(H)6,O(H)4。再如(*****1**)1,O(*******1)1 显然,当字符串的长度固定时,模式的阶数越高,能与该模式匹配的字符串(称为样本)数就越少,因而该模式的确定性也就越高。
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
2.模式定理
在引入模式的概念之后,遗传算法的实质可看作是对模式的一种运算。对基本遗传算法而言,也就是某一模式H的各个样本经过选择运算、交叉运算、变异运算之后,得到一些新的样本和新的模式。
假设在进化过程中的第t代时,当前群体P(t)中能与模式H匹配的个体数(样本数)记为m(H,t),下一代群体P(t1)中能与模式H匹配的个体数记为m(H,t1)。则在选择算子、交叉算子、变异算子的连续作用下,模式H的样本数m(H,t)的变化情况分析如下:(1)选择算子的作用
基本遗传算法中的选择算子使用的是比例选择算子。将当前群体中适应度的总和记为F(t)F(Ai),在这个算子作用下,与模式H所匹配
i的各个个体Ai能够平均复制Mm(H,t1)
F(Ai)个个体到下一代群体中,即 F(t)Mf(H,t)F(t)AiHP(t)MF(Ai)F(t)AiHP(t)Mf(H,t)f(H,t)m(H,t)m(H,t)_F(t)F(t)
(9-2)
F(t)式中,f(H,t)是第t代群体中模式H所隐含个体的平均适应度;
_F(t)M是第t代群体的平均适应度。
若再假设模式H的平均适应度总是高出群体平均适应度的倍,则(9-2)式可改写为
m(H,t1)m(H,t)(1C)
(9-3)由此可见,m(H,t1)为一等比级数。其通项公式为
m(H,t)m(H,0)(1C)t
(9-4)显然,有
若C>0,则m(H,t)呈指数级增长;
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
若C<0,则m(H,t)呈指数级减少。
由此可得如下结论:在选择算子作用下,对于平均适应度高于群体平均适应度的模式,其样本数将呈指数级增长;反之,呈指数级减少。(2)交叉算子的作用
以单点交叉算子为例,见图所示的一个模式。
隐含在该模式中的样本与其他个体进行交叉操作时,根据交叉点的位置不同,有可能破坏该模式,也可能不破坏该模式而使其继续生存到下一代群体中。下面估算该模式生存概率ps的下界。
显然,当随机设置的交叉点在模式的定义长度之内时,将有可能破坏该模式;而当随机设置的交叉点在模式定义长度之外时,肯定不会破坏该模式。则由交叉概率pc发生时,模式H的生存概率的下界为
ps1pc(H)l(9-5)
这样,经过选择算子和交叉算子作用之后,模式H的样本数满足下式:
m(H,t1)m(H,t)(1C)[1pc(H)l1]
(9-6)
由式(9-6)知,在其他值固定的情况下(C>0)
(H)越小,则m(H,t)越呈指数增长; (H)越大,则m(H,t)越不容易呈指数增长。(3)变异算子的作用
这里,以常用的基本位变异算子为例进行研究。
若某一模式被破坏,则必然是模式描述形式中通配符“*”之处的某一基因发生了变化,其发生概率是:
1(1pm)O(H)当pm1时,有:
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
1(1pm)O(H)O(H)pm
由此可知,在变异算子作用下,模式H的生存概率大约是:
ps1O(H)pm
(9-7)显然知
O(H)越小,模式H越易于生存; O(H)越大,模式H越易被破坏。
综合上面的各式,并忽略一些极小项,则比例选择算子、单点交叉算子、基本位变异算子的连续作用下,群体中模式H的子代样本数为:
m(H,t1)m(H,t)f(H,t)F(t)_[1pc(H)l1O(H)pm]
(9-8)
[模式定理] 遗传算法中,在选择、交叉和变异算子的作用下,具有低价、短的定义长度,并且平均适应度高于群体平均适应度的模式将按指数级增长。
模式定理阐述了遗传算法的理论基础,说明了模式的增长规律,同时也给遗传算法的应用提供指导作用。9.6 积木块假设与遗传算法欺骗问题
1.积木块假设
具有模式定理中所述的呈指数增长的模式称为积木块或基因块。之所以称为积木块,是由于遗传算法的求解过程并不是在搜索空间中逐一地测试各个基因的枚举组合,而是通过一些较好的模式,像搭积木一样,将它们拼接在一起,从而逐渐地构造出适应度越来越高的个体编码串。
模式定理说明了积木块的样本呈指数增长,亦即说明了用遗传算法寻找最优样本的可能性,但它并未指明遗传算法一定能够寻找到最优样本。
[积木块假设] 个体的基因块通过选择、交叉、变异等遗传算子作用,能够拼接在一起,形成适应度更高的个体编码。
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
注:积木块假设已得到完整而严密的数学证明,但大量的应用实践也已说明了其有效性。
2.遗传算法欺骗问题(GA Deceptive Problem)
应用实践表明,存在着一类用遗传算法难以求解的问题,这类称为“GA-难”的问题往往不满足积木块假设,即由基因块之间的拼接,往往会欺骗遗传算法,使其进化过程偏离最优解。
原因:各种研究结果表明,属于“GA-难”的问题一般包含有孤立的最优点,即在这个最优点周围是一些较差的点,从而使得遗传算法较难通过基因之间的相互拼接而达到这个最优点的模式。实际上,目前也尚无解决这类问题的较好方法或策略。所幸的是,现实所遇到的各种应用问题中,很少有这种奇怪的性质。9.7 基于遗传算法的数据挖掘示例
【示例】从200名脑出血和脑血栓病例中,按如下属性:“病人的既往史”、“起病方式”、“局部症状”、“病理反射”、“膝腱反射”和“病情发展”等六个方面,找出这两类病人的识别规则。其中
(1)病人的既往史
包括:高血压(有01,无00)、动脉硬化(有01,无00);(2)起病方式
快(01)、慢(00);(3)局部证状
偏瘫(是01,否00)
瞳孔不等大(是01,否00)
两便失禁(是01,否00)
语言障碍(是01,否00)
意识障碍(无00,深度01,轻度10)
(4)病理反射
阳(01),阴(00)
┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊
(5)膝腱反射
无(00),活跃(01),不活跃(10)
(6)病情发展
快(01),慢(00)
则可选30个病例作为训练样本,100个作为测试样本。
a)采用二进制编码方式。每个训练样本是由11个特征和1个类别组成,每个特征和类别都由2位二进制字符表示。那么,将样本编码成二进制字符串的消息就是一个由22位条件和2位结论组成的二元组。如,消息M=[***00101,01] b)假设训练集是由15个脑出血和15个脑血栓患者组成30个训练样本。本实验在对30个训练样本进行学习后,得到12条规则,学习终止于第170代。
(参见P201《数据仓库与数据挖掘》,陈文伟、黄金才编,人民邮电出版社,2004)
c)获取如下的7条主要规则:
(1)if 高血压=有∧瞳孔不等大=是∧膝腱反射=不活跃 then 脑出血(11)
(2)if 瞳孔不等大=是∧语言障碍=是 then 脑出血(12)
(3)if 高血压=有∧起病方式=快∧意识障碍=深度 then 脑出血(13)(4)if 高血压=有∧病情发展=快 then 脑出血(15)
(5)if 高血压=有∧动脉硬化=有∧起病方式= 慢 then 脑血栓(13)(6)if 动脉硬化=有∧病情发展=慢 then 脑血栓(15)(7)if 动脉硬化=有∧意识障碍=无 then 脑血栓(12)以上括号内的数值表示该规则的适应值。
第三篇:数据挖掘与电子商务
数据挖掘与电子商务
姓名:龚洪虎
学号:X2009230111
[摘 要] 企业的竞争优势并不取决于信息的拥有量,而是取决于信息的处理利用能力。如何化信息优势为竞争优势,是企业制胜于市场的一个法宝。本文论述了一种信息处理利用的有效工具——数据挖掘方法及其在电子商务中的应用。
[关键词] 数据挖掘 方法 电子商务 应用
随着网络技术和数据库技术的成熟,传统商务正经历一次重大变革,向电子商务全速挺进。这种商业电子化的趋势不仅为客户提供了便利的交易方式和广泛的选择,同时也为商家提供了更加深入了解客户需求信息和购物行为特征的可能性。数据挖掘技术作为电子商务的重要应用技术之一,将为正确的商业决策提供强有力的支持和可靠的保证,是电子商务不可缺少的重要工具。
一、电子商务和数据挖掘简介。
电子商务是指个人或企业通过Internet网络,采用数字化电子方式进行商务数据交换和开展商务业务活动。目前国内已有网上商情广告、电子票据交换、网上订购,网上银行、网上支付结算等多种类型的电子商务形式。电子商务正以其成本低廉、方便、快捷、安全、可靠、不受时间和空间的限制等突出优点而逐步在全球流行。
数据挖掘(DataMining)是伴随着数据仓库技术的发展而逐步完善起来的。数据挖掘主要是为了帮助商业用户处理大量存在的数据,发现其后隐含的规律性,同时将其模型化,来完成辅助决策的作用。它要求从大量的、不完全的、有噪声的、模糊的和随机的数据中,提取人们事先不知道的但又是潜在有用的信息和知识。数据挖掘的过程有时也叫知识发现的过程。
而电子商务中的数据挖掘即Web挖掘,是利用数据挖掘技术从www的资源(即Web文档)和行为(即We服务)中自动发现并提取感兴趣的、有用的模式和隐含的信息,它是一项综合技术涉及到Internet技术学、人工智能、计算机语言、信息学、统计学等多个领域。
二、何谓数据挖掘及方法
确切地说,数据挖掘(Data Mining),又称数据库中的知识发现(Knowledge Discovery in Database,KDD),是指从大型数据库或数据仓库中提取隐含的、未知的、非平凡的及有潜在应用价值的信息或模式。它融合了数据库、人工智能、机器学习、统计学等多个领域的理论和技术。比较典型的数据挖掘方法有关联分析、序列模式分析、分类分析、聚类分析等。它们可以应用到以客户为中心的企业决策分析和管理的各个不同领域和阶段。
1.关联分析。关联分析,即利用关联规则进行数据挖掘。关联分析的目的是挖掘隐藏在数据间的相互关系,它能发现数据库中形如”90%的顾客在一次购买活动中购买商品A的同时购买商品B”之类的知识。
2.序列模式分析。序列模式分析和关联分析相似,但侧重点在于分析数据间的前后序列关系。它能发现数据库中形如”在某一段时间内,顾客购买商品A,接着购买商品B,而后购买商品C,即序列A→B→C出现的频度较高”之类的知识,序列模式分析描述的问题是:在给定交易序列数据库中,每个序列是按照交易时间排列的一组交易集,挖掘序列函数作用在这个交易序列数据库上,返回该数据库中出现的高频序列。在进行序列模式分析时,同样也需要由用户输入最小置信度C和最小支持度S。
3.分类分析。设有一个数据库和一组具有不同特征的类别(标记),该数据库中的每一个②
记录都赋予一个类别的标记,这样的数据库称为示例数据库或训练集。分类分析就是通过分析示例数据库中的数据,为每个类别做出准确的描述或建立分析模型或挖掘出分类规则,然后用这个分类规则对其他数据库中的记录进行分类。
4.聚类分析。聚类分析输入的是一组未分类记录,并且这些记录应分成几类事先也不知道,通过分析数据库中的记录数据,根据一定的分类规则,合理地划分记录集合,确定每个记录所在类别。它所采用的分类规则是由聚类分析工具决定的。采用不同的聚类方法,对于相同的记录集合可能有不同的划分结果。
应用数据挖掘技术,较为理想的起点就是从一个数据仓库开始,数据挖掘可以直接跟踪数据并辅助用户快速做出商业决策,用户还可以在更新数据的时候不断发现更好的行为模式,并将其运用于未来的决策当中。
三、选择数据挖掘技术的两个重要依据。
数据挖掘使用的技术很多,其中主要包括统计方法、机器学习方法、和神经网络方法和数据库方法。统计方法可细分为回归分析、判别分析、聚类分析、探索性分析等。机器学习方法可细分为归纳学习方法(决策树、规则归纳)、基于范例学习、遗传算法等。神经网络方法可细分为钱箱神经网络(BP算法)、自组织神经网络等。数据库方法主要是多维数据分析或OLAP方法,另外还有面向属性的归纳方法。由于每一种数据挖掘技术都有其自身的特点和实现的步骤,对数据的形式有具体的要求,并且与具体的应用问题密切相关,因此成功的应用数据挖掘技术以达到目标过程本身就是一件很复杂的事情,本文主要从挖掘任务和可获得的数据两个角度来讨论对数据挖掘技术的选择。
三、数据挖掘在电子商务中的应用
数据挖掘能发现电子商务客户的的共性和个性的知识、必然和偶然的知识、独立和关联的知识、现实和预测的知识等,所有这些知识经过分析,能对客户的消费行为如心理、能力、动机、需求、潜能等做出统计和正确地分析,为管理者提供决策依据。具体应用如下:
1.分类与预测方法在电子商务中的应用。在电子商务活动中,分类是一项非常重要的任务,也是应用最多的技术。分类的目的是构造一个分类函数或分类模型,通常称作分类器。分类器的构造方法通常由统计方法、机器学习方法、神经网络方法等。这些方法能把数据库中的数据映射到给定类别中某一个,以便用于预测,也就是利用历史数据记录,自动推导出给定数据的推广描述,从而对未来数据进行预测。
2.聚类方法在电子商务中的应用。聚类是把一组个体按照相似性原则归成若干类别。对电子商务来说,客户聚类可以对市场细分理论提供有力的支持。市场细分的目的是使得属于同一类别的个体之间的距离尽可能小,而不同类别的个体之间的距离尽可能大,通过对聚类的客户特征的提取,电子商务网站可以为客户提供个性化的服务。
3.数据抽取方法在电子商务中的应用。数据抽取的目的是对数据进行浓缩,给出它的紧凑描述,如求和值、平均值、方差值、等统计值、或者用直方图、饼状图等图形方式表示,更主要的是他从数据泛化的角度来讨论数据总结。数据泛化是一种把最原始、最基本的信息数据从低层次抽象到高层次上的过程。可采用多维数据分析方法和面向属性的归纳方法。在电子商务活动中,采用维数据分析方法进行数据抽取,他针对的是电子商务活动中的客户数据仓库。在数据分析中经常要用到诸如求和、总计、平均、最大、最小等汇集操作,这类操作的计算量特别大,可把汇集操作结果预先计算并存储起来,以便用于决策支持系统使用。
4.关联规则在电子商务中的应用。管理部门可以收集存储大量的售货数据和客户资料,对这些历史数据进行分析并发现关联规则。如分析网上顾客的购买行为,帮助管理者规划市场,确定商品的种类、价格、质量等。通常关联规则有两种:有意义的关联规则和泛化关联规则,有意义的关联规则,即满足最小支持度和最小可信度的规则。最小支持度,它表示一组对象在统计意义上的需满足的最低程度,如电子商务活动中的客户数量、客户消费能力、消费方式等。后者即用户规定的关联规则的最低可靠度。第二是泛化规则,这种规则更实用,因为研究对象存在一种层次关系,如面包、蛋糕属西点类,而西点又属于食品类,有了层次关系后,可以帮助发现更多的有意义的规则。
5、优化企业资源
节约成本是企业盈利的关键。基于数据挖掘技术,实时、全面、准确地掌握企业资源信息,通过分析历史的财务数据、库存数据和交易数据, 可以发现企业资源消耗的关键点和主要活动的投入产出比例, 从而为企业资源优化配置提供决策依据, 例如降低库存、提高库存周转率、提高资金使用率等。通过对Web数据挖掘,快速提取商业信息,使企业准确地把握市场动态,极大地提高企业对市场变化的响应能力和创新能力,使企业最大限度地利用人力资源、物质资源和信息资源,合理协调企业内外部资源的关系,产生最佳的经济效益。促进企业发展的科学化、信息化和智能化。
例如:美国运通公司(American Express)有一个用于记录信用卡业务的数据库,数据量达到54亿字符,并仍在随着业务进展不断更新。运通公司通过对这些数据进行挖掘,制定了“关联结算(Relation ship Billing)优惠”的促销策略,即如果一个顾客在一个商店用运通卡购买一套时装,那么在同一个商店再买一双鞋,就可以得到比较大的折扣,这样既可以增加商店的销售量,也可以增加运通卡在该商店的使用率。
6、管理客户数据
随着“以客户为中心”的经营理念的不断深入人心, 分析客户、了解客户并引导客户的需求已成为企业经营的重要课题。基于数据挖掘技术,企业将最大限度地利用客户资源,开展客户行为的分析与预测,对客户进行分类。有助于客户盈利能力分析,寻找潜在的有价值的客户,开展个性化服务,提高客户的满意度和忠诚度。通过Web资源的挖掘,了解客户的购买习惯和兴趣,从而改善网站结构设计,推出满足不同客户的个性化网页。利用数据挖掘可以有效地获得客户。比如通过数据挖掘可以发现购买某种商品的消费者是男性还是女性,学历、收入如何, 有什么爱好,是什么职业等等。甚至可以发现不同的人在购买该种商品的相关商品后多长时间有可能购买该种商品, 以及什么样的人会购买什么型号的该种商品等等。在采用了数据挖掘后, 针对目标客户发送的广告的有效性和回应率将得到大幅度的提高, 推销的成本将大大降低。同时,在客户数据挖掘的基础上,企业可以发现重点客户和评价市场性能,制定个性化营销策略,拓宽销售渠道和范围,为企业制定生产策略和发展规划提供科学的依据。通过呼叫中心优化与客户沟通的渠道,提高对客户的响应效率和服务质量,促
①进客户关系管理的自动化和智能化。
三、结束语
电子商务是现代信息技术发展的必然结果,也是未来商业运作模式的必然选择。利用数据挖掘技术,充分发挥企业的独特优势,促进管理创新和技术创新,使企业在在电子商务的潮流中立于不败之地。随着数据挖掘算法的不断发展和成熟,数据挖掘一定会有更加广阔的应用前景。
参考文献:
(1)《浅谈数据挖掘在电子商务中的运用》 钟连福;
(2)《电子商务中商业数据的挖掘方法》 中国电子商务研究中心;
(3)《在电子商务中如何正确有使用数据挖掘技术》 侠名;
(4)《曾贞:数据挖掘在电子商务中的应用》 甘肃农业,2004(7);
(5)《冯艳王坚强:数据挖掘在电子商务上的应用》 2002(3);
(6)《吕延杰徐华飞:中国电子商务发展研究报告》北京邮电大学出版社 ;
(7)《数据挖掘与电子商务》 邓鲲鹏,周延杰,严瑜筱。①
第四篇:数据挖掘心得体会
心得体会
这次数据挖掘实验结束了,期间我们小组明确分工并积极去完成,虽然有点辛苦,但我感觉充实而有收获感!
根据老师给的一些资料,我们决定采用SQL Server 2000中的Northwind数据库里的数据作为我们的实验数据。根据表Order Details中的数据,我们分别根据ProductID和OrderID字段,并结合我们规定的最小支持度阀值对数据进行筛选。依次筛选出1项频繁集、2项频繁集和3项频繁集,其中还会使用游标的方式来遍历2项集与3项集的候选集,分别选出2项频繁集和3项频繁集。
由于数据较多,因此过程比较复杂,要编写很多的查询语句,建立许多数据表,包括临时表。开始不知道则操作,但经过我们各自多次重复的建表与查询,逐渐的理解和有了自己的思路。尤其是在运用游标的方法进行遍历这块,因为我们比较陌生而不理解,操作时一时无法实现结果,但经过我们在网上查询了解相关知识,最终得以解决。
经过该次实验,使我对数据库的操作更加熟练,而且还使我对课本上的“挖掘频繁模式”这块知识有了很好的掌握,今后我会多做实验,使我在实际操作过程中学得更好!
第五篇:数据挖掘试题
《数据挖掘》总复习题
1.数据挖掘系统可以根据什么标准进行分类?
答:根据挖掘的数据库类型分类、根据挖掘的知识类型分类、根据挖掘所用的技术分类、根据应用分类
2.知识发现过程包括哪些步骤?
答:数据清理、数据集成、数据选择、数据变换、数据挖掘、模式评估、知识表示3.什么是概念分层?
答:一个映射序列,将低层概念映射到更一般的较高层概念。4.多维数据模型上的 OLAP 操作包括哪些?
答:上卷、下钻、切片和切块、转轴 / 旋转、其他OLAP操作5.OLAP 服务器类型有哪几种?
答:关系 OLAP 服务器(ROLAP)、多维 OLAP 服务器(MOLAP)、混合 OLAP 服务器(HOLAP)、特殊的 SQL 服务器6.数据预处理技术包括哪些?
答:聚集、抽样、维规约、特征子集选择、特征创建、离散化和二元化、变量变换。7. 什么是数据清理?
答:填写缺失的值,平滑噪声数据,识别、删除离群点,解决不一致性 8. 什么是数据集成?
答:集成多个数据库、数据立方体或文件 9.什么是数据归约?
答:得到数据集的压缩表示,它小得多,但可以得到相同或相近的结果 10.数据清理的内容包括哪些?
答:缺失值、噪声数据、数据平滑、聚类、回归11.将下列缩略语复原
OLAP——on-line analytical processing DM——data mining
KDD——knowledge discovery in databases OLTP——on-line transaction processingDBMS——database management system DWT——discrete wavelet transform
(DMQL)--Data Mining Query Language 12.什么是数据挖掘?
答:简单地说,数据挖掘是从大量数据中提取或挖掘知识。具体地说,数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际 应用数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和 知识的过程。13.什么是关联规则? 答:(关联规则是形如X→Y的蕴涵式,其中且,X和Y分别称为关联规则的先导和后继。)假设I是项的集合。给定一个交易数据库,其中每个事务(Transaction)t是I的非空子集,即,每一个交易都与一个唯一的标识符TID(Transaction ID)对应。关联规则在D中的支持度(support)是D中事务同时包含X、Y的百分比,即概率;置信度(confidence)是包含X的事务中同时又包含Y的百分比,即条件概率。关联规则是有趣的,如果满足最小支持度阈值和最小置信度阈值。这些阈值是根据挖掘需要人为设定。
(关联规则反映一个事物与其它事物之间的相互依存性和关联性,如果两个事物或者多个事物之间存在一定的关联关系,那么其中一个事物就能够通过其他事物预测到。)15.什么是概念描述?什么是特征化?什么是属性相关分析?
答:概念描述:用汇总的、简洁的和精确的方式描述各个类和概念可能是有用的。特征化:是目标类数据的一般特性或特征的汇总。
属性相关分析:可能需要在分类和预测之前进行,它试图识别对于分类或预测过程无用的属性。这些属性应当排除。
16.什么是数据仓库?其主要特征是什么?
答:数据仓库是一个提供决策支持功能的数据库,它与组织机构的操作数据库分别维护。它允许将各种应用系统集成在一起,为统一的历史数据分析提供坚实的平台,对信息处理提供支持。
特征:面向主题、数据集成、随时间而变化、数据不易丢失(数据不易丢失是最明显特征)17.什么是数据集市?
答:数据集市包含企业范围数据的一个子集,对于特定的用户群是有用的。其范围限于选定的主题。
(是完整的数据仓库的一个逻辑子集,而数据仓库正是由所有的数据集市有机组合而成的)18.数据库中的知识发现过程由哪几个步骤组成?
答:数据清理、数据仓库、任务相关数据、数据挖掘、模式评估、知识表示 19.典型的数据挖掘系统有哪几个主要成分?
答:数据库、数据仓库、万维网或其他信息库;数据库或数据仓库服务器;知识库;数据挖掘引擎;模式评估模块;用户界面
20.从软件工程的观点来看,数据仓库的设计和构造包含哪些步骤?
答:规划、需求研究、问题分析、仓库设计、数据集成和测试、部署数据仓库。21.在数据挖掘系统中,为什么数据清理十分重要?
答: 脏数据的普遍存在,使得在大型数据库中维护数据的正确性和一致性成为一个极其困难的任务。
22.脏数据形成的原因有哪些?
答:滥用缩写词、数据输入错误、数据中的内嵌控制信息、不同的的惯用语、重复记录、丢失值、拼写变化、不同的计量单位、过时的编码23.数据清理时,对空缺值有哪些处理方法?
答:忽略元组、人工填写缺失值、使用一个全局变量填充缺失值、使用属性的平均值填充缺失值、使用与给定元组属同一类的所有样本的属性均值、使用最可能的值填充缺失值 24.什么是数据变换?包括哪些内容?
答:将数据转换或统一成适合于挖掘的形式。包括:光滑、聚集、数据泛化、规范化、属性构造 25. 数据归约的策略包括哪些?
答:数据立方体聚集、性子集选择、维度归约、数值归约、离散化和概念分层产生 26.提高数据挖掘算法效率有哪几种思路?
答:减少对数据的扫描次数;缩小产生的候选项集;改进对候选项集的支持度计算方法 27.假定属性income的最小值与最大值分别为12000和980到区间[0.0,1.0],根据 min-max 规范化,income的值73600将变为_3631/551_。
28.假定属性income的平均值和标准差分别为54000和16000,使用 Z-score 规范化,值73600被转换为_1.225_。
29.假定A的值由-986到917.A的最大绝对值为986,使用小数定标规范化,-986被规范化为_-0.986_
30.从结构角度来看,有哪三种数据仓库模型。答:企业仓库、数据集市、虚拟仓库
31.什么是聚类分析?它与分类有什么区别?
答:将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程 区别:分类有监督 聚类无监督 分类要靠学习聚类要靠启发式搜索 32.与数据挖掘类似的术语有哪些?
答:数据库中挖掘知识、知识提取、数据/模式分析、数据考古和数据捕捞。33.解释下列术语 34.翻译下列术语
Data Mining 数据挖掘Data warehousing 数据仓库Data Mart 数据集市
drill-down 下钻roll-up上卷OLAP 联机分析处理Data cube 数据立方体 Association rule 关联规则Data cleaning数据清理Data integration 数据集成 Data transformation数据变换Data reduction 数据归约
35.可以对按季度汇总的销售数据进行___B___,来观察按月汇总的数据。A 上卷 B 下钻 C 切片 D 切块
36.可以对按城市汇总的销售数据进行____A__,来观察按国家总的数据。A 上卷 B 下钻 C 切片 D 切块
37.通过不太详细的数据得到更详细的数据,称为____B____。A 上卷 B 下钻 C 细化 D 维规约
38.三层数据仓库结构中,从底层到尾层分别是_仓库数据服务器、OLAP服务器、前端客户层__。
42.常用的四种兴趣度的客观度量。
答:简单性 确定性 实用性 新颖性43.四种常用的概念分层类型。
答:模式分层、集合分组分层、操作导出的分层、基于规则的分层45.如何理解现实世界的数据是“肮脏的”?答:不完整的、含噪声的、不一致的、重复的 46.多维数据仓库有哪几种概念模型?
答:星形模式、雪花形模式或事实星座形模式。
48.在多路数组聚集算法中,如何尽量少地占用内存?
答:将最小的平面放在内存中,将最大的平面每次只是提取并计算一块。49.给出方体的维数,会计算各D方体有多少,总的方体个数有多少?2^n50.什么是离群点?离群点都需要删除吗?为什么?
答:离群点:一些与数据的一般行为或模型不一致的孤立数据。不需要。通常离群点被作为“噪音”或异常被丢弃,但在欺诈检测中却可以通过对罕见事件进行离群点分析而得到结论。
【51.所有模式都是有趣的吗?
答:一个模式是有趣的,如果(1)它易于被人理解 ;(2)在某种程度上,对于新的或测试数据是有效的;(3)具有潜在效用;(4)新颖的;(5)符合用户确信的某种假设。】