![]()
内容推荐 k-均值问题是经典组合优化问题,也是著名的NP-难问题之一,相应的Lloyd算法是数据挖掘的十大经典算法之一、k-均值问题在人工智能、数据挖掘、理论计算机科学、运筹学和管理科学中有着广泛的应用。本书介绍k-均值问题及其变形的基于随机抽样、降维、核心集、近似质心集、局部搜索、线性规划舍入等技术的近似算法,主要内容包括:经典k-均值问题的近似算法,k-中位,球面k-均值,鲁棒k-均值,带约束的k-均值,隐私保护k-均值,k-均值的其他变形等。 本书可作为运筹学、统计学、计算机科学、管理科学和应用数学专业的高年级本科生和研究生的教材和参考书,亦可作为相关研究领域科研人员的参考书。 目录 第1章 绪论 1.1 k-均值问题 1.2 k-均值问题的重要变形 1.2.1 k-中位问题 1.2.2 球面k-均值问题 1.2.3 鲁棒k-均值/中位问题 1.2.4 带约束的k-均值问题 1.2.5 隐私保护k-均值问题 1.2.6 泛函k-均值问题 1.2.7 模糊C-均值问题 1.2.8 其他变形 第2章 k-均值初始化方法 2.1 k-均值++算法 2.1.1 算法设计 2.1.2 算法分析 2.1.3 下界 2.2 k-均值||算法 2.2.1 并行算法设计 2.2.2 并行算法分析 第3章 Johnson-Lindenstrauss降维引理 3.1 预备知识 3.1.1 基本概念 3.1.2 Brunn-Minkowski不等式 3.2 高维空间及其特性 3.2.1 超球体的几何特性 3.2.2 高维空间的概率集中性 3.3 随机投影定理和Johnson-Lindenstrauss降维引理 3.3.1 随机投影定理 3.3.2 Johnson-Lindenstrauss降维引理 第4章 核心集与近似质心集 4.1 核心集 4.1.1 问题描述 4.1.2 核心集构造算法 4.1.3 核心集结论的证明 4.2 ε-近似质心集 4.2.1 ε-近似质心集的定义和性质 4.2.2 整数格上的k-均值问题 4.2.3 稀疏实例 4.2.4 一般实例 第5章 k-中位和k-均值问题的局部搜索算法 5.1 k-中位问题的局部搜索算法 5.1.1 问题描述 5.1.2 单交换局部搜索算法 5.1.3 简单情形的局部比值 5.1.4 一般情形的局部比值 5.1.5 多项式时间近似算法 5.1.6 多交换局部搜索算法 5.2 k-均值问题的局部搜索算法 5.2.1 单交换局部搜索算法 5.2.2 多交换局部搜索算法 第6章 k-均值问题的双准则近似算法 6.1 线性规划舍入算法 6.2 局部搜索算法 第7章 有序k-中位问题 7.1 问题描述 7.2 近似算法 7.2.1 算法框架 7.2.2 矩形有序k-中位问题的近似比分析 7.2.3 一般有序k-中位问题的近似比分析 第8章 球面k-均值问题 8.1 问题描述 8.1.1 概述 8.1.2 性质 8.2 球面k-均值问题的初始化算法 8.2.1 问题描述 8.2.2 可分离球面k-均值问题的近似初始化算法 8.2.3 推广的球面k-均值问题的近似算法 8.3 局部搜索算法 8.3.1 单交换的局部搜索算法 8.3.2 多交换的局部搜索算法 第9章 鲁棒k-均值问题 9.1 带惩罚的k-均值问题 9.1.1 概述 9.1.2 单交换局部搜索算法 9.1.3 多交换局部搜索算法 9.2 带惩罚k-中位/均值问题局部搜索算法 9.2.1 问题描述 9.2.2 算法及分析 9.3 带异常点k-中位/均值问题局部搜索算法 9.3.1 问题描述 9.3.2 算法描述 9.3.3 近似比分析 第10章 带约束k-均值问题 10.1 问题描述 10.2 带约束k-均值问题的剥离封闭算法 10.2.1 单纯形引理 10.2.2 剥离封闭算法 10.2.3 剥离封闭算法分析 10.3 带约束k-均值问题的选择算法 10.3.1 下界约束后.均值问题的选择算法 10.3.2 r-容量约束k-均值问题的选择算法 10.3.3 色谱k-均值问题的选择算法 第11章 其他变形 11.1 隐私保护k-均值 11.1.1 差分隐私概念 11.1.2 差分隐私k-均值问题描述 11.1.3 差分隐私常用的机制 11.1.4 高维差分隐私k-均值问题 11.2 泛函k-均值问题 11.2.1 问题描述 11.2.2 泛函k-均值问题的初始化算法 11.3 模糊C-均值问题 11.3.1 问题描述 11.3.2 模糊C-均值问题的初始化算法 11.4 平方和设施选址问题 11.4.1 问题描述 11.4.2 连续SOS-FLP的局部搜索算法 11.4.3 离散SOS-FLP的局部搜索算法 11.5 带惩罚μ-相似Bregman散度k-均值问题 11.5.1 问题描述 11.5.2 带惩罚μ-相似Bregman散度K-均值问题的初始化算法 参考文献 名词索引 |