- k-均值问题的近似算法
- - 作者：张冬梅//李敏//徐大川|责编:刘颖
  - 出版社：清华大学
  - ISBN：9787302617563
  - 出版日期：2022/10/01
  - 页数：265
- 售价：27.6

内容大纲
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-均值问题的初始化算法
参考文献
名词索引

内容大纲

作者介绍

目录

同类热销排行榜

推荐书目