發(fā)布時(shí)間：2020-11-13 02:08

　　 隨著科學(xué)技術(shù)的迅猛發(fā)展,圖結(jié)構(gòu)越來(lái)越廣泛地被應(yīng)用于各行各業(yè)的數(shù)據(jù)挖掘和分析中。圖結(jié)構(gòu)抽象了事物之間的關(guān)系與聯(lián)系,為人們的研究分析提供了便利。結(jié)構(gòu)聚類(lèi)作為一種重要的圖結(jié)構(gòu)數(shù)據(jù)的分析挖掘工具,不僅可以找出網(wǎng)絡(luò)中稠密連接的簇,還可以識(shí)別其中的離群點(diǎn)與中介點(diǎn),從而更好地理解圖中各點(diǎn)的角色與它們之間的關(guān)系�，F(xiàn)有的結(jié)構(gòu)聚類(lèi)研究主要是針對(duì)確定圖的,即圖上的點(diǎn)與邊都確定存在。然而在科學(xué)研究與現(xiàn)實(shí)生活中,由于種種原因,許多的關(guān)系存在不確定性。例如社交網(wǎng)絡(luò)中受個(gè)人隱私保護(hù)影響的不確定關(guān)系、生物網(wǎng)絡(luò)中受實(shí)驗(yàn)因素影響的不確定關(guān)聯(lián)、移動(dòng)點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)中受環(huán)境影響的不確定連接等。這些不確定性通常需要使用不確定圖(概率圖)來(lái)表征。為此,需要考慮不確定圖上的結(jié)構(gòu)聚類(lèi)問(wèn)題。然而,現(xiàn)有的確定圖上的結(jié)構(gòu)聚類(lèi)算法往往不能準(zhǔn)確地表征不確定圖上的連通關(guān)系。因此,在本文中,我們提出了一個(gè)不確定圖上的結(jié)構(gòu)聚類(lèi)算法問(wèn)題,目的是找出一個(gè)給定的概率圖上的可靠結(jié)構(gòu)聚類(lèi),并給出了它的形式化定義。在此基礎(chǔ)上,設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)不確定圖上的結(jié)構(gòu)聚類(lèi)求解算法。具體地,本文首先對(duì)不確定圖上的結(jié)構(gòu)聚類(lèi)算法問(wèn)題的定義進(jìn)行了研究。分析總結(jié)了現(xiàn)有的確定圖上結(jié)構(gòu)聚類(lèi)問(wèn)題模型,從而推廣出不確定圖上的結(jié)構(gòu)聚類(lèi)算法的問(wèn)題定義。不同于確定圖上的結(jié)構(gòu)聚類(lèi),本文的結(jié)構(gòu)聚類(lèi)問(wèn)題依賴(lài)于一種全新定義的概念——可靠結(jié)構(gòu)相似度�？煽拷Y(jié)構(gòu)相似度度量了概率圖上兩個(gè)節(jié)點(diǎn)之間的結(jié)構(gòu)相似的概率。從而可以用一個(gè)概率來(lái)衡量節(jié)點(diǎn)之間的相似性。隨后,由于可靠結(jié)構(gòu)相似度的求解是一個(gè)比較困難的問(wèn)題,直接求解具有很高的時(shí)間復(fù)雜度,是不可取的。為此,本文詳細(xì)分析了可靠結(jié)構(gòu)相似度的求解過(guò)程,并在此基礎(chǔ)上設(shè)計(jì)了一種基于動(dòng)態(tài)規(guī)劃思想的求解算法。該算法能夠快速地求解可靠結(jié)構(gòu)相似度問(wèn)題,在該算法的基礎(chǔ)上,本文根據(jù)目前最好的確定圖上結(jié)構(gòu)聚類(lèi)算法,設(shè)計(jì)出不確定圖上結(jié)構(gòu)聚類(lèi)算法框架。為了進(jìn)一步加快我們算法的速度,我們?cè)O(shè)計(jì)了多種強(qiáng)有力的剪枝和優(yōu)化措施。最后,我們使用了五個(gè)真實(shí)的數(shù)據(jù)集對(duì)我們所提出的算法進(jìn)行了較為全面的研究與分析。通過(guò)與現(xiàn)有聚類(lèi)算法的比較,我們的算法可以得到更好的不確定圖上的聚類(lèi)。同時(shí),通過(guò)性能分析,我們驗(yàn)證了優(yōu)化措施的有效性。綜合實(shí)驗(yàn)的結(jié)果,得出我們的算法能夠有效且高效地完成不確定圖上的結(jié)構(gòu)聚類(lèi)問(wèn)題。
【學(xué)位單位】：深圳大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2018
【中圖分類(lèi)】：TP311.13;O157.5
【部分圖文】：

