黃鑫

摘要：由于現(xiàn)在科學(xué)技術(shù)的迅猛發(fā)展以及人民生活水平的不斷提升，互聯(lián)網(wǎng)行業(yè)在悄無聲息的進(jìn)入大眾的生活中，計(jì)算機(jī)也被應(yīng)用在各行各業(yè)中。從社會網(wǎng)絡(luò)到蛋白質(zhì)交互網(wǎng)絡(luò)等不同的領(lǐng)域產(chǎn)生了大量的數(shù)據(jù)，而圖作為統(tǒng)計(jì)這些巨大數(shù)據(jù)的一個(gè)載體不僅能精確的描述出數(shù)據(jù)的屬性，還能說明數(shù)據(jù)結(jié)構(gòu)的特征，這些優(yōu)勢讓以不確定圖模型的數(shù)據(jù)挖掘算法在社會中得到廣泛的應(yīng)用。

關(guān)鍵詞：數(shù)據(jù)；挖掘算法；不確定圖

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）12-0182-02

Research on Data Mining Algorithm -- with Uncertain Graph Model as an Example

HUANG Xin

（Dehong Normal College， Dehong 678400， China）

Abstract： since the rapid development of science and technology and the continuous improvement of people's living standards， the Internet industry in quietly into the public life， computer has been used in all walks of life. From the field of social network to different protein interaction networks produce a large amount of data， and the map as a carrier of these huge data statistics can not only accurately describe the attribute of the data， but also illustrate the characteristics of the data structure， these advantages make with uncertain graph data mining algorithm is widely used in the society.

Key words： data mining； algorithm； uncertain graph

現(xiàn)代的科學(xué)技術(shù)正在以飛快的速度發(fā)展，其中互聯(lián)網(wǎng)和計(jì)算機(jī)技術(shù)也在蓬勃發(fā)展，國內(nèi)的每個(gè)行業(yè)都會積累大量的數(shù)據(jù)信息來促進(jìn)本企業(yè)的迅猛發(fā)展。不同的領(lǐng)域都會使用不同的圖結(jié)構(gòu)來記錄這些數(shù)據(jù)，而不確定圖模型就是統(tǒng)計(jì)這些數(shù)據(jù)的結(jié)構(gòu)之一。但是在實(shí)際應(yīng)用當(dāng)中，不同的獲取數(shù)據(jù)的工具以及原始數(shù)據(jù)的微小差距都能使獲得的數(shù)據(jù)不精確，再加上人們個(gè)體之間的工作關(guān)系網(wǎng)和生活關(guān)系網(wǎng)都能用圖來描述，將這些不確定的數(shù)據(jù)信息用圖來說明就形成了不確定圖模型數(shù)據(jù)。由于這些不確定圖數(shù)據(jù)存在的量比較大，所以它包涵著豐富的信息，從中挖掘有用的知識是非常重要的，也是極具現(xiàn)實(shí)意義的。

1 數(shù)據(jù)挖掘

在利用不同的技術(shù)手段或者查閱大量的資料所獲得的這些真實(shí)的、可能含有噪聲的數(shù)據(jù)中挖掘出用戶感興趣的、能夠理解的的有效數(shù)據(jù)的過程就稱之為數(shù)據(jù)挖掘。換句話說用戶需要從不完整的、模糊的、有噪聲的大量的數(shù)據(jù)中發(fā)現(xiàn)突出點(diǎn)以及潛藏的有用信息。數(shù)據(jù)挖掘所涉及到的學(xué)科非常廣泛，其最重要的就是借助計(jì)算機(jī)技術(shù)來完成這個(gè)過程，在最初搜集數(shù)據(jù)時(shí)需要數(shù)理統(tǒng)計(jì)、數(shù)據(jù)庫方面的知識，在進(jìn)行數(shù)據(jù)挖掘時(shí)需要各種分析工具，最后再將有效的數(shù)據(jù)與對應(yīng)的模型進(jìn)行轉(zhuǎn)化時(shí)需要數(shù)學(xué)知識。

2 確定圖數(shù)據(jù)挖掘

由于真實(shí)物理世界中的網(wǎng)絡(luò)普遍具有不確定性，因此網(wǎng)絡(luò)可以表示為不確定圖。Jin等使用數(shù)據(jù)挖掘方法研究了如何從不確定圖中挖掘連通可靠性高于某閾值的全部導(dǎo)出子圖。該問題在蛋白質(zhì)復(fù)合體發(fā)現(xiàn)、通信網(wǎng)絡(luò)路由和社會網(wǎng)絡(luò)分析中具有重要應(yīng)用。

2.1 圖

