聚類是將給定的集合按照某種特征進(jìn)行分類的過程,其應(yīng)用于各個(gè)領(lǐng)域,為各行業(yè)的發(fā)展提供便利,具有極高的實(shí)用價(jià)值。按照分類方法的不同,聚類可以分為很多種,但其中應(yīng)用最廣的是fk-means聚類。fk-means聚類問題可以表述為:給定Rd上含有n個(gè)點(diǎn)的集合P和一個(gè)整數(shù)fk,目標(biāo)是在Rd上找出fk個(gè)中心點(diǎn),使得P中每個(gè)點(diǎn)到距它最近的中心點(diǎn)的距離的平方和最小。不同于一般的fk-meams聚類問題,在數(shù)據(jù)流模型下的fk-means聚類問題中,集合P中的點(diǎn)是隨時(shí)間依次到達(dá)的,且數(shù)據(jù)量極其龐大沒有足夠的空間來(lái)存儲(chǔ)全部的數(shù)據(jù)點(diǎn)。因此,為了解決該模型下的fk-means聚類問題,我們引入了核心集這一概念,較原始集合P而言,核心集規(guī)模更小,更便于儲(chǔ)存,并且在所求得的核心集上進(jìn)行聚類得到的解與在原始集合P上聚類得到的解之間的相對(duì)誤差可以任意小。然而,fk-means聚類問題是NP-難問題,在P≠NP的假設(shè)下,不存在多項(xiàng)式時(shí)間的精確算法。因此,本文首先考慮了 fk-means聚類問題所得解為近似解時(shí),如何計(jì)算原始集合的核心集。我們發(fā)現(xiàn)在近似解的情況下,無(wú)法找到滿足定義的真正的核心集,但可以得到帶有微小誤差的近似... 

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

【文章頁(yè)數(shù)】：38 頁(yè)

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

【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 研究背景以及研究意義
    1.2 國(guó)內(nèi)外研究現(xiàn)狀
    1.3 k-means聚類
    1.4 預(yù)備知識(shí)
    1.5 論文結(jié)構(gòu)
第2章 k-means聚類的(k,ε)-核心集構(gòu)建算法
    2.1 算法介紹
    2.2 算法及主要結(jié)論
    2.3 算法分析
    2.4 本章小結(jié)
第3章 k-means聚類的ξ-近似(k,ε)-核心集構(gòu)建算法
    3.1 算法介紹
    3.2 算法及主要結(jié)論
    3.3 算法分析
    3.4 本章小結(jié)
結(jié)論
參考文獻(xiàn)
致謝


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



本文編號(hào)：3512246