仓库管理_数据仓库与数据挖掘技术

数据仓库与数据挖掘技术 ElectronicCommerce夏火松E MAIL BXXHS SINA COM 数据仓库与数据挖掘技术教案 第6章数据挖掘基本算法 本章内容 6 1分类规则挖掘6 2预测分析与趋势分析规则6 3数据挖掘的关联算法6 4数据挖掘的聚类算法6 5数据挖掘的统计分析算法6 6数据挖掘的品种优化算法6 7数据挖掘的进化算法 6 1分类规则挖掘 6 1 1分类与估值1分类为了理解事物特征并做出预测使用历史数据建立一个分类模型 即分类器 的过程 应用于信用卡系统中的信用分级 市场调查 疗效诊断 寻找店址等实践应用参照课本 6 1分类规则挖掘 6 1 1分类与估值2估值估值 estimation 与分类类似 不同之处在于 分类描述的是离散型变量的输出 而估值处理连续值的输出 分类的类别是确定的数目 估值的量是不确定的 3分类方法与步骤方法 决策树归纳 贝叶斯分类 贝叶斯网络 神经网络 还有K 最临近分类 基于案例的推理 遗传算法 粗糙集和模糊集方法 步骤 模型创建 模型使用 6 1分类规则挖掘 6 1 1分类与估值4评估分类方法要考虑的指标 预测准确率 速度 创建速度 使用速度 鲁棒性 处理噪声和丢失值 伸缩性 对磁盘驻留数据的处理能力 可解释性 对模型的可理解程度 规则好坏的评价 决策树的大小和分类规则的简明性 6 1分类规则挖掘 6 1 2决策树 6 1分类规则挖掘 6 1 2决策树1 决策树的构造过程ID3算法应用如下 信息量计算公式 I s1 s2 sm 6 1 其中 pi为si占整个类别的概率利用属性A划分当前样本集合所需要的信息 熵 的计算公式为 E A 6 2 信息增益公式 Gain A I s1 s2 sm E A 6 3 例如 一个销售的顾客数据库 训练样本集合 对购买计算机的人员进行分类 字段为 年龄 取值 40 收入 高 中 低 学生否 Y N 信用 一般 很好 购买计算机否 Y N 记录为14个 具体数据如下 X1 40 中 N 一般 Y X5 40 低 Y 一般 Y X6 40 低 Y 很好 N X7 40 中 Y 一般 Y X11 40 中 N 很好 N 6 1分类规则挖掘 6 1 2决策树1 决策树的构造过程决策树的构造算法 决策树的构造算法可通过训练集T完成 其中T 而x a1 a2 an 为一个训练实例 它有n个属性 分别列于属性表 A1 A2 An 中 其中ai表示属性Ai的取值 Cj C C1 C2 Cm 为x的分类结果 从属性表中选择属性Ai作为分类属性 若属性Ai的取值有ki个 则将T划分为ki个子集 T1 Tki 其中Tij T 且x的属性取值A为第i个值 接下来从属性表中删除属性Ai 对于每一个Tij 1 j K1 令T Tij 如果属性表非空 返回第1步 否则输出 6 1分类规则挖掘 6 1 2决策树2 分类器定义 输入的数据含有千万个记录 每个记录又有很多个属性 其中有一个特别的属性叫做类 例如信用程度的高 中 低 具体步骤 1 树的建立 2 树的修剪 SLIQ采用了MDL 最小叙述长度 的方法来修剪树 6 1分类规则挖掘 6 1 2决策树3 决策树的可扩展性4 基于决策树方法的数据挖掘工具KnowledgSEEKER 6 1分类规则挖掘 6 1 3贝叶斯分类1 贝叶斯信任网络如何工作 6 1分类规则挖掘 6 1 3贝叶斯分类2 贝叶斯定理与朴素贝叶斯分类贝叶斯定理 P H X P X H P H P X 其中 P H X 表示条件X下H的概率 也称为条件概率或称为后验概率 posterioriprobabilities 朴素贝叶斯分类 假定有m个类C1 Cm 对于数据样本X 分类法将预测X属于类Ci 当且仅当P Ci X P Cj X 6 2预测分析与趋势分析规则 6 2 1预言的基本方法预言 prediction 是一门掌握对象变化动态的科学 它是对对象变动趋势的预见 分析和判断 也是一种动态分析方法 预测的基本步骤 确定预测目标 包括预测对象 目的 对象范围 收集分析内部和外部资料 数据的处理及模型的选择 预测模型的分析 修正 确定预测值 6 2预测分析与趋势分析规则 6 2 2定量分析预测时间序列法回归预测非线性模型灰色预测模型GM 1 1 组合预测 6 2预测分析与趋势分析规则 6 2 3预测的结果分析预测的结果分析要考虑到的因素 相反的预测结果胜出裕度成本收益分析 6 2预测分析与趋势分析规则 6 2 4趋势分析挖掘分析时间序列数据需要注意以下方面 长时间的走向周期的走向与周期的变化季节性的走向与变化不规则的随机走向 6 3数据挖掘的关联算法 6 3 1关联规则的概念及分类1 关联规则的概念定义1设I i1 i2 i3 im 是由m个不同的数据项目组成的集合 其中的元素称为项 item 项的集合称为项集 包含k个项的项集称为k项集 给定一个事务 交易 D 即交易数据库 其中的每一个事务 交易 T是数据项I的一个子集 即 T有一个惟一的标积符TID 当且仅当时 称交易T包含项集X 那么关联规则就形如 X Y 的蕴涵式 其中 即表示满足X中条件的记录也一定满足Y 关联规则X Y在交易数据库中成立 具有支持度s和具有置信度c 这也就是交易数据集D中具有支持度s 即D中至少有s 的事务包含 描述为 support X Y 比如Support X Y 同时购买商品X和Y的交易数 总交易数同时交易数据集D中具有置信度c 即D中包含X的事务至少有c 同时也包含Y 描述为 confidence X Y 比如购买了商品X 同时购买商品Y可信度 confidence X Y 同时购买商品X和Y的交易数 购买了商品X的交易数一般称满足一定要求的规则为强规则 通常称满足最小支持度和最小置信度的关联规则为强关联规则 strong 一般将最小支持度简记为minsup和最小置信度简记为minconf 6 3数据挖掘的关联算法 6 3 1关联规则的概念及分类2关联规则的分类 6 3数据挖掘的关联算法 6 3 2简单形式的关联规则算法 单维 单层和布尔关联规则 1 简单形式的关联规则的核心算法找到所有支持度大于最小支持度的项集 即频集 有k个数据频集称为k项频集 找出所有的频集由apriori算法实现 Apriori性质具有一个频集的任一非空子集都是频集 使用第1步找到的频集产生期望的规则apriori算法的详细介绍见课本 6 3数据挖掘的关联算法 6 3 2简单形式的关联规则算法 单维 单层和布尔关联规则 2频集算法的几种优化方法基于划分的方法基于hash的方法基于采样的方法减少交易的个数 6 3数据挖掘的关联算法 6 3 2简单形式的关联规则算法 单维 单层和布尔关联规则 3其他的频集挖掘方法FP growth方法min hashing MH 和locality sensitive hashing LSH 6 3数据挖掘的关联算法 6 3 3多层和多维关联规则的挖掘多层关联规则多维关联规则关联规则价值衡量的方法6 3 4货篮子分析存在的问题详见课本 6 3数据挖掘的关联算法 6 3 5关联分析的其他算法发现关联的更好方法统计相关以外的理解关联有效可行的市场篮子分析6 3 6挖掘序列模式序列模式的概念及定义序列模式挖掘的主要算法GSP算法描述PrefixSpan算法 关联规则挖掘 一个例子 最小值尺度50 最小可信度50 对于A C support support A C 50 confidence support A C support A 66 6 Apriori的基本思想 频繁项集的任何子集也一定是频繁的 关键步骤 挖掘频繁集 频繁集 是指满足最小支持度的项目集合频繁集的子集也一定是频繁的如 如果 AB 是频繁集 则 A B 也一定是频繁集从1到k k 频繁集 递归查找频繁集用得到的频繁集生成关联规则 Apriori算法 连接 用Lk 1自连接得到Ck修剪 一个k 项集 如果他的一个k 1项集 他的子集 不是频繁的 那他本身也不可能是频繁的 伪代码 Ck CandidateitemsetofsizekLk frequentitemsetofsizekL1 frequentitems for k 1 Lk k dobeginCk 1 candidatesgeneratedfromLk foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk 1thatarecontainedintLk 1 candidatesinCk 1withmin supportendreturn kLk Apriori算法 例子 如何生成候选集 假定Lk 1中的项按顺序排列第一步 自连接Lk 1insertintoCkselectp item1 p item2 p itemk 1 q itemk 1fromLk 1p Lk 1qwherep item1 q item1 p itemk 2 q itemk 2 p itemk 1 q itemk 1第二步 修剪forallitemsetscinCkdoforall k 1 subsetssofcdoif sisnotinLk 1 thendeletecfromCk 如何计算候选集的支持度 计算支持度为什么会成为一个问题 候选集的个数非常巨大一笔交易可能包含多个候选集方法 用hash tree存放候选集树的叶子节点of存放项集的列表和支持度内部节点是一个hash表Subset函数 找到包含在一笔交易中的所有候选集 生成候选集的例子 L3 abc abd acd ace bcd 自连接 L3 L3abc和abd得到abcdacd和ace得到acde修剪 ade不在L3中 删除acdeC4 abcd 提高Apriori效率的方法 基于Hash的项集计数 如果一个k 项集在hash tree的路径上的一个计数值低于阈值 那他本身也不可能是频繁的 减少交易记录 不包含任何频繁k 项集的交易也不可能包含任何大于k的频繁集分割 一个项集要想在整个数据库中是频繁的 那么他至少在数据库的一个分割上是频繁的 采样 在给定数据的子集上挖掘 使用小的支持度 完整性验证方法动态项集计数 在添加一个新的候选集之前 先估计一下是不是他的所有子集都是频繁的 Apriori够快了吗 性能瓶颈 Apriori算法的核心 用频繁的 k 1 项集生成候选的频繁k 项集用数据库扫描和模式匹配计算候选集的支持度Apriori的瓶颈 候选集生成巨大的候选集 104个频繁1 项集要生成107个候选2 项集要找尺寸为100的频繁模式 如 a1 a2 a100 你必须先产生2100 1030个候选集多次扫描数据库 如果最长的模式是n的话 则需要 n 1 次数据库扫描 6 4数据挖掘的聚类算法 6 4 1聚类分析的概念与分类聚类分析概念聚类分析方法的分类 6 4数据挖掘的聚类算法 6 4 2聚类分析中两个对象之间的相异度计算方法区间标度变量计算方法二元变量计算方法标称型 序数型和比例标度型变量计算方法混合类型的变量计算方法 6 4数据挖掘的聚类算法 6 4 3划分方法典型的划分方法 k 平均和k 中心点基于簇的重心技术 k 平均方法基于有代表性的对象的技术 k 中心点方法大型数据库中的划分方法 基于选择的K 中心点CLARANS方法 6 4数据挖掘的聚类算法 6 4 4层次方法凝聚的和分裂的层次聚类凝聚层次聚类方法AGNES分裂层次聚类方法DIANA利用层次方法的平衡迭代归约和聚类综合的层次聚类方法BIRCH利用代表点聚类一种新颖的层次聚类算法CURE一个利用动态模型的层次聚类算法动态模型的聚类法chameleon 变色龙 6 4数据挖掘的聚类算法 6 4 5基于密度的方法一个基于高密度连接区域的聚类方法DBSCAN聚类方法通过对象排序识别聚类结构OPTICS聚类分析方法基于密度分布函数的聚类基于一组密度分布函数的聚类算法DENCLUE 6 4数据挖掘的聚类算法 6 4 6基于网格的方法统计信息网络STING是一种基于网格的多分辨率聚类技术聚类高维空间CLIQUE clusteringinquest CLIQUE 聚类算法6 4 7基于模型的聚类方法增量概念聚类算法COBWEB6 4 8模糊聚类算法 6 5数据挖掘的统计分析算法 6 5 1辨别方法6 5 2回归模型6 5 3优点与缺点 6 6数据挖掘的品种优化算法 6 6 1品种优化6 6 2品种优化算法 6 7数据挖掘的进化算法 6 7 1遗传算法如何工作优缺点6 7 2神经网络算法如何工作无指导的学习竞争学习自组织特征映射模型优缺点 6 7数据挖掘的进化算法 神经网络模型 第7章非结构化数据挖掘 本章内容 7 1Web数据挖掘7 2空间群数据挖掘7 3多媒体数据挖掘 7 1Web数据挖掘 7 1 1非结构化数据源Web数据挖掘的难点对数据来源分析异构数据环境半结构化的数据结构解决半结构化的数据源问题文本总结XML与Web数据挖掘技术XML的产生与发展XML的主要特点 7 1Web数据挖掘 7 1 1非结构化数据源XML在Web数据挖掘中的应用两个或更多异质数据库之间进行通信的应用大部分处理负载从Web服务器转到Web客户端的应用Web客户端将同样的数据以不同的浏览形式提供给不同的用户的应用需要智能Web代理根据用户个人的需要裁减信息内容的应用 7 1Web数据挖掘 7 1 2Web挖掘分类 Web挖掘三种方法比较 7 1Web数据挖掘 Web挖掘的基本构架 7 1Web数据挖掘 7 1 3Web内容挖掘信息检索 informationretrieve IR 方法数据库方法7 1 4Web结构挖掘Page Rank方法7 1 5Web访问挖掘对Web日志进行清洗 过滤和转换以及剔除无关记录采用统计学 模式识别 人工智能 数据库数据挖掘等领域的成熟技术在Web的使用记录中挖掘知识Web使用挖掘中的模式分析 7 1Web数据挖掘 7 1 6利用Web日志的聚类算法客户群体的模糊聚类算法用户访问兴趣的算法客户群体聚类的Hamming距离算法基于模糊理论的Web页面聚类算法Web页面聚类的Hamming距离算法 7 1Web数据挖掘 电子商务中的Web挖掘电子商务中Web挖掘的作用电子商务中Web挖掘的基本问题电子商务中的数据挖掘工具文本信息挖掘工具用户访问模式挖掘工具用户导航行为挖掘工具综合性的Web分析工具 7 2空间群数据挖掘 7 2 1空间群数据挖掘概念从空间数据中抽取隐含的知识 空间关系 空间及与非空间之间的有意义的特征或模式 7 2 2空间群数据挖掘分类空间检索空间拓扑叠加分析空间模拟分析 7 2空间群数据挖掘 7 2 3空间数据挖掘的体系结构 7 3多媒体数据挖掘 7 3 1多媒体数据挖掘的概念7 3 2多媒体数据挖掘的分类图像数据挖掘视频数据挖掘音频数据挖掘 7 3多媒体数据挖掘 7 3 3多媒体数据挖掘的体系结构 第8章离群数据挖掘 本章内容离群数据挖掘概念离群数据挖掘分类离群数据挖掘算法市场营销离群数据的特点 第8章离群数据挖掘 8 1离群数据挖掘的概念8 2离群数据挖掘的分类基于统计学基于距离的方法基于偏移高维数据的离群数据探测基于规则的分类离群数据挖掘方法基于密度 density based 的离群挖掘方法 8 3离群数据挖掘的算法 8 3 1基于统计的方法8 3 2基于距离的离群数据方法基于距离的离群数据定义基于距离的离群数据挖掘的算法分类及算法描述基于距离的算法的改进8 3 3基于偏离的离群数据挖掘序列离群数据技术OLAP数据立方体技术 8 3离群数据挖掘的算法 8 3 4高维数据的离群数据挖掘8 3 5基于小波的离群数据挖掘时序数据的离群数据挖掘基于聚类的离群数据CL 8 4市场营销离群数据挖掘 8 4 1市场营销离群数据挖掘特点8 4 2基于分形的市场营销离群数据挖掘模型几个定义 第9章数据挖掘语言与工具选择 本章内容9 1数据挖掘语言及其标准化9 2数据挖掘研究热点9 3数据挖掘工具的选择 9 1数据挖掘语言及其标准化 9 1 1数据挖掘语言分类 9 1数据挖掘语言及其标准化 9 1 1数据挖掘语言分类数据挖掘查询语言 5种数据挖掘原语定义 任务相关数据原语被挖掘的知识的种类原语背景知识原语兴趣度测量原语被发现模式的表示和可视化原语 9 1数据挖掘语言及其标准化 9 1 1数据挖掘语言分类数据挖掘建模语言头文件 aheader 数据模式 adataschema 数据挖掘模式 adataminingschema 预言模型模式 apredictivemodelschema 预言模型定义 definitionsforpredictivemodels 全体模型定义 definitionsforensemblesofmodels 选择和联合模型 全体模型的规则 rulesforselectingandcombiningmodelsandensemblesofmodels 异常处理的规则 rulesforexceptionhandling 9 1数据挖掘语言及其标准化 9 1 1数据挖掘语言分类通用数据挖掘语言数据挖掘模型 DataMiningModel DMM 预言联接操作 PredicationJoinOperation OLEDBforDM模式行集合 SchemaRowsets 9 1 2分析与评价 9 2数据挖掘的研究热点 网站的数据挖掘生物信息或基因的数据挖掘文本的数据挖掘 9 3数据挖掘工具的选择 9 3 1评价数据挖掘工具的优劣指标数据准备数据访问算法与建模模型的评价和解释用户界面 9 3数据挖掘工具的选择 9 3 2通用数据挖掘产品与工具POLYANALYSTIBMDB2lntelligentMiner和并行可视化探索者PVEDBMinerBO的BusinessMinerSPSS股份公司 SPPSCHAID SAS研究所股份公司 SAS JMP NeuralWare股份公司信息发现股份公司 IDIS RightPoint公司的数据挖掘工具DataCruncherDataMind公司 DataMind专业版 DataMindCruncher Pilot软件股份公司 Pilot发现服务器 Angoss国际有限公司 KnowledgeSEEKER SiliconGraphics计算机系统公司 MineSet 商务项目公司 商务挖掘器 Cognos软件公司 Scenario 思维机器公司 Darwin 9 3数据挖掘工具的选择 9 3 3国内的数据挖掘产品与工具菲奈特一融通公司广州华工明天科技有限公司复旦大学数据采掘工具ARMiner9 3 4数据可视化工具的选择高级可视化系统公司 AVS Express Alt