圖，就是我們在數(shù)據(jù)結(jié)構(gòu)中學(xué)到的圖，它是一中存儲信息的結(jié)構(gòu)，在數(shù)據(jù)結(jié)構(gòu)中它是被安排在后面的章節(jié)，所以很容易被我給忘記。圖，在數(shù)據(jù)結(jié)構(gòu)中的定義的基本意思是這樣的：圖中的每個(gè)節(jié)點(diǎn)都可以有多個(gè)父節(jié)點(diǎn)，多個(gè)子節(jié)點(diǎn)。所以圖的結(jié)構(gòu)是非常靈活的，它包含了鏈表的結(jié)構(gòu)，包含了樹的結(jié)果。它是整個(gè)數(shù)據(jù)結(jié)構(gòu)的綜合體。它的信息存儲也是通過節(jié)點(diǎn)和邊的形式進(jìn)行存儲。這就是圖的概念，下面也給出了一個(gè)基本的圖的結(jié)構(gòu)圖：

如圖1就是一個(gè)圖，該圖是一個(gè)無向帶權(quán)重的圖，在我們現(xiàn)實(shí)生活中這樣的圖是存在的，例如我們?nèi)珖慕煌ňW(wǎng)絡(luò)圖，就是一個(gè)無向圖，因?yàn)槟憧梢缘揭粋€(gè)地方去肯定也可以沿著這條路返回，無向是兩個(gè)節(jié)點(diǎn)不管是哪到哪沿著這條路徑都可到達(dá)，例如：上圖的V1——>V6可達(dá)，同時(shí)V6——>V1也可達(dá)，這樣就稱之為無向邊。當(dāng)然也存在有向邊。

2.2 圖數(shù)據(jù)挖掘

那么上面介紹了圖的概念，那么什么事圖數(shù)據(jù)挖掘，這個(gè)概念比較廣，它是屬于數(shù)據(jù)挖掘中的一種，我們知道數(shù)據(jù)挖掘有web數(shù)據(jù)挖掘（就是我們的百度/google等）、還有圖像數(shù)據(jù)挖掘、還有基于場地的圖像數(shù)據(jù)挖掘。那么圖數(shù)據(jù)挖掘是什么呢？我們知道百度/谷歌是IR，他是信息檢索，他是對文本信息進(jìn)行檢索，也就是我們的html頁面。那么圖的關(guān)鍵詞搜索和IR有什么不同呢？我們知道IR是搜索包含我們關(guān)鍵詞的文本內(nèi)容全部返回給用戶，但是返回的內(nèi)容是否存在關(guān)系那就不好說，所以此時(shí)就出現(xiàn)了圖的關(guān)鍵詞搜索。圖的關(guān)鍵詞搜索就是返回給用戶你輸入的關(guān)鍵詞相互之間的關(guān)系，例如：你輸入張三、李四這兩個(gè)人名關(guān)鍵詞，那么圖的關(guān)鍵詞搜索機(jī)制將會返回包含在圖中包含這兩個(gè)關(guān)鍵詞的節(jié)點(diǎn)這件的一個(gè)關(guān)系，一般是采取樹的方式展現(xiàn)出來。那么究竟是什么關(guān)系呢？例如：張三是李四的同學(xué)，張三是李四的哥哥、張三和李四是老鄉(xiāng)。那么這里的同學(xué)、哥哥、老鄉(xiāng)就是這個(gè)兩個(gè)關(guān)鍵詞之間的關(guān)系。想想在IR中能做到這些嗎？因?yàn)镮R搜索注重的不是關(guān)系，它注重的是信息，他是將包含關(guān)鍵詞的信息返回給用戶，而不考慮關(guān)鍵詞之間的關(guān)系。

那么在圖數(shù)據(jù)挖掘中找這種關(guān)系是如何實(shí)現(xiàn)的呢？例如上圖：假設(shè)要查找張三、李四這兩個(gè)關(guān)鍵詞，剛好在上圖中有V1包含關(guān)鍵詞張三，V2包含關(guān)鍵詞李四，在普通的IR系統(tǒng)中是就將同時(shí)包含張三、李四的節(jié)點(diǎn)返回給用戶（注意：此處的節(jié)點(diǎn)就是一個(gè)信息點(diǎn)，里面有內(nèi)容而V1，V2....只是一個(gè)代號）。那圖的關(guān)鍵詞搜索返回關(guān)系，到底是返回什么關(guān)系呢？上圖，我們知道從V1到V2有多條路徑，如：V1——>V5——>V2、V1——>V3——>V2等等，此處就不一一列舉出。那么我上面舉出的兩條路徑，不就是一個(gè)棵樹嗎？一個(gè)是以V5為根節(jié)點(diǎn)，一個(gè)是以V3為根節(jié)點(diǎn)。那么節(jié)點(diǎn)V5和V3就是這兩個(gè)關(guān)鍵詞之間的一個(gè)關(guān)系，這就是我上面說的如何找出兩個(gè)關(guān)鍵詞之間的關(guān)系。這里就將如何找到兩個(gè)關(guān)鍵詞之間的關(guān)系總結(jié)一句話：找到包含關(guān)鍵詞的節(jié)點(diǎn)公共父節(jié)點(diǎn)。那么這時(shí)候就面臨這兩個(gè)關(guān)鍵詞的公共父節(jié)點(diǎn)肯定不只一個(gè)，那么我們該返回哪個(gè)？這就要看到我們圖中邊的權(quán)重了，這里就要用到了對圖遍歷的一些算法（Dijkstra），此處就不對搜索的詳細(xì)過程進(jìn)行過多的描述，后期我會發(fā)到此博客上。此處肯定的是將結(jié)果排序，按照到達(dá)公共父節(jié)點(diǎn)的路徑消耗和節(jié)點(diǎn)的權(quán)重來排序。

