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

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

【學位級別】：碩士

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



本文編號：3806696