數(shù)據(jù)挖掘中半結(jié)構(gòu)化數(shù)據(jù)

1、數(shù)據(jù)挖掘中半結(jié)構(gòu)化數(shù)據(jù)    摘  要 半結(jié)構(gòu)化數(shù)據(jù)是網(wǎng)絡(luò)中一種重要的數(shù)據(jù)形式，也是進行數(shù)據(jù)挖掘的重要基礎(chǔ)。因此要對Internet上巨量的數(shù)據(jù)進行數(shù)據(jù)挖掘，半結(jié)構(gòu)化數(shù)據(jù)及模型是前提。本文介紹了半結(jié)構(gòu)化數(shù)據(jù)的相關(guān)概念及其數(shù)據(jù)模型。     關(guān)鍵詞 半結(jié)構(gòu)化數(shù)據(jù)、數(shù)據(jù)挖掘、數(shù)據(jù)模型      1 數(shù)據(jù)挖掘與半結(jié)構(gòu)化數(shù)據(jù)模型 1.1 數(shù)據(jù)挖掘與異構(gòu)數(shù)據(jù)庫     數(shù)據(jù)挖掘(DM)是從在大型數(shù)據(jù)庫或數(shù)據(jù)倉庫中發(fā)現(xiàn)并提取隱藏在其中的信息或者知識

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、關(guān)算法的并行性、效率、動態(tài)性都提出了新的要求。進一步的工作包括模式提取、查詢表達及優(yōu)化、DBMS集成服務(wù)、將聚類方法應(yīng)用于半結(jié)構(gòu)化數(shù)據(jù)，以及為半結(jié)構(gòu)化數(shù)據(jù)提供適當?shù)牟樵兡Ｊ健?參考文獻 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