2.3 不確定圖數(shù)據(jù)的產(chǎn)生

伴隨著數(shù)據(jù)收集以及存儲技術(shù)日新月異的變更，互聯(lián)網(wǎng)在社會中的應(yīng)用隨之增加，同時(shí)也會產(chǎn)生巨大的數(shù)據(jù)并且這些數(shù)據(jù)是不確定的。造成數(shù)據(jù)不確定的原因有很多種，首先其直接原因就是原始數(shù)據(jù)的不確定性，一般情況下這種不確定圖數(shù)據(jù)是不能通過外在方式進(jìn)行補(bǔ)償?shù)?。其次要原因這里介紹三種，一是在對這些數(shù)據(jù)處理過程中要進(jìn)行編碼、索引、量化、存儲等，每一個(gè)過程都會存在著不確定因素，這就造成了抽象數(shù)據(jù)誤差。二是具體應(yīng)用到每個(gè)用戶的手中，而用戶為了保護(hù)自己的隱私就會對加密數(shù)據(jù)進(jìn)行干擾處理，使外人無法識別這些數(shù)據(jù)從而造成數(shù)據(jù)在還原過程中也出現(xiàn)不確定性。三是對數(shù)據(jù)進(jìn)行分析完之后，往往會有缺失值的處理問題，由于儀器故障、接收雙方字段不統(tǒng)一等因素導(dǎo)致最后出現(xiàn)缺失值，這種不確定圖數(shù)據(jù)的缺失值可以通過插值的方法來削弱或解決，但是這種方法不能保證原始數(shù)據(jù)的不變，進(jìn)而也引入了不確定性。

3 不確定圖數(shù)據(jù)挖掘的算法研究

雖然用確定圖的挖掘辦法可以解決一部分不確定圖數(shù)據(jù)挖掘，但是這種方法確實(shí)對確定圖有極大的用途，對不確定圖將會造成重要語義的嚴(yán)重丟失。現(xiàn)在數(shù)據(jù)庫、網(wǎng)絡(luò)等領(lǐng)域的科學(xué)研究人員討論最多的話題就是不確定圖數(shù)據(jù)的研究，他們主要針對不確定圖模型的數(shù)據(jù)挖掘算法進(jìn)行深入的探討，讓這種方法更好的服務(wù)于人們。

3.1 不確定圖數(shù)據(jù)分類

數(shù)據(jù)挖掘方法通常是根據(jù)數(shù)據(jù)的不準(zhǔn)確性來進(jìn)行劃分的，一般包括以下幾種技術(shù)及方法：關(guān)聯(lián)挖掘、數(shù)據(jù)劃分、數(shù)據(jù)集聚三種。但是這些技術(shù)要通過相應(yīng)的改進(jìn)才能運(yùn)用于不確定圖數(shù)據(jù)的算法。其中，數(shù)據(jù)集聚可以劃分為一般集聚和模糊集聚兩類。一般集聚是通過針對預(yù)期的數(shù)據(jù)來提高算法的精準(zhǔn)度；模糊集聚表示集聚的數(shù)據(jù)的結(jié)果為一個(gè)模糊的狀態(tài)，可以表示為表格或者一定的概率。

3.2 不確定圖數(shù)據(jù)模型

目前在國內(nèi)使用最多也是應(yīng)用最廣的不確定圖數(shù)據(jù)類型應(yīng)該是可能世界模型，顧名思義這種模型是將每一個(gè)組成元素進(jìn)行任意的拼湊，這種組合完的圖形就能構(gòu)成可能世界實(shí)例，他的概率由組成該圖的元組的概率來計(jì)算。除了這種模型之外還包括半結(jié)構(gòu)化數(shù)據(jù)模型、概率P—文檔數(shù)據(jù)模型、關(guān)系數(shù)據(jù)模型等。

3.3 不確定圖上子圖研究

