發(fā)布時間：2021-11-09 11:43

　　K-平均問題是經(jīng)典的NP-難問題,NP-難問題無法在多項式時間內(nèi)找到精確解除非P=NP.k-平均問題在數(shù)據(jù)挖掘、機器學習等領域有廣泛的應用.在大數(shù)據(jù)時代,與大數(shù)據(jù)相關的聚類問題也成為當前研究的熱點.我們通常采用啟發(fā)式算法或近似算法求解該類問題.在該問題中,給定由n個d維空間中觀測點組成的數(shù)據(jù)集χ和整數(shù)k（k≤n）,目標是將χ劃分成k個子集,使得所有子集的方差（或點到其聚類中心的距離平方）和最小.在χ中觀測點有不同的重要程度,為了將重要的觀測點更好聚類,學者們提出了帶懲罰的k-平均問題.在該問題中,越重要的觀測點給定懲罰費用越大.帶懲罰的k-平均問題是k-平均問題的推廣.任意一個觀測點x∈χ尤的懲罰費用為p（x）.每個觀測點必須聚類到某個中心點或者被懲罰.在本文中,我們研究了帶懲罰的kk-平均問題,給出了并行初始化算法,每次迭代采樣點的數(shù)量是隨機的,在給定迭代次數(shù)的情形下,給出了算法的近似比分析. 

【文章來源】：北京工業(yè)大學北京市 211工程院校

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

【學位級別】：碩士

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 研究背景以及研究意義
    1.2 國內(nèi)外研究現(xiàn)狀
    1.3 預備知識
    1.4 主要結(jié)果
    1.5 論文結(jié)構(gòu)
第2章 帶懲罰的k-平均問題有效并行初始化算法
    2.1 k-means++算法
        2.1.1 算法介紹
        2.1.2 算法
    2.2 k-means||算法
        2.2.1 算法介紹
        2.2.2 算法
        2.2.3 算法分析
    2.3 帶懲罰的k-means||算法
        2.3.1 算法介紹
        2.3.2 算法
        2.3.3 算法分析
    2.4 本章小結(jié)
結(jié)論
參考文獻
致謝


【參考文獻】：
期刊論文
[1]k-平均問題及其變形的算法綜述[J]. 徐大川,許宜誠,張冬梅.  運籌學學報. 2017(02)



本文編號：3485266