基于因子分析的時(shí)序聚類算法分析2400字

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