1、數據挖掘中半結構化數據    摘  要 半結構化數據是網絡中一種重要的數據形式，也是進行數據挖掘的重要基礎。因此要對Internet上巨量的數據進行數據挖掘，半結構化數據及模型是前提。本文介紹了半結構化數據的相關概念及其數據模型。     關鍵詞 半結構化數據、數據挖掘、數據模型      1 數據挖掘與半結構化數據模型 1.1 數據挖掘與異構數據庫     數據挖掘(DM)是從在大型數據庫或數據倉庫中發現并提取隱藏在其中的信息或者知識

2、的過程。其目的是幫助分析人員尋找數據之間的關聯，發現被忽略的要素，而這些信息對于預測趨勢和決策行為是十分有用的。     數據挖掘源于人工智能的機器學習領域，其實質的內涵是在一個已知狀態的數據集(DataSet)上，通過設定一定的學習算法，從數據集中獲取所謂的知識。知識發現技術的相關研究為數據挖掘技術提供了堅實的理論基礎，數據挖掘技術實際上是人工智能領域中的知識發現技術和數據庫技術共同發展的結果。     傳統意義的數據庫、數據倉庫和上面我們提到的Internet中的數據是我們所擁有的數據資源，也是進行數據挖掘的基礎。傳統數據庫中的數

3、據結構性很強，其中的數據為完全結構化的數據；數據倉庫是由數據庫導出的用于分析型的數據環境；我們可把Web網站上的信息看作一個數據庫，一個更大、更復雜的數據庫，Web上的每一個站點就是一個數據源，每個數據源都是異構的，因而每一站點之間的信息和組織都不一樣，這就構成了一個巨大的異構數據庫環境。 1.2 半結構化數據模型與數據挖掘     Internet上的數據與傳統的數據庫中的數據不同，傳統的數據庫都有一定的數據模型，可以根據模型來具體描述特定的數據，同時可以很好地定義和解釋相關的查詢語言。而Internet上的數據非常復雜，沒有特定的模型描述，每一站點的數據都各自

4、獨立設計，并且數據本身具有自述性和動態可變性，其結構也不可琢磨，是一種我們稱之為半結構化數據。所謂半結構化是相對于結構化(傳統數據庫)和非結構化(如一本書、一張圖片等)而言的。但是Internet上存在的數據既不是完全結構化的也不是完全非結構化的，因為它的頁面也具有一定的描述層次的，存在一定的結構，所以我們將它稱為半結構化的數據。如果想要利用Internet上的數據進行數據挖掘，必須先要研究站點之間異構數據的集成問題，只有將這些站點的數據都集成起來，提供給用戶一個統一的視圖，才有可能從巨大的數據資源中獲取所需的東西。其次，還要解決Web上的數據查詢問題，因為如果所需的數據不能很有效地得到，對這

5、些數據進行分析、集成、處理就無從談起。針對Internet上的數據半結構化的特點，尋找一個半結構化的數據模型則成為了解決上述問題的關鍵所在。此外，除了要定義這樣一個半結構化數據模型外，還需要一項技術能夠自動地從現有數據中將這個模型抽取出來，這就是所謂的模型抽取技術。因此半結構化數據模型及其抽取技術是面向Internet的數據挖掘技術實施的前提。 2 半結構化數據的定義     半結構化數據有兩層含義，一種是指在物理層上缺少結構的數據，另一種是指在邏輯層上缺少結構的數據。有一些結構化數據，為用于web頁面的顯示而與html語言的標記符號嵌在一起，構成了物理上的半結構

6、化數據。Internet中有大量豐富的數據，這些數據多存在于html文件中，沒有嚴格的結構及類型定義，這些都是邏輯層半結構化的數據。Internet上的數據與傳統數據庫中的數據不同，傳統的數據庫都有一定的數據模型，可以根據模型來具體描述特定的數據.而上的數據非常復雜，沒有特定的模型描述，每一站點的數據都各自獨立設計，并且數據本身具有自述性和動態可變性.因而，Internet上的數據具有一定的結構性，但因自述層次的存在，是一種非完全結構化的數據，這也被稱為半結構化數據。半結構化是上數據的最大特點。     半結構化數據主要來源有3方面:   &#

7、160; 1）在WWW等對存儲數據無嚴格模式限制的情形下，常見的有HTML、XML和SGML文件；     2）在電子郵件、電子商務、文獻檢索和病歷處理中，存在著大量結構和內容均不固定的數據；     3）異構信息源集成情形下，由于信息源上的互操作要存取的信息源范圍很廣，包括各類數據庫、知識庫、電子圖書館和文件系統等。 3 半結構化數據具有如下特點:       隱含的模式信息     雖然具有一定的結構，但結構和數據混合在一起，沒有顯式的模式定義(HMTL文件是一

8、個典型)。       不規則的結構     一個數據集合可能由異構的元素組成，或用不同類型的數據表示相同的信息。       沒有嚴格的類型約束     由于沒有一個預先定義的模式，以及數據在結構上的不規則性，導致缺乏對數據的嚴格約束。 4  半結構化數據的數據模型     半結構化數據是缺乏嚴格、完整結構的數據。這類數據并非毫無結構，但它們的結構可能是隱含的、不完整的，甚至可能是需要不斷修改的。要對這樣的數據進行

