决策支持系统案例

.,决策支持系统,案例,.,层次分析模型的决策应用,层次分析法(AnalyticHierarchyProcess，AHP)是美国运筹学家、匹兹堡大学萨第（T.L.Saaty）教授于20世纪70年代提出的一种系统分析方法，80年代初引进我国，是一种定性与定量分析相结合的多目标属性决策分析方法。,.,运用层次分析法进行决策的过程包括建立层次结构模型、构造判断模型等内容。具体而言，层次分析法分析过程包括步：建立层次结构模型；决定各层指标的权重，将同一层的指标与上一层中某个指标进行两两成对比较，采用定性和定量标度其重要程度，构造出判断模型，计算出各层指标的权重，并通过计算判断矩阵的一致性来验证权重是否合理；计算出待选方案的相对权重并排序，完成决策。,层次分析模型,2020/5/18,.,4,层次分析法的基本步骤,建立层次结构模型；构造判断矩阵；层次单排序及一致性检验；层次总排序及一致性检验。,2020/5/18,.,5,多级递阶结构一般可以分成三层，即目标层，准则层和方案层。目标层：解决问题要想达到的目标。准则层：针对目标，评价各方案时所考虑的各个子目标（因素或准则），可以逐层细分。方案层：解决问题的方案。分解法：目的分目标(准则)指标(子准则)方案解释结构模型化方法(ISM法),建立层次结构模型,2020/5/18,.,6,层次结构往往用结构图形式表示，图中标明上一层次与下一层次要素之间的联系。如果上一层的每一要素与下一层次所有要素均有联系，称为完全相关结构。如果上一层每一要素都有各自独立的、完全不相同的下层要素，称为完全独立性结构由上述两种结构结合的混合结构,2020/5/18,.,7,判断矩阵是层次分析法的基本信息，也是计算各要素权重的重要依据。建立判断矩阵假设在准则H下要素的权重分别为即,判断矩阵,2020/5/18,.,8,表示以判断准则H的角度考虑要素对的相对重要程度。,对于准则H，对下一层的n个要素进行两两比较，来确定矩阵的元素值，满足：,2020/5/18,.,9,判断矩阵中的元素是表示两个要素的相对重要性的数量尺度，称做判断尺度，其取值如表所示。选择19之间的整数及其倒数作为取值的主要原因是，它符合人们进行比较判断时的心理习惯实验心理学表明，普通人在对一组事物的某种属性同时作比较、并使判断基本保持一致时，所能够正确辨别的事物最大个数在59。,的判断尺度,2020/5/18,.,10,判断矩阵标度定义,2020/5/18,.,11,在应用层次分析法进行系统评价和决策时，需要知道Ai关于H的相对重要度，也就是Ai关于H的权重,相对重要度及判断矩阵的最大特征值的计算(单排序),2020/5/18,.,12,由于判断矩阵A的最大特征值所对应的特征向量即为W，为此，可先求出判断矩阵的最大特征值所对应的特征向量，再经过归一化处理，即可求出Ai关于H的相对重要度,求A的最大特征值和其对应的特征向量,单位化,权重向量W,2020/5/18,.,13,(a)求和法(算术平均法),A的元素按列归一化将归一化后的各列相加将相加后的向量归一化,2020/5/18,.,14,（b）方根法(几何平均法),A的元素按行相乘开n次方归一化,2020/5/18,.,15,(c)特征根方法,由正矩阵的Perron定理可知存在且唯一，W的分量均为正分量，可以用幂法求出及相应的特征向量W。该方法对AHP的发展在理论上有重要作用。,2020/5/18,.,16,求特征值：,2020/5/18,.,17,根据矩阵理论，判断矩阵在满足上述一致性的条件下，n阶矩阵具有唯一非零的、也是最大的特征值，其余特征值均为零。W是矩阵A的对应于特征值n的特征向量。,相容性（一致性）判断,2020/5/18,.,18,由于判断矩阵的三个性质中的前两个容易被满足，第三个“一致性“则不易保证。如判断矩阵A被判断为A有偏差，则称A为不相容判断矩阵，这时就有若矩阵A完全相容，则有max=n，否则maxn这样就提示我们可以用max-n的关系来度量偏离相容性的程度。,2020/5/18,.,19,度量相容性的指标为C.I.一般情况下，若C.I.0.10，就可认为判断矩阵A有相容性，据此计算的W是可以接受的，否则重新进行两两比较判断。,一致性检验：,2020/5/18,.,20,判断矩阵的维数n越大，判断的一致性将越差，为克服一致性判断指标随n增大而明显增大的弊端，于是引入修正值R.I.，见下表：,R.I.是同阶平均随机一致性指标,2020/5/18,.,21,C.R.作为衡量判断矩阵一致性的指标更为合理的C.R.0.1时，便认为判断矩阵具有满意的一致性,2020/5/18,.,22,最终归结为最低层（方案、措施、指标等）相对于最高层（总目标）相对重要程度的权值或相对优劣的次序。,综合重要度的计算,2020/5/18,.,23,考虑投资兴建一个旅游点，选择一个最理想的地点就是决策目标。现在有三个地点D1、D2、D3可供选择。评选的标准有六个:,例题分析,A1:古迹的吸引力；,A2:名胜风光的条件；,A3:费用程度；,A4:生活条件；,A5:交通条件；,A6:接待工作的水平。,2020/5/18,.,24,两两对比的判断矩阵列于下，试对此问题决策。,2020/5/18,.,25,2020/5/18,.,26,2020/5/18,.,27,第二层到第三层：A1-A6与各方案的权重分别为,一致性检验相关数据结果依次为：,2020/5/18,.,28,各判断矩阵一致性检验系数均小于0.1，认为判断矩阵具有满意的一致性。最后，各方案对总目标的权重为：,=（0.370.380.25）,第二个方案的权重最大，因此选择地点D2最佳。,.,层次分析法在图书馆设备采购决策中的应用,某高校图书馆为了扩展读者培训的服务范围，提高服务档次，欲采购一批笔记本电脑用作培训用计算机，构建采购决策的层次结构模型。,.,判断模型,.,Web挖掘与个性化决策支持,数据挖掘概念：数据挖掘是运用计算机及信息技术,从大量的、不完全的数据集中获取隐含在其中的有用知识的高级过程。数据挖掘涉及的学科领域和方法很多，有多种分类法。,.,数据挖掘分类法,根据挖掘对象分：关系数据库、面向对象数据库、空间数据库、时序数据库、DNA数据库、多媒体数据库、异质数据库、遗产数据库以及Web数据库等；根据挖掘方法分：机器学习方法、统计方法、神经网络方法和数据库方法等；a.机器学习方法可细分为：归纳学习方法（决策树、规则归纳等）、基于范例学习、遗传算法等。,.,数据挖掘分类法,b.统计方法可细分为：回归分析（多元回归、自回归等）、判别分析（贝叶斯判别、费歇尔判别、非参数判别等）、聚类分析（系统聚类、动态聚类等）、探索性分析（主元分析法、相关分析法等）等。c.神经网络方法可细分为：前向神经网络（BP算法等）、自组织神经网络（自组织特征映射、竞争学习等）等。,.,数据挖掘分类法,根据挖掘任务分：可分为关联规则、分类、聚类、时间序列预测模型发现和时序模式发现等。,.,关联规则,案例：美国沃尔玛连锁店超市将尿布和啤酒赫然摆在一起出售。该举措使尿布和啤酒的销量双双增加。沃尔玛拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是：跟尿布一起购买最多的商品竟是啤酒！经过大量实际调查和分析，揭示了一个隐藏在尿布与啤酒背后的美国人的一种行为模式：在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30%40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。,.,关联规则举例,.,关联规则定义,定义一：设，是m个不同的项目的集合，每个ik称为一个项目。项目的集合I称为项集。其元素的个数称为项集的长度，长度为k的项集称为k-项集。上例中每个商品就是一个项目，项集为I=bread,beer,cake,cream,milk,tea，I的长度为6。,.,关联规则定义,定义二：每笔交易T是项集I的一个子集。对应每一个交易有一个唯一标识交易号，记作TID。交易全体构成了交易数据库D，|D|等于D中交易的个数。上例中包含10笔交易，因此|D|=10。,.,关联规则定义,定义三：对于项集X，设定count(XT)为交易集D中包含X的交易的数量，则项集X的支持度为：support(X)=count(XT)/|D|上例中X=bread,milk出现在T1，T2，T5，T9和T10中，所以支持度为0.5。,.,关联规则定义,定义四：最小支持度是项集的最小支持阀值，记为SUPmin，代表了用户关心的关联规则的最低重要性。支持度不小于SUPmin的项集称为频繁集，长度为k的频繁集称为k-频繁集。如果设定SUPmin为0.3，上例中bread,milk的支持度是0.5，所以是2-频繁集。,.,关联规则定义,定义五：关联规则是一个蕴含式：R：XY其中XI，YI，并且XY=。表示项集X在某一交易中出现，则导致Y以某一概率也会出现。用户关心的关联规则，可以用两个标准来衡量：支持度和可信度。,.,关联规则定义,定义六：关联规则R的支持度是交易集同时包含X和Y的交易数与|D|之比。即：support(XY)=count(XY)/|D|支持度反映了X、Y同时出现的概率。关联规则的支持度等于频繁集的支持度。,.,关联规则定义,定义七：对于关联规则R，可信度是指包含X和Y的交易数与包含X的交易数之比。即：confidence(XY)=support(XY)/support(X)可信度反映了如果交易中包含X，则交易包含Y的概率。一般来说，只有支持度和可信度较高的关联规则才是用户感兴趣的。,.,关联规则定义,定义八：设定关联规则的最小支持度和最小可信度为SUPmin和CONFmin。规则R的支持度和可信度均不小于SUPmin和CONFmin，则称为强关联规则。关联规则挖掘的目的就是找出强关联规则，从而指导商家的决策。,.,关联规则举例,.,关联规则举例,顾客购买记录的数据库D，包含6个事务。项集I=网球拍,网球,运动鞋,羽毛球。考虑关联规则（频繁二项集）：网球拍与网球，事务1,2,3,4,6包含网球拍，事务1,2,6同时包含网球拍和网球，XY=3,D=6，支持度(XY)/D=0.5；X=5,置信度(XY)/X=0.6。若给定最小支持度=0.5，最小置信度=0.6，认为购买网球拍和购买网球之间存在关联。,.,关联规则的挖掘过程,关联规则挖掘过程主要包含两个阶段：第一阶段必须先从资料集合中找出所有的高频项目组(FrequentItemsets)，第二阶段再由这些高频项目组中产生关联规则(AssociationRules)。,.,Apriori算法,Apriori算法是对于事务处理数据序进行频繁项集挖掘和关联规则的一种经典算法。算法从寻找单一频繁项集开始,逐渐往K-频繁项集扩展,只要项集出现的比例高于设定的最小支持度阈值,就一直扩展卜去。这些频繁项集中满足置信度参数即为强关联规则,否则为弱关联规则。关联规则挖掘就是在频繁项集中找到所冇强关联规则。Apriori算法得到的关联规则可以确定在数据库中突出的总体趋势。,.,Apriori算法的具体步骤,C1,即1-项频繁项集候选集：扫描数据库,对每个单独的项进行计数得到C1。L1,即1-项频繁项集：从C1中删除支持度小于最小支持度的项得到L1。Ck+1,即K+1项频繁集候选集：Ck+1由Lk与自身连接得到,连接条件是参与连接的两个K项集前K-1项相同，第K项不同。LK+1,K+1项频繁集:从CK+1中删除支持度小最小支持度的项,删除CK+1中K项自己不在LK中的项。,.,分类规则,数据挖掘的一个重要任务是对海量数据进行分类。数据分类是基于一组数据的某些属性的值进行的。数据分类的方法很多，包括决策树方法、统计学方法、神经网络方法、最近邻居方法等等。其中，基于决策树的分类方法与其它的分类方法比较起来，具有速度较快、较容易转换成简单的并且易于被理解的分类规则、较易转换成数据库查询语言、友善、可得到更高的准确度等优点。,.,决策树算法,决策树(DecisionTree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。,.,决策树的组成部分,决策点，是对几种可能方案的选择，即最后选择的最佳方案。如果决策属于多级决策，则决策树的中间可以有多个决策点，以决策树根部的决策点为最终决策方案。1状态节点，代表备选方案的经济效果（期望值），通过各状态节点的经济效果的对比，按照一定的决策标准就可以选出最佳方案。由状态节点引出的分支称为概率枝，概率枝的数目表示可能出现的自然状态数目每个分枝上要注明该状态出现的概率。1结果节点，将每个方案在各种自然状态下取得的损益值标注于结果节点的右端。,.,决策树算法举例,.,决策树预备定义信息墒,熵是无序性（或不确定性）的度量指标。假如事件A的全概率划分是（A1,A2,.,An），每部分发生的概率是(p1,p2,.,pn)，那信息熵定义为：通常以2位底数，所以信息墒的单位是bit。,.,ID3算法构造决策树,构造树的基本想法是随着树深度的增加，节点的熵迅速地降低。熵降低的速度越快越好，目标是得到一棵高度最矮的决策树。例子中在没有给定任何天气信息时，根据历史数据，我们只知道新的一天打球的概率是9/14，不打的概率是5/14。此时的熵为：,.,确定决策树的节点,4个属性outlook，temperature，humidity，windy。首先要决定哪个属性作树的根节点。对每项指标分别统计：在不同的取值下打球和不打球的次数。,.,计算各属性的信息墒,计算当已知变量outlook的值时，信息熵为多少。outlook=sunny时，2/5的概率打球，3/5的概率不打球。entropy=0.971outlook=overcast时，entropy=0outlook=rainy时，entropy=0.971而根据历史统计数据，outlook取值为sunny、overcast、rainy的概率分别是5/14、4/14、5/14，所以当已知变量outlook的值时，信息熵为：5/140.971+4/140+5/140.971=0.693系统熵就从0.940下降到了0.693，信息增溢gain(outlook)为0.940-0.693=0.247,.,得到根节点,同样可以计算出gain(temperature)=0.029，gain(humidity)=0.152，gain(windy)=0.048。gain(outlook)最大（即outlook在第一步使系统的信息熵下降得最快），所以决策树的根节点就取outlook。,.,接下来要确定N1取temperature、humidity还是windy?在已知outlook=sunny的情况，根据历史数据，我们作出类似table2的一张表，分别计算gain(temperature)、gain(humidity)和gain(windy)，选最大者为N1。依此类推，构造决策树。当系统的信息熵降为0时，就没有必要再往下构造决策树了，此时叶子节点都是纯的-这是理想情况。最坏的情况下，决策树的高度为属性（决策变量）的个数，叶子节点不纯（这意味着我们要以一定的概率来作出决策）。,.,.,聚类,对数据进行分析的过程中，在考虑数据间的“距离”的同时，更侧重考虑某些数据间具有类的共同内涵。数据聚类是对一组数据进行分组，这种分组基于如下的原理：最大的组内相似性与最小的组间相似性。,.,聚类的一般步骤,聚类的一般步骤的细节如下：（1）特征选择。必须适当地选择特征，尽可能多的包含任务关心的信息。在特征中，信息多余减少和最小化是主要目的。（2）相似性度量。用于定量度量两个特征向量之间如何“相似”或“不相似”。一个简单的度量如欧氏距离经常被用来反应两个特征向量之间的非相似性。（3）聚类算法。已经选择了合适的相似性度量，这步涉及到选择特定的聚类算法，用于揭示数据集中的聚类结构。,.,聚类的一般步骤,（4）结果验证。一旦用聚类算法得到结果，就需要验证其正确性。（5）结果判定。在许多情况下，应用领域的专家必须用其他实验数据和分析判定聚类结果，最后做出正确的结论。,.,.,聚类在图情领域中的应用,基于聚类的词表自动构建UCINET社会化网络分析软件,.,时序规则挖掘,时间序列(Timeseries)是指按时间顺序取得的一系列观测值。时序数据挖掘就是从大量的时序数据中提取潜在的有用的知识。时序关联规则,就是对时序数据库采用某种数据挖掘算法,得到具有时间约束的关联规则。与一般的布尔型关联规则最大的区别在于时序关联规则与时间或时态是密切相关的.除此之外,还可以把数据挖掘的概念,支持度、置信度等等一些相关概念运用到挖掘时序关联规则的过程中。,.,基本概念,.,基本概念,.,基本概念,.,例子,.,.,Web日志时序关联规则挖掘模型,首先明确如何根据Web日志提取出需要分析的页面序列。Web日志记录了每一天对某个网站服务器的访问情况,包括访问的时间、页面、停留时间。对于访问网站的每个用户,由其自己的ocokie来决定他访问了那些页面,这些页面是否可以通过其它页面的链接来访问。如果通过页面上的链接来访问其它页面,前后的页面就可以构成一个页面序列。可以将访问页面序列及其访问时间记录到数据库中作为Web时序关联规则挖掘的对象。,.,Step1整理数据,以“天”作为时序数据的时间单位,每一天的数据将对应着数据库表中的一个元组。设置一个时间段,如10天、30天等等,把这个时间段称为一个“时间窗口”,窗口长度就是时间段的长度。时间窗口从起始时间开始,每过一天,向后滑动一个单位,生成新的时间窗口。,.,Step2计算窗口变化率,将某个页面访问序列在某个时间窗口的变化率计算出来,就可以将时序数据库转化为一般的关系数据库，而且关系的属性都是数值型的。,.,Step2计算窗口变化率,设一个数值序列P=P1,P2,P3,，Pn，设时间窗口的大小为i,in,P1,P2,P3,，Pi为第一个时间窗口T1中的元素，P2,P3,，Pi+1为第二个时间窗口Ti中的元素,依此类推,Pn-i+1,Pn-i+2,Pn,为最后一个时间窗口（即第n一i+1个时间窗口）Tn-i+1中的元素。要计算第j个时间窗口中属性的变化率，按照下面的公式进行计算:,.,监督学习,监督学习又称为分类（Classification）或者归纳学习（InductiveLearning）。监督学习中一种典型的类型：学习一个目标函数从而用于预测实例的类属性值。监督学习通过发现数据属性和类别属性之间的关联模式，并通过利用这些模式来预测未知数据实例的类别属性。这些类别通常表示一些现实世界中的预测或分类问题。,.,基本概念,一个用于学习的数据集就是一张关系表，表里的每条记录描述了一条“以往的经验”。在机器学习和数据挖掘的词汇中，一条数据记录又称作一个样例、一个实例、一个用例或者一个向量。一个数据集就是包括一系列样例的集合。,.,基本概念,给出一个数据集D，机器学习任务的目标就是产生一个联系属性值集合A和类标集合C的分类/预测函数（Classification/PredictionFunction），这个函数可以用于预测新的属性集合（数据实例）的类标。这个函数又被称为分类模型（ClassificationModel）、预测模型（PredictiveModel），或者简称为分类器（Classifier）。分类其可以是任何形式的，决策树、规则集、贝叶斯模型或者一个超平面。,.,朴素贝叶斯分类,例假设训练数据有两个属性A和B，类别C。计算所有必须的概率值学习一个朴素贝叶斯分类器。,.,.,学习过程,由经验数据可以得出P(C=t)=1/2P(C=f)=1/2P(A=m|C=t)=2/5P(A=g|C=t)=2/5P(A=h|C=t)=1/5P(A=m|C=f)=1/5P(A=g|C=f)=2/5P(A=h|C=f)=2/5P(B=b|C=t)=1/5P(B=s|C=t)=2/5P(B=q|C=t)=2/5P(B=b|C=f)=1/5P(B=s|C=f)=1/5P(B=q|C=f)=2/5,.,预测,一个测试样例A=mB=qC=？P(C=t)*P(A=m|C=t)*P(B=q|C=t)=1/2*2/5*2/5=2/25P(C=f)*P(A=m|C=f)*P(B=q|C=f)=1/2*1/5*2/5=1/25C=t的可能性更大，测试样例的预测类别就是t。,.,朴素贝叶斯文本分类,文本分类是指如何从训练文本中学习得到分类模型的问题，并且用获得的模型来对新的文档进行分类。例如将新闻报道分为三个类别：Sport、Politics和Science，目标是学习一个分类器，能够将以后的新闻报道分门别类到这三个类别中。,.,朴素贝叶斯文本文档模型,一个文本文档包括一系列句子，每个句子又包含一连串的单词。朴素贝叶斯分类将每篇文档看作一个词汇（word）的集合。生成模型基于以下假设：文档中的词汇都是独立于语境生成的。也就是说当给定类别后，每个词汇的生成和别的词汇是相互独立的。单词被生成的概率与它在文档中的位置无关。文档的长度与类别无关。根据以上假设，每个文档服从单词的二项分布。单词都是从一个给定的词典V=w1，w2，w|v|中提取，|V|是词典中单词总数。,.,二项分布,.,说明,.,说明,.,无监督学习,如果数据的类别属性缺失，用户希望通过浏览数据来发现其中的某些内在结构。聚类(Clustering)就是一种发现内在结构的技术。聚类把全体数据实例组织成一些相似组，这些相似组被称为聚类(Cluster)。处于相同聚类中的数据实例彼此相似，处于不同聚类中的实例则彼此不同。聚类技术通常被称为无监督学习。,.,聚类应用实例,.,聚类应用实例,.,聚类应用实例,.,分析,从以上的例子可以看到聚类需要一个相似度函数来度量两个数据点（对象）的相似程度，或者说利用一个距离函数(DistanceFunction)来度量两个数据点之间的距离。聚类的目的就是通过使用某个聚类算法和某个距离函数来发现数据中内在的分组结构。,.,距离函数,.,Web使用日志挖掘,基于web的组织在日常运作中收集大量的点击流（ClickStream）和用户数据（UserData）。对这些数据的分析可以帮助这些组织决定客户的生命周期、设计产品和服务的交叉营销策略、评估促销活动的效果、优化Web应用程序的功能、为访问者提供更个性化的内容以及为自己的Web空间找到最有效的逻辑结构。,.,概念,Web使用记录挖掘是指自动发现和分析模式，这些模式来自于收集的点击流和相关数据或用户与一个或多个网站互动的结果。其目标是捕捉、建模并分析用于与网站交互的行为模式和模型。所发现的模式经常被表示成有着共同需求或兴趣的一群用户频繁访问的页面、对象或者资源的集合。,.,挖掘过程,数据收集和预处理模式发现模式分析,.,数据预处理阶段,确定数据的来源和类型使用记录数据：Web服务器和应用服务器自动收集的日志数据是Web使用记录挖掘中首要的数据来源。用户对服务器的每一次访问相当于一个HTTP请求，在服务器访问日志里产生一条记录。每条记录可包含请求的时间、客户端IP、所请求的资源、调用Web应用服务器所使用的参数、请求的状态、使用HTTP方法、用户代理.,.,.,.,数据预处理阶段,确定数据的来源和类型内容数据：一个站点的内容数据是已传送给用户的对象和关系的集合。这些数据由文字材料和图片组成，包括静态的HTML/XML页面、多媒体文件、由脚本动态生成的页面片段以及来自操作数据库的记录集合；嵌入在网站或单独页面中的含语义的或结构化的元数据；网站的领域本体也是内容数据的一部分，包括网页内容的概念层次等。,.,数据预处理阶段,确定数据的来源和类型结构数据：结构数据展示了以设计者的角度所看到的网站的内容组织结构。通过超链接建立页面间的连接结构；一个页面内容过标签形成的属性结构；一个站点的资源地图。用户数据：包括注册用户统计信息、用户对各种对象的访问率、用户的购买记录或历史访问记录以及其他显式或隐式的用户兴趣描述。,.,数据预处理阶段,必要任务数据的融合清理：数据融合是指将来自多个Web和应用服务器的日志文件合并。由于用户的行为分析基于来自多个相关网站的多个日志文件，因此这一步在站间Web使用数据挖掘中很必要。数据清理通常根据站点不同而不同，涉及对分析不重要的或无关的嵌入式对象的引用，包括css、图像或声音文件。,.,数据预处理阶段,必要任务页面访问识别：页面访问的识别主要依赖于网站的页面结构、页面内容以及基础站点领域知识。由于每个页面访问可以被看作表示特定“用户事件”的Web对象或资源的集合。一个静态单框架的站点，每个HTML文件就是一个页面访问；静态多框架站点，多个文件组成一个页面访问；对于动态站点，一个页面访问可能表示一些静态模版和应用程序服务器接受参数后生成的内容结合。为了给大量数据挖掘活动提供合适的框架，每个页面访问记录的属性包括页面访问的ID、静态页面访问类型以及其他元数据。,.,数据预处理阶段,必要任务用户识别：由于一个用户可能多次访问同一个网站，服务器日志会为每个用户记录多个会话，因此大多数用来区分不同访问者的方法是使用客户端的cookies信息。以下例子是用户IP加代理的用户识别方式。,.,.,数据预处理阶段,必要任务会话识别：将每个用户的活动记录分成一个一个会话的过程，每个会话代表一次对站点的访问。会话识别的目的是从点击流数据中重构信息，以获得一个用户一次访问站点的真实行为序列。会话识别分为面向时间的探索方法和面向导航的探索方法。,.,.,h1探索法,.,h-ref探索法,.,数据预处理阶段,必要任务事务识别：一个事务是一个在语义上或功能上相关联的页面访问所组成的会话的子集或子序列。事务识别需要自动或半自动的将页面访问按照功能类型或者根据领域本体或概念层次而来的概念类别进行分类。,.,数据预处理阶段,必要任务路径完善：客户端或代理端的缓存功能经常会导致对那些被缓存的页面和对象的访问引用的丢失。例如，如果一个用户在同一个会话中返回到页面A，第2次对A的访问很有可能看到的是存在客户端缓存中的A的上一个版本，因此并没有请求向服务器发送。由于缓存而丢失的记录可以通过路径完善探索式的补全，路径完善依靠服务器日志上站点结构和引用信息完成。对于动态生成的页面，基于表单的应用程序使用HTTPPOST方法来处理所有或部分用户输入的参数。,.,数据预处理阶段,必要任务数据整合：以上预处理任务最终形成用户会话的集合，每一个对应一个有限的页面访问序列。例如，在电子商务应用中，除了整合来自多渠道的用户数据（例如用户统计信息、用户访问率、购物历史记录），还要包括产品属性和目录、购物车的改变、订单和发货信息等。,.,Web使用记录挖掘的数据建模,.,页面权重的确定方法,依赖于使用相似用户模型给当前用户推荐的协同过滤中，权重可能基于用户在某些项目上的访问率。可以表示一个页面访问在事务访问中存在不存在，这时权重的取值就是0和1。可以是一个计算页面访问在用户的会话中持续时间的函数。,.,页面访问序列模型的矩阵表示,.,.,其他数据的整合,除了页面访问序列外，需要整合的数据还有其他知识来源，例如Web页面内容的语义信息。每个页面访问p可以用一个r维特征向量表示，其中r是从全局词典中抽出的来自站点特征（词或概念）数量。,.,页面访问特征矩阵表示,.,用户页面访问矩阵和页面访问特性矩阵的乘积的到一个新的矩阵TFM。这时一个用户事务被表示成一个内容特征向量，反映了用户在特定概念和话题上的兴趣。,.,.,.,.,内容增强型事务数据的应用,对内容增强型事务矩阵聚类发现，从用户导航行为所表明的具有不同思想但是拥有相同兴趣的用户。如果内容特征包含与网站中的项目相关联的关系属性，发现的模式可以展示更深语义层次的用户兴趣。,.,Web用法模式的发现和分析,会话和访问者分析聚类分析和访问者分割关联和相关度分析序列和导航模式分析基于Web事务的分类和预测,.,聚类分析和访问者分割,用户聚类用户记录聚类是Web使用记录挖掘和Web分析中最普遍使用的分析任务。用户聚类为了建立拥有相同浏览模式的用户的分组。这种知识在推断用户统计信息方面特别有用，例如在电子商务中进行市场划分或给具有相似兴趣的用户提供个性化的Web内容。更进一步的在用户分组上基于用户统计属性（例如年龄、性别、收入级别等）的分析可以发现有价值的商业智能。,.,K-means算法思想,先从随机选取k个数据点作为初始的聚类中心。然后计算每个数据点与各个种子聚类中心之间的距离，把每个数据点分配给距离它最近的聚类中心。聚类中心以及分配给他的数据点就代表一个聚类。如果全部数据点都被分配了，每个聚类的聚类中心根据聚类中现有的数据点重新计算其平均距离。以上循环退出条件：没有（或最小数目）数据点被重新分配给不同的聚类；没有（或最小数目）聚类中心再发生变化；误差平方和局部最小。,.,.,.,关联与相关度分析实例,.,.,序列和导航模式分析,序列模式挖掘技术用来发现会话之间的模式，发现在一个按照时间顺序排列的会话或事务中存在于一个项目之后的另一个项目。例如Web销售商可以预测未来的访问模式，以帮助针对特定用户组的广告排放顺序。,.,.,观点挖掘,网络提供给用户表达观点的途径：用户既可以在商业网站发布产品评价，也可以在论坛、讨论组、博客等网络媒体上对几乎任何事物发表自己的意见。这些评价和意见通常被称为用户生成内容或者用户生成媒体。这些表述为很多实际应用提供了可测量的资源。观点挖掘主要有文本评估和观点搜索及观点欺诈。,.,文本评估,意见分类基于特征的观点挖掘和摘要比较性句子和比较关系挖掘,.,意见分类,.,基于意见短语的分类,该算法思想的基础是词性标注的自然语言处理技术。词性是指根据词的句法和形态特征而定义的语言类别。英语语法中常见的词性类别有：名词、动词、形容词、副词、代词、介词、连词和感叹词。对词性进行标注是将句子中的每个词都标上合适的词性。,.,算法步骤,第一步：抽取包含有形容词和副词的短语。这是因为形容词和副词是用户意见和观点很好的指示词。但有时采用单独的形容词并不足以确定它的语义倾向。因此需要抽取两个连续的词组成词对，其中一个词是形容词/副词，另一个词是上下文词汇。,.,.,.,.,例子,在句子“thiscameraproducesbeautifulpictures”中，“beautifulpictures”由于满足第一个模式被抽取。,.,算法步骤,.,短语的语义倾向（SO）,.,算法步骤,第三步：给定一个评审，算法计算评审中所有短语的平均SO。如果平均SO是正的，那么将该评审归为正面评价，否则，归为负面评价。,.,基于评分函数的意见分类,.,基于评分函数的意见分类,.,观点挖掘和摘要,用户可以针对任何事物的任何方面发表观点，例如，产品、个人、组织、时间、主题等。这些被评价的实体称作对象。对象包括一个组件集合和一个属性集合。因此，该对象根据部分隶属关系被层次化的分解，也就是说每个组件又有它的子组件。,.,对象,定义（对象）：一个对象O是指一个实体。它关联到一个有序对，O：(T，A)。一个特定的数码相机品牌就是一个对象。它有一系列组件，包括lens、battery、view-finder；还有一系列属性，picturequality、size、weight。同时电池组件有它自己的属性集合，batterylife、batterysize、batteryweight。可以将一个对象表示成一棵树。,.,例子,对一个相机（以上例子树的根结点）表达看法，Idonotlikethiscamera；或者对它的属性进行评价，thepicturequalityofthiscameraispoor；可以对相机的一个组件发表看法，thebatteryofthiscameraisbad；对一个组件的属性发表看法，thebatterylifeofthiscameraistooshort。采用特征来统一表示组件和属性。,.,显式和隐式特征,定义（显式和隐式特征）：如果一个特征f出现在一个评估文本r中，那么被称为r的一个显示特征，如果f没有在r中出现，但是被暗指，那么将其称为r的一个隐式特征。,.,例子,Batterylife在Thebatterylifeofthiscameraistooshort是显式特征。Size在Thiscameraistoolarge中没有出现，但是被暗指，因此它是该句子的隐式特征。,.,某一特征的观点段,定义（某一特征的观点段）:一个关于对象r的特征f的观点段是r中一组表达了关于f的正面或负面观点的连续句子。Thepicturequalityisgood,butthebatterylifeisshort.,.,显式和隐式观点,定义（显式和隐式观点）：一个关于特征f的显式观点是一个直接表达了正面或者负面观点的主观句子。一个关于特征f的隐式观点是一个蕴含了正面或者负面观点的客观句子。例如，thepicturequalityofthiscameraisamazing表达了一个显式的正面观点；theearphonebrokeintwodays表达一个隐式的负面观点。,.,基于特征的摘要,例子，假设总结某一数码相机，difital_camera_1的评审摘要,.,.,对象特征的抽取,评审格式：格式1-区分正面、负面以及细节的评审,.,对象特征的抽取,评审格式：格式2-区分正面、负面的评审,.,对象特征的抽取,评审格式：格式3-自由格式,.,格式1中正面和负面评价的特征抽取,特征抽取基于以下的规定：每个正面和负面评价中的句子片段只包含一个特征。句子片段通过逗号、句号、分好、连字号、&、and、but分开。例如,.,格式2、3中正面和负面评价的特征抽取,第一步：找到所有高频名词和名词短语，通过词性标注工具来识别。第二步：利用意见词找到不频繁出现的特征。第三步：观点倾向分类。,.,观点欺诈,观点欺诈指的是人们故意误导读者和自动观点挖掘系统的行为。写欺诈性评审的目的主要有两个：推销某些目标对象；损害某些其他目标对象的声誉。,.,结构化数据抽取,Web信息抽取是从网页中抽取出目标信息。Web上的结构话数据一般是从后台数据库获取的数据记录，按照一定的模版被展现在网页上。抽取结构化的数据能够获取和整合来自多个来源（网站或者网页）的数据，以提供增值服务。,.,预备知识,富含数据的网页主要有两种：列表页；详情页。,.,.,列表页,每个列表页都包含有多个对象。一般从布局角度来看，可以在列表页上看到不同的数据区域（DataRegion）。在每一个区域中，数据记录根据同一种模板被格式化。不同区域所采用的模板一般不同。,.,.,详情页,侧重描述一个对象。一般包括产品的所有细节，如名称、图片、价格和其他销