清華大學(xué)系統(tǒng)工程11 (7)

1、系統(tǒng)工程導(dǎo)論,開課單位：清華大學(xué)自動化系 授課時間：2009年春季學(xué)期 主講教師：胡堅(jiān)明副教授,清華大學(xué)本科專業(yè)限選課程,第五章 主成分分析方法,5.1 引言 5.2 主成分分析基本原理 5.3 主成分的計(jì)算方法及有關(guān)性質(zhì) 5.4 主成分的計(jì)算方法證明,例：一批龜殼化石的長、寬、高數(shù)據(jù)，請將全部烏龜分為三類,5.1 引言,若存在一個線性關(guān)系,或者,或者,或者,觀察：長、寬、高之間近似存在線性關(guān)系,只需要根據(jù)兩個變量分類！,5.1 引言,或者,或者,或者,若存在兩個線性關(guān)系,只需要根據(jù)一個變量分類,5.1 引言,據(jù)長分類,據(jù)高分類,4,4,據(jù)寬分類,5,5,根據(jù)什么變量分類較好？,4,5,5.1

2、 引言,任取,只要有關(guān)向量線性無關(guān)，就成立,若存在兩個線性關(guān)系，例如,5.1 引言,一般性建模問題,使得,和,如果變量間近似線性相關(guān)，則存在低維向量,所以，一旦知道,，于是,的樣本數(shù)據(jù)，可考慮低維問題,5.1 引言,主成分分析試圖從樣本點(diǎn)定量變量的數(shù)據(jù)表中，找出最為關(guān)鍵的少數(shù)綜合變量，能與原有系統(tǒng)數(shù)據(jù)保持很高的一致性。 實(shí)際采用降維方法（如20維降為2維），只選擇起最主要作用的自變量和因變量來建模。 在數(shù)學(xué)上，可以看成將坐標(biāo)做平移和旋轉(zhuǎn)變換，使得新坐標(biāo)的原點(diǎn)與樣本數(shù)據(jù)群的重心重合，第一軸（稱為第一主軸u1）與數(shù)據(jù)變異最大的方向?qū)?yīng)；第二軸與數(shù)據(jù)變異次大的方向?qū)?yīng)依此類推。經(jīng)有效舍棄后，主軸u1

3、 u2 up能十分有效地表示原數(shù)據(jù)的變異情況。,5.2 主成分分析基本原理,主成分分析幾何意義： 平移旋轉(zhuǎn)，使得樣本點(diǎn)在第一主軸的方差最大,5.2 主成分分析基本原理,變量的樣本均值,變量的樣本方差,基本準(zhǔn)則：分類變量的分散程度越大越有利,變量的分散程度可用其樣本方差表示,5.2 主成分分析基本原理,確定分類變量的基本方式,5.2 主成分分析基本原理,輔助措施：對組合變量施加規(guī)范化約束,措施1：對原始變量的尺度規(guī)范化,措施2：對組合參數(shù)的尺度規(guī)范化,5.2 主成分分析基本原理,最終的優(yōu)化模型,其中,該問題的最優(yōu)解,就是這組樣本數(shù)據(jù)的第一主成分,5.2 主成分分析基本原理,在當(dāng)前情況下用第一主成

4、分分類最有利！,因?yàn)橛删€性關(guān)系,仍可得到,5.2 主成分分析基本原理,任取,只要有關(guān)行向量線性無關(guān)，就成立,若僅存在一個線性關(guān)系，例如,5.2 主成分分析基本原理,類似于前面的討論，可求解,措施3：,保證兩個組合向量線性無關(guān)！,5.2 主成分分析基本原理,最終模型,最優(yōu)解就是第一和第二主成分,5.2 主成分分析基本原理,給定一組樣本數(shù)據(jù)：,一般情況,首先求出其規(guī)格化的數(shù)據(jù)：,5.2 主成分分析基本原理,確定m個主成分的優(yōu)化模型為,5.2 主成分分析基本原理,符號約定：,5.2 主成分分析基本原理,5.2 主成分分析基本原理,因?yàn)?5.2 主成分分析基本原理,結(jié)論：,5.3 主成分的計(jì)算方法及有

5、關(guān)性質(zhì),主成分的樣本均值,主成分的樣本方差,5.3 主成分的計(jì)算方法及有關(guān)性質(zhì),主成分的樣本方差之和,5.3 主成分的計(jì)算方法及有關(guān)性質(zhì),樣本相關(guān)矩陣,因?yàn)?所以,5.3 主成分的計(jì)算方法及有關(guān)性質(zhì),分類變量的個數(shù)選擇準(zhǔn)則,設(shè)定方差閾值,選擇最小的m，滿足,取前m個主成分為分類變量,5.3 主成分的計(jì)算方法及有關(guān)性質(zhì),烏龜數(shù)例的計(jì)算結(jié)果,取第一個主成分為分類變量,5.3 主成分的計(jì)算方法及有關(guān)性質(zhì),-2.4310 -2.4410 -2.0023 0.2349 0.1351 -0.6467 0.3475 0.5134 0.1407 2.1487 2.0953 1.9055,主成分,分類結(jié)果,1-

