两元矩阵聚类算法研究

《两元矩阵聚类算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：TP301密级：单位代码：学号：10422200720622⑧∥菇办；博士学位论文论文题目：两元矩阵聚类算法研究STUDlES0NALGORITHNSFORCLUSTERlNGOFBlNARYMATRlCES作者姓名刘培强学院名称计算机科学与技术学院专业名称计算机软件与理论指导合作教师导师朱大铭教授2013年4月15日STUDIESONALGOlUTHMSFoRCLUSTERINGOFBINARYMATRICESbyLiuPeiqiangSupervisor：ProfessorZhuDamingForthedegreeofDoctorofPhilosophy

2、ShandongUniversity,Ji’nan，Shandong，P．R．ChinaApril15，2013原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。论文作者签名：锄彳次办’，关于学位论文使用授权的声明本人同意学校保留或向国家有关部门或机构送交论文的印刷件和电子版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有

3、关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。(保密论文在解密后应遵守此规定)论文作者签名：山东大学博士学位论文摘要⋯⋯⋯⋯⋯。目录ABSTRACT⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．第1章绪论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．⋯⋯⋯．⋯．I⋯⋯⋯⋯⋯。Vl1．1算法与计算模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．11．2复杂性类⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。41．3NP．完全问题与NP．难问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．51．4近似算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．71．5启

4、发式算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯81．6本文研究的问题及主要贡献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯91．7参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．9第2章两元矩阵聚类问题⋯⋯⋯102．1聚类⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯lO2．2双向聚类⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯112．3两元矩阵聚类问题⋯⋯⋯⋯⋯：．．．⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．142．4聚类问题求解目标的形式化描述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯152．5参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

5、⋯⋯⋯⋯⋯⋯⋯⋯l6第3章带缺失值的两元指纹向量聚类问题⋯⋯⋯⋯。⋯⋯⋯⋯⋯⋯．．183．1引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯l83．2问题介绍⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯2l3．3BCMV(2)的复杂性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯233．3．1图零件⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯233．3．2由X3C(3)实例构造图G⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．243．3．3由图G构造BCMV(2)实例⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．263．3．4完成复杂性证明⋯⋯⋯⋯

6、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．303．4总结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯303．5参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯30第4章两元指纹向量聚类问题的求解算法山东大学博士学位论文4．1GCP算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．344．2GCP链表实现法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯374．2．1GCP链表实现法及其实验结果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．374．2．2模拟数据⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．434．3基于线性规

7、划舍入法的BCMV(p)求解算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．444．3．1BLP算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯444．3．2BLP算法实现及实验结果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯474．4总结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯484．5参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯49第5章两元矩阵的子矩阵划分问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．505．1引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．505．2问题介绍⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