电子工业出版社-网上书店

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

第1章  绪论	1
1.1  聚类分析	1
1.2  双向聚类	3
1.2.1  双向簇的类型	4
1.2.2  双向聚类的解格式	5
1.3  数据矩阵上的聚类问题	6
1.4  两元矩阵聚类问题	7
1.5  割聚类	8
1.6  设施定位问题和k-median问题	9
第2章  计算复杂性理论简介	11
2.1  算法	11
2.2  计算模型	13
2.3  复杂性类	18
2.4  NP-完全问题	20
2.5  NP-难问题	21
2.6  近似算法与启发式算法	22
第3章  带缺失值的基因表达谱聚类问题	29
3.1  问题的应用背景	29
3.2  问题的形式化描述	33
3.3  BCMV(2)问题的复杂性	34
3.3.1  零件图及其性质	36
3.3.2  基于零件图和X3C(3)实例构造图G	37
3.3.3  由关联图构造BCMV(2)问题的实例	38
3.3.4  完成NP-难证明	42
3.4  求解BCMV问题的GCP算法	42
3.4.1  基于团划分的启发式算法	43
3.4.2  基于链表的GCP算法	45
3.4.3  基于链表的GCP算法实验结果分析	50
3.4.4  经验公式	54
3.5  基于线性规划的求解算法	55
3.5.1  LAB算法	55
3.5.2  LAB算法的实验结果及分析	59
3.6  本章小节	61
第4章  两元矩阵的子矩阵划分问题的复杂性及求解算法	62
4.1  引言	62
4.2  k-SPBM问题和k-PBB问题介绍	66
4.3  3-PBB问题是NP-完全的	67
4.3.1  二分图零件Ti1, Ti2, Ti3	69
4.3.2  由二分图零件的MO3实例构造二分图B	74
4.3.3  完成3-PBB的NP-完全性证明	81
4.4  当k为大于3的正整数常量时，k-PBB (k＞3)问题的复杂性	83
4.5  k-SPBM问题的NP-完全性证明	84
4.6  k-PBB问题求解算法	85
4.6.1  求解算法	85
4.6.2  算法分析	86
4.6.3  算法测试	87
4.7  本章小节	88
第5章  均衡负载聚类	90
5.1  问题的应用背景	90
5.2  引言	92
5.3  预备知识	93
5.4  链和环中的均衡负载聚类	93
5.5  树和限制树宽图中的均衡负载聚类	95
5.6  本章小结	97
第6章  颜色相关最小负载聚类	98
6.1  引言	98
6.2  预备知识	99
6.3  仙人掌图	100
6.4  参数为k的几乎树	103
6.5  本章小节	106
第7章  设施定位和k -median问题	107
7.1  相关概念和算法介绍	107
7.1.1  公制空间（Metric Space）	107
7.1.2  组合的生成算法	108
7.2  设施定位问题	108
7.2.1  基本概念	108
7.2.2  设施定位问题局部搜索算法	109
7.2.3  局部搜索算法的实现与求解实验	115
7.2.4  局部搜索算法的改进	121
7.3  k-median问题	122
7.3.1  基本概念	122
7.3.2  k-median贪心近似算法	123
7.3.3  贪心算法近似度分析	124
7.3.4  贪心算法实验数据	126
7.4  本章小节	128
本书符号说明	129
参考文献	130

聚类分析方法是人们认识和理解世界的最基本方式之一，是我们获取知识的重要方法，它广泛应用于计算生物学、金融数据分析、市场分析、社交网络数据分析、电子商务数据分析等众多领域。由于聚类分析的多样性、重要性和广泛性，尤其是在目前大数据时代背景下，众多应用领域为聚类分析算法提出了新的挑战，使得有60 余年的聚类分析方法仍是目前研究的热点问题之一。
    聚类分析是指根据给定的多个对象及其属性，以对象属性为参数设计相似性函数，基于相似性函数度量对象间的相似性，以寻找有意义或有用的分组，具有相似特征的一组对象称为一个簇（Cluster）。若相似性函数的参数为对象的全部属性，则称此种聚类为单向聚类；若相似性函数的参数为对象全部属性的一个子集，则称此种聚类为双向聚类。
    本书从计算复杂性的角度对若干个聚类问题进行了讨论和研究，这些聚类问题包括：
（1）带缺失值的两元指纹向量聚类问题；
（2）两元矩阵的k-子矩阵划分问题；
（3）割聚类问题；
（4）设施定位问题与k-median 问题。
    本书共分为7 章。第1 章为绪论，介绍聚类的基本概念和本书所讨论的聚类问题。第2 章介绍计算复杂性理论。第3 章讨论基因表达谱分析的两元指纹向量聚类问题的复杂，给出了两个求解算法。第4 章讨论两元矩阵的k-子矩阵划分问题（k 是正整数常量，下同）和二分图的二分团划分问题；先后证明了MO3 问题的一个变体形式、3-二分团划分问题、k-二分团划分问题（k ＞ 3）、k-子矩阵划分问题（k ＞ 3）是NP-完全的，并给出了二分图＆#1048664;若干聚类问题复杂性及其算法的k-二分团划分问题的一个指数精确算法。第5 章证明链和环上最优聚类的一个良好结构，并据此结构设计了一个最优算法，然后为树和限制树宽图中的这一问题设计一个两阶段算法，其近似性能比为2-1/2k2，其中k 表示给定终端的数目。第6 章讨论颜色相关最小负载聚类问题，给出固定参数可解算法。第7 章首先分析设施定位问题局部搜索求解算法的求解质量，并编程测试对比贪心算法和随机算法；然后提出一个解决k-median 问题的贪心算法，实验证明此算法实用效果较好。
    本书由刘培强、李曙光、肖进杰著，第1、2、3、4 章由刘培强编写，第5、6 章由李曙光编写，第7 章由肖进杰编写。
    本书的出版工作得到了国家自然基金（61173173）、教育部科学技术研究重点项目（ 2012101 ）、山东省自然科学基金（ ZR2011FL004,ZR2011FM035）、烟台市科技发展计划项目（2010167）、山东省高等学校科技计划项目（J11LG14）、山东省科学技术发展计划（软科学）（2013RKB01127）等项目和山东省高校智能信息处理重点实验室（山东工商学院）的资助，在此表示感谢！
    此外，还要特别感谢山东大学的朱大铭教授，山东工商学院的范辉教授、原达教授、谢青松教授，感谢他们为本书写作提供的帮助与支持。
    本书可作为从事计算复杂性理论、聚类分析研究和应用科技人员的参考书。
    由于我们学术水平有限，书中难免有错误和疏漏之处，敬请读者指正。作者的联系方式：liupq@126.com。

作 者
2013 年6 月

本书配套资源下载

对不起，暂无音视频资源！