电子商务新进展-.ppt

电子商务新进展 数据挖掘 合肥工业大学管理学院刘业政等liuyezheng 2020年2月20日 电子商务新进展 数据挖掘 课外文献阅读 1 FrankHoppner AssociationRules 299 3192 LiorRokach AsurveyofClusteringAlgorithms 269 2983 LiorRokach OdedMaimon ClassificationTrees 149 1744 JerzyW Grzymala Busse RuleInduction 249 2655 ArminShmilovici SupportVectorMachines 231 247In O Maimon L Rokach eds DataMiningandKnowledgeDiscoveryHandbook 2nded 2010 Springer 参考书推荐 2020年2月20日 电子商务新进展 数据挖掘 2020年2月20日 电子商务新进展 数据挖掘 数据挖掘 基本概念Apriori算法 关联规则发现 K means算法 聚类 决策树神经网络支持向量机遗传算法 2020年2月20日 电子商务新进展 数据挖掘 DefinitionofKDD DM KnowledgeDiscoveryinDatabases KDD isanautomatic exploratoryanalysisandmodelingoflargedatarepositories KDDistheorganizedprocessofidentifyingvalid novel useful andunderstandablepatterns 模式 fromlargeandcomplexdatasets DataMining DM isthecoreoftheKDDprocess involvingtheinferringofalgorithmsthatexplorethedata developthemodelanddiscoverpreviouslyunknownpatterns Themodelisusedforunderstandingphenomenafromthedata analysisandprediction 2020年2月20日 电子商务新进展 数据挖掘 TheKDDProcess understandanddefinethegoalsoftheend userandtheenvironmentinwhichtheknowledgediscoveryprocesswilltakeplace findingoutwhatdataisavailable obtainingadditionalnecessarydata andthenintegratingallthedatafortheknowledgediscoveryintoonedataset includingtheattributesthatwillbeconsideredfortheprocess handlingmissingvaluesandremovalofnoiseoroutliers includingdimensionreduction suchasfeatureselectionandextractionandrecordsampling andattributetransformation suchasdiscretizationofnumericalattributesandfunctionaltransformation 1 decidingonwhichtypeofDataMiningtouse forexample classification regression orclustering 2 selectingthespecificmethodtobeusedforsearchingpatterns 3 implementingtheDataMiningalgorithm evaluatingandinterpretingtheminedpatterns rules reliabilityetc focusingonthecomprehensibilityandusefulnessoftheinducedmodel incorporatingtheknowledgeintoanothersystemforfurtheraction Challenge Dynamic incrementalmining 2020年2月20日 电子商务新进展 数据挖掘 TaxonomyofDataMiningMethods 2020年2月20日 电子商务新进展 数据挖掘 TaxonomyofDataMiningMethods Verification oriented thesystemverifiestheuser shypothesis includingthemostcommonmethodsoftraditionalstatistics likegoodnessoffit 拟合优度 test testsofhypotheses 假设检验 e g t testofmeans andanalysisofvariance ANOVA 方差分析或F 检验 Discovery oriented thesystemfindsnewrulesandpatternsautonomously predictionmethodsVSdescriptionmethods supervisedlearning 有导师学习 VSunsupervisedlearning 2020年2月20日 电子商务新进展 数据挖掘 KDDGoals 归纳总结 Induction Summarization 从泛化的角度总结数据 即从低层次数据抽象出高层次的描述的过程 主要方法 归纳 泛化 关联规则 AssociationRules 关联规则的形式为A B A为前件 B为后件 Day Friday and Product Nappies Product Beer 为一典型关联规则A为满足前件的对象集 B为满足后件的对象 N为全部对象集 典型方法 Apriori算法 2020年2月20日 电子商务新进展 数据挖掘 KDDGoals 分类 Classification 等价关系 判别 按类标签 为数据库中的某属性集 一般仅包含一个属性 对数据库中的对象进行分类 具有相同标签值或标签值在指定区间内的对象属于同类 分类规则是判断某个对象属于某类的充分条件即对象具有某类的属性时则表示该对象属于该类 其规则形式一般为IFLogicExpThenA类ElseB类 主要方法 逻辑回归 判别分析 决策树 ANN 粗糙集 SVM等 聚类 Clustering 相容关系 聚类也叫分段 就是将数据库中的实体分成若干组或簇 每簇内的实体是相似的 规则形式为IFO1与O2相似ThenO1 O2在同一簇 对象相似的判断方法有多种如距离法 典型方法 K means 2020年2月20日 电子商务新进展 数据挖掘 KDDGoals 特征规则 CharacteristicRules 特征规则是刻划某个概念的特征的断言 它相当于分类规则的逆命题 例如病症是某种疾病的特征 规则一般形式是 IFA类Then特征表达式 序列模式 SequencePattern 它与关联规则相似 不同之处在于事件的发生有前后顺序 该规则一般形式为 At i Bt j 其中t i t j 例如序贯规则JacketandTie Shoes表示客户在买了 夹克 和 领带 之后就会买 鞋 2020年2月20日 电子商务新进展 数据挖掘 KDDGoals 异常探测 OutlierDetection 探测测量值与期望值之间的差别并对其进行解释 噪音or小概率事件 常有三种偏离类型 随时间偏离 以历史值为期望值 与标准偏离 以标准值为期望值 与预测偏离 以预测值为期望值 回归 Regression 根据历史数据拟合一函数将属性集映射到相应的值集 回归可以看作一种分类 区别是分类的类标签值是离散的 而回归是连续的 2020年2月20日 电子商务新进展 数据挖掘 KDDGoals 2020年2月20日 电子商务新进展 数据挖掘 DataMiningwithintheDSS 2020年2月20日 电子商务新进展 数据挖掘 数据挖掘 基本概念Apriori算法 关联规则发现 K means算法 聚类 决策树神经网络支持向量机遗传算法 2020年2月20日 电子商务新进展 数据挖掘 关联规则发现 Apriori算法 TheApriorimethod ProposedbyAgrawal Srikant1994Majoridea AsubsetofafrequentitemsetmustbefrequentE g if beer diaper nuts isfrequent beer diaper mustbe Anyoneisinfrequent itssupersetcannotbe Apowerful scalablecandidatesetpruningtechnique Itreducescandidatek itemsetsdramatically fork 2 2020年2月20日 电子商务新进展 数据挖掘 关联规则发现 Apriori算法 ProcedureFindthefrequentitemsets thesetsofitemsthathaveminimumsupport Apriori Asubsetofafrequentitemsetmustalsobeafrequentitemset i e if A B isafrequentitemset both A and B shouldbeafrequentitemsetIterativelyfindfrequentitemsetswithcardinalityfrom1tok k itemset Usethefrequentitemsetstogenerateassociationrules 2020年2月20日 电子商务新进展 数据挖掘 关联规则发现 Apriori算法 2020年2月20日 电子商务新进展 数据挖掘 数据挖掘 基本概念Apriori算法 关联规则发现 K means算法 聚类 决策树神经网络支持向量机遗传算法 2020年2月20日 电子商务新进展 数据挖掘 聚类 K means算法 聚类分析是把研究对象按照一定的规则分成若干类别 并使类之间的差别尽可能地大 类内的差别尽可能地小 换句话说 使类间的相似性最小 而类内的相似性最大 聚类方法的核心问题是样品间的相似性度量 通常用距离来度量 2020年2月20日 电子商务新进展 数据挖掘 聚类 K means算法 聚类分析中的常用距离 1 欧氏 Euclidean 距离 2 绝对距离 3 Minkowski距离显然当m 1时就是绝对距离 m 2时就是欧氏距离 在实际应用时常分析两个样品之间的相对距离 这时需要对样品数据进行标准化处理 然后用标准化数据计算距离 2020年2月20日 电子商务新进展 数据挖掘 聚类 K means算法 对于给定的n个样品 先粗略地形成k k n 个分割 使得每个分割对应一个类 每个类至少有一个样品并且每个样品精确地属于一个类 然后按照某种原则进行修正 直至分类比较合理为止 具体步骤如下 1 聚点的选择 聚点是一批有代表性的样品 它的选择决定了初始分类 首先确定分类数k 然后选择k个有代表性的样品作为每个类的初始元素即聚点 聚点可由用户根据经验选择 也可随机选择 或将全部样品人为地或随机地分成k类 以每类的重心作为聚点 2020年2月20日 电子商务新进展 数据挖掘 聚类 K means算法 2 初始聚类 有了聚点集合后 可根据下列最靠近原则实现初始分类 若对于某样品x出现 则x任意归于Gi 0 或Gj 0 类 这样就得到了样品空间的初始分类 2020年2月20日 电子商务新进展 数据挖掘 聚类 K means算法 3 迭代过程设聚类形成的一个分类为则可从G m 出发计算新的聚点集合L m 1 一般可以以G m 中各类的重心作为新的聚点 其中根据新的聚点集 对样品空间重新聚类 形成新的分类 其中 2020年2月20日 电子商务新进展 数据挖掘 聚类 K means算法 4 迭代终止随着m的增大 分类趋于稳定 当G m 1 G m 或在一定的精度范围内近似有G m 1 G m 则递推过程结束 2020年2月20日 电子商务新进展 数据挖掘 数据挖掘 基本概念Apriori算法 关联规则发现 K means算法 聚类 决策树神经网络支持向量机遗传算法 2020年2月20日 电子商务新进展 数据挖掘 决策树 示例 叶结点 2020年2月20日 电子商务新进展 数据挖掘 决策树 概念 决策树学习是以实例为基础的归纳学习算法 所谓决策树是一个类似流程图的树结构 其中树的内结点对应属性或属性集 每个分枝表示检验结果 属性值 树枝上的叶结点代表所关心的因变量的取值 类标签 最顶端的结点称为根结点 决策树学习采用自顶向下的递归方式 在决策树的内部结点进行属性值比较并根据不同的属性值判断从该结点向下的分支 在叶结点得到结论 从根结点到每个叶结点都有唯一的一条路径 这条路径就是一条决策 规则 当经过一批训练实例集的训练产生一颗决策树 那么该决策树就可以根据属性的取值对一个未知实例集进行分类 2020年2月20日 电子商务新进展 数据挖掘 决策树 CLS学习算法 概念学习系统CLS Hunt 从一颗空的决策树出发 添加新的判定结点来改善原来的决策树 直到该决策树能够正确地将训练实例分类为止 产生根节点T T包含所有的训练样本 如果T中的所有样本都是正例 则产生一个标有 1 的节点作为T的子节点 并结束 如果T中的所有样本都是反例 则产生一个标有 1 的节点作为T的子节点 并结束 选择一个属性A 如何选 根据该属性的不同取值v1 v2 vn将T中的训练集划分为n个子集 并根据这n个子集建立T的n个子节点T1 T2 Tn 并分别以A vi作为从T到Ti的分支符号 以每个子节点Ti为根建立新的子树 2020年2月20日 电子商务新进展 数据挖掘 决策树 2020年2月20日 电子商务新进展 数据挖掘 决策树 ID3学习算法 ID3算法 Quinlan ID3算法对CLS做了两方面的改进 1 增加窗口技术 2 以信息熵的下降速度 信息增益 作为测试属性选择标准 窗口技术 对于训练集很大的情形可选择其某个子集 称为窗口 构造一棵决策树 如果该决策树对训练集中的其它样本的判决效果很差 则扩大窗口 选择不能被正确判别的样本加入到窗口中 再建立一个新的决策树 重复这个过程得到最终的决策树 显然不同的初始窗口会产生不同的决策树 2020年2月20日 电子商务新进展 数据挖掘 决策树 ID3学习算法 信息增益 设决策树根结点的样本数据为X x1 x2 xn 称X的两个训练子集PX 对应类标签为1 和NX 对应类标签为 1 为正例集和反例集 并记正例集和反例集的样本数分别为P和N 则样本空间的信息熵为假设以随机变量A作为决策树根的测试属性 A具有k个不同的离散值v1 v2 vk 它将X划分为k个子集 且假设第j个子集中包含Pj个正例 Nj个反例 则第j个子集的信息熵为I Pj Nj 2020年2月20日 电子商务新进展 数据挖掘 决策树 ID3学习算法 以A为测试属性的期望信息熵为以A为根节点的信息增益是 Gain A I P N E A ID3的策略就是选择信息增益最大的属性作为测试属性 ID3的问题 测试属性的分支越多 信息增益值越大 但输出分支多并不表示该测试属性有更好的预测效果 2020年2月20日 电子商务新进展 数据挖掘 决策树 C4 5学习算法 信息增益率 其中 目前一种比较流行的决策树算法C4 5算法就是以信息增益率作为测试属性的选择条件 生成的决策树往往过大 不利于决策时的应用 需要对其剪枝 Pruning 请参阅相关文献 决策树 算例 2020年2月20日 电子商务新进展 数据挖掘 确定根结点I P N 10 16log 10 16 6 16log 6 16 5 8log5 3 8log3 3 0 9544E A0 1 2 4 8log 4 8 4 8log 4 8 1 2 6 8log 6 8 2 8log 2 8 0 9056E A1 1 3 8log3 0 4084E A2 1 3 16log3 0 9056E A3 3 5 8log5 3 8log3 0 9544因此选A1作为起始根结点 A3没有改变任何信息量 无分类价值 可以删除 2020年2月20日 电子商务新进展 数据挖掘 决策树 算例 确定子树根结点I P N 6 8log6 8 2 8log2 8 0 8112E A0 E A2 1 2 0 5E A3 2 3 4log3 0 8112A0 A2具有相同的分类能力 任取一个均可 2020年2月20日 电子商务新进展 数据挖掘 决策树 算例 2020年2月20日 电子商务新进展 数据挖掘 数据挖掘 基本概念Apriori算法 关联规则发现 K means算法 聚类 决策树神经网络支持向量机遗传算法 2020年2月20日 电子商务新进展 数据挖掘 神经网络 神经网络 ArtificialNeuralNetworks 是由具有适应性的简单单元组成的广泛并行互连的网络 它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应 T Koholen 神经网络分为前向型 反馈型 随机型以及自组织型 我们重点介绍前向型网络及其学习算法 2020年2月20日 电子商务新进展 数据挖掘 基本神经元及感知机模型 神经网络 wj1 wji wjn yj f iwijxi j x1 xi xn 2020年2月20日 电子商务新进展 数据挖掘 神经网络 神经元函数f的选择线性函数 f x x带限的线性函数 为最大输出 阈值型函数 sigmoid函数 2020年2月20日 电子商务新进展 数据挖掘 神经网络 感知机学习算法 选取f为阈值函数 学习权值向量w 1 初始化 将权值向量和阈值赋予随机量 t 0 2 连接权的修正 设训练样本的输入为x1 xi xn 期望输出为yj 1 进行如下计算 计算网络输出 1 y t f iwij t xi t j t 计算期望输出与实际输出的误差 e t yj y t 若e 0 则说明当前样本输出正确 不必更新权值 否则更新权值和阈值wij t 1 wij t yjxi t j t 1 j t yjt t 1 为学习率 3 返回 2 重复所有的训练样本直到所有的样本输出正确 2020年2月20日 电子商务新进展 数据挖掘 神经网络 多层前向神经网络 包括一个输入层 一个输出层以及多层隐单元 x1 xi xI y1 yk yK 输入层 隐含层 输出层 u1 ui uI v1 vj vJ wji wkj 2020年2月20日 电子商务新进展 数据挖掘 神经网络 隐含层的接受与投射 以隐含层第j个神经元为例 接受 第j个神经元的值来自于前一层网络 本例是输入层 输出值的加权和 即netj iwjiui 投射 将第j个神经元的值经过变换f netj 作为下一层网络 本例是输出层 的输入 一般f x 1 1 e x 因此可得到yk jwkjf netj 上述过程一直持续到所有的输出单元得到输出为止 最后一层的输出就是网络的输出 因此 神经网络是一个黑匣子 2020年2月20日 电子商务新进展 数据挖掘 神经网络 BP算法 BP算法的核心是确定W的调节规则 学习规则 使实际的输出Y1 t 尽可能接近期望的输出Y t 误差函数 对于每种输入模式特征矢量 x1 x2 xI 都有对应的输出矢量 y1 y2 yK 作为训练网络的输出参考基准 如果用符号Xp表示第p个输入模式特征矢量 用符号Yp表示对应的第p个输出基准矢量 在训练时 同时按输入输出矢量对 Xp Yp 给出训练集 p 1 P 对于每个Xp 按照神经元的输入输出公式 一个个一层层地求出网络的实际输出Y1p 则误差函数定义为 2020年2月20日 电子商务新进展 数据挖掘 神经网络 权重调节策略 学习的目标是使E最小或不大于规定的误差 从理论上可用求极值的方法获得权值调整的一种典型规则 其他最流行的网络结构 径向基函数 RBF 神经网络 自组织映射 SOM Hopfield网络等 Matlab提供了一套神经网络工具箱 NeuralNetworksToolbox 其中包含了一组new函数 用以创建各种类型的神经网络 2020年2月20日 电子商务新进展 数据挖掘 神经网络 newcf cascade forwardbackpropagationnetwork newelm Elmanbackpropagationnetwork newff feed forwardbackpropagationnetwork newfftd feed forwardinput delaybackpropnetwork newgrnn generalizedregressionneuralnetwork newhop Hopfieldrecurrentnetwork newlvq learningvectorquantizationnetworknewpnn probabilisticneuralnetwork newrb radialbasisnetwork newrbe exactradialbasisnetwork newsom self organizingmap 2020年2月20日 电子商务新进展 数据挖掘 神经网络 MatLab工具箱之多层前向BP网络示例P 012345678910 实际输出 已学习 plot P T P Y o 2020年2月20日 电子商务新进展 数据挖掘 机器学习 神经网络 2020年2月20日 电子商务新进展 数据挖掘 数据挖掘 基本概念Apriori算法 关联规则发现 K means算法 聚类 决策树神经网络支持向量机遗传算法 2020年2月20日 电子商务新进展 数据挖掘 支持向量机 支持向量机 SupportVectorMachines SVM 是20世纪90年代在统计学习理论的基础上提出的一种新的学习算法 其核心思想是将统计学习理论的结构风险最小化原则引入分类问题的求解 针对线性可分问题 就是在高维空间中寻找一个超平面分割两类 使分类错误率最小化 SVM在数学上可归结为一个求解不等式约束条件的正定二次规划问题 2020年2月20日 电子商务新进展 数据挖掘 支持向量机 margin与支持向量 设样本集为U x1 x2 xl m维空间中的l个向量 类别空间Y 1 1 xi为输入向量 对应的类标签为yi 1或 1 若样本集是线性可分的 则存在超平面H wx b 0使得 1 当wxi b 1时 yi 1 2 当wxi b 1时 yi 1其中 w为权值向量 b为偏离值 统一 1 2 得 yi wxi b 1对于样本集的任一向量 点 xi 其到超平面H的距离为 2020年2月20日 电子商务新进展 数据挖掘 支持向量机 那么 margin的大小可按下式计算 margin d d d min di i 1 2 l yi 1 d min di i 1 2 l yi 1 若存在样本点xi使得wxi b 1 则称此向量xi为支持向量 此时 d d 1 w margin 2 w 分类模型 寻求最优超平面H 使得margin最大 因此分类问题转为二次凸规划问题 支持向量机 图中H为最优分类超平面 H 1和H 1为最大间隔超平面 H 1和H 1上的点为支持向量 2020年2月20日 电子商务新进展 数据挖掘 2020年2月20日 电子商务新进展 数据挖掘 支持向量机 线性不可分 可引入核函数将线性不可分问题转换为高维空间的线性可分问题 常见核函数有 d次多项式函数高斯径向基函数神经网络核函数 2020年2月20日 电子商务新进展 数据挖掘 数据挖掘 基本概念Apriori算法 关联规则发现 K means算法 聚类 决策树神经网络支持向量机遗传算法 2020年2月20日 电子商务新进展 数据挖掘 遗传算法 遗传算法 GeneticAlgorithm GA 是一种借鉴生物界自然选择和自然遗传机制的高度并行 随机 自适应搜索算法 它利用结构化的随机交换技术组合群体中各个结构中最好的生存因素 形成最佳代码串并使之一代一代地进化 最终获得满意的优化结果 其基本构成要素有染色体编码 适应度函数 遗传算子 遗传 交叉 变异 以及相关的运行参数 种群规模 20 100 进化代数 100 500 交叉概率Pc 0 4 0 99 变异概率Pm 0 0001 0 1 2020年2月20日 电子商务新进展 数据挖掘 遗传算法 遗传算法基本步骤 1 确定遗传算法的有关参数 群体规模N 最大代数M 交叉概率Pc 变异概率Pm 停机准则 初始化种群 随机产生N条表示可能方案集的染色体 2 是否满足停机准则 若是 终止 3 计算群体中每个个体的适应值 4 复制 根据适应度