聚類原本是統(tǒng)計學上的概念,隨著人工智能的發(fā)展,現(xiàn)在屬于機器學習中無監(jiān)督學習的范疇,其被廣泛應用在數(shù)據(jù)挖掘、數(shù)據(jù)分析等領域。聚類算法通常是按照一定的規(guī)則將具有共同特性的對象歸為一類,不同特性的對象劃分為不同類。關(guān)聯(lián)聚類是聚類問題中最為重要的方法之一,它是圖上的一種聚類。在圖中,相似的對象之間有一條正邊相連,不相似的對象之間則用負邊相連。關(guān)聯(lián)聚類就是要根據(jù)這種圖結(jié)構(gòu)將具有正邊的對象盡量放入一個類中而負邊的兩個對象放入不同的類。然而現(xiàn)實關(guān)系紛繁復雜,由此構(gòu)建的關(guān)系網(wǎng)絡十分復雜,簡單的二元關(guān)系往往無法應用于這樣的場景。自然而然產(chǎn)生了對彩色關(guān)聯(lián)聚類問題的研究。彩色關(guān)聯(lián)聚類問題是關(guān)聯(lián)聚類問題的一種高度概括,它將關(guān)聯(lián)聚類中的二元關(guān)系進行擴展,在圖上的邊中引入顏色的概念,從而能夠應對現(xiàn)實中更多的場景。目前彩色關(guān)聯(lián)聚類有著十分廣泛的應用,如社交網(wǎng)絡、生物信息學等。但彩色關(guān)聯(lián)聚類問題的研究還很不完善,這些算法的近似比和關(guān)聯(lián)聚類算法相差甚遠。目前近似比最好的算法是Pivot算法,但其在聚類過程中忽視了顏色屬性。本文基于松弛線性規(guī)劃解針對彩色關(guān)聯(lián)聚類問題提出了一個確定性的近似算法,從而將該問題的近似比提升到了 ...

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

【學位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
第1章 緒論
    1.1 研究背景及意義
        1.1.1 關(guān)聯(lián)聚類
        1.1.2 彩色關(guān)聯(lián)聚類
    1.2 主要研究內(nèi)容和貢獻
        1.2.1 主要研究內(nèi)容
        1.2.2 本文貢獻
    1.3 論文組織結(jié)構(gòu)
第2章 基礎知識
    2.1 關(guān)聯(lián)聚類簡介
    2.2 標準彩色關(guān)聯(lián)聚類
        2.2.1 定義
        2.2.2 整數(shù)線性規(guī)劃及其松弛形式
        2.2.3 整數(shù)界
    2.3 非對稱權(quán)重的彩色關(guān)聯(lián)聚類問題
        2.3.1 定義
        2.3.2 松弛線性規(guī)劃形式
        2.3.3 整數(shù)界
    2.4 本章小結(jié)
第3章 標準彩色關(guān)聯(lián)聚類問題的近似算法設計與分析
    3.1 算法
        3.1.1 算法描述
        3.1.2 背后的思想
        3.1.3 算法性能
    3.2 近似比分析
        3.2.1 證明脈絡
        3.2.2 更多細節(jié)
    3.3 去隨機化
    3.4 本章小結(jié)
第4章 標準彩色關(guān)聯(lián)聚類問題的啟發(fā)式算法設計與評估
    4.1 算法介紹
        4.1.1 算法描述
        4.1.2 背后的思想
        4.1.3 時空復雜度
    4.2 實驗評估
        4.2.1 真實數(shù)據(jù)介紹
        4.2.2 參數(shù)實驗
        4.2.3 對比實驗
    4.3 本章小結(jié)
第5章 非對稱權(quán)重的彩色關(guān)聯(lián)聚類問題的近似算法設計與分析
    5.1 算法
        5.1.1 算法描述
        5.1.2 背后的思想
        5.1.3 算法性能
    5.2 近似比分析
        5.2.1 在θ≤0.169時的近似比分析
0.169時的近似比分析">        5.2.2 在θ>0.169時的近似比分析
    5.3 本章小結(jié)
第6章 總結(jié)與展望
    6.1 工作總結(jié)
    6.2 工作展望
參考文獻



本文編號：4006898