6、3,4-9,10-12,5.3 主成分的計(jì)算方法及有關(guān)性質(zhì),5.4 主成分的計(jì)算方法證明,基本出發(fā)點(diǎn)：實(shí)對稱矩陣的正交對角分解,5.4 主成分的計(jì)算方法證明,記,q(k)是 XXT 的第 k 大的 特征向量對應(yīng)的特征根,5.4 主成分的計(jì)算方法證明,5.4 主成分的計(jì)算方法證明,令,注意,所以,5.4 主成分的計(jì)算方法證明,5.4 主成分的計(jì)算方法證明,記,5.4 主成分的計(jì)算方法證明,引理1,則成立,5.4 主成分的計(jì)算方法證明,證明,因?yàn)?所以,另外，顯然成立,5.4 主成分的計(jì)算方法證明,因?yàn)?記,5.4 主成分的計(jì)算方法證明,的對角線元素大于或等于0,證明結(jié)束,引理2,則成立,5.4

7、主成分的計(jì)算方法證明,證明,如果m = n，,如果m n，但是,顯然成立,下面將推出矛盾，從而證明引理成立。,5.4 主成分的計(jì)算方法證明,證明結(jié)束,5.4 主成分的計(jì)算方法證明,根據(jù)引理1,根據(jù)引理2,5.4 主成分的計(jì)算方法證明,令,5.4 主成分的計(jì)算方法證明,5.4 主成分的計(jì)算方法證明,因此,是最優(yōu)解！,回憶,最終,是原問題的最優(yōu)解！,5.4 主成分的計(jì)算方法證明,結(jié)論,是優(yōu)化問題,的一個最優(yōu)解,5.4 主成分的計(jì)算方法證明,例：一批龜殼 化石的長 寬高數(shù)據(jù),5.5 主成分在數(shù)據(jù)壓縮中的作用,如前所述，若存在一個線性關(guān)系,總之，可以用兩個變量的樣本數(shù)據(jù)近似恢復(fù)三個變量的樣本數(shù)據(jù)。,或

8、者,或者,或者,5.5 主成分在數(shù)據(jù)壓縮中的作用,或者,或者,或者,若采用規(guī)格化的數(shù)據(jù)，前面三式可化為,可以用兩個變量的規(guī)格化數(shù)據(jù)近似恢復(fù)三個變量的規(guī)格化數(shù)據(jù)。,5.5 主成分在數(shù)據(jù)壓縮中的作用,更好的做法是極小化逼近誤差,確定存儲什么數(shù)據(jù)，其中采用規(guī)格化的樣本數(shù)據(jù)是為了平衡不同變量的逼近誤差。,有了規(guī)格化的樣本數(shù)據(jù)，只要再記住原變 量的樣本均值和方差，即可恢復(fù)原數(shù)據(jù)。,5.5 主成分在數(shù)據(jù)壓縮中的作用,或者,或者,或者,同樣，若存在兩個線性關(guān)系,總之，可以用一個變量的樣本數(shù)據(jù)近似恢復(fù)三個變量的樣本數(shù)據(jù)。,5.5 主成分在數(shù)據(jù)壓縮中的作用,同樣，可以求解優(yōu)化問題,來確定存儲什么數(shù)據(jù)！,5.5

9、主成分在數(shù)據(jù)壓縮中的作用,給定一組樣本數(shù)據(jù)：,一般情況：,首先求出其規(guī)格化的數(shù)據(jù)：,5.5 主成分在數(shù)據(jù)壓縮中的作用,然后求解優(yōu)化問題,可將其寫成,由于 L 和 y(t) 均為變量，為使解比較確定，應(yīng)對它們加一定的限制。,5.5 主成分在數(shù)據(jù)壓縮中的作用,對于數(shù)據(jù)壓縮問題,若列向量 線性相關(guān),5.5 主成分在數(shù)據(jù)壓縮中的作用,對于數(shù)據(jù)壓縮問題,第二、假定 L 滿足下式也不影響優(yōu)化效果,5.5 主成分在數(shù)據(jù)壓縮中的作用,第一、假定 L 列滿秩不影響優(yōu)化效果,有如下兩個性質(zhì)：,因?yàn)楫?dāng) L 列滿秩時，存在可逆矩陣 G,使得,和滿足,的 P,于是,5.5 主成分在數(shù)據(jù)壓縮中的作用,數(shù)據(jù)壓縮問題成為,下