于是節(jié)點(diǎn)9v 與節(jié)點(diǎn)6 7v ,v 和8v 就可能不再屬于同一個(gè)聚類(lèi)。從例子 1 中，我們可以看出來(lái)，簡(jiǎn)單地將不確定圖轉(zhuǎn)化為確定圖，然后再求解確定圖上的結(jié)構(gòu)聚類(lèi)的方法是有很大問(wèn)題的，并不能用來(lái)很好地解決不確定圖上的聚類(lèi)問(wèn)題。為此，我們必須針對(duì)不確定圖的性質(zhì)和特點(diǎn)，給出一個(gè)適用于不確定圖條件下的結(jié)構(gòu)聚類(lèi)解決方案。在本文中，我們首先給出了不確定圖上的結(jié)構(gòu)聚類(lèi)的形式化定義，這個(gè)定義基本沿襲了確定圖上的結(jié)構(gòu)聚類(lèi)的思路，但是根據(jù)不確定圖的性質(zhì)，進(jìn)行了調(diào)整和改進(jìn)。隨后，在不確定圖上的結(jié)構(gòu)聚類(lèi)的形式化定義基礎(chǔ)上，我們提出了一個(gè)高效的解決方案。本文主要的貢獻(xiàn)包括以下三個(gè)方面：1.全新的概念和問(wèn)題。為了度量不確定圖上節(jié)點(diǎn)之間的相似程度，我們首先提出了“可靠結(jié)構(gòu)相似度”的概念。值得注意的是，不確定圖上兩個(gè)節(jié)點(diǎn)之間的可靠結(jié)構(gòu)相似度綜合考慮了該圖上所有可能世界的情況�；诳煽拷Y(jié)構(gòu)相似度，我們給出了不確定圖上的結(jié)構(gòu)聚類(lèi)問(wèn)題的定義。

我們可以很容易地得到(0.5,0.2 ) 41 2 3 4 5N [ v ] = {v , v , v , v , v}。( ,η)-可靠結(jié)構(gòu)鄰居也可以被叫做可靠相似鄰居。顯然，一個(gè)頂點(diǎn)擁有的相似鄰居越多，則這個(gè)頂點(diǎn)在這個(gè)網(wǎng)絡(luò)中重要性就越強(qiáng)，同樣，在聚類(lèi)的過(guò)就扮演越重要的作用。于是，當(dāng)一個(gè)頂點(diǎn)擁有足夠多的可靠相似鄰居的時(shí)候們就稱(chēng)該頂點(diǎn)為一個(gè)可靠核心頂點(diǎn)（Reliable Core Vertex）。定義 7（( ,η ,μ)-可靠核心節(jié)點(diǎn)，( ,η ,μ)- Reliable Core Vertex）：對(duì)不圖 上的一個(gè)頂點(diǎn) u ，給定一個(gè)相似性閾值 0 < ≤1，一個(gè)可靠性閾 < η≤ 1，和一個(gè)整數(shù) μ ≥ 2，當(dāng)( ,)| N [u ]|η≥μ 時(shí)，該頂點(diǎn)u 為一個(gè)( ,η ,μ可靠核心節(jié)點(diǎn)。定義 7 給出了可靠核心節(jié)點(diǎn)，在可靠核心節(jié)點(diǎn)的基礎(chǔ)上，我們可以進(jìn)一步可靠結(jié)構(gòu)可達(dá)的定義。定義 8（可靠結(jié)構(gòu)可達(dá)，Reliable Structure-reachable）：給定參數(shù)0 < ≤1 < η≤ 1，和 μ ≥ 2，節(jié)點(diǎn)u 可靠結(jié)構(gòu)可達(dá)節(jié)點(diǎn) v ，當(dāng)且僅當(dāng)存在一個(gè)頂點(diǎn)

基于表達(dá)式(3.1)，我們可以給出動(dòng)態(tài)規(guī)( , ) ( , ) ) ( , ) ( , ) ( , ) ) ( , )) ( 1, 1, 1)) (1 )) ( 1,)(1 )) ( 1, , )h hh h hhw u w vu w v w u w vu w vn p p X h m np p p X h p X h m n′ ′ ′ + ′ ′，對(duì)于每一條邊，我們可以把 DP 算是因?yàn)樵跊](méi)有頂點(diǎn)被處理的情況下 m ' 了我們的 DP 算法的具體實(shí)現(xiàn)過(guò)程。Pr ( e, ) =0（見(jiàn)第 1~2 行）。隨后，根2,2) = 1。這里我們假定只有邊e存在的后結(jié)束的地方，（第 11 行）我們會(huì)把結(jié)我們將不斷地處理每一個(gè)點(diǎn)，根據(jù)式子的每一種可能。在第 8-10 行，算法計(jì)算
【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 林佳楠;;一種基于結(jié)構(gòu)相似度的部分參考型圖像質(zhì)量評(píng)價(jià)方法[J];長(zhǎng)春大學(xué)學(xué)報(bào);2016年10期

2 尋琛;杜向云;張錫寶;;中美貿(mào)易結(jié)構(gòu)相似度研究的因素分析——從比較優(yōu)勢(shì)和要素稟賦角度[J];現(xiàn)代商業(yè);2015年27期

3 王宇慶;劉維亞;王勇;;一種基于局部方差和結(jié)構(gòu)相似度的圖像質(zhì)量評(píng)價(jià)方法[J];光電子.激光;2008年11期