9、查詢等處理，首要問題就是對半結構化的數據進行描述。由于沒有強制性模式限制，使半結構化數據具有很大靈活性，能夠滿足網絡這種復雜分布式環境需要，但同時也給數據描述和處理帶來了很大困難。 4.1 半結構化數據的表示     具體地，象WWW這種數據模型可表示成3種關系：     Obj(oid)，Ref(source，label，destination)，Val(oid，value) 其中Obj表示一個無限的對象集合，例如WWW上的網頁，網頁中的內容都可看成是對象。Ref(o1，label，o2)表示從源對象o1到目標對象o2間存在一種聯系

10、，這種聯系的語義信息用標記label表示。在我們的實現中，這種聯系不僅包括了網頁間存在的鏈接，而且當某個網頁Pageobj包含多個具有相同意義的對象o1，o2，on時，可以引入一個虛擬對象Vobj，這樣，網頁代表的對象Pageobj作為源對象，虛擬對象Vobj作為其目標對象，而o1，o2，on又作為Vobj的目標對象，并且Vobj與o1，o2，on的聯系都有相同的標記。如，在我校圖書館的電子資源的網頁中，包含對象中國期刊網，而其具體的論文的題目等內容在另一個頁面，這樣對象中國期刊網與鏈接所指頁面就是源與目標對象的關系。關系Val（oid，value）提供了原子對象的取值信息，例如可以將每一篇論

11、文作為一個對象，它的值為論文的題目。 4.2 半結構化數據的數據模型     目前，對半結構化數據及其模式主要有五種描述方法:基于圖的描述形式、基于樹的描述形式、基于邏輯的描述形式、基于關系的描述形式以及基于對象的描述形式?；趫D的描述形式一般對半結構化數據采用標記有向圖(labeled directed graph)來表示，其中最有代表性的是OEM(Object Exchange Model)模型。這種描述形式的一個顯著優點是模式和數據采用同一種數據模型(圖模型)，非常便于處理。模式數據圖通常是一個有根且帶邊標記的有向圖，模式圖的邊標記可以與數據圖相同，也可以加

12、以擴充，如允許正規式形式，或采用特定形式規則，等等。對于模式圖中的節點，可以加一定注釋，表明其代表語義或其它特定含義。     一般地，一個OEM對象表示為：    OID:    Label    Type    value         即OEM對象由4部分組成：對象的標識OID，標記，類型，值。其中OID唯一標識了一個OEM對象，

13、既可以是一個無符號整數，也可以是某個用于描述該對象出自何處的表達式；標記表達一種語義信息，即對象表示的是什么；對象值的類型可取集合類型或原子類型；對象的值可以是原子值或是對象集合。OEM是一種基于圖的數據模型，對象對應節點，對象與對象的關系以帶標記的邊表示。如下圖所示：        圖中，頂層結點為根對象，其標記為Music，它的值為一對象集合，因此其類型為set型。在構成Music值的對象集合中，MTV是其中的一個成員。當然，可能還有其它的標記為song的對象出現在該集合中。對象MTV的取值類型也是set型，然而與MTV

14、不同的是，此處的集合類似一種記錄結構，即對象MTV的值是具有不同標記的子對象集合，每個標記相當于結構的域。 5 半結構化數據的模式與以往關系數據模式的區別     半結構化數據的模式與傳統的關系數據模式或面向對象數據模式的區別在于:先有數據，后有模式；不對數據結構進行強制約束，只描述數據的結構信息；它是只描述數據部分結構的非精確模式；隨著被描述對象數據的不斷更新而動態變化，分析半結構化數據的特點及產生原因，半結構化數據查詢應該能夠處理:     (1)單值和集合值屬性兼容。即同一查詢對應不同的半結構化數據，結果可能是單值，也可能是集合

15、值。     (2)不同的查詢對象數據類型。如HMTL文件中同一項目可以是描述信息，也可以是一個鏈接(網址)。     (3)未知結構的查詢對象。有時查詢對象往往是部分結構已知，需要通過一些機制了解數據源中的對象結構及關聯的內容。 6 結語     隨著Internet的日益普及，半結構化數據源也將會越來越豐富，因而如何有效地利用這些豐富的信息資源也逐漸受到人們的重視。半結構化數據是網絡數據的一種重要形式，是一種特殊的數據資源，在半結構化數據上進行數據組織、管理和分析的技術有不同于結構化數據的特點，并對相

16、關算法的并行性、效率、動態性都提出了新的要求。進一步的工作包括模式提取、查詢表達及優化、DBMS集成服務、將聚類方法應用于半結構化數據，以及為半結構化數據提供適當的查詢模式。 參考文獻 1SergeAbiteboul.Queryingsemi-structureddata.In:FotoAfrati，PhokionKolaitiesed.Lecture Notes in Computer Science 1186，Database Theory-ICDT97.New York， Springer-Verlag， 1997，1-18. 2FlorescuD.DatabaseTechniquesfortheWorld-WideWeb:ASurvey.ACM