Oleg+Granichin

隨機算法是算法本身包含了隨機數(shù)生成器的算法。在進行算法分析時，有時可以在獲得了一定輸入分布信息之后對輸入的分布進行一定的假定，在此基礎上進行平均情況分析，得到算法的時間復雜度。然而有時候無法獲得輸入分布的信息，這時可以添加一定的隨機性，繼而實現(xiàn)進行平均情況分析。通過設計隨機算法有效地避免較壞輸入情況的出現(xiàn)，從而提高平均情況下算法的性能。而在數(shù)據(jù)挖掘和控制領域，系統(tǒng)描述中巨量非結構化數(shù)據(jù)及不確定性的存在一直是關鍵的難題。本書向讀者介紹了隨機算法應用在數(shù)據(jù)挖掘（尤其是聚類）和自動控制領域的基礎知識。

全書共3部分，分為7章。第1部分 隨機算法，含第1-2章：1.反饋、平均和控制與數(shù)據(jù)挖掘中的隨機現(xiàn)象：首先從信息與控制、信號和數(shù)據(jù)量、噪聲觀測等方面介紹反饋知識，然后從數(shù)據(jù)平均級平均隨機控制介紹平均的概念，最后介紹噪聲估計與隨機貝葉斯方法；2.歷史概述：主要對一些經(jīng)典理論及算法進行概述，包括蒙特卡羅方法、隨機搜索、模擬退火、遺傳算法、線性回歸和過濾、壓縮感知、機器學習與數(shù)據(jù)挖掘等。第2部分 任意的外部噪聲下的隨機估計、濾波和識別，含第3-5章：3.隨機逼近：包括收斂估計與跟蹤策略、量子計算、算法實現(xiàn)及最后的應用實例；4.線性模型：包括任意外部噪聲下的線性回歸與濾波、隨機投影、壓縮感知及相關應用實例；5.隨機控制策略：以簡單的例子進行了問題的陳述，然后介紹了假設和模型參數(shù)化、隨機逼近算法及在無人機上的應用實例。第3部分 數(shù)據(jù)挖掘，含第6-7章：6.聚類：包括K均值聚類、高斯混合聚類、信息方法、譜聚類、NJW算法等多種聚類算法的介紹；7.集群驗證：通過介紹驗證的相關幾何準則、信息標準及穩(wěn)定性判據(jù)，再利用多種仿真方法，對實驗結果進行了綜合評定。附錄：實驗所有數(shù)據(jù)集。

本書所提出的方法保證了經(jīng)典算法計算復雜性的降低和魯棒性能的提高。結果表明，當一個問題需要強制性選擇的時候，根據(jù)隨機選擇性算法在有限的時間內(nèi)能夠提供良好的效果，并大大減少作業(yè)量。本書尤其適合自動控制、數(shù)據(jù)挖掘、算法設計與分析領域的學生與科研人員閱讀參考。

李亞寧，碩士研究生

（中國科學院自動化研究所）