基於主成分分析方法確定超平面的任務分解方法
2023-12-06 16:21:21
專利名稱：基於主成分分析方法確定超平面的任務分解方法
技術領域：
本發明涉及一種智能信息處理技術領域的任務分解方法，具體是一種基於主成分分析方法確定超平面的任務分解方法。
背景技術：
最小最大模塊化分類器(簡稱M3分類器)是一種新型的模式分類器。最小最大模塊化分類器按照訓練集劃分將K類問題分解成多個二類問題，每個二類問題由一個基分類器進行訓練。各個基分類器的分類結果通過MIN單元和MAX單元組合成最終的分類結果，其中的基分類器可以是某種簡單的判別器，k-NN分類器、SVM或多層神經網絡等。最小最大模塊化分類器在模式分類上具有分類精度高、訓練速度快和大規模並行性的特點，已經被成功地應用於解決文本分類、工業故障檢測、腦信號分類、詞性標註等問題。
在傳統的最小最大模塊化分類器任務分解過程中，對於訓練集的劃分是隨機進行的。這種隨機的訓練集劃分方法，不能保證不同的訓練集劃分對最終組合分類器具有穩定的、良好的分類精度。然而，對於彈性的分類來說，常常涉及到多種不同規模的任務分解需求，這就提出了基於訓練集劃分的有效的任務分解問題。因此，是否能夠找到一種有效的任務分解方法，對於最小最大模塊化分類器是一件非常重要的任務。
經對現有技術的文獻檢索，至今尚未發現與本發明主題相同或者類似的文獻報導。
發明內容
本發明的目的在於針對現有技術中存在的不足，提出一種基於主成分分析方法確定超平面的任務分解方法，使其用於最小最大模塊化分類器的任務分解，以實現保證彈性任務分解情形下的組合分類精度的目的。
本發明是通過以下技術方案實現的，本發明利用一組平行的超平面對各個單類訓練集作分割，使用主成分分析方法中的散度矩陣的特徵向量作為劃分的一組超平面的法向量，在訓練集的超平面劃分中，採用訓練樣本數量的加權排序實現樣本的順序抽取，繼而將分割的訓練子集按照最小最大模塊化分類器的要求實現指定的任務分解。具體描述為兩個步驟如下第一個步驟，所述的超平面法向量，其確定方法如下(1)計算所有樣本的均值m=k=1nxk]]>(2)計算該訓練集所有輸入樣本的散度矩陣S=k=1n(xk-m)(xk-m)T]]>(3)計算散度矩陣的最大特徵值e，取劃分超平面的法向量A＝e。
其中，xk是第k個訓練樣本，n是單類樣本數量，m是單類樣本均值，S是全部單類訓練樣本的散度矩陣，e是S的最大特徵值。
第二個步驟，所述的訓練集的超平面劃分，具體實現如下(1)對於每個類別，按照第一個步驟確定相應的超平面PAx＝0；(2)計算單類訓練集中所有樣本x的加權值d(x，P)＝Ax；(3)對於所有這些值Ax排序；(4)根據各個子集的樣本數量要求，順序抽取指定數量的樣本數量構成劃分後的子樣本集；(5)對於各個單類劃分出來的各個單類訓練子集，按照最小最大模塊化分類器的要求實現各個子任務生成，從而實現所要求的任務分解。
其中，P是超平面代號，A是按照第一個步驟確定的超平面法向量，x是任意一個單類訓練樣本，d(x，P)表示所需的加權值。
最小最大模塊化分類器的實現分為兩個步驟，第一個步驟是多類到二類的分解以及對應的結果合成，第二個步驟是二類問題的進一步分解和對應的結果合成。
對於一個多類問題，根據一類對一類分解策略實現任務分解，也就是對於一個K類問題，分別一一搭配不同類別的訓練集，生成K(K-1)/2個訓練集對，用對應的K(K-1)/2個二類分類器進行訓練。從而實現了多類到二類問題的分解。記各個二類分類器為Mij，0＜＝i，j＜k且i和j不等。如果Mij的分類結果為1，表明這個二類分類器支持i類的分類結果，如果分類輸出為0，則表明它支持j類的分類結果。對於每一個二類分類器Mij，將其結果取反作為分類器的Mij結果，這樣可以本發明可以調用K(K-1)個二類分類器。稱這樣一些二類分類器Mij，j＝0，1，2，…，K-1，且i和j不等為一組二類分類器。i稱為它的組號。對於各個二類分類器的測試結果的組合，使用兩個階段來實現，第一階段，在各組二類分類器中，所有的二類分類器輸出的分類結果Min操作作為該組的類別輸出，這裡Min操作是從多個輸入中找出最小的輸入。第二階段，將第一階段的操作的所有結果進行Max操作得到本階段的組合結果，這裡Max操作是從多個輸入中找出最大的輸入。如果第二階段的組合結果是0，則組合分類結果本發明定義為未知類別，也就是不是任何已知的類別，如果第二階段的組合結果是1，則在Max過程中導致了這個結果的那一組二類分類器的組號作為最終的組合分類結果。
對於一個二類問題，將其類別輸出分別表示為0和1。設，0類訓練集劃分為n個模塊，1類訓練集劃分為m個模塊。分別完全搭配這m個和n個訓練集產生m*n個訓練集對。如果每個訓練集對由一個二值分類器來學習，就將一個原始的較大規模的二類問題分解為m*n個較小規模二類問題。對於原始的二類問題，稱用於解決分解後產生的較小規模的二類問題的二值分類器為相應的基分類器。
設原始分類問題中，用Tij表示劃分後的訓練集對，其中i＝1，2，...，m，j＝1，...，n，相對應的基分類器表示為Xij。最小最大組合定義了如何將這m*n個基分類器的分類結果重新合成為原始問題的分類結果。在組合之前，需要對m*n個基分類器進行分組，對於一個固定的i，定義Xij，其中j＝1，...，n，為一個1類組。i稱為該組的組號。分類結果的最小最大組合過程分為兩個階段第一階段，在各個1類組中，所有的基分類器輸出的分類結果Min操作作為該組的類別輸出，這裡Min操作是從多個輸入中找出最小的輸入。第二階段，將第一階段的操作的所有結果進行Max操作就得到組合後的最終分類結果，這裡Max操作是從多個輸入中找出最大的輸入。
本發明提出了使用一種簡單的排序過程來實現這個超平面劃分過程，避免了巨量的聚類算法的時間消耗，同時它有效地保證了分解後產生的分類器組合的精度，避免了以往的隨機的樣本抽取過程無法保證最終的分類器組合精度的情況。此外，基於超平面劃分方法產生的最小最大模塊化分類器具有更好的測試性能。
具體實施例方式
以下結合本發明的內容提供具體實施例實施例1數據集取自UCI資料庫和STATLOG benchmark repository的3組兩類數據，數據特性如表1所示。
由於二類問題是所有分類問題的基礎，多類問題總是可以通過二類問題組合的最小最大化等方法實現，而本發明提出的技術也只需要考慮單類上的訓練集分解，具體的實現和類別數特性無關。因此，二類問題分類效果展示足以本發明提出的技術的效果。
表1。數據集的類別信息和SVM訓練參數
針對兩類較小規模的那個類別，依次分為2到26個模塊，較大的類別進行對應的劃分，使得劃分出來的單類樣本數量和較小類別的單類樣本數量相當。兩種分類算法k-NN和RBF核的SVM用來進行算法效果的驗證工作。SVM訓練參數如表1所示。k-NN算法均使用從1-40的40組不同k值進行測試。
實施過程具體如下1、按照隨機劃分和本發明所提的方法分別進行單類訓練集上的指定模塊規模的劃分。
2、按照最小最大模塊化分類器的構成方法進行訓練，分別使用k-NN分類器和SVM分類器。
3、對於測試集中的樣本進行逐一測試，按照最小最大模塊化分類器的結果合成方法輸出測試結果。
通過比較隨機訓練集劃分、法向量A＝[1，1，…，1]的超平面劃分以及由主成分分析方法確定的超平面劃分的分類精度，所獲得的結論是，由主成分分析方法確定的超平面劃分的分類精度在所有數據集上是最佳的，同時分類精度曲線平穩，能夠有效保證更多模塊數量下的組合分類器的分類效果。在不同的數據集上的一致效果表明了本發明所提方法的通用性。
實施例2基分類器採用SVM算法。SVM訓練參數如表1所示。針對兩類較小規模的那個類別，依次分為2到26個模塊，較大的類別進行對應的劃分，使得分出來的單類樣本數量和較小類別的單類樣本數量相當。
實施過程具體如下1、按照隨機劃分和本發明所提的方法分別進行單類訓練集上的指定模塊規模的劃分。
2、按照最小最大模塊化分類器的構成方法進行SVM分類器訓練。
3、對於測試集中的樣本進行逐一測試，按照最小最大模塊化分類器的結果合成方法輸出測試結果。
通過比較隨機訓練集劃分、法向量A＝[1，1，…，1]的超平面劃分以及由主成分分析方法確定的超平面劃分的分類速度，所獲得的結論是，由主成分分析方法確定的超平面劃分在所有數據集上的分類速度是最快的。在不同的數據集上的一致效果表明了本發明所提方法的通用性。
權利要求
1.一種基於主成分分析方法確定超平面的任務分解方法，其特徵在於，利用一組平行的超平面對各個單類訓練集作分割，使用主成分分析方法中的散度矩陣的特徵向量作為劃分的一組超平面的法向量，在訓練集的超平面劃分中，採用訓練樣本數量的加權排序實現樣本的順序抽取，繼而將分割的訓練子集按照最小最大模塊化分類器的要求實現指定的任務分解。
2.根據權利要求1所述的基於主成分分析方法確定超平面的任務分解方法，其特徵是，所述的超平面法向量，其確定方法如下(1)計算所有樣本的均值m=k=1nxk]]>(2)計算該訓練集所有輸入樣本的散度矩陣S=k=1n(xk-m)(xk-m)l]]>(3)計算散度矩陣的最大特徵值e，取劃分超平面的法向量A＝e。其中，xk是第k個訓練樣本，n是單類樣本數量，m是單類樣本均值，S是全部單類訓練樣本的散度矩陣，e是S的最大特徵值。
3.根據權利要求1所述的基於主成分分析方法確定超平面的任務分解方法，其特徵是，所述的訓練集的超平面劃分，具體實現如下(1)確定相應的超平面PAx＝0；(2)計算單類訓練集中所有待分樣本x的加權值d(x，P)＝Ax；(3)對於所有這些值Ax排序；(4)根據各個子集的樣本數量要求，順序抽取指定數量的樣本數量構成劃分後的子樣本集；(5)對於各個單類劃分出來的各個單類訓練子集，按照最小最大模塊化分類器的要求實現各個子任務生成，從而實現所要求的任務分解。其中，P是超平面代號，A是按照第一個步驟確定的超平面法向量，x是任意一個單類訓練樣本，d(x，P)表示所需的加權值。
全文摘要
一種用於智能信息處理技術領域的基於超平面劃分過程可以用於最小最大模塊化分類器的任務分解，使用主成分分析方法來確定該超平面的方向。本發明提出了使用一種簡單的排序過程來實現這個超平面劃分過程，避免了巨量的聚類算法的時間消耗，同時它有效地保證了分解後產生的分類器組合的精度，避免了以往的隨機的樣本抽取過程無法保證最終的分類器組合精度的情況。此外，基於超平面劃分方法產生的最小最大模塊化分類器具有更好的測試性能。
文檔編號G06K9/62GK1713210SQ20051002771
公開日2005年12月28日 申請日期2005年7月14日 優先權日2005年7月14日
發明者趙海, 呂寶糧 申請人:上海交通大學