圖分割是圖處理領(lǐng)域中一種重要方法,并且可應(yīng)用到計算機科學(xué)的其它分支,例如計算機視覺、數(shù)據(jù)挖掘等,具有重要的影響。由于大規(guī)模圖分割在實踐中意義重大,其性質(zhì)和處理方法不同于小規(guī)模的圖,因此對于大規(guī)模圖的研究是一項重要工作。為了提高圖分割質(zhì)量,降低運行時間,本文將多層次圖分割框架和譜聚類方法的思想結(jié)合起來,提出大規(guī)模圖上新的圖分割方法。本文的主要工作包括如下幾個方面:(1)邊加權(quán)圖或是點加權(quán)圖上的圖分割已經(jīng)得到了充分的研究,雙重加權(quá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)拉普拉斯方法。通過計算加權(quán)拉普拉斯的前k個最小的特征向量,并對這些向量的各個分量逐一進行聚類,最終能產(chǎn)生雙重加權(quán)圖上的k-分割。通過研究加權(quán)拉普拉斯的性質(zhì),并利用Eluer-Lagrange方程計算最小割的極...

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

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

【文章目錄】：
摘要
ABSTRACT
第1章 緒論
    1.1 選題背景與意義
    1.2 國內(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 細化算法
    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)割問題和初始聚類問題的等價性
        4.1.1 平衡最小割問題和加權(quán)割問題的等價性
        4.1.2 初始聚類問題和加權(quán)割問題的等價性
    4.2 加權(quán)譜算法
    4.3 準(zhǔn)正則圖上最小割問題的多項式時間近似算法
    4.4 本章小結(jié)
第5章 實驗與結(jié)果分析
    5.1 實驗環(huán)境
        5.1.1 KaHIP多層次圖分割框架
        5.1.2 實驗平臺和數(shù)據(jù)
    5.2 實驗結(jié)果和分析
        5.2.1 粗化算法實驗和分析
        5.2.2 加權(quán)譜算法實驗與分析
    5.3 本章小結(jié)
第6章 總結(jié)與展望
    6.1 總結(jié)
    6.2 展望
參考文獻
致謝
在讀期間發(fā)表的學(xué)術(shù)論文與取得的研究成果



本文編號：3806696