基于因子分析的時序聚類算法分析綜述1.1因子分析因子分析法的基本思想是對觀測變量進(jìn)行分類，讓它們之間相關(guān)性較高，即聯(lián)系比較緊密的分在同一類中，而不同類變量之間的相關(guān)性則較低，那么每一類變量實際上就代表了一個基本結(jié)構(gòu)，也被叫做公共因子。對于所研究的問題就是試圖用最少個數(shù)的不可測的被稱作公共因子的線性函數(shù)與特殊因子之和來描述原來觀測的每一分量。這樣，用少數(shù)幾個因素就比較容易反映出原始數(shù)據(jù)的大部分信息，從而集中數(shù)據(jù)，從小而大，把握問題的本質(zhì)與核心。因子分析法的核心是對若干綜合指標(biāo)進(jìn)行因子分析并提取公共因子,再用每個因子的方差貢獻(xiàn)率作為權(quán)數(shù)與該因子的得分乘數(shù)之和構(gòu)造得分函數(shù)。因子分析法的數(shù)學(xué)表示為矩陣:X=AF+B，即x1=a11f1+模型中,向量X(x1,x2,x3,……,xp)是可觀測隨機(jī)向量，即原始觀測變量。F(x1,x2,x3,……,xp)是F(f1,f2,f3,……,fp)的公共因子,即各個原觀測變量的表達(dá)式中共同出現(xiàn)的因子，是相互獨(dú)立的不可觀測的理論變量。公共因子的具體含義必須結(jié)合實際研究問題來界定。A(aij)是公共因子F(f1,f2,f3,……,fp)的系數(shù)，稱為因子載荷矩陣，aij(i=1,2,……,p:j=1,2,……,k)稱為因子載荷，是第i個原有變量在第j個因子上的負(fù)荷，或可將aij看作第i個變量在第j公共因子上的權(quán)重。aij是xi;與fj的協(xié)方差，也是xi;與fj,的相關(guān)系數(shù)，表示xi對fj的依賴程度或相關(guān)程度。aij的絕對值越大，表明公共因子fj，對于xi的載荷量越大。B(β1,β2,β3,……,βp,)是X(x1,x2,x3,……,xp)的特殊因子，是不能被前k個公共因子包含的部分，這種因子也是不可觀測的。各特殊因子之間以及特殊因子與所有公共因子之間都是相互獨(dú)立的。一般步驟如下REF_Ref103803465\r\h[10]1)對所給的數(shù)據(jù)樣本進(jìn)行標(biāo)準(zhǔn)化處理2)計算樣本的相關(guān)矩陣R3)求相關(guān)矩陣R的特征值、特征向量4)根據(jù)系統(tǒng)要求的累積貢獻(xiàn)度確定主因子的個數(shù)4)計算因子載荷矩陣A5)最終確定因子模型1.2Birch聚類算法1.2.1Birch概述BIRCH（BalancedIterativeReducingandClusteringUsingHierarchies）的主要功能是兩個方面，一是處理大數(shù)據(jù)集，二是對異常值的魯棒性。該算法中引入兩個概念：聚類特征（ClusteringFeature，CF）和聚類特征樹（CF-tree），通過這兩個概念對簇進(jìn)行概括，利用各個簇之間的距離，采用層次方法的平衡迭代對數(shù)據(jù)集進(jìn)行規(guī)約和聚類。1.2.2聚類特征CF是BIRCH增量聚類算法的核心，使用CF概括描述各簇的信息，設(shè)某簇中有N個D維數(shù)據(jù)點(diǎn){x→n}(n=1,2,...,N)，則該簇的聚類特征定義為三元組： CF=N,LS,SS (1.其中N是簇中點(diǎn)的數(shù)目，矢量LS是各個點(diǎn)的線性求和即n=1標(biāo)量SS是各數(shù)據(jù)點(diǎn)的平方和即ΣCF具有可加性：CF1=（n1,LS1,SS1），CF2=（n2,LS2,SS2），則CF1+CF2=（n1+n2,LS1+LS2,SS1+SS2）表示將兩個不相交的簇合并成一個大簇的聚類特征。聚類特征本質(zhì)上是給定簇的統(tǒng)計匯總，可以有效地對數(shù)據(jù)進(jìn)行壓縮，而且基于聚類特征可以很容易地推導(dǎo)出簇的許多統(tǒng)計量和距離度量。假設(shè)給定簇中有N個D維數(shù)據(jù)點(diǎn)，可用以下公式定義簇的質(zhì)心X0,半徑R，直徑D。簇質(zhì)心: x0=Σ?=1NxiN=簇半徑： R=Σ?=1Nxi簇直徑： D=Σ?=1NΣj=11.2.3聚類特征樹CF樹存儲了層次聚類的簇的特征，有三個參數(shù)：枝平衡因子β，葉平衡因子λ和空間閾值τ。CF樹由根節(jié)點(diǎn)、枝節(jié)點(diǎn)和葉節(jié)點(diǎn)構(gòu)成非葉節(jié)點(diǎn)中包含不多于β個形如[CFi,c??ldi]的條目。其中表示該節(jié)點(diǎn)上子簇的聚類特征信息，指針c??l如圖1.1所示。圖1.1CF樹的性質(zhì)1.2.4聚類特征樹的生成1.從根節(jié)點(diǎn)向下尋找和新樣本距離最近的葉子節(jié)點(diǎn)和葉子節(jié)點(diǎn)里最近的CF節(jié)點(diǎn)2.如果新樣本加入后，這個CF節(jié)點(diǎn)對應(yīng)的超球體半徑仍然滿足小于閾值T，則更新路徑上所有的CF三元組，插入結(jié)束。否則轉(zhuǎn)入1.1.如果當(dāng)前葉子節(jié)點(diǎn)的CF節(jié)點(diǎn)個數(shù)小于閾值L，則創(chuàng)建一個新的CF節(jié)點(diǎn)，放入新樣本，將新的CF節(jié)點(diǎn)放入這個葉子節(jié)點(diǎn)，更新路徑上所有的CF三元組，插入結(jié)束。否則轉(zhuǎn)入4。4.將當(dāng)前葉子節(jié)點(diǎn)劃分為兩個新葉子節(jié)點(diǎn)，選擇舊葉子節(jié)點(diǎn)中所有CF元組里超球體距離最遠(yuǎn)的兩個CF元組，分布作為兩個新葉子節(jié)點(diǎn)的第一個CF節(jié)點(diǎn)。將其他元組和新樣本元組按照距離遠(yuǎn)近原則放入對應(yīng)的葉子節(jié)點(diǎn)。依次向上檢查父節(jié)點(diǎn)是否也要分裂，如果需要按和葉子節(jié)點(diǎn)分裂方式相同。圖1.2CF樹的生成1.2.5Birch算法將所有的訓(xùn)練集樣本建立了CFTree，一個基本的BIRCH算法就完成了，對應(yīng)的輸出就是若干個CF節(jié)點(diǎn)，每個節(jié)點(diǎn)里的樣本點(diǎn)就是一個聚類的簇。也就是說BIRCH算法的主要過程，就是建立CFTree的過程。其實還有一些可選的算法步驟的，1)將所有的樣本依次讀入，在內(nèi)存中建立一顆CFTree,建立的方法參考之前的描述。2)(可選)將第一步建立的CFTree進(jìn)行篩選，去除一些異常CF節(jié)點(diǎn)，這些節(jié)點(diǎn)一般里面的樣本點(diǎn)很少。對于一些超球體距離非常近的元組進(jìn)行合并3)(可選)利用其它的一些聚類算法比如K-Means對所有的CF元組進(jìn)行聚類，得到一顆比較好的CFTree.這一步的主要目的是消除由于樣本讀入順序?qū)е碌牟缓侠淼臉浣Y(jié)構(gòu)，以及一些由于節(jié)點(diǎn)CF個數(shù)限制導(dǎo)致的樹結(jié)構(gòu)分裂。4)(可選)利用第三步生成的CFTree的所有CF節(jié)點(diǎn)的質(zhì)心，作為初始質(zhì)心點(diǎn)，對所有的樣本點(diǎn)按距離遠(yuǎn)近進(jìn)行聚類。這樣進(jìn)一步減少了由于CFTree的一些限制導(dǎo)致的聚類不合理的情況。從上面可以得知，BIRCH算法的關(guān)鍵就是步驟1)，也就是CFTree的生成，其他步驟都是為了優(yōu)化最后的聚類結(jié)果。1.3時間序列聚類算法由于時間序列的長度很大，并且不確定時間序列在每個采樣點(diǎn)的取值具有不確定性，導(dǎo)致時間序列在相似性匹配和聚類挖掘中時間復(fù)雜度很高REF_Ref103803489\r\h[11],且由于時間序列數(shù)據(jù)的緯度大，直接對原始數(shù)據(jù)直接進(jìn)行聚類會產(chǎn)生例如計算量巨大，精確度差、受冗余信息的干擾等諸多問題，因此，先對數(shù)據(jù)進(jìn)行緯度降低