数据分析方法及模型.ppt

*贝叶斯网与概率推理精确推理算法精度高，但是当网络节点众多并且连接稠密时，它们的计算复杂度高，不适用近似推理算法降低了对精度的要求，以求在限定的时间内得到一个近似解随机抽样算法是一种常用的近似推理算法，其基本思想是从某个概率分布随机抽样，生成一组样本，然后从样本出发近似估计要计算的量随机抽样算法可以分为重要性抽样算法和马尔科夫链蒙特卡洛算法（MCMC算法）两种算法的主要区别在于重要性抽样算法产生的样本之间相互独立，而MCMC算法产生的样本却互相关联第191页,共200页，2024年2月25日，星期天*基于单元（Cell-Based）算法相关概念性质4：①若Cx,y中的对象数M，那么Cx,y中的对象都不异常②若Cx,y中的对象数+L1(Cx,y)中的对象数M，那么Cx,y中的对象都不异常③若Cx,y中的对象数+L1(Cx,y)中的对象数+L2(Cx,y)中的对象数?M，那么Cx,y中的每一个对象都是异常第159页,共200页，2024年2月25日，星期天*基于单元（Cell-Based）算法FM算法基于单元的算法分为两个：FindAlloutsM（FM）和FindAlloutsD（FD）FM适用于检测存储于主存的数据集中的异常FM算法使用性质1~性质4来检测异常和非异常这种检测是以单元-单元为基础，而不是以对象-对象为基础，从而可以将大量不可能是异常的对象排除只有不满足性质4①~③的单元内的对象才进行对象-对象的处理第160页,共200页，2024年2月25日，星期天*基于单元（Cell-Based）算法FM算法描述输入：数据对象集合D，邻域半径dmin，一个异常的dmin邻域内最多对象数目M输出：D中的异常对象步骤：（1）forq=1tomcountq=0//m是单元数，单元的对象计数器清零（2）将D中每个对象p映射到合适的单元Cq中，存储p，countq+1（3）检测各个单元，ifcountqM，then将Cq标记为红色//Cq中的所有对象都不是异常（4）对每一个红色单元Cr，将它的每一个L1邻域标记为粉红色，提供未曾被标记为红色的邻域（5）for每一个非空的白色单元Cw（未被标记颜色）第161页,共200页，2024年2月25日，星期天*基于单元（Cell-Based）算法FM算法描述（5.1）（5.2）ifcountw2M，then标记Cw为粉红色（5.3）else（5.3.1）（5.3.2）ifcountw3?M，then输出Cw中的所有对象//都是异常（5.3.3）elseforCw中的每一个对象pcountp=countw2forL2(Cw)中的每一个对象ifthencountp+1ifcountp?Mthen输出p//p是异常Cw中的对象p必须与Cw的L2邻域中的对象p?比较，决定有多少个p?在p的dmin邻域内第162页,共200页，2024年2月25日，星期天*基于单元（Cell-Based）算法FM算法描述设M=10在k=2维的情况下，FM算法的时间复杂性为O(m+N)m是单元数，N是对象数在实际中，有很多单元都是红色和粉红色，白色单元较少因此，对象-对象的比较也较少，算法所需的时间也会减少第163页,共200页，2024年2月25日，星期天*基于单元（Cell-Based）算法FD算法FD算法适用于适用于处理大型、磁盘数据集对于大型磁盘数据集，无法将整个数据集存储于主存中，因此，将数据集分页，各页依次读入主存处理提高效率的关键在于使读页的次数或遍历数据库的次数最小化在基于单元的算法中，有两个阶段需要读页：1）初始映射阶段：在算法FM的（2），每个对象被映射到合适的单元中遍历数据库一次2）对象成对比较阶段：在算法FM的5.3.3步，每一对对象（p，p?）的比较可能要求读一页p、p’不一定相邻I/O次数多第164页,共200页，2024年2月25日，星期天*基于单元（Cell-Based）算法FD算法FD算法的方法：挑选对象子集保存在主存中，将磁盘上的数据页分类各类数据页按一定顺序读入，从而使读页次数最小化被挑选的子集由映射到白色单元中的对象（白色对