10、面說明，這組樣本數(shù)據(jù)的前 m 個主成分就是該問題的一個最優(yōu)解。,5.5 主成分在數(shù)據(jù)壓縮中的作用,為簡化符號，考慮下述優(yōu)化問題,先求各 y(t) 的最優(yōu)解,將 y(t) 的最優(yōu)解代入目標(biāo)函數(shù)，可得,5.5 主成分在數(shù)據(jù)壓縮中的作用,因?yàn)?5.5 主成分在數(shù)據(jù)壓縮中的作用,原問題等價于,5.5 主成分在數(shù)據(jù)壓縮中的作用,由于,所以,5.5 主成分在數(shù)據(jù)壓縮中的作用,最終可知，求數(shù)據(jù)壓縮問題等價于求解,并且，最優(yōu)的壓縮變量是,它就是前 m 個主成分。,數(shù)據(jù)壓縮問題的相對逼近誤差,5.5 主成分在數(shù)據(jù)壓縮中的作用,對于烏龜數(shù)例，若用第一個主成分壓縮原數(shù)據(jù)，只需存儲:,共15個數(shù)據(jù)，僅占原數(shù)據(jù)的15/

11、36=42%,5.5 主成分在數(shù)據(jù)壓縮中的作用,因?yàn)?令,相對逼近誤差為,5.5 主成分在數(shù)據(jù)壓縮中的作用,注意,能夠利用主成分有效壓縮數(shù)據(jù)，是因?yàn)閿?shù)據(jù)本身具有可壓縮性，這就是樣本相關(guān)矩陣的特征根相差很大，其本質(zhì)是變量間近似線性相關(guān)。,5.5 主成分在數(shù)據(jù)壓縮中的作用,對某組10維規(guī)格化向量的數(shù)據(jù)壓縮問題，用第一至第四個主成分進(jìn)行壓縮和用第一至第五個主成分進(jìn)行壓縮的誤差相同；用第一、第三個主成分進(jìn)行壓縮和用第二、第四個主成分進(jìn)行壓縮的誤差相同；用第一個主成分進(jìn)行壓縮相對誤差是0.6。請求出每個主成分的樣本方差。,例題,5.5 主成分在數(shù)據(jù)壓縮中的作用,基于PCA的海量數(shù)據(jù)壓縮實(shí)例,5.5 主成

12、分在數(shù)據(jù)壓縮中的作用, 交通數(shù)據(jù)預(yù)處理,壓縮與恢復(fù)性能評價指標(biāo),主要研究結(jié)果,其他結(jié)果分析,軟件展示, 交通數(shù)據(jù)預(yù)處理,交通流中的“尖峰” 這些非線性的尖峰嚴(yán)重影響了PCA對數(shù)據(jù)的壓縮恢復(fù)效果。 利用均值濾波器提取“尖峰” 尖峰時刻的交通流量在壓縮前單獨(dú)存儲。 用均值濾波器平滑后的流量值代替尖峰值。,5.5 主成分在數(shù)據(jù)壓縮中的作用,壓縮與恢復(fù)性能評價指標(biāo),5.5 主成分在數(shù)據(jù)壓縮中的作用,主要研究結(jié)果,主成分分析 第一主成分貢獻(xiàn)率達(dá)80.97%。 前25個主成分貢獻(xiàn)率和達(dá)92.88%。,Fig. 壓縮比和誤差隨主成分個數(shù)增加的變化趨勢,結(jié)果 CR(壓縮比)為6.2。 平均APRE為13。 平

13、均相關(guān)系數(shù)為0.9524。,5.5 主成分在數(shù)據(jù)壓縮中的作用,主要實(shí)驗(yàn)結(jié)果,對于具有不同特征的交通流均可以較好的恢復(fù)。 不同的早、晚高峰時間 同一時段不同的流量值 特殊的“尖峰”,Fig 原始數(shù)據(jù)與恢復(fù)數(shù)據(jù),5.5 主成分在數(shù)據(jù)壓縮中的作用,其他結(jié)果分析,恢復(fù)誤差分布 具有正態(tài)分布的特征 絕大多數(shù)恢復(fù)數(shù)據(jù)點(diǎn)與原始數(shù)據(jù)點(diǎn)基本相同。,對異常數(shù)據(jù)具有魯棒性 “尖峰”點(diǎn) 交通流異常（如在白天出現(xiàn)堵車現(xiàn)象時的交通流）,5.5 主成分在數(shù)據(jù)壓縮中的作用,Table 各路口壓縮和恢復(fù)性能參數(shù),5.5 主成分在數(shù)據(jù)壓縮中的作用,軟件展示,5.5 主成分在數(shù)據(jù)壓縮中的作用,龜殼化石數(shù)據(jù),5.6 主成分在線性回歸中的作用,規(guī)格化的重量和長寬高之間存在線性關(guān)系,參數(shù)估計(jì)：,5.6 主成分在線性回歸中的作用,相對擬合誤差：,另一組樣本,5.6 主成分在線性回歸中的作用,預(yù)報精度：,5.6 主成分在線性