通過對相關(guān)資料的綜合分析，可以將不確定圖數(shù)據(jù)分為圖的查詢和圖的數(shù)據(jù)挖掘兩個(gè)部分。本論文著重研究對于不確定圖的挖掘的研究。到目前為止，關(guān)于不確定圖的研究尚未形成完整的理論體系，但不可否認(rèn)的是在一定程度上已經(jīng)取得了較為有價(jià)值的成就，尤其在最可靠子圖問題的研究方面。針對某一用戶特定的搜索值的涉及的最可靠字圖課題的研究，可以通過一種兩個(gè)階段的數(shù)據(jù)挖掘的算法來解決此類搜索，首先使用抽樣技術(shù)搜索可靠子圖，通?？煽孔訄D存在高概率的近似性；然后進(jìn)行相應(yīng)的確定圖的相應(yīng)指令，需要繼續(xù)挖掘關(guān)鍵不確定圖數(shù)據(jù)的算法。

4 不確定圖模型數(shù)據(jù)挖掘運(yùn)用

數(shù)據(jù)挖掘是為了在這個(gè)信息爆炸的大時(shí)代獲取對實(shí)現(xiàn)目標(biāo)有一定作用的信息。信息質(zhì)量的優(yōu)劣從其本質(zhì)分析主要決定于其對原始數(shù)據(jù)挖掘的程度。當(dāng)原始數(shù)據(jù)信息豐富、數(shù)據(jù)準(zhǔn)備、挖掘方法合適的時(shí)候，其所獲得的信息價(jià)值就會很高；反之，如果原始數(shù)據(jù)信息匱乏、數(shù)據(jù)模糊，挖掘方法失當(dāng)，其所獲得的信息價(jià)值就會很低。本節(jié)主要是為了提高獲取信息價(jià)值，探討對于不確定圖模型數(shù)據(jù)挖掘技術(shù)及方法的運(yùn)用。

數(shù)據(jù)挖掘的步驟會隨不同領(lǐng)域的應(yīng)用而有所變化，每一種數(shù)據(jù)挖掘技術(shù)也會有各自的特性和使用步驟，針對不同問題和需求所制定的數(shù)據(jù)挖掘過程也會存在差異。本論文著重針對不確定圖模型進(jìn)行相關(guān)的數(shù)據(jù)挖掘算法的運(yùn)用的研究。

不確定圖模型的數(shù)據(jù)挖掘完整的步驟如下：

1）理解不確定圖模型。2）確定不確定圖模型的數(shù)據(jù)。3）圖模型數(shù)據(jù)分類。4）獲取相關(guān)數(shù)據(jù)挖掘算法的知識與技術(shù)。5）分析不確定圖模型數(shù)據(jù)。6）刪掉錯(cuò)誤圖模型的數(shù)據(jù)。7）實(shí)際不確定圖模型數(shù)據(jù)挖掘算法工作。8）測試和驗(yàn)證挖掘算法的結(jié)果。

由上述步驟可看出，針對不確定圖模型的數(shù)據(jù)挖掘算法工作涉及了許多環(huán)節(jié)的工作，其中在數(shù)據(jù)預(yù)處理階段的工作尤為重要，是整個(gè)不確定數(shù)據(jù)挖掘算法工作順利開展以及取得成功的基礎(chǔ)。

參考文獻(xiàn)：

[1] 翟秋瑛.基于可達(dá)性的不確定圖查詢研究[D]. 哈爾濱：哈爾濱工業(yè)大學(xué)， 2013.

[2] 王文龍.一種高效的不確定圖數(shù)據(jù)庫上頻繁子圖模式挖掘算法[D]. 哈爾濱：哈爾濱工業(yè)大學(xué)， 2013.

[3] 楊健.不確定數(shù)據(jù)頻繁模式挖掘算法研究[D].贛州：江西理工大學(xué)， 2012.

[4] 丁悅.不確定圖聚類分析研究[D].西安：西北農(nóng)林科技大學(xué)， 2012.

[5] 汪金苗.基于不確定數(shù)據(jù)的頻繁項(xiàng)集挖掘算法的研究[D].淄博：山東理工大學(xué)， 2012.

[6] 周傲英，金澈清，王國仁，等.不確定性數(shù)據(jù)管理技術(shù)研究綜述[J].計(jì)算機(jī)學(xué)報(bào)， 2009（01）.

[7] 夏菁.基于可信度計(jì)算的不確定數(shù)據(jù)起源研究[D]. 南京：南京航空航天大學(xué)， 2012.

[8] 汪金苗，張龍波，鄧齊志，等.不確定數(shù)據(jù)頻繁項(xiàng)集挖掘方法綜述[J].計(jì)算機(jī)工程與應(yīng)用， 2011（20）.