若干聚类问题复杂性及其算法

若干聚类问题复杂性及其算法

刘培强, 李曙光, 肖进杰, 著

出版社:电子工业出版社

年代:2013

定价:29.0

书籍简介:

使用聚类法对基因表达谱进行分析需要在方法上、理论上和算法上进一步研究,寻求突破。本书基于计算复杂性理论和基因表达谱分析理论,围绕单向、双向聚类问题某些形式未解决问题的复杂性证明、更高效的双向聚算法的设计与开发、聚类算法的计算复杂度研究、求解缺失值算法的研究等展开,具体研究内容包括:(1)聚类分析求解算法;(2)未解决问题的复杂性;(3)在单向、双向聚类方法中缺失数据的处理;(4)基因表达谱双向聚类算法的性能评价。

书籍目录:

第1章 绪论

1.1 聚类分析

1.2 双向聚类

1.2.1 双向簇的类型

1.2.2 双向聚类的解格式

1.3 数据矩阵上的聚类问题

1.4 两元矩阵聚类问题

1.5 割聚类

1.6 设施定位问题和k-median问题

第2章 计算复杂性理论简介

2.1 算法

2.2 计算模型

2.3 复杂性类

2.4 NP-完全问题

2.5 NP-难问题

2.6 近似算法与启发式算法

第3章 带缺失值的基因表达谱聚类问题

3.1 问题的应用背景

3.2 问题的形式化描述

3.3 BCMV(2)问题的复杂性

3.3.1 零件图及其性质

3.3.2 基于零件图和X3C(3)实例构造图G

3.3.3 由关联图构造BCMV(2)问题的实例

3.3.4 完成NP-难证明

3.4 求解BCMV问题的GCP算法

3.4.1 基于团划分的启发式算法

3.4.2 基于链表的GCP算法

3.4.3 基于链表的GCP算法实验结果分析

3.4.4 经验公式

3.5 基于线性规划的求解算法

3.5.1 LAB算法

3.5.2 LAB算法的实验结果及分析

3.6 本章小节

第4章 两元矩阵的子矩阵划分问题的复杂性及求解算法

4.1 引言

4.2 k-SPBM问题和k-PBB问题介绍

4.3 3-PBB问题是NP-完全的

4.3.1 二分图零件Ti1, Ti2, Ti3

4.3.2 由二分图零件的MO3实例构造二分图B

4.3.3 完成3-PBB的NP-完全性证明

4.4 当k为大于3的正整数常量时,k-PBB (k>3)问题的复杂性

4.5 k-SPBM问题的NP-完全性证明

4.6 k-PBB问题求解算法

4.6.1 求解算法

4.6.2 算法分析

4.6.3 算法测试

4.7 本章小节

第5章 均衡负载聚类

5.1 问题的应用背景

5.2 引言

5.3 预备知识

5.4 链和环中的均衡负载聚类

5.5 树和限制树宽图中的均衡负载聚类

5.6 本章小结

第6章 颜色相关最小负载聚类

6.1 引言

6.2 预备知识

6.3 仙人掌图

6.4 参数为k的几乎树

6.5 本章小节

第7章 设施定位和k -median问题

7.1 相关概念和算法介绍

7.1.1 公制空间(Metric Space)

7.1.2 组合的生成算法

7.2 设施定位问题

7.2.1 基本概念

7.2.2 设施定位问题局部搜索算法

7.2.3 局部搜索算法的实现与求解实验

7.2.4 局部搜索算法的改进

7.3 k-median问题

7.3.1 基本概念

7.3.2 k-median贪心近似算法

7.3.3 贪心算法近似度分析

7.3.4 贪心算法实验数据

7.4 本章小节

本书符号说明

参考文献

内容摘要:

《若干聚类问题复杂性及其算法》从问题的计算复杂性证明和近似算法设计的角度,对若干个聚类问题进行了讨论和研究,主要研究了带缺失值的两元指纹向量聚类问题、两元矩阵的k-子矩阵划分问题、割聚类问题、设施定位问题与k-median问题等。《若干聚类问题复杂性及其算法》可作为从事计算复杂性理论、聚类分析研究和应用科技人员的参考书。聚类是指根据给定的多个对象及其属性,基于相似性函数度量对象间的相似性,以寻找有意义或有用的对象分组。聚类分析方法是人们认识和理解世界的最基本方式之一,广泛应用于计算生物学、市场分析、社交网络数据分析、电子商务数据分析等众多领域。由于聚类分析的多样性、重要性和广泛性,尤其是在目前大数据时代背景下,众多应用领域对聚类分析算法提出了新的挑战。

书籍规格:

书籍详细信息
书名若干聚类问题复杂性及其算法站内查询相似图书
9787121213793
如需购买下载《若干聚类问题复杂性及其算法》pdf扫描版电子书或查询更多相关信息,请直接复制isbn,搜索即可全网搜索该ISBN
出版地北京出版单位电子工业出版社
版次1版印次1
定价(元)29.0语种简体中文
尺寸24 × 17装帧平装
页数印数

书籍信息归属:

若干聚类问题复杂性及其算法是电子工业出版社于2013.10出版的中图分类号为 Q786 的主题关于 基因表达-聚类分析 的书籍。