圖分割是圖處理領(lǐng)域中一種重要方法,并且可應(yīng)用到計(jì)算機(jī)科學(xué)的其它分支,例如計(jì)算機(jī)視覺、數(shù)據(jù)挖掘等,具有重要的影響。由于大規(guī)模圖分割在實(shí)踐中意義重大,其性質(zhì)和處理方法不同于小規(guī)模的圖,因此對(duì)于大規(guī)模圖的研究是一項(xiàng)重要工作。為了提高圖分割質(zhì)量,降低運(yùn)行時(shí)間,本文將多層次圖分割框架和譜聚類方法的思想結(jié)合起來,提出大規(guī)模圖上新的圖分割方法。本文的主要工作包括如下幾個(gè)方面:(1)邊加權(quán)圖或是點(diǎn)加權(quán)圖上的圖分割已經(jīng)得到了充分的研究,雙重加權(quán)圖是一種邊和點(diǎn)都帶權(quán)的加權(quán)圖,在很多問題中有重要的應(yīng)用,例如路徑規(guī)化、最優(yōu)圈問題等,然而尚未得到充分研究。本文提出了加權(quán)拉普拉斯方法,較好地解決了雙重加權(quán)圖上的圖分割問題。該方法受譜聚類方法的啟發(fā),利用圖上的加權(quán)拉普拉斯來處理最小割問題,其中加權(quán)拉普拉斯是圖拉普拉斯的推廣。借助這一概念,我們將雙重加權(quán)圖上的最小割問題轉(zhuǎn)化為加權(quán)拉普拉斯的特征分解問題,并稱為加權(quán)拉普拉斯方法。通過計(jì)算加權(quán)拉普拉斯的前k個(gè)最小的特征向量,并對(duì)這些向量的各個(gè)分量逐一進(jìn)行聚類,最終能產(chǎn)生雙重加權(quán)圖上的k-分割。通過研究加權(quán)拉普拉斯的性質(zhì),并利用Eluer-Lagrange方程計(jì)算最小割的極...

【文章頁(yè)數(shù)】：63 頁(yè)

【學(xué)位級(jí)別】：碩士

【文章目錄】：
摘要
ABSTRACT
第1章 緒論
    1.1 選題背景與意義
    1.2 國(guó)內(nèi)外研究現(xiàn)狀
    1.3 本文的主要研究工作
    1.4 本文的組織安排
第2章 圖分割和正則圖背景介紹
    2.1 圖分割
        2.1.1 圖的一些基本概念
        2.1.2 圖分割經(jīng)典算法
        2.1.3 圖分割近似算法
    2.2 多層次圖分割
        2.2.1 粗化算法
        2.2.2 初始聚類算法
        2.2.3 細(xì)化算法
    2.3 正則圖和正則性引理
    2.4 本章小結(jié)
第3章 加權(quán)拉普拉斯方法
    3.1 相關(guān)理論介紹
    3.2 圖拉普拉斯方法在雙重加權(quán)圖上的拓展
    3.3 本章小結(jié)
第4章 基于加權(quán)拉普拉斯方法的加權(quán)譜算法
    4.1 平衡最小割問題、加權(quán)割問題和初始聚類問題的等價(jià)性
        4.1.1 平衡最小割問題和加權(quán)割問題的等價(jià)性
        4.1.2 初始聚類問題和加權(quán)割問題的等價(jià)性
    4.2 加權(quán)譜算法
    4.3 準(zhǔn)正則圖上最小割問題的多項(xiàng)式時(shí)間近似算法
    4.4 本章小結(jié)
第5章 實(shí)驗(yàn)與結(jié)果分析
    5.1 實(shí)驗(yàn)環(huán)境
        5.1.1 KaHIP多層次圖分割框架
        5.1.2 實(shí)驗(yàn)平臺(tái)和數(shù)據(jù)
    5.2 實(shí)驗(yàn)結(jié)果和分析
        5.2.1 粗化算法實(shí)驗(yàn)和分析
        5.2.2 加權(quán)譜算法實(shí)驗(yàn)與分析
    5.3 本章小結(jié)
第6章 總結(jié)與展望
    6.1 總結(jié)
    6.2 展望
參考文獻(xiàn)
致謝
在讀期間發(fā)表的學(xué)術(shù)論文與取得的研究成果



本文編號(hào)：3806696