基于团分划改进的ips算法

基于团分划改进的ips算法

ID:35062738

大小:938.59 KB

页数:35页

时间:2019-03-17

基于团分划改进的ips算法_第1页
基于团分划改进的ips算法_第2页
基于团分划改进的ips算法_第3页
基于团分划改进的ips算法_第4页
基于团分划改进的ips算法_第5页
资源描述:

《基于团分划改进的ips算法》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

1、分类号:O21单位代码:10190研究生学号:201312020密级:无硕士学位论文基于团分划改进的IPS算法AnImprovedIPSAlgorithmbyPartitioningCliques研究生姓名:孙聚波专业:统计学指导教师姓名:徐平峰指导教师职称:副教授2016年4月长春工业大学硕士学位论文原创性声明本人郑重声明:所呈交的硕士学位论文,《基于团分划改进的IPS算法》是本人在指导教师的指导下,独立进行研究工作所取得的成果。除文中已经注明引用的内容外,本论文不包含任何其他个人或集体已经发表或撰

2、写过的作品成果。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。作者签名:年月日长春工业大学硕士学位论文版权使用授权书本学位论文作者及指导教师完全了解“长春工业大学硕士学位论文版权使用规定”,同意长春工业大学保留并向国家有关部门或机构送交学位论文的复印件和电子版,允许论文被查阅和借阅。本人授权长春工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。作者签名:年月日校内指导教师签名

3、:年月日摘要图模型用图直观地、清晰地表达变量间的结构关系,并将复杂的大型全局问题分解为相对简单局部问题,这样不仅极大地减少推理计算时的计算量,而且也将提高推理的功效。在图模型的各种推理计算中,参数估计和模型选择是最核心的两个问题。本文将研究完全数据时的极大似然估计和不完全数据情形下的模型选择。图模型的极大似然估计一般采用迭代比例拟合(IPS)算法。由于IPS算法的稳定性和易于执行性,自从DemingandStephan首次提出之后,陆续有许多学者从几何解释、收敛性、空间复杂度、时间复杂度等许多方面进行

4、了深入研究和改进。然而,许多实际问题往往结构复杂、涉及的变量众多,此时IPS算法复杂度较高。本文从计算局部化的角度对IPS算法作了进一步研究。受Xu等人发表在JCGS的关于高斯图模型中利用团分划进行局部计算的启发,我们给出了在多项分布图模型中基于团分划进行局部计算的理论。由构成该理论的2个定理知,基于团分划的局部计算没有利用变量间的条件独立关系,这样即使图结构非常复杂,团分划策略仍然有效,这是前辈学者的诸多算法所不具备的优点。进一步,提出了基于团分划进行局部计算的算法,即IPSP算法。在该算法中,先将

5、团集分划为几个非重叠和非空的块,然后在每个块中局部地、逐次地调整团边缘。找到使IPSP算法胜过IPS算法的团分划不难,但是整体最优的分划是很难确定地找到。本文采用模拟退火(SA)算法来寻找到一个近似最优分划。此外,我们还证明了n元圈图模型的最优分划为连续二等分划。由于团分划的策略没有利用图的结构和模型的条件独立关系,而TehandWelling提出的UPS-JT算法中利用连接树进行局部计算的策略不具备此特性,因此团分划能提高UPS-JT算法中的拟合步的计算速度,进而提高UPS-JT算法的整体计算效率,

6、本文称之为UPSP-JT算法。然后,本文模拟比较了IPS、IPSP、UPS-JT、UPSP-JT这几种算法的算法效率,我们发现使用连接树的UPS-JT算法和UPSP-JT算法优于没使用连接树的IPS算法和IPSP算法,并且IPSP算法和UPSP-JT算法运行的分别比IPS算法和UPS-JT算法更快,所以基于团分划的局部计算能有效地提高计算效率。含不完全数据的模型选择问题,传统的方法是先在备选模型下求极大似然估计,而后采用信息准则(例如BIC等)选择模型。但Jiang等人的JASA论文指出,传统的方法可

7、能不会收敛,甚至可能选错模型,并提出了在一定条件下具有收敛性的E-MS算法。本文将利用Jiang等人提出的E-MS算法,考虑不完全数据情形下图模型的模型选择问题。但由于E-MS其嵌套计算的特性,计算量随变量个数的增加迅速的增大,因而本文在最大化Q函数中将采用IPSP算法提高计算速度,同时进行了模拟研究。本文结构安排如下。第一章中,简要介绍了研究背景和IPS算法发展的历史和现状,以及本文的组织结构安排。第二章中,简要介绍了一些预备知识,即图模型的一些定义、概念和记号。第三章中,首先简介了属性数据的列联表

8、和经典的IPS算法。I其次给出了基于团分划进行局部计算的理论结果和算法(IPSP算法),以及利用模拟退火算法求团集的近似最优分划中进行MH抽样的算法(MHDP算法),并证明了图模型的一种基础结构n元圈的最优分划为连续二等分划。然后利用团分划策略改进了UPS-JT算法,并通过模拟实验比较了IPS、IPSP、UPS-JT和UPSP-JT这四种算法的计算效率。第四章中,简介了不完全数据情形下模型选择的较新理论成果,即E-MS算法,并分析了其复杂度,同时还进行了

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。