4 朱震鋒;曹玉昆;王非;陳麗榮;;黑龍江森工林區(qū)產(chǎn)業(yè)結(jié)構(gòu)相似度測(cè)算及動(dòng)態(tài)評(píng)價(jià)[J];林業(yè)經(jīng)濟(jì)問(wèn)題;2016年03期

5 樊福卓;;一種改進(jìn)的產(chǎn)業(yè)結(jié)構(gòu)相似度測(cè)度方法[J];數(shù)量經(jīng)濟(jì)技術(shù)經(jīng)濟(jì)研究;2013年07期

6 李波;;基于協(xié)同視角的武陵山區(qū)產(chǎn)業(yè)結(jié)構(gòu)相似度比較研究[J];中南民族大學(xué)學(xué)報(bào)(人文社會(huì)科學(xué)版);2012年06期

7 尹永超;徐敏;傅皇麟;孫勝男;;鏈路預(yù)測(cè)中的一種局部結(jié)構(gòu)相似度算法[J];小型微型計(jì)算機(jī)系統(tǒng);2018年01期

8 桑慶兵;梁狄林;吳小俊;李朝鋒;;基于膨脹的梯度結(jié)構(gòu)相似度圖像質(zhì)量評(píng)價(jià)方法[J];計(jì)算機(jī)科學(xué);2014年06期

9 李京娜;王國(guó)宏;孫少燕;王剛;;基于改進(jìn)后的結(jié)構(gòu)相似度的三維圖像配準(zhǔn)[J];光電工程;2012年12期

10 樓斌;沈海斌;趙武鋒;嚴(yán)曉浪;;基于失真模型的結(jié)構(gòu)相似度圖像質(zhì)量評(píng)價(jià)[J];浙江大學(xué)學(xué)報(bào)(工學(xué)版);2009年05期

相關(guān)博士學(xué)位論文 前9條

1 俞唯仁;普適的結(jié)構(gòu)相似度在大規(guī)模網(wǎng)絡(luò)中的計(jì)算優(yōu)化技術(shù)研究[D];東華大學(xué);2012年

2 錢(qián)方;激光對(duì)光電系統(tǒng)圖像干擾的效果評(píng)估[D];中國(guó)科學(xué)院研究生院(長(zhǎng)春光學(xué)精密機(jī)械與物理研究所);2015年

3 杜小坤;數(shù)據(jù)庫(kù)模式匹配算法研究[D];華中科技大學(xué);2010年

4 張蕾;紅外與可見(jiàn)光圖像融合技術(shù)研究[D];中國(guó)科學(xué)院研究生院(長(zhǎng)春光學(xué)精密機(jī)械與物理研究所);2015年

5 楊俊豐;基于感知的全參圖像質(zhì)量評(píng)價(jià)研究[D];湖南大學(xué);2018年

6 陳曉琳;基于視覺(jué)特征的圖像質(zhì)量評(píng)價(jià)技術(shù)研究[D];上海交通大學(xué);2012年

7 黎新;面向問(wèn)答系統(tǒng)的段落檢索技術(shù)研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2010年

8 張樺;基于視覺(jué)感知的圖像質(zhì)量評(píng)價(jià)方法研究[D];浙江大學(xué);2009年

9 曹立民;喹諾酮藥物族特異性識(shí)別材料及其檢測(cè)性能的研究[D];中國(guó)海洋大學(xué);2008年

相關(guān)碩士學(xué)位論文 前10條

1 邱宇軒;不確定圖上的結(jié)構(gòu)聚類(lèi)算法研究與實(shí)現(xiàn)[D];深圳大學(xué);2018年

2 朱毅;基于雙邊濾波的連續(xù)腦圖像序列隨機(jī)噪聲去除方法研究[D];華中科技大學(xué);2017年

3 郭旭超;基于結(jié)構(gòu)相似度的社區(qū)發(fā)現(xiàn)方法研究[D];山東農(nóng)業(yè)大學(xué);2018年

4 孫芬芬;基于源碼結(jié)構(gòu)相似度檢測(cè)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D];內(nèi)蒙古大學(xué);2017年

5 李紅芳;基于梯度的結(jié)構(gòu)相似度圖像質(zhì)量評(píng)價(jià)方法研究[D];西安科技大學(xué);2012年

6 程梅娟;中國(guó)與東盟出口結(jié)構(gòu)相似度與雙邊貿(mào)易研究[D];湖南大學(xué);2011年

7 周進(jìn);基于結(jié)構(gòu)相似度的動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)社團(tuán)增量更新算法研究[D];遼寧大學(xué);2016年

8 盧亞廣;基于分組統(tǒng)計(jì)及梯度結(jié)構(gòu)相似度的AVS2幀內(nèi)預(yù)測(cè)高效算法[D];西南交通大學(xué);2017年

9 劉婧;基于結(jié)構(gòu)相似度的圖像質(zhì)量評(píng)價(jià)方法研究[D];長(zhǎng)沙理工大學(xué);2016年

10 江程;基于結(jié)構(gòu)相似度的圖像客觀(guān)質(zhì)量評(píng)價(jià)方法研究[D];湘潭大學(xué);2012年

本文編號(hào)：2881571