關(guān)于作者
一個畢業(yè)于北京大學(xué)數(shù)學(xué)力學(xué)系，在中國科學(xué)院計算所、計算中心和網(wǎng)絡(luò)中心工作過，在澳大利亞科工組織DMS、香港浸會學(xué)院數(shù)學(xué)系和中國21世紀(jì)議程管理中心等處工作過，多次獲國家和中科院科技獎并享受政府特殊津貼的退休老頭?，F(xiàn)在在【中國科普博覽】網(wǎng)“科學(xué)新語林”欄目里開設(shè)一個《數(shù)學(xué)與計算機》的個人專欄，愿和愛好數(shù)學(xué)與計算機的各界網(wǎng)友和青少年朋友，談?wù)剬?shù)學(xué)與計算機的看法、想法。
常用算法之統(tǒng)計計算（一）
張建中
2017年05月31日
（1）統(tǒng)計計算概述
統(tǒng)計計算（Statistical Computing），又稱概率統(tǒng)計計算、計算統(tǒng)計或計算機統(tǒng)計，是概率論、數(shù)理統(tǒng)計和應(yīng)用統(tǒng)計、數(shù)學(xué)和計算機科學(xué)等學(xué)科之間的交叉性、邊緣性、融合性和應(yīng)用性的計算數(shù)學(xué)的一個分支，數(shù)學(xué)技術(shù)中的一類常用算法。
統(tǒng)計計算早已有之，和概率統(tǒng)計有著同樣長的發(fā)展史，只是由于計算機的出現(xiàn)和網(wǎng)絡(luò)技術(shù)的發(fā)展，解決了巨量計算、海量數(shù)據(jù)采集、存貯和傳輸?shù)壤щy，才得到了較快發(fā)展和大量應(yīng)用。統(tǒng)計計算軟件的發(fā)展和普及，同計算機圖形、圖表及數(shù)據(jù)庫等數(shù)學(xué)技術(shù)的有機結(jié)合，計算機網(wǎng)絡(luò)的發(fā)展使全球數(shù)據(jù)得以共享，進(jìn)一步推動了統(tǒng)計計算的快速發(fā)展和廣泛應(yīng)用。
統(tǒng)計計算，研究如何根據(jù)實際問題提出的要求，利用概率統(tǒng)計中提供的數(shù)學(xué)模型，計算數(shù)學(xué)中提供的有效算法及其自身發(fā)展起來的一些特別有效的算法，對數(shù)據(jù)進(jìn)行統(tǒng)計分析，挖掘其中隱含的信息和知識，對問題做出科學(xué)的分析、合理的分類、可用的預(yù)測和輔助性決策，給出實際問題的統(tǒng)計描述和統(tǒng)計控制等結(jié)果。因此，現(xiàn)在組成了大數(shù)據(jù)處理中很重要的一類算法。
統(tǒng)計計算是處理海量數(shù)據(jù)的科學(xué)，是用海量計算替代理論公式推導(dǎo)的一組工具，開辟了統(tǒng)計理論和算法研究的一條新途徑、一類新方法。
統(tǒng)計計算研究的主要范圍包括海量數(shù)據(jù)的處理和分析，如數(shù)據(jù)預(yù)處理、數(shù)據(jù)分析計算、數(shù)據(jù)挖掘計算、多元統(tǒng)計分析計算、時序分析計算，隨機模型模擬的蒙特卡羅方法，在計算機上實現(xiàn)具體計算的軟件等多個相互關(guān)聯(lián)的方面。同時，利用計算機高速實現(xiàn)數(shù)值運算和邏輯運算的特點，推出了一系列和傳統(tǒng)統(tǒng)計計算不同的算法，如各種探索性數(shù)據(jù)分析算法、非參數(shù)統(tǒng)計算法、穩(wěn)健性統(tǒng)計算法，神經(jīng)元網(wǎng)絡(luò)算法，遺傳性搜索算法和再抽樣算法等等，大大豐富和增強了統(tǒng)計計算處理實際問題的能力。現(xiàn)對其所含內(nèi)容簡介如下。
隨機數(shù)據(jù)的統(tǒng)計分析計算
在計算機上，對實際問題中給出的一組試驗觀測數(shù)據(jù)或概率統(tǒng)計模型的隨機模擬數(shù)據(jù)x1,x2？,…,xn？進(jìn)行分析計算。這里，xi=(xi1，xi2，…，xim),(i=1,2,…,n；m≧1) 表示在第i次試驗中或第i次模擬中得到的觀測數(shù)據(jù)，可以是一個標(biāo)量 (m＝1)，也可以是一個向量(m>1)。根據(jù)xi所含變量個數(shù)m的不同（m=1或m>1）和各次觀測模擬之間是否統(tǒng)計相關(guān)或相互獨立，在分析計算時使用不同的概率統(tǒng)計模型和不同的概率統(tǒng)計算法。對各次觀測或模擬間相互獨立的隨機數(shù)據(jù)，有一元(m=1)和多元(m>1)統(tǒng)計分析計算之分；對相關(guān)性的觀測數(shù)據(jù)，有處理平穩(wěn)隨機數(shù)據(jù)的數(shù)字時間序列分析計算，處理突發(fā)隨機事件的隨機點過程計算，處理狀態(tài)離散的馬爾可夫鏈計算和處理各種觀測系統(tǒng)的數(shù)字濾波計算等。
對一組給定的隨機觀測數(shù)據(jù){xi}進(jìn)行統(tǒng)計分析計算，重要的是選擇恰當(dāng)?shù)母怕式y(tǒng)計模型和有效的進(jìn)行統(tǒng)計分析計算的算法。以對多元數(shù)據(jù)進(jìn)行統(tǒng)計分析計算為例，目的各有不同：有的要求對觀測變量之間進(jìn)行調(diào)整，使它們之間可以進(jìn)行平衡和便于比較；有的要求在不影響結(jié)果的精度和可靠度的條件下,降低觀測數(shù)據(jù)的維數(shù),化簡問題的結(jié)構(gòu)；有的要求按照一定的標(biāo)準(zhǔn)，對數(shù)據(jù)進(jìn)行分類或分組；有的要求給出觀測數(shù)據(jù)的方程或方程組,用這類模型解釋因變量的變異，預(yù)測系統(tǒng)的未來可能取值等等。因此，在多元分析計算中，不僅要明確進(jìn)行分析計算的目的和觀測數(shù)據(jù){xi}自身的一些性質(zhì)和特點，而且還要了解各種不同的多元統(tǒng)計分析模型及其相應(yīng)算法的特點。在多元統(tǒng)計分析計算中，進(jìn)行統(tǒng)計分析的主要目的、相應(yīng)可用的統(tǒng)計模型及其常用算法如圖所示（箭頭指示出可選用的統(tǒng)計模型）。
以多元回歸分析和多元判別分析為例，用這種統(tǒng)計分析模型進(jìn)行計算,就是根據(jù)由變量組(x1,x2,…,xm;y)得到的相互獨立的 n組觀測數(shù)據(jù)(xi1,xi2,…,xim；yi)(i=1,2,…,n;n>m), 確定因變量y和自變量(x1，x2，…，xm) 之間的關(guān)系，用于識別、預(yù)報、控制或分類。這里，因變量y在回歸模型中取連續(xù)值,表示分析系統(tǒng)所處的水平；在判別模型中取離散值，表示系統(tǒng)的類別。對這組數(shù)據(jù)進(jìn)行統(tǒng)計分析計算的目的,就是從給定的變量組(x1，x2，…,xm)中，選取一個“最優(yōu)”的子集：在回歸模型中,經(jīng)計算給出回歸方程
能夠解釋因變量y的變異;在判別模型中,經(jīng)計算給出判別函數(shù),能夠?qū)⒂?em>y表示的類別數(shù)據(jù)按類分開。所以,對給定的觀測數(shù)據(jù)進(jìn)行分析計算時，主要注意力集中在最優(yōu)變量子集選取的不同算法及其實現(xiàn)上。在實際問題中，預(yù)選自變量的個數(shù)m和觀測的次數(shù)n通常都很大，各個自變量之間也不相互正交，存在著錯綜復(fù)雜的相互關(guān)系，需要按照一定的標(biāo)準(zhǔn)對自變量xi進(jìn)行舍選。目前常用的算法有四種：①漸增法，把自變量按照各自重要性的大小，逐個選入回歸方程或判別函數(shù)；②漸降法，先把所有能引入的自變量全部引入回歸方程或判別函數(shù)，然后再把不重要的自變量逐個舍去；③舍選法，在把重要的自變量引入回歸方程或判別函數(shù)的同時，檢驗已在模型中的自變量是否繼續(xù)顯著,把不符合要求的自變量從中舍去;④最佳子集法,利用自變量各個不同子集合之間的關(guān)系,從所有可能的子集中選取最佳的子集。第三種算法最為常用，通常把它稱為逐步回歸和逐步判別算法。
對系統(tǒng)中依賴于時間t的一個變量或一組變量x(t)進(jìn)行觀測或模擬，在時間t的等距間隔 t上，得到一組有序離散相關(guān)的數(shù)集合x1,x2,…,xn,其中xi=x(t0+i t)(i=1,2,…,n)稱為數(shù)字時間序列，分析這類數(shù)據(jù)的方法稱為數(shù)字時間序列分析，或簡稱為時間序列分析。這類方法包括時域中的相關(guān)分析，頻域中的譜分析和時間序列模型，特別是p階自回歸、q階滑動平均線性模型ARMA(p,q)的識別、估計和檢驗的計算問題等。
時間序列分析與回歸分析、判別分析等多元分析方法相比，發(fā)展較遲。由于在實際問題中應(yīng)用的重要性和廣泛性，特別是數(shù)字計算機的迅速發(fā)展和一些重大算法（如快速傅里葉變換算法？FFT）和理論（如模型識別理論）的突破，從一維時間序列到多維時間序列、從線性模型到非線性模型，都有很快的發(fā)展和廣泛的應(yīng)用。
概率統(tǒng)計模型的隨機模擬計算
隨機抽樣是概率統(tǒng)計中的一類經(jīng)典方法。由于數(shù)字計算機的出現(xiàn)和發(fā)展，隨機抽樣作為一種算法在第二次世界大戰(zhàn)之后得到了迅速發(fā)展，并在許多不同的領(lǐng)域中得到了廣泛的成功應(yīng)用。當(dāng)時從事這一方法研究的物理學(xué)家，借用歐洲著名賭城蒙特卡羅（Monte Carlo）的名字，給該法起名為蒙特卡羅法。
和隨機數(shù)據(jù)的統(tǒng)計分析計算不同，隨機模擬計算利用實際系統(tǒng)的概率統(tǒng)計模型，通過模擬計算，“仿造”系統(tǒng)的試驗觀測數(shù)據(jù)，進(jìn)而分析系統(tǒng)的漸近統(tǒng)計性質(zhì)。在數(shù)字計算機上，隨機模擬計算用系統(tǒng)概型的隨機數(shù)字模擬代替實際系統(tǒng)的物理模擬，用偽隨機數(shù)代替隨機變量的真實抽樣，這種雙重模擬計算，為概率統(tǒng)計計算解決實際問題開辟了不少新的應(yīng)用領(lǐng)域。鑒于蒙特卡羅法的算法上的重要性和應(yīng)用的普遍性，下面將另外開辟新的一節(jié)進(jìn)行介紹。
概率統(tǒng)計計算程序包
為方便使用者在計算機上使用統(tǒng)計算法已經(jīng)研制出為數(shù)眾多的概率統(tǒng)計計算程序包，它們可提供完整配套的統(tǒng)計模型，快速可靠的算法，易于使用、便于移植和二次開發(fā)的各種計算機語言的程序。它們在計算機上的廣泛應(yīng)用，既帶來了方便，也出現(xiàn)了一些值得注意的問題，主要集中在概率統(tǒng)計計算的誤用和濫用上。因此，具有模型自動檢驗、識別功能和有效算法選取功能的統(tǒng)計程序包更受到使用者的歡迎。
統(tǒng)計計算（Statistical Computing），又稱概率統(tǒng)計計算、計算統(tǒng)計或計算機統(tǒng)計，是概率論、數(shù)理統(tǒng)計和應(yīng)用統(tǒng)計、數(shù)學(xué)和計算機科學(xué)等學(xué)科之間的交叉性、邊緣性、融合性和應(yīng)用性的計算數(shù)學(xué)的一個分支，數(shù)學(xué)技術(shù)中的一類常用算法。
統(tǒng)計計算早已有之，和概率統(tǒng)計有著同樣長的發(fā)展史，只是由于計算機的出現(xiàn)和網(wǎng)絡(luò)技術(shù)的發(fā)展，解決了巨量計算、海量數(shù)據(jù)采集、存貯和傳輸?shù)壤щy，才得到了較快發(fā)展和大量應(yīng)用。統(tǒng)計計算軟件的發(fā)展和普及，同計算機圖形、圖表及數(shù)據(jù)庫等數(shù)學(xué)技術(shù)的有機結(jié)合，計算機網(wǎng)絡(luò)的發(fā)展使全球數(shù)據(jù)得以共享，進(jìn)一步推動了統(tǒng)計計算的快速發(fā)展和廣泛應(yīng)用。
統(tǒng)計計算，研究如何根據(jù)實際問題提出的要求，利用概率統(tǒng)計中提供的數(shù)學(xué)模型，計算數(shù)學(xué)中提供的有效算法及其自身發(fā)展起來的一些特別有效的算法，對數(shù)據(jù)進(jìn)行統(tǒng)計分析，挖掘其中隱含的信息和知識，對問題做出科學(xué)的分析、合理的分類、可用的預(yù)測和輔助性決策，給出實際問題的統(tǒng)計描述和統(tǒng)計控制等結(jié)果。因此，現(xiàn)在組成了大數(shù)據(jù)處理中很重要的一類算法。
統(tǒng)計計算是處理海量數(shù)據(jù)的科學(xué)，是用海量計算替代理論公式推導(dǎo)的一組工具，開辟了統(tǒng)計理論和算法研究的一條新途徑、一類新方法。
統(tǒng)計計算研究的主要范圍包括海量數(shù)據(jù)的處理和分析，如數(shù)據(jù)預(yù)處理、數(shù)據(jù)分析計算、數(shù)據(jù)挖掘計算、多元統(tǒng)計分析計算、時序分析計算，隨機模型模擬的蒙特卡羅方法，在計算機上實現(xiàn)具體計算的軟件等多個相互關(guān)聯(lián)的方面。同時，利用計算機高速實現(xiàn)數(shù)值運算和邏輯運算的特點，推出了一系列和傳統(tǒng)統(tǒng)計計算不同的算法，如各種探索性數(shù)據(jù)分析算法、非參數(shù)統(tǒng)計算法、穩(wěn)健性統(tǒng)計算法，神經(jīng)元網(wǎng)絡(luò)算法，遺傳性搜索算法和再抽樣算法等等，大大豐富和增強了統(tǒng)計計算處理實際問題的能力。現(xiàn)對其所含內(nèi)容簡介如下。
隨機數(shù)據(jù)的統(tǒng)計分析計算
在計算機上，對實際問題中給出的一組試驗觀測數(shù)據(jù)或概率統(tǒng)計模型的隨機模擬數(shù)據(jù)x1,x2？,…,xn？進(jìn)行分析計算。這里，xi=(xi1，xi2，…，xim),(i=1,2,…,n；m≧1) 表示在第i次試驗中或第i次模擬中得到的觀測數(shù)據(jù)，可以是一個標(biāo)量 (m＝1)，也可以是一個向量(m>1)。根據(jù)xi所含變量個數(shù)m的不同（m=1或m>1）和各次觀測模擬之間是否統(tǒng)計相關(guān)或相互獨立，在分析計算時使用不同的概率統(tǒng)計模型和不同的概率統(tǒng)計算法。對各次觀測或模擬間相互獨立的隨機數(shù)據(jù)，有一元(m=1)和多元(m>1)統(tǒng)計分析計算之分；對相關(guān)性的觀測數(shù)據(jù)，有處理平穩(wěn)隨機數(shù)據(jù)的數(shù)字時間序列分析計算，處理突發(fā)隨機事件的隨機點過程計算，處理狀態(tài)離散的馬爾可夫鏈計算和處理各種觀測系統(tǒng)的數(shù)字濾波計算等。
對一組給定的隨機觀測數(shù)據(jù){xi}進(jìn)行統(tǒng)計分析計算，重要的是選擇恰當(dāng)?shù)母怕式y(tǒng)計模型和有效的進(jìn)行統(tǒng)計分析計算的算法。以對多元數(shù)據(jù)進(jìn)行統(tǒng)計分析計算為例，目的各有不同：有的要求對觀測變量之間進(jìn)行調(diào)整，使它們之間可以進(jìn)行平衡和便于比較；有的要求在不影響結(jié)果的精度和可靠度的條件下,降低觀測數(shù)據(jù)的維數(shù),化簡問題的結(jié)構(gòu)；有的要求按照一定的標(biāo)準(zhǔn)，對數(shù)據(jù)進(jìn)行分類或分組；有的要求給出觀測數(shù)據(jù)的方程或方程組,用這類模型解釋因變量的變異，預(yù)測系統(tǒng)的未來可能取值等等。因此，在多元分析計算中，不僅要明確進(jìn)行分析計算的目的和觀測數(shù)據(jù){xi}自身的一些性質(zhì)和特點，而且還要了解各種不同的多元統(tǒng)計分析模型及其相應(yīng)算法的特點。在多元統(tǒng)計分析計算中，進(jìn)行統(tǒng)計分析的主要目的、相應(yīng)可用的統(tǒng)計模型及其常用算法如圖所示（箭頭指示出可選用的統(tǒng)計模型）。
以多元回歸分析和多元判別分析為例，用這種統(tǒng)計分析模型進(jìn)行計算,就是根據(jù)由變量組(x1,x2,…,xm;y)得到的相互獨立的 n組觀測數(shù)據(jù)(xi1,xi2,…,xim；yi)(i=1,2,…,n;n>m), 確定因變量y和自變量(x1，x2，…，xm) 之間的關(guān)系，用于識別、預(yù)報、控制或分類。這里，因變量y在回歸模型中取連續(xù)值,表示分析系統(tǒng)所處的水平；在判別模型中取離散值，表示系統(tǒng)的類別。對這組數(shù)據(jù)進(jìn)行統(tǒng)計分析計算的目的,就是從給定的變量組(x1，x2，…,xm)中，選取一個“最優(yōu)”的子集：在回歸模型中,經(jīng)計算給出回歸方程
能夠解釋因變量y的變異;在判別模型中,經(jīng)計算給出判別函數(shù),能夠?qū)⒂?em>y表示的類別數(shù)據(jù)按類分開。所以,對給定的觀測數(shù)據(jù)進(jìn)行分析計算時，主要注意力集中在最優(yōu)變量子集選取的不同算法及其實現(xiàn)上。在實際問題中，預(yù)選自變量的個數(shù)m和觀測的次數(shù)n通常都很大，各個自變量之間也不相互正交，存在著錯綜復(fù)雜的相互關(guān)系，需要按照一定的標(biāo)準(zhǔn)對自變量xi進(jìn)行舍選。目前常用的算法有四種：①漸增法，把自變量按照各自重要性的大小，逐個選入回歸方程或判別函數(shù)；②漸降法，先把所有能引入的自變量全部引入回歸方程或判別函數(shù)，然后再把不重要的自變量逐個舍去；③舍選法，在把重要的自變量引入回歸方程或判別函數(shù)的同時，檢驗已在模型中的自變量是否繼續(xù)顯著,把不符合要求的自變量從中舍去;④最佳子集法,利用自變量各個不同子集合之間的關(guān)系,從所有可能的子集中選取最佳的子集。第三種算法最為常用，通常把它稱為逐步回歸和逐步判別算法。
對系統(tǒng)中依賴于時間t的一個變量或一組變量x(t)進(jìn)行觀測或模擬，在時間t的等距間隔 t上，得到一組有序離散相關(guān)的數(shù)集合x1,x2,…,xn,其中xi=x(t0+i t)(i=1,2,…,n)稱為數(shù)字時間序列，分析這類數(shù)據(jù)的方法稱為數(shù)字時間序列分析，或簡稱為時間序列分析。這類方法包括時域中的相關(guān)分析，頻域中的譜分析和時間序列模型，特別是p階自回歸、q階滑動平均線性模型ARMA(p,q)的識別、估計和檢驗的計算問題等。
時間序列分析與回歸分析、判別分析等多元分析方法相比，發(fā)展較遲。由于在實際問題中應(yīng)用的重要性和廣泛性，特別是數(shù)字計算機的迅速發(fā)展和一些重大算法（如快速傅里葉變換算法？FFT）和理論（如模型識別理論）的突破，從一維時間序列到多維時間序列、從線性模型到非線性模型，都有很快的發(fā)展和廣泛的應(yīng)用。
概率統(tǒng)計模型的隨機模擬計算
隨機抽樣是概率統(tǒng)計中的一類經(jīng)典方法。由于數(shù)字計算機的出現(xiàn)和發(fā)展，隨機抽樣作為一種算法在第二次世界大戰(zhàn)之后得到了迅速發(fā)展，并在許多不同的領(lǐng)域中得到了廣泛的成功應(yīng)用。當(dāng)時從事這一方法研究的物理學(xué)家，借用歐洲著名賭城蒙特卡羅（Monte Carlo）的名字，給該法起名為蒙特卡羅法。
和隨機數(shù)據(jù)的統(tǒng)計分析計算不同，隨機模擬計算利用實際系統(tǒng)的概率統(tǒng)計模型，通過模擬計算，“仿造”系統(tǒng)的試驗觀測數(shù)據(jù)，進(jìn)而分析系統(tǒng)的漸近統(tǒng)計性質(zhì)。在數(shù)字計算機上，隨機模擬計算用系統(tǒng)概型的隨機數(shù)字模擬代替實際系統(tǒng)的物理模擬，用偽隨機數(shù)代替隨機變量的真實抽樣，這種雙重模擬計算，為概率統(tǒng)計計算解決實際問題開辟了不少新的應(yīng)用領(lǐng)域。鑒于蒙特卡羅法的算法上的重要性和應(yīng)用的普遍性，下面將另外開辟新的一節(jié)進(jìn)行介紹。
概率統(tǒng)計計算程序包
為方便使用者在計算機上使用統(tǒng)計算法已經(jīng)研制出為數(shù)眾多的概率統(tǒng)計計算程序包，它們可提供完整配套的統(tǒng)計模型，快速可靠的算法，易于使用、便于移植和二次開發(fā)的各種計算機語言的程序。它們在計算機上的廣泛應(yīng)用，既帶來了方便，也出現(xiàn)了一些值得注意的問題，主要集中在概率統(tǒng)計計算的誤用和濫用上。因此，具有模型自動檢驗、識別功能和有效算法選取功能的統(tǒng)計程序包更受到使用者的歡迎。