數(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ù)形式，也是進(jìn)行數(shù)據(jù)挖掘的重要基礎(chǔ)。因此要對(duì)Internet上巨量的數(shù)據(jù)進(jìn)行數(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ù)庫(kù)     數(shù)據(jù)挖掘(DM)是從在大型數(shù)據(jù)庫(kù)或數(shù)據(jù)倉(cāng)庫(kù)中發(fā)現(xiàn)并提取隱藏在其中的信息或者知識(shí)

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

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

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

5、些數(shù)據(jù)進(jìn)行分析、集成、處理就無(wú)從談起。針對(duì)Internet上的數(shù)據(jù)半結(jié)構(gòu)化的特點(diǎn)，尋找一個(gè)半結(jié)構(gòu)化的數(shù)據(jù)模型則成為了解決上述問(wèn)題的關(guān)鍵所在。此外，除了要定義這樣一個(gè)半結(jié)構(gòu)化數(shù)據(jù)模型外，還需要一項(xiàng)技術(shù)能夠自動(dòng)地從現(xiàn)有數(shù)據(jù)中將這個(gè)模型抽取出來(lái)，這就是所謂的模型抽取技術(shù)。因此半結(jié)構(gòu)化數(shù)據(jù)模型及其抽取技術(shù)是面向Internet的數(shù)據(jù)挖掘技術(shù)實(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頁(yè)面的顯示而與html語(yǔ)言的標(biāo)記符號(hào)嵌在一起，構(gòu)成了物理上的半結(jié)構(gòu)

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

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

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

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

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

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

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

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

14、不同的是，此處的集合類似一種記錄結(jié)構(gòu)，即對(duì)象MTV的值是具有不同標(biāo)記的子對(duì)象集合，每個(gè)標(biāo)記相當(dāng)于結(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ù)，后有模式；不對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行強(qiáng)制約束，只描述數(shù)據(jù)的結(jié)構(gòu)信息；它是只描述數(shù)據(jù)部分結(jié)構(gòu)的非精確模式；隨著被描述對(duì)象數(shù)據(jù)的不斷更新而動(dòng)態(tài)變化，分析半結(jié)構(gòu)化數(shù)據(jù)的特點(diǎn)及產(chǎn)生原因，半結(jié)構(gòu)化數(shù)據(jù)查詢應(yīng)該能夠處理:     (1)單值和集合值屬性兼容。即同一查詢對(duì)應(yīng)不同的半結(jié)構(gòu)化數(shù)據(jù)，結(jié)果可能是單值，也可能是集合

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

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