一種基於擴展熵信息瓶頸理論的聚類方法

2023-09-22 15:21:35

專利名稱：：一種基於擴展熵信息瓶頸理論的聚類方法
技術領域：
：本發明涉及數據挖掘領域，特別涉及聚類分析。
背景技術：
：聚類分析是數據挖掘領域的重要研究內容，旨在將數據集合劃分為若干類的過程，使得類內差異小，類間差異大。通常用數據之間的距離來描述相似度，距離越大，相似度越小，反之則越大。聚類分析應用在模式識別、數據分析、圖像處理、智能交通、醫學等領域，用途相當廣泛。已經形成了很多有效的聚類方法，常用的有K-均值法、k中心點法、自組織神經網絡、Bayes神經網絡、Fisher聚類等。不同的聚類方法出發點不同，主要體現在度量樣本或變量之間的距離測度上，K-均值聚類法與k中心點法度量兩個變量之間的距離都是用歐幾裡德距離，或者用加權的歐幾裡德距離。這種聚類方法只是以簡單的歐氏距離不適合變量之間存在複雜的非線性關係的問題。自組織神經網絡都是以非線性的空間距離來度量樣本或變量之間的相關性，通過不斷調整聚類中心達到聚類目的，但這些方法沒有考慮變量的統計特性。Bayes神經網絡聚類是將隱含單元看作聚類數，通過分析特徵變量與隱含單元的條件概率對數據進行聚類，該分類方法適用的範圍比較廣，在不同領域都得到了廣泛的應用。但該方法需要一定的先驗經驗確定其先驗概率分布，而且運算量非常大，當變量很多的情況下很難得到最優的聚類結果。信息瓶頸理論是由Tishby等人在1999年根據Shannon熵信息失真率理論提出的數據壓縮方法，接下來的幾年裡，基於信息瓶徑理論的無監督聚類方法得到了廣泛的研究，該方法是從變量合併前後信息損失量一個全新的角度來分析變量的聚類問題，是一種適合於複雜聚類問題的一種新方法，現已被用於圖像、文本、星系等複雜的聚類問題，得到了令人滿意的結果。由於該方法是基於Shannon熵的，因此必須通過統計分析得到變量的概率分布情況，當特徵變量只是一個數值而無法統計出其概率時，該方法無法使用，針對這種情況，本發明提出了基於擴展熵信息瓶頸理論的聚類方法。擴展熵是基於數值比值的一種熵的定義形式，適合於分析數值集合的不確定性問題。基於擴展熵信息瓶頸理論的聚類方法可應用於交通流的時間段劃分，從交通流的馬鞍型很大的區別，如果將所有數據同時考慮，將很難建立精確的交通流預測模型。根據交通流的不同模式將時間進行分段，對每個時段來建立相應的交通流預測模型將會提高相應的預測精度。如何對一天的交通流進行時間分段是個關鍵的問題，不能只根據交通流曲線主觀劃分。目前常用的劃分方法是Fisher在1958年提出的有序樣本聚類方法，但由於在該方法中通常選擇的距離測度為歐幾裡德距離，很難體現交通流數據的非線性複雜關係，而且，在該方法中將一天劃分成幾段，沒有一個客觀的標準，需要人為的判斷。基於擴展熵信息瓶頸理論的聚類方法可用於中醫的辨證。中醫是中華的瑰寶，擁有3000多年的歷史。辨證是中醫的核心理論，證侯要素是中醫辨證的基本要素。辨證通常依賴於醫生的經驗，缺乏一定的客觀基礎，因此很多研究人員開始用現代技術來研究中醫。因此用客觀的方法來確定證侯要素是中醫現代化急需解決的問題。這就需要我們只根據中醫臨床收集的病人症狀數據，根據其數據內在的相關性，將相關性大的症狀組合找出來，結合中醫專家經驗，對這些有意義的相關症狀組合進行命名，作為症狀要素。由於事先沒有任何的目標作為參照，因此該問題屬於無監督聚類分析問題。該問題是對特徵變量進行聚類，因此基於擴展熵信息瓶頸理論的聚類方法非常適合該問題的分析。關於基於擴展熵信息瓶頸理論的聚類方法，聚類數組的擴展熵計算是基礎，目前熵的定義有多種形式，Shannon熵是目前常用的一種熵的定義形式，可以度量變量之間的任意統計相關性。基於擴展熵信息瓶頸理論的聚類方法與其它聚類方法相比主要有以下優點1)信息熵可以度量變量之間的任意統計相關性，用它作為相關測度進行聚類，能夠真實體現系統變量之間的相關性；2)擴展熵是以比值代替概率，不受統計特性的限制，而且在信息損失量計算過程中，可以體現兩組變量對應位置之間的相關性；3)基於擴展熵信息瓶頸理論的聚類方法可以提供一個聚類的客觀截尾準則，而現有的方法中的截尾準則通常是人為指定聚類個數
發明內容本發明的目的之一在於提出一種基於擴展熵信息瓶頸理論的聚類方法，該方法以比例代替概率計算信息熵，可以不受概率特性的限制，而且可以為聚類提供一個客觀的聚類截尾準則，避免由主觀指定聚類個數的弊端。為達到上述目的，本發明採用的技術方案為該基於擴展熵信息瓶頸理論的聚類方法，包括步驟-根據樣本確定聚類數組及數組的取值，計算每個取值的比值；用比值代替概率計算數組的擴展熵；確定數組合併後聯合擴展熵的計算形式；根據信息瓶頸理論選擇信息損失量最小的聚類數組進行合併，生成一個新的數組；以聚類產生的信息損失量變化率作為確定聚類截尾準則，即獲得最終的聚類結果。圖1為本發明的基於擴展熵信息瓶頸理論的聚類方法流程圖；圖2為本發明實施例中醫辨證中由每步合併產生的信息損失量；圖3為本發明實施例交通流時間段劃分中道路分布圖4為本發明實施例交通流時間段劃分中由每步合併產生的信息損失量；圖5為本發明實施例交通流時間段劃分中聚類結果；圖6為本發明實施例交通流時間段劃分中由Fisher聚類結果。具體實施例方式為了更好地理解本發明，下面結合附圖和具體實施方式對本發明作詳細說明。聚類是通過分析變量之間的相關性將數據集合劃分為若干類的過程，使得類內差異小，類間差異大。聚類過程重要的是如何度量數據集合之間的相關性，並且能夠給聚類一個客觀的聚類標準。本發明提出了一種基於擴展熵信息瓶頸理論的聚類方法，該方法的具體操作方法介紹如下信息瓶頸理論首先介紹一下信息瓶頸理論。在給定一個目標集合，基於瓶頸原理的聚類方法是尋找在所有的聚類中使目標類與特徵之間的信息損失達到最小。設在目標空間義和特徵空間y上的聯合概率分布為p(x,力，信息瓶頸理論是找一個聚類i在給定聚類質量的約束條件下使信息損失y)-/(^;y)達到最小。i)是Z和1之間的互信息信息瓶頸理論源於Shannon的率失真理論，它提供了在給定失真約束的條件下分類數的下線，給定一個隨機變量l和失真測度^/(x"x》，Shannon的率失真理論是指在使平均失真最小的情況下可以僅用i個字節表示變量Z，失真率函數表示為Z)(i)=minS)其中S)=ZpW戶(SI力d(X仝)。由聚類f而導致的變量;r與y之間互信息損失可看作平均的失真測度dOc,;)=/(X;y)-/(i;}04,少pO)pO)=五")||由|幼其中D(/IIg)=~1ogC/7g)是K-L散度。可得到失真函數為Z)(i)=min(/(Z;r)—/(i;r))它正是信息瓶頸理論提出的最小化標準，即找到一個聚類使目標空間與特徵空間的互信息損失最小。設q和^是聚成的兩個類，由於兩個類聚到一起而導致的信息損失可表示為o(c!,c2)=/(q;r)+/(c2;r)-/(c,，c2;7)通過標準的資訊理論運算可得d(Cl，c2)=Z水,力log*,力-Z難uc2,力log*uc2,力其中/7(。)=^,|/|1|，lc」表示類c/的勢，pTl表示目標空間的勢，/7(qUC2)—C,UC2l/prl。在基於信息熵的概率合併中，假定兩類是相互獨立的，因此，並後的概率形式為兩類概率分布的和可以看出，兩類的合併只能體現各組中的y值總體概率分布的疊加，無法體現由於對應位置取值不同而產生的距離，該方法無法解決對於需要考慮位置對應的聚類問題。因此，本發明利用擴展熵的概念，將每個對應點看作變量y的取值，將該點對應的少值與該樣本所有y值和的比值作為該點的概率，這樣可以充分體現對應點的對應關係。基於擴展熵信息瓶頸理論的聚類方法設有W組數據《，/=1，2,…,iV，每組數據都對應"個正實數值_yn,，…，_ym，/=1,2,…，W，每個數值與該組所有數值總和的比值為formulaseeoriginaldocumentpage8l",)相當於上面提到的條件概率，顯然滿足1>"l《)=i，且K力l",)^o,/",2,…,"。這時，基於比值的擴展熵定義為產i設q,^為目前聚成的兩類數據，兩類數據合併後的每個數值所對應的比值為formulaseeoriginaldocumentpage8根據擴展熵的定義，兩組數據聚在一起而產生的信息損失定義為化，formulaseeoriginaldocumentpage8基於擴展熵信息瓶頸理論的聚類問題可以通過貪婪法由底向上合併的方式得到解決，該方法起始於最小的聚類集，即每一類只包括一個點，為了使聚類產生信息損失達到最小，每一步聚類都要使該聚類所產生的互信息損失最小。該方法即可以對樣本進行聚類，也可以對特徵變量進行聚類。該方法可以有效避免基於信息瓶頸理論中無法體現對應位置相關性的問題，例如，兩組數據:c={1,1,2,2}和^={2,2,1,1}，其概率分布分別為=0.5,;,(2)=0.5,;^(1)=0.5,&(2)=0.5。當用信息瓶頸理論時，聯合概率為/^(1)=0.5,p砂(2)-0.5，x與y合併產生的信息損失為0.當用擴展熵信息瓶頸理論時，每組數據都有4個變量，用1，2,3,4表示，每個變量的比值分別為&(1)=^(2)=1/6，a(3)=a(4)=1/3，&(1)=;^(2)=1/3，&(3)=^(4)=1/3，聯合比值為~(1)=~(2)=&(3)=~(4)=1/4。合併產生的信息損失為0.1634。因此，信息瓶頸理論不適合有位置對應的聚類問題。參考圖1，用基於擴展熵信息瓶頸理論的聚類過程的步驟總結如下-步驟一、首先將要聚類的對象看成最小的聚類集合，即每組數據都是一類；步驟二、對每對數據組都計算其合併所產生的信息損失量，選擇信息損失量最小的一對數據組，將兩數組並，合併後將其看作一個數組；步驟三、對合併後的數組對象重新按照步驟2進行聚類，直到所有數組合併成一類為止；步驟四、根據每一步聚類的信息損失量的變化率來確定聚類數，由於隨著聚類步驟的增加，信息損失量會逐漸增加，確定聚類數的一個客觀標準就是兩步之間的信息損失量有顯著變化，說明接下來聚類信息損失量太大而不能代表原數據對象。結合中醫的辨證論治問題，本發明基於擴展熵信息瓶頸理論的聚類方法，用於對從人體觀測到的中間症狀信息進行處理，通過聚類分析，得到證候所對應的症狀組合，包括如下具體步驟步驟一、根據樣本的模式，確定聚類數組，並將每個聚類數組看作一類，樣本數即為每個聚類數組的取值個數(數組的維數)。分析600份有關血瘀證病人的臨床數據，根據中醫理論可知，血瘀證中包含多種中醫證候要素，通過用客觀的數據挖掘方法來分析這些證候要素的症狀組合，為證侯要素的制定提供客觀依據。數據收集的是中醫四診信息，都用類型變量表示，0、l分別表示該症狀的無、有，共記錄了65個症狀。步驟二、計算每個聚類數組的比值，計算擴展熵。每個聚類數組對應600個取值，利用rCy,|《)=-^-計算每個取值與600個乂l+乂2+"'+乂力取值之和的比。然後利用S(乂,…,凡I《)=-|>"1《)1nK力l",)計算相應的擴展熵。步驟三、計算任意兩個聚類數組合併後的比值，並計算擴展熵。根據K^huc2)=Z^^K^lc,)計算兩個症狀集合合併後的各取值的比值。然後利用5(乂,'.',;;^1^^2)=—^>O0kuc2)lnK^Ic,uc2)計算聯合熵。步驟四、計算任意兩個聚類數組合併後產生的信息損失，選擇信息損失量最小的一組進行合併，然後重複步驟三，直至聚類結束。根據J(C,，C2):^SZ2K^l")l0g,;、計算任意兩組症狀合併後產生的信息損,=1,2—乂=1Kj^lqUC2)失，通過計算將損失量最小的一組進行合併，接下來的聚類步驟將其看作一個聚類數組，並將該信息損失量保存。由於在中醫辨證實際應用中，當一類中症狀個數大於7個時，通常沒有實際意義，因此我們在聚類過程中，需要加一定的限制，當一類中的聚類數組個數大於7個時，不能再與其它類進行合併。步驟五、根據每步產生的信息損失量，選擇變化顯著的一步作為聚類的最終結果。圖2為每步產生的信息損失量。表l為聚類結果，從結果可以看出，通過本發明的聚類方法的聚類結果可以看出，有13類的聚類結果與中醫臨床經驗相符，有明確的中醫意義。通過對比，本發明的聚類結果要好於以往的聚類結果。表ltableseeoriginaldocumentpage10tableseeoriginaldocumentpage11本發明另一實例為利用本發明對交通流時間序列進行時間段劃分。該實例是要實現根據交通流數據間的相關性，將一天的交通流分成不同的時間段，然後針對不同時間段對交通流數據進行分析，以提高分析的正確性。在時間序列聚類中，只有相鄰的數組才能夠進行合併。利用本發明基於擴展熵信息瓶頸理論的聚類方法對交通流時間序列時間段劃分。步驟一、根據樣本的模式，確定聚類數組，並將每個聚類數組看作一類，樣本數即為每個聚類數組的取值個數(數組的維數)。以採集的2007年6月1日到2007年7月1日濟南市經十路與山師東路和環山路交叉口交通流數據為研究對象，道路的分布情況參考圖3。數據採集設備為線圈檢測器，採集的交通流參數主要為流量、車速、時間佔用率三個參數，數據採集的時間間隔是5分鐘。從圖3可以看出，每個交叉口都有4個位置安裝了線圈檢測器，分別用1、2、3、4標出，這裡我們對經十路與山師東路交叉口的第2個位置所在車道的流量參數進行預測，該交叉口上遊路口為經十路與環山路的交叉口，與研究路口相關的參數為該交叉口第2個位置測得的流量參數。利用經十路與山師東路交叉口第2個檢測器2007年1月1日到2007年7月1日採集的流量數據進行時間段分段，在該段時間內採集的數據有一些缺失數據，為了不影響分析，將這些缺失數據的天數剔除，最後用來分析的有146天的交通數據，每天有288個數據採集點。以時間採集點為聚類變量，每個變量對應146個取值。步驟二、計算每個聚類數組的比值，計算擴展熵。每個聚類數組對應146個取值，利用formulaseeoriginaldocumentpage11計算每個取值與146個取值之和的比。然後利用formulaseeoriginaldocumentpage11計算相應的擴展熵。步驟三、計算任意兩個相鄰聚類數組合併後的比值，並計算擴展熵。由於該聚類屬於有序樣本聚類，只有相鄰數組可以進行合併，根據kuc2)=S^JL^K^k,)計算兩個相鄰時間點合併後的各取值的比值。然後利用S(^，...，yIc)uc2)=r1quc2)Inr(力|c,uc2)計算聯合熵。步驟四、計算任意兩個相鄰聚類數據合併後產生的信息損失，選擇信息損失量最小的一組進行合併，然後重複步驟三，直至聚類結束。根據d(q，C2)-ZZtK力l力log/(力W)、計算任意相鄰兩組數據合併後產生的信息損失，通過計算將損失量最小的一組進行合併，接下來的聚類步驟將其看作一個數組，並將該信息損失量保存。步驟五、根據每步產生的信息損失量，選擇變化顯著的一步作為聚類的最終結果。將一天288個時間點當作聚類點，每點由146個數據組成，由聚類產生的信息損失量參見圖4，當聚類到283步即將一天分成5段時信息損失量有顯著變化，因此我們選擇將一天分成5個時間段，分段結果和該路口一個月的交通數據參見圖5。當用Fisher有序樣本聚類方法進行聚類時，將一天分成5段的結果參見圖6。為了驗證聚類方法結果的好壞，我們針對聚類方法劃分的時間段進行交通流預測分析。用支持向量機進行交通流預測將要預測時間點流量用變量r表示，作為支持向量機的輸出，用變量《,…,X,表示預測點前6個時間點流量，變量17為上遊相關路口前一個時間點流量，變量Z8，…,《。表示當前路口前3天當前時間點的流量。變量A，…，^。作為支持向量機的輸入。預測結果的評價方法有很多指標，這裡採用平均絕對百分比誤差作為評價標準夕,一乂少，其中，w為測試樣本數，j),為樣本預測值，乂.為樣本測量值。分別對用基於擴展熵信息瓶頸理論的聚類和Fisher聚類得到的5個時間段進行分析，針對每個時間段，分別訓練支持向量機，選取每段中75%的數據作為訓練樣本，25%的數據作為測試樣本。用支持向量機進行預測的MAPE(平均絕對百分比誤差)如表2。從預測的結果可以看出，本發明提出的聚類方法獲得的結果更好。12M4戶五二丄t表2tableseeoriginaldocumentpage13本發明基於擴展熵信息瓶頸理論的聚類方法，主要是數組之間關係複雜而又無法用統計概率描述的數組集合聚類問題，該方法既可以體現數組之間複雜的關係，又可以體現數組對應位置之間的相關性，而且聚類方法可以提供一個客觀的聚類截尾準則。該聚類方法可以廣泛應用於醫學、藥學、智能交通、模式識別等領域的聚類問題。權利要求1、一種基於擴展熵信息瓶頸理論的聚類方法，其特徵在於，包括步驟根據樣本確定聚類數組及數組的取值，計算每個取值的比值；用比值代替概率計算聚類數組的擴展熵；確定數組合併後聯合擴展熵的計算形式；根據信息瓶頸理論選擇信息損失量最小的聚類數組進行合併，生成一個新的數組；以聚類產生的信息損失量變化率作為確定聚類結束的標準，即獲得最終的聚類結果。2、根據權利要求1所述的基於擴展熵信息瓶頸理論的聚類方法，其特徵在於，所述的聚類數組為一天中交通流釆集的時間點，有多少天的樣本，每個聚類數組就有多少個取值，每個取值的比值為該天在當前採集時間點的數值與所有天的數值和的比；或者，所述的聚類數組為中醫中的症狀，每個病人看作該症狀的取值，有多少個病人樣本就有多少個取值，每個取值的比值為每個病人該症狀的取值與所有病人該症狀取值和的比，其中病人的症狀通常為類型變量。3、根據權利要求1所述的基於擴展熵信息瓶頸理論的聚類方法，其特徵在於，用比值代替概率計算擴展熵，其計算公式為比值r表示為formulaseeoriginaldocumentpage2擴展熵為4、根據權利要求1所述的基於擴展熵信息瓶頸理論的聚類方法，其特徵在於，確定聯合擴展熵的計算形式聯合比值為formulaseeoriginaldocumentpage2其中，c,，q為已經生成的兩個類，lc,.l為類c,包含數組的個數；聯合擴展熵為S(JIuc2)=-》0,Iquc2)logr(>,Iquc2)。5、根據權利要求1所述的基於擴展熵信息瓶頸理論的聚類方法，其特徵在於，根據信息瓶頸理論，兩組數組合併所產生的信息損失量為formulaseeoriginaldocumentpage3其中，formulaseeoriginaldocumentpage36、根據權利要求1所述的基於擴展熵信息瓶頸理論的聚類方法，其特徵在於，聚類過程可分為以下幾步a.將每個聚類數組看作最初的類；b.選擇合併後產生的信息損失量最小的一組進行合併，生產新的數組；C.重複步驟b直至所有數組合併成一個類；d.根據信息損失量的變化率，選擇變化顯著的一步作為最後的聚類結果。7、根據權利要求1和權利6所述的基於擴展熵信息瓶頸理論的聚類方法，其特徵在於，聚類有一個客觀的截尾準則來確定最終的聚類個數，其確定過程為根據各步合併產生的信息損失量畫出一條曲線，在曲線斜率有顯著變化時，表示接下來的聚類由於信息損失太大而不能代表原始數據所包含的信息，可以將該步作為最終的聚類結果。全文摘要本發明公開了一種基於擴展熵信息瓶頸理論的聚類方法，主要是針對數據挖掘中無監督聚類問題，當聚類數組之間關係複雜而又無法用統計概率描述的數組集合聚類問題，該方法既可以體現數組之間複雜的相關性，又可以體現數組對應位置之間的對應關係，而且該聚類方法可以提供一個客觀的聚類截尾準則，有效避免由主觀指定聚類個數的缺陷。該聚類方法可以廣泛應用於醫學、智能交通、模式識別等領域的聚類問題。文檔編號G06F17/30GK101655847SQ20081013954公開日2010年2月24日申請日期2008年8月22日優先權日2008年8月22日發明者孫佔全申請人:山東省計算中心