一種資料庫模式重構系統和方法
2023-09-27 06:37:00
專利名稱：一種資料庫模式重構系統和方法
技術領域：
本發明涉及計算機資料庫和數據挖掘領域，特別是涉及一種提高 多關係分類的資料庫模式重構系統和方法。
背景技術：
在當今資訊時代，網際網路上的很多數據都以 一個令人驚訝的速度 增長。我們要進行數據挖掘，就會用到分類，聚類這些方法從數據中
得到有用的模式。很多機器學習和數據挖掘都會面臨同樣一個問題 高維魔咒。在高維數據集面前，大部分方法都會低效，準確率下降， 處理時間增長。1970年，有計算機學家就提出屬性選擇是一個很有效 的方法，能夠解決高維魔咒的問題。事實上，屬性選擇就是一個學習 知識方法的預處理過程，它最大程度地去除無關和冗餘的信息，是一 個提高數據集質量的步驟。大量的實驗證明對訓練集進行屬性特徵選 擇後，對學習算法效率和準確率的提高都有好處。 但是，我們還是面臨著兩個問題
(1)在多關係的資料庫中，沒有一種屬性選擇的方法能夠適合多 關係的結構。由於不適合的原因，直接運用屬性選擇方法到多關係數 據庫是不成功的，也是不合理的。而多關係資料庫在日常生活中又是 隨處可見，並且逐漸成為存儲數據的流行格式，因此，缺乏對這種數 據庫進行屬性選擇方法會導致分類、聚類等應用的效率下降。
(2 )即使是用常規的單表屬性選擇方法對多表資料庫進行處理， 也會有效率不高，處理時間長的毛病。原因在於，在多關係資料庫中， 有些表的存在是沒有必要的，它們與類別的關係不大，造成了分類方
4法搜索上的浪費。因此，不僅僅要對每個表中的屬性進行選擇，還要 對表進行選擇。這樣才能提高分類應用的效率。
發明內容
本發明是鑑於上述技術問題而產生的。本發明的一個目的是提出 一種可提高多關係分類的資料庫模式重構系統和方法。
在一個方面中，根據本發明的資料庫模式重構系統包括多關係 資料庫，用於存儲若干多關係數據表；數據預處理器，用於對多關係 數據表中的多關係數據進行屬性與表的選擇和處理以對資料庫進行重 構；以及分類應用設備，用於對重構後的多關係資料庫進行訓練，用 產生的規則來預測新的數據。
在這個方面中，其中數據預處理器進一步包括構建模塊，用於
構建所述每個表中屬性與類別間的關係；屬性選擇模塊，用於計算出
單個表中的每個屬性與類別的相關性值以選擇單個表的屬性子集；關 系計算模塊，用於計算每個表的屬性子集與類別的相關性值；排序模
塊，用於根據每個表與類別的相關性值的大小來對表進行降序排列； 召回模塊，用於召回在屬性選擇模塊中未被選擇的屬性，並且該屬性 與類別的相關性值大於表的屬性子集與類別的相關性值中的最小值。
在一個方面中，根據本發明的資料庫模式重構方法包括步驟a、 構建每個表中屬性與類別間的關係；B、計算出單個表中的每個屬性與 類別的相關性值以選擇單個表的屬性子集；c、計算每個表的屬性子集 與類別的相關性值；D、根據每個表與類別的相關性值的大小來對表進 行降序排列；e、召回在步驟B中未被選擇的屬性，並且該屬性與類別 的相關性值大於表的屬性子集與類別的相關性值中的最小值。
在這個方面中，其中在步驟B中通過下述^^式來計算每個屬性與 類別的相關性值，其中InformationGain是計算屬性X與Y間的信息增益值，H (X)是計算屬性的熵值。
在這個方面中，其中在步驟c中通過屬性子集中所有屬性與類別
間相關性的平均值除以屬性間相關性的平均值來計算每個表的屬性子 集與類別的相關性值。
通過本發明，對多關係資料庫的結構進行了改造，使之按照與類 別大小的關係線性排列。由此使分類應用更快的找到與類別相關的表 與屬性，減少搜索空間，從而提高了分類的時間。
結合隨後的附圖，從下面的詳細說明中可顯而易見的得出本發明
的上述及其他目的、特徵及優點。在附圖中
圖1給出了根據本發明的資料庫模式重構系統的方框圖； 圖2給出了根據本發明的數據預處理器的詳細方框圖； 圖3給出了根據本發明的資料庫模式重構方法的流程圖； 圖4給出了根據本發明的多關係資料庫的示例； 圖5給出了根據本發明的多關係資料庫的示例； 圖6給出了根據本發明的重構後的資料庫的示例。
具體實施例方式
在下文中將詳細地論述的，本公開可以採用完全硬體的實施例、 完全軟體的實施例或包括硬體和軟體元件兩者的實施例的形式。在優 選實施例中，本公開可以用軟體來實施，其可以包括但不局限於固件、 駐留軟體、微碼等等。
為了更全面地理解本發明及其優點，下面結合附圖及具體實施例 對本發明做進一步詳細地說明。首先，參考圖1，對根據本發明的資料庫模式重構系統進行說明。 如圖1所示，該資料庫模式系統包括多關係資料庫、數據預處理 器、以及分類應用設備。
該多關係資料庫用於存儲若干多關係數據表，其中 一個多關係數
據表。圖4給出了多關係資料庫的一個示例。在該示例中，多關係數 據庫是金融資料庫，該資料庫有8張表，表間由主鍵和外鍵連接在一 起。長口圖5所示，表loan與表account之間有account—id這個屬性作為 主外鍵連結。目標表是loan表，目標屬性是status有兩個值，yes代表 此貨款(loan)按期償還，no代表此貨款沒有按期償還。
數據預處理器對多關係數據表中的多關係數據進行屬性與表的選 擇和處理以對資料庫進行重構。隨後參考圖2,對該數據預處理器進行 更詳細;也i兌明。
分類應用設備也就是多表分類器。該分類應用設備用於在一個多 關係環境下依靠原有的數據訓練出一個能夠自動預測新數據類別的分 類器。如果不經過我們資料庫模式重構的方法，分類應用設備也能對 現有的資料庫進行分類處理，但性能上有所不足。例如圖4中，分類 應用設備會先處理表loan,緊接著處理四個表trans、 account、 disposition 和order,依次下去。這樣的話，性能不足具體表現在訓練數據的時間 長，訓練後對新紀錄的預測準確度差。原因在於第一，按原有數據 庫模式，分類應用設備每次處理不止一個表，這樣訓練規則的時間增 長；第二，分類應用設備處理表的順序不是最優的，那麼得到的規則 不是最優的，造成預測新紀錄類別的準確度降低。然而，我們對數據 庫模式重構以後，這兩個缺陷有所彌補第一，重構後的資料庫模式 是鍊表結構，分類應用設備每次只會處理一個表，訓練時間減短；第 二，重構後的資料庫是按與類別相關性排序，也就是說，與類別最相 關的會優先處理，得到比原來更優化的規則。例如，原來的模式中，由於表district離表loan遠，所以很可能會漏掉這個MJ'J: district.avg—salary〈10000 => label=no,;也區人均》1欠入在一萬元以下時的 帳戶不會按期償還貨款。而這個規則實際上是4艮重要的，能幫助提高 預測準確度。
現在，參考圖2，對根據本發明的數據預處理器進行說明。 如圖2所示，該數據預處理器包括構建模塊、屬性選擇模塊、關 系計算模塊、排序模塊、以及召回模塊。
構建模塊用於構建每個表中屬性與類別間的關係。具體地說，將 資料庫中每個表裡的每條記錄都標記上類別。例如，在原有的資料庫 中，只有目標表loan中的記錄是包含類別的，而其餘7張表中記錄沒 有標記類別；若當前表中沒有類別屬性，則從目標表中通過主外鍵鏈 接的關係，把相應的類別值傳到當前表中，如圖6所示，表loan與表 account之間有Account ID這個屬性作為主外4建連結，才艮據這個連結， 把目標表loan中的LoanID傳到了 account表，並且把相對應的類別值 傳到了 account表。
屬性選擇模塊用於選擇單表的屬性子集。具體地說，按照下述公 式計算出單個表中的每個屬性與類別的相關性值。
i/(X) = -2>")log2,,》 \丄、，、
' 公式(1 J
其中該式計算屬性X的熵值，其中P (x)是計算屬性X取值x時 的概率值；
formula see original document page 8其中該式計算在Y取值y時，屬性X取值x的熵值formula see original document page 8
其中該式計算屬性X在屬性Y出現後的信息增益值
公式(2 ) 公式(3)formula see original document page 9該式是計算屬性與類別間的相關性值，其中InformationGain是計算 屬性X與Y間的信息增益值，H ( X)是計算屬性的熵值。按照相關性值的大小排序，值越大代表此屬性與類別越相關，然 後從中選出與類別最相關的屬性子集。關係計算模塊用於計算每個表的屬性子集與類別的相關性值。應 該說明的是表的屬性子集與類別的相關性值在下文中也被稱為表與類 別的相關性值。具體地說，利用下述公式計算出每個表中選出的屬性 子集作為一個整體與表之間的關係，即用屬性子集中所有屬性與類別 間相關性的平均值除以屬性間的相關性的平均值。formula see original document page 9其中，n代表屬性個數，s^表示每個屬性與表相關性值的平均值，*^#表示屬性間相關性值的平均值，其中屬性與表的相關性值和屬性間 相關性的值都是由公式4計算出來的。該式子計算結果是表與類別的 相關性，同樣的，該值越大代表該表與類別越相關。該式子計算表也 就是屬性集合與類別的相關性值。排序模塊用於根據每個表與類別的相關性值的大小對表進行降序 排列，如圖6所示，經過上述幾個步驟的計算，trans這個表與類別最 相關，所以把它排在loan表的附近，緊接著是order表，依次下去。這 樣即改變原有的資料庫空間結構，把原有的主外4建連結結構改成一定 順序的鍊表結構，把資料庫進行了重構。召回模塊用於召回在屬性選擇模塊中未被選"^奪的屬性，並且該屬 性與類別的相關性值大於表與類別的相關性值中的最小值。接下來，參考圖3,對根據本發明的資料庫模式重構方法進行說明。如圖3所示，該資料庫模式重構方法包括步驟A、 構建每個表中屬性與類別間的關係。具體地說，將資料庫中每個表裡的每條記錄都標記上類別。例如， 在原有的資料庫中，只有目標表loan中的記錄是包含類別的，而其餘 7張表中記錄沒有標記類別；若當前表中沒有類別屬性，則從目標表中 通過主外鍵連結的關係，把相應的類別值傳到當前表中，例如圖5中， account表沒有類別，那麼通過主外鍵傳遞，account表獲得類別在最後 一列，用符號"+"代表yes,符號"-"代表no;如果有的記錄沒有 得到類別值，則刪去。如圖6所示，AccountID=67這一行沒有從loan 表中得到類別值，則我們認為它沒有分類信息，刪去。此外，如圖5 所示，表loan與表account之間有Account ID這個屬性作為主外4建連 接，根據這個連結，把目標表loan中的Loan ID傳到了 account表，並 且把相對應的類別值傳到了 account表，這樣操:作沒有經過物理連接， 而是虛擬連接，節省了時間和空間，減少了代價。B、 對單個表的屬性進行選擇。具體地說，屬性選擇方法是現有的技術，主要是利用信息熵這個 概念，信息熵是資訊理論中用於度量信息量的一個概念。也就是說，從 單表中選出一個屬性子集，使這個子集中的每個屬性都與類別相關， 並且每個屬性間的冗餘最小。也就是說，按照下述公式計算出單個表 中的每個屬性與類別的相關性值。i/(x) = -p")log2(/^)) \ L、，、' 公式(1 )其中該式計算屬性X的熵值，其中P (x)是計算屬性X取值x時 的概率值；I JO = -S屍(力)S屍"I力)i。g2 I ^))乂 ' 公式(2)其中該式計算在Y取值y時，屬性X取值x的熵值；formula see original document page 11其中該式計算屬性X在屬性Y出現後的信息增益值。formula see original document page 11
該式是計算屬性與類別間的相關性值，其中InformationGain是計算 屬性X與Y間的信息增益值，H ( X)是計算屬性的熵值。按照相關性值的大小排序，值越大代表此屬性與類別越相關，然 後從中選出與類別最相關的屬性子集。C、計算每個表的屬性子集與類別的相關性值，即利用下述公式計 算出每個表中選出的屬性子集作為一個整體與表之間的關係，用屬性 子集中所有屬性與類別的相關性值的平均值除以屬性間的相關性值的 平均值。其中，n代表屬性個數，s^/表示每個屬性與表相關性值的平均值， ^表示屬性間相關性值的平均值，其中屬性與表的相關性值和屬性間 相關性的值都是由公式4計算出來的。該式子計算結果是表與類別的 相關性，同樣的，該值越大代表該表與類別越相關。該式子計算也就 是屬性子集與類別的相關性值。D、根據每個表與類別的相關性值的大小來對表進行降序排列，如 圖6所示，經過上述幾個步驟的計算，trans這個表與類別最相關，所 以把它排在loan表的附近，緊接著是order表，依次下去。這樣即改變 原有的資料庫空間結構，把原有的主外鍵連結結構改成一定順序的鏈 表結構，把資料庫進行了重構，這樣的好處在於使得與類別最相關 的表離目標表近，分類器能儘早的處理，提高分類效率。如圖6所示， 圖6給出了重構後的資料庫。公式(5 )E、召回去除的一些屬性，即步驟B中有些屬性被去除了，如果此 屬性與類別的相關性的值大於表與類別的相關性值中的最小值，則召 回。例如，表trans中有屬性A，在單表屬性選擇過程中沒^皮選中。在 本步驟中，如屬性A與類別的相關性值大於account表與類別的相關性 值(此資料庫結構中相關性值最小的表)，則把屬性A召回。通過上面的描述可知，根據本發明的方法可以適用於多關係數據 庫。多關係資料庫在當今社會是最豐富、最常見的數據存儲格式。但 是對多關係資料庫進行屬性選擇優化的方法幾乎沒有，最直接的方法 就是把處理單關係資料庫的方法用到多關係資料庫上，但是會造成格 式不符，還需要進行格式的轉換，所以本方法填補了這一空白。此外， 本發明對多關係資料庫進行了優化，使得分類應用的效率提高。新的 方法對多關係資料庫的結構進行了改造，使之按照與類別大小的關係 線性排列。這樣排列的好處在於使分類應用更快的找到與類別相關的 表與屬性，減少搜索空間，從而提高了分類的時間。而且這個方法解 決了一個問題如果有個表在資料庫中離目標表很遠，而分類應用會 從目標表開始進行搜索，有可能停止的時候並沒有搜索到這個遠離的 表，對分類準確度也很大的影響。對於本領域的普通技術人員來說可顯而易見的得出其他優點和修改。因此，具有更廣方面的本發明並不局限於這裡所示出的並且所描 述的具體說明及示例性實施例。因此，在不脫離由隨後權利要求及其 等價體所定義的 一般發明構思的精神和範圍的情況下，可對其做出各 種修改。
權利要求
1、一種資料庫模式重構系統包括多關係資料庫，用於存儲若干多關係數據表；數據預處理器，用於對多關係數據表中的多關係數據進行屬性與表的選擇和處理以對資料庫進行重構；以及分類應用設備，用於對重構後的多關係資料庫進行訓練，用產生的規則來預測新的數據。
2、 根據權利要求1的資料庫模式重構系統，其中數據預處理器進一 步包括構建^^塊，用於構建所述每個表中屬性與類別間的關係；屬性選擇才莫塊，用於計算出單個表中的每個屬性與類別的相關性值以選擇單個表的屬性子集；關係計算模塊，用於計算每個表的屬性子集與類別的相關性值； 排序模塊，用於根據每個表與類別的相關性值的大小來對表進行降序排列；召回模塊，用於召回在屬性選擇模塊中未被選擇的屬性，並且該 屬性與類別的相關性值大於表的屬性子集與類別的相關性值中的最小值。
3、 一種用於資料庫模式重構系統的方法，其中該系統包括存儲若干 多關係數據表的多關係資料庫、數據預處理器、以及分類應用設備， 該方法包括A、構建每個表中屬性與類別間的關係；B 、計算出單個表中的每個屬性與類別的相關性值以選擇單個表的 屬性子集；C、 計算每個表的屬性子集與類別的相關性值；D、 根據每個表與類別的相關性值的大小來對表進行降序排列；E、召回在步驟B中未被選擇的屬性，並且該屬性與類別的相關性 值大於表的屬性子集與類別的相關性值中的最小值。
4、 根據權利要求3的方法，其中在步驟B中通過下述公式來計算每 個屬性與類別的相關性值，其中InformationGain是計算屬性X與Y間 的信息增益值，H (X)是計算屬性的熵值。formula see original document page 3
5、 根據權利要求4的方法，其中在步驟C中通過屬性子集中所有屬 性與類別間相關性的平均值除以屬性間相關性的平均值來計算每個表 的屬性子集與類別的相關性值。
全文摘要
一種資料庫模式重構系統和方法，其中該系統包括存儲若干多關係數據表的多關係資料庫、數據預處理器、以及分類應用設備，該方法包括A.構建每個表中屬性與類別間的關係；B.計算出單個表中的每個屬性與類別的相關性值以選擇單個表的屬性子集；C.計算每個表的屬性子集與類別的相關性值；D.根據每個表與類別的相關性值的大小來對表進行降序排列；E.召回在步驟B中未被選擇的屬性，並且該屬性與類別的相關性值大於表的屬性子集與類別的相關性值中的最小值。
文檔編號G06F17/30GK101576906SQ200910078789
公開日2009年11月11日 申請日期2009年3月3日 優先權日2009年3月3日
發明者軍 何, 劉紅巖, 杜小勇, 泊 胡 申請人:杜小勇