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

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

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

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

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

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 研究背景以及研究意義
    1.2 國內(nèi)外研究現(xiàn)狀
    1.3 預(yù)備知識(shí)
    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é)論
參考文獻(xiàn)
致謝


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



本文編號(hào)：3485266