自动控制和数据挖掘中的随机算法

Oleg+Granichin

随机算法是算法本身包含了随机数生成器的算法。在进行算法分析时，有时可以在获得了一定输入分布信息之后对输入的分布进行一定的假定，在此基础上进行平均情况分析，得到算法的时间复杂度。然而有时候无法获得输入分布的信息，这时可以添加一定的随机性，继而实现进行平均情况分析。通过设计随机算法有效地避免较坏输入情况的出现，从而提高平均情况下算法的性能。而在数据挖掘和控制领域，系统描述中巨量非结构化数据及不确定性的存在一直是关键的难题。本书向读者介绍了随机算法应用在数据挖掘（尤其是聚类）和自动控制领域的基础知识。

全书共3部分，分为7章。第1部分 随机算法，含第1-2章：1.反馈、平均和控制与数据挖掘中的随机现象：首先从信息与控制、信号和数据量、噪声观测等方面介绍反馈知识，然后从数据平均级平均随机控制介绍平均的概念，最后介绍噪声估计与随机贝叶斯方法；2.历史概述：主要对一些经典理论及算法进行概述，包括蒙特卡罗方法、随机搜索、模拟退火、遗传算法、线性回归和过滤、压缩感知、机器学习与数据挖掘等。第2部分 任意的外部噪声下的随机估计、滤波和识别，含第3-5章：3.随机逼近：包括收敛估计与跟踪策略、量子计算、算法实现及最后的应用实例；4.线性模型：包括任意外部噪声下的线性回归与滤波、随机投影、压缩感知及相关应用实例；5.随机控制策略：以简单的例子进行了问题的陈述，然后介绍了假设和模型参数化、随机逼近算法及在无人机上的应用实例。第3部分 数据挖掘，含第6-7章：6.聚类：包括K均值聚类、高斯混合聚类、信息方法、谱聚类、NJW算法等多种聚类算法的介绍；7.集群验证：通过介绍验证的相关几何准则、信息标准及稳定性判据，再利用多种仿真方法，对实验结果进行了综合评定。附录：实验所有数据集。

本书所提出的方法保证了经典算法计算复杂性的降低和鲁棒性能的提高。结果表明，当一个问题需要强制性选择的时候，根据随机选择性算法在有限的时间内能够提供良好的效果，并大大减少作业量。本书尤其适合自动控制、数据挖掘、算法设计与分析领域的学生与科研人员阅读参考。

李亚宁，硕士研究生

（中国科学院自动化研究所）