国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于密度和半監(jiān)督學(xué)習(xí)的數(shù)據(jù)修復(fù)與聚類

2020-04-24 02:25張倩倩李國(guó)和鄭藝峰
關(guān)鍵詞:正確率約束聚類

張倩倩,李國(guó)和,3,鄭藝峰,4,5

(1.中國(guó)石油大學(xué)(北京) 石油數(shù)據(jù)挖掘北京市重點(diǎn)實(shí)驗(yàn)室,北京 102249;2.中國(guó)石油大學(xué)(北京) 信息科學(xué)與工程學(xué)院,北京 102249;3.石大兆信數(shù)字身份管理與物聯(lián)網(wǎng)技術(shù)研究院, 北京 100029;4.閩南師范大學(xué) 數(shù)據(jù)科學(xué)與智能應(yīng)用福建省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室, 福建 漳州 363000;5.閩南師范大學(xué) 計(jì)算機(jī)學(xué)院,福建 漳州 363000)

0 引 言

由于硬件、軟件、人為等因素的影響,數(shù)據(jù)在收集、存儲(chǔ)、傳輸?shù)冗^(guò)程會(huì)出現(xiàn)數(shù)據(jù)質(zhì)量問(wèn)題。數(shù)據(jù)修復(fù)是數(shù)據(jù)質(zhì)量中的一個(gè)重要組成部分,因此數(shù)據(jù)修復(fù)算法的研究是當(dāng)務(wù)之急,對(duì)數(shù)據(jù)挖掘質(zhì)量起著積極作用。數(shù)據(jù)修復(fù)算法是根據(jù)約束和規(guī)則對(duì)關(guān)系數(shù)據(jù)庫(kù)進(jìn)行修復(fù),如何獲得正確的約束和規(guī)則是難點(diǎn),如何對(duì)簡(jiǎn)單數(shù)據(jù)集進(jìn)行修復(fù)是一個(gè)需要解決的問(wèn)題?,F(xiàn)有的數(shù)據(jù)修復(fù)算法可以分為3類:基于約束的數(shù)據(jù)修復(fù)算法[1-5]、基于規(guī)則的數(shù)據(jù)修復(fù)算法[6-8]以及人工修復(fù)算法?,F(xiàn)有修復(fù)算法不適用于簡(jiǎn)單數(shù)據(jù)集,本文在現(xiàn)有修復(fù)算法上加入密度信息和成對(duì)約束信息,對(duì)現(xiàn)有修復(fù)算法進(jìn)行擴(kuò)展,使其不僅提高修復(fù)正確率而且適用于簡(jiǎn)單數(shù)據(jù)集。

1 相關(guān)研究

基于密度的聚類算法可比較成功識(shí)別噪聲數(shù)據(jù)并丟棄處理[9-11]。但很多數(shù)據(jù)集往往存在大量不精確數(shù)據(jù),將其丟棄必然影響聚類效果,因此需要對(duì)此類數(shù)據(jù)進(jìn)行修復(fù),以減小對(duì)聚類效果影響?,F(xiàn)有的數(shù)據(jù)修復(fù)算法只適合于關(guān)系數(shù)據(jù)庫(kù)中的數(shù)據(jù)修復(fù),需要知道約束函數(shù)或者規(guī)則,基于約束的修復(fù)側(cè)重點(diǎn)在于從數(shù)據(jù)庫(kù)中挖掘出相關(guān)約束,例如函數(shù)依賴[1]、條件函數(shù)依賴[2]、近似函數(shù)依賴的挖掘[3],這些算法側(cè)重于約束的挖掘,利用所得的約束對(duì)數(shù)據(jù)集進(jìn)行修復(fù)[4,5]。利用規(guī)則對(duì)數(shù)據(jù)集進(jìn)行修復(fù)[6-8]則需要用戶對(duì)數(shù)據(jù)庫(kù)有較深的理解,這種修復(fù)更準(zhǔn)確,但是不易操作。以上的數(shù)據(jù)修復(fù)算法都不適合具有簡(jiǎn)單模式的數(shù)據(jù)集,即不含有約束或者規(guī)則的數(shù)據(jù)集。

Song等提出了一種基于密度的最優(yōu)修復(fù)和聚類算法[12](DORC),同時(shí)進(jìn)行數(shù)據(jù)修復(fù)和數(shù)據(jù)聚類,實(shí)驗(yàn)結(jié)果表明DORC能提高聚類精度和修復(fù)正確率。不足之處在于,DORC算法修復(fù)噪聲數(shù)據(jù)會(huì)選擇離其最近的非噪聲數(shù)據(jù),無(wú)法有效保證修復(fù)和聚類結(jié)果的正確性。例如,分別位于邊界線兩側(cè)的兩棟臨近建筑,如果其中一棟建筑被識(shí)別為噪聲數(shù)據(jù),則會(huì)錯(cuò)誤的將兩棟建筑修復(fù)到邊界線的同一邊,在聚類時(shí)會(huì)錯(cuò)誤的將兩棟建筑劃分為一個(gè)村莊,從而導(dǎo)致聚類結(jié)果不正確。為了解決上述問(wèn)題,引入實(shí)例間的成對(duì)約束,利用背景知識(shí)約束修復(fù)和聚類過(guò)程,從而進(jìn)一步提高聚類精度和修復(fù)準(zhǔn)確率。

本文提出使用基于成對(duì)約束和最小修復(fù)原則的方法進(jìn)行修復(fù)和聚類,首先將CL和ML約束信息用于指導(dǎo)數(shù)據(jù)修復(fù)和臨時(shí)簇的形成,再對(duì)形成的臨時(shí)聚類簇進(jìn)行約束檢驗(yàn);若違反,則在違反約束的簇上,運(yùn)行聚類算法進(jìn)行二次簇的劃分,得到最后的聚類簇。算法的優(yōu)點(diǎn)在于:①同時(shí)對(duì)數(shù)據(jù)進(jìn)行數(shù)據(jù)修復(fù)和數(shù)據(jù)聚類。②充分利用數(shù)據(jù)集本身的密度信息和現(xiàn)有的背景知識(shí),不需要額外的完整性約束或規(guī)則。

定義1 信息系統(tǒng):信息系統(tǒng)表示為K=(U,A,VS), 其中U={u1,u2,…,u|P|} 為對(duì)象集合 (|U| 為集合元素個(gè)數(shù),對(duì)象ui∈U也稱為樣本,對(duì)象集U也稱為樣本集);A={ai|i=1,2,…,k} 為屬性集合;VS={Vai|i=1,2,…,k},Vai為對(duì)象屬性ai的值域,表示對(duì)象u∈U在ai∈A上的投影,即ai:U→Vai,ai(u)∈Vai。

定義2 決策表:信息系統(tǒng)K=(U,A,VS), 若C?A,D?A, 并且C∩D=Φ,C∪D=A, 稱C為條件屬性集,D為決策屬性集,信息系統(tǒng)K為決策表,記為DT=(U,C∪D,VS)。

對(duì)于?ai∈A,ai(u)≠EMPTY(空),K為完備信息系統(tǒng),否則,?ai∈A,ai(u)=EMPTY(空),K為不完備信息系統(tǒng)。其中,EMPTY是空值,表示值存在,但不知具體值。

對(duì)于A′?A,K′=(U,A′,VS), 稱K′為K的信息子系統(tǒng)。

更直觀看,K′=(U,A′,VS) 為完全信息子系統(tǒng),也可理解為以?ai∈A′為坐標(biāo), |A′| 為維數(shù),K′也成為關(guān)于A′樣本空間,?u∈U為樣本子空間點(diǎn)。

定義3 距離函數(shù)δ: 對(duì)于完全信息子系統(tǒng)K′=(U,A′,VS), ?ui,uj∈U, δ:U×A′→R+, 滿足非負(fù)性δ(ui,uj,A′)≥0、 對(duì)稱性δ(ui,uj,A′)=δ(uj,ui,A′) 和同一性當(dāng)且僅當(dāng)uj=ui時(shí)δ(ui,uj,A′)=0, 則稱δ是關(guān)于屬性集A′樣本間的距離函數(shù)。

定義4ε鄰居、ε鄰居集、鄰域密度η:對(duì)于完全信息子系統(tǒng)K′=(U,A′,VS), ?ui,uj∈U, 如果δ(ui,uj,A′)≤ε(鄰域距離), 則稱ui和uj是關(guān)于屬性集A′的ε鄰居。集合S(ui,A′,ε)={uj|?uj∈U, δ(ui,uj,A′)≤ε} 為樣本ui關(guān)于屬性集A′的ε鄰居集,η=|S(ui,A′,ε)| 稱為ui關(guān)于屬性集A′的鄰域密度。關(guān)于屬性集A′的ε鄰居的鄰居矩陣h(ui,uj,A′,ε)

(1)

h(ui,uj,A′,ε)=1表示ui和uj是關(guān)于屬性集A′的ε鄰居,反之表示ui,uj不是關(guān)于屬性集A′的ε鄰居。

定義5 中心點(diǎn),邊界點(diǎn),噪聲點(diǎn):對(duì)于完全信息子系統(tǒng)K′=(U,A′,VS), ?ui,uj∈U給定的距離閾值ε和密度閾值η,對(duì)于點(diǎn)ui,如果 |S(ui,A′,ε)|≥η則稱ui為關(guān)于屬性集A′的中心點(diǎn),如果 |S(ui,A′,ε)|<η但ui是關(guān)于屬性集A′的中心點(diǎn)uj的ε鄰居,即δ(ui,uj,A′)<ε, 則ui稱為關(guān)于屬性集A′的邊界點(diǎn),否則ui稱為關(guān)于屬性集A′的噪聲點(diǎn)。

對(duì)于完全信息子系統(tǒng)K′=(U,A′,VS), 給出關(guān)于屬性集A′的核心點(diǎn)集、邊界點(diǎn)集和噪聲點(diǎn)集定義:

核心點(diǎn)集

Cest(U,A′,ε,η)={ui|?ui∈U,|S(ui,A′,ε)|≥η}

(2)

邊界點(diǎn)集

Best(U,A′,ε,η)={ui|?ui∈U,|S(ui,A′,ε)|<η, ?uj∈Cest(U,A′,ε,η),δ(uj,ui,A′)<ε}

(3)

噪聲點(diǎn)集

Nest(U,A′,ε,η)=U-Cest(U,A′,ε,η)∪Best(U,A′,ε,η)

(4)

定義6 樣本修復(fù):對(duì)于完全信息子系統(tǒng)K′=(U,A′,VS), 樣本修復(fù)為函數(shù)映射λ∶U→U,λ(ui) 為樣本ui∈U修復(fù)之后的數(shù)據(jù),修復(fù)代價(jià)是

Δ(K′,λ)=∑?ui∈Uω(ui,λ(ui),A′)

(5)

其中,ω(ui,λ(ui),A′) 表示單個(gè)數(shù)據(jù)修復(fù)代價(jià),例如當(dāng)修復(fù)前后的數(shù)據(jù)不一致時(shí),可以令修復(fù)代價(jià)為1,一致時(shí)為0,也可以用修復(fù)前后的數(shù)據(jù)距離(編輯距離,曼哈頓距離等)作為修復(fù)代價(jià)。

定義7 成對(duì)約束:成對(duì)約束信息包含Must-Link(ML)約束集和Cannot-Link(CL)約束集,對(duì)于樣本集U,ui,uj是樣本集的樣本,如果ui,uj兩個(gè)樣本的label(標(biāo)簽)相等,則兩個(gè)樣本在聚類時(shí)一定要屬于同一類,如果兩個(gè)樣本標(biāo)簽不同,則兩個(gè)樣本在聚類時(shí)一定不能屬于同一個(gè)聚類簇,即:

如果 (ui,uj) ∈ML, 則ui.label=uj.label, ML(ui,uj)=1否則ML(ui,uj)=0。

如果 (ui,uj)∈CL則ui.label≠u(mài)j.label, CL(ui,uj)=1否則CL(ui,uj)=0。

定義8 基于密度的半監(jiān)督修復(fù)與聚類(SDORC):對(duì)于完全信息子系統(tǒng)K′=(U,A′,VS), 距離閾值ε,密度閾值η,成對(duì)約束CL,SDORC為

2 基于密度的半監(jiān)督修復(fù)與聚類算法

DORC算法[12]有效利用了樣本集內(nèi)部的密度信息,改善了數(shù)據(jù)的修復(fù)準(zhǔn)確率和聚類精度,但是在很多實(shí)際應(yīng)用中,獲取無(wú)標(biāo)簽數(shù)據(jù)的同時(shí)會(huì)得到一部分背景知識(shí)(成對(duì)約束關(guān)系或樣本的標(biāo)簽信息,本文采用成對(duì)約束信息)。DORC沒(méi)能充分利用得到的背景知識(shí),本文在DORC算法的基礎(chǔ)上,將得到的背景知識(shí)用于指導(dǎo)數(shù)據(jù)的修復(fù)和聚類過(guò)程得到基于密度和半監(jiān)督學(xué)習(xí)的修復(fù)與聚類算法(SDORC),以期得到更好的修復(fù)準(zhǔn)確率和聚類精度。

2.1 將SDORC問(wèn)題轉(zhuǎn)化為整數(shù)線性規(guī)劃問(wèn)題

在這部分,將SDORC問(wèn)題轉(zhuǎn)換為整數(shù)線性規(guī)劃問(wèn)題:

假設(shè)變量x(ui,uj,A′,ε)∈{0,1},x(ui,uj,A′,ε)=1表示將樣本ui修復(fù)到uj,相應(yīng)的修復(fù)代價(jià)表示為ωij=ω(ui,uj,A′), 否則x(ui,uj,A′,ε)=0。 對(duì)于完全信息子系統(tǒng)K′=(U,A′,VS), 任何一個(gè)樣本如果修復(fù)只能在不違反CL約束的情況下修復(fù)到一個(gè)位置(不能同時(shí)修復(fù)到不同的樣本點(diǎn),當(dāng)i=j時(shí)表明該樣本點(diǎn)沒(méi)有進(jìn)行修復(fù)操作),對(duì)于任意的樣本點(diǎn)ui

∑?ui∈Ux(ui,uj,A′,ε)CL(ui,uj)=1

(6)

對(duì)于完全信息子系統(tǒng)K′=(U,A′,VS), 修復(fù)完成之后,可能有多個(gè)樣本點(diǎn)同時(shí)修復(fù)到同一個(gè)樣本點(diǎn),修復(fù)后uj的鄰居樣本數(shù)表示為

c(uj,A′,ε)=|{ui|?ui∈U,δ(ui,uj,A′)≤ε}|

(7)

c(uj,A′,ε) 記錄了樣本點(diǎn)uj在ε距離范圍內(nèi)的鄰居點(diǎn)的個(gè)數(shù)。

使yj=1表示樣本點(diǎn)uj的ε鄰居個(gè)數(shù)不少于η個(gè)(核心點(diǎn)),否則yj=0,n表示樣本集U的樣本個(gè)數(shù),滿足下式

(8)

修復(fù)完成后所有的數(shù)據(jù)都是非噪聲數(shù)據(jù),即所有樣本點(diǎn)不是核心樣本點(diǎn)就是邊界樣本點(diǎn)(鄰居點(diǎn)中有核心點(diǎn)),即

(9)

對(duì)于上面給定的式(6),式(8),式(9), SDORC問(wèn)題可以轉(zhuǎn)化為下面的整數(shù)線性規(guī)劃問(wèn)題(ILP):

目標(biāo)函數(shù)

約束條件

(10)

2.2 SDORC算法的相關(guān)定義

將式(10)中的變量取值范圍放松至為0到1之間的實(shí)數(shù),可以將整數(shù)線性規(guī)劃問(wèn)題(ILP)轉(zhuǎn)化為線性規(guī)劃問(wèn)題(LP)。

(11)

定義10 臨時(shí)聚類簇:如果一個(gè)核心對(duì)象ui滿足(ui,uj)屬于ML,則將ui加入到ui的近鄰集中,然后利用密度相連概念形成聚類簇,此時(shí)是在滿足ML約束忽略部分CL約束的情況下形成的聚類簇,稱之為臨時(shí)聚類簇。

定義11 最終聚類簇:臨時(shí)聚類簇的形成可能違反部分CL約束,在每一個(gè)臨時(shí)聚類簇上檢驗(yàn)是否有違反CL的聚類簇,如果沒(méi)有違反則此臨時(shí)聚類簇便是最終聚類簇,如果違反,則在違反的聚類簇上運(yùn)行算法,進(jìn)行臨時(shí)聚類簇的再次劃分或合并,形成最終聚類簇。

2.3 SDORC算法步驟

根據(jù)給定的密度閾值和距離閾值和成對(duì)約束初始化x,y, 求噪聲數(shù)據(jù),在滿足ML約束的情況下進(jìn)行噪聲數(shù)據(jù)的修復(fù)形成臨時(shí)聚類簇,在所有違反CL約束的臨時(shí)聚類簇上進(jìn)行臨時(shí)簇的再分形成最終聚類簇,此時(shí)滿足CL和ML的聚類簇就是最終聚類簇。

算法: SDORC=(U,h,ε,η,CL,ML)

輸入: 樣本集合U, 鄰居矩陣h, 距離閾值ε, 密度閾值η, 成對(duì)約束CL,ML

輸出: 聚類簇

步驟1

(1)N=N(h)

(3) while N≠Φ

(4) 找到最大yjandyj<1 anduj∈U

(5) if |N|-|(ui,uj)∈CL|≥η(1-yj) then

(6) repeat

(7) If ?ui使 (ui,uj)∈ML andui∈N

(8)xii=0,xij=1,N=N-{ui}

(9) else

(10) 找到最小wijandui∈N(h)

(11)xii=0,xij=1,N=N-{ui}

(12) untilη(1-yj) times

(13)yj=1,N=N-({uj}∪{uk|hij=1})

(14) else

(15) forui∈Ndo

(16) finduk∈U-Nwith minimumwikand (uk,ui)?CL

(17)xii=0,xik=1,N=N-{ui}

步驟2

(18) 基于密度可達(dá)和ML得到臨時(shí)聚類簇(TC)

(19) repeat

(20) 如果TC中有違反CL的聚類簇

(21) 根據(jù)ML和CL進(jìn)行合并或者分裂

(22) until |TC| 次

(23) return 聚類簇

SDORC算法的簡(jiǎn)要流程如下:

首先初始化各個(gè)參數(shù),然后根據(jù)距離矩陣求出所有的噪聲數(shù)據(jù)。當(dāng)存在噪聲數(shù)據(jù)時(shí),在非核心點(diǎn)中找到最有可能成為核心點(diǎn)的數(shù)據(jù)點(diǎn)uj;如果現(xiàn)有噪聲點(diǎn)的個(gè)數(shù)能保證uj成為核心點(diǎn),在噪聲點(diǎn)中依次找到修復(fù)代價(jià)最小的點(diǎn)ui,將其修復(fù)到點(diǎn)uj,直到uj成為核心點(diǎn),如果噪聲點(diǎn)的個(gè)數(shù)不能使uj成為核心點(diǎn),則對(duì)噪聲點(diǎn)中的每一個(gè)點(diǎn)找到修復(fù)代價(jià)最小的點(diǎn)uw,將其修復(fù)到點(diǎn)uw,直到所有噪聲數(shù)據(jù)都被修復(fù)。

在形成的臨時(shí)聚類簇上檢測(cè)是否違反CL約束,如果違反CL約束,找出臨時(shí)聚類簇上違反的所有CL約束形成CL1,然后找出CL1上最短距離的數(shù)據(jù)對(duì),將數(shù)據(jù)對(duì)分開(kāi)形成兩個(gè)樣本集data1和data2;對(duì)CL1上的所有數(shù)據(jù)對(duì),分別計(jì)算距離data1和data2的距離,選擇距離最近的樣本集,將數(shù)據(jù)對(duì)中的數(shù)據(jù)分別加入距離較近的樣本集中;然后對(duì)臨時(shí)聚類簇的剩余數(shù)據(jù)運(yùn)行KNN算法,形成最終聚類簇。

3 實(shí)驗(yàn)與分析

3.1 性能評(píng)價(jià)標(biāo)準(zhǔn)

聚類精度: 聚類精度我們采用純度[13](purity)度量,以每個(gè)聚類簇中標(biāo)簽數(shù)量最多標(biāo)簽作為評(píng)價(jià)標(biāo)準(zhǔn),即

Purity的值越大表示聚類精度越高。

修復(fù)精度:修復(fù)精度表示修復(fù)位置λ(ui) 和實(shí)際位置truth(ui) 的距離,根均方誤差(RMS)來(lái)衡量

修復(fù)誤差越小,修復(fù)精度越高。

修復(fù)正確率:修復(fù)精度只考慮了修復(fù)前后數(shù)據(jù)的距離,沒(méi)有考慮修復(fù)是否相對(duì)正確,例如一條小河兩邊的兩所房屋,它們地理位置非常接近,但是卻屬于不同的村莊,這個(gè)時(shí)候簡(jiǎn)單的將一所房子的位置修復(fù)到另一所房屋就會(huì)導(dǎo)致樣本集修復(fù)的錯(cuò)誤,為了平衡距離和約束的關(guān)系,提出下面的修復(fù)正確率

其中,ωi表示樣本ui修復(fù)正確的權(quán)重,error越小,修復(fù)精度越高。

3.2 餐館樣本集實(shí)驗(yàn)結(jié)果及其分析

為了驗(yàn)證SDORC算法是基于約束修復(fù)算法的擴(kuò)展,在餐館數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),餐館數(shù)據(jù)集是包含112個(gè)副本的864條餐館記錄的樣本集,通常用于記錄匹配。每組副本都可以看作一個(gè)類,每條記錄包含4個(gè)屬性,分別是名字、地址、城市和餐館類型。在此實(shí)驗(yàn)中采用編輯距離作為距離函數(shù),為了驗(yàn)證算法修復(fù)正確率,我們按照一定的臟數(shù)據(jù)比例將數(shù)據(jù)在一定范圍內(nèi)進(jìn)行隨機(jī)改變以獲得不同程度的臟數(shù)據(jù)集。此數(shù)據(jù)集具有完整性約束(函數(shù)依賴關(guān)系(名字,地址)→城市),現(xiàn)有的數(shù)據(jù)修復(fù)和聚類方法可以應(yīng)用在此數(shù)據(jù)集上,對(duì)比實(shí)驗(yàn)采用基于函數(shù)依賴的數(shù)據(jù)修復(fù)算法(FD)[5]、半監(jiān)督聚類(CDBSCAN)[10]以及同時(shí)修復(fù)和聚類算法(DORC)[12],表1表示密度閾值和距離閾值一定的情況下,不同臟數(shù)據(jù)率下的聚類精度,表2表示距離閾值和密度閾值一定時(shí),不同臟數(shù)據(jù)率下的修復(fù)精度。

表1 不同臟數(shù)據(jù)率下各個(gè)算法的聚類精度

表2 不同臟數(shù)據(jù)率下各個(gè)算法的修復(fù)正確率

由表1可知,當(dāng)不對(duì)數(shù)據(jù)進(jìn)行修復(fù)操作時(shí)的聚類精度最低,因?yàn)榇藭r(shí)含有不精確數(shù)據(jù),會(huì)對(duì)聚類結(jié)果產(chǎn)生影響;利用FD算法先對(duì)數(shù)據(jù)進(jìn)行修復(fù)然后再聚類,聚類精度會(huì)有一定程度的提高,因?yàn)榇藭r(shí)一些臟數(shù)據(jù)會(huì)被修復(fù)成正確數(shù)據(jù);僅僅使用DORC算法時(shí),相比先修復(fù)再聚類的方法,聚類精度有了明顯提高,在使用DORC算法之前先對(duì)數(shù)據(jù)集用FD進(jìn)行修復(fù),又會(huì)有精度的提高,使用SDORC算法相對(duì)DORC算法聚類精度有了一定提高;SDORC考慮了背景知識(shí),使修復(fù)更為正確,如果先使用FD算法,再使用SDORC,聚類精度還有一定程度的提高,說(shuō)明SDORC是現(xiàn)有數(shù)據(jù)修復(fù)算法的拓展。

臟數(shù)據(jù)比例一定的情況下,聚類精度隨距離閾值的變化如圖1所示;聚類精度隨密度閾值的變化如圖2所示;修復(fù)正確率隨距離閾值的變化如圖3所示;修復(fù)正確率隨密度閾值的變化如圖4所示。

圖1 聚類精度VS距離閾值

圖2 聚類精度VS密度閾值

圖3 修復(fù)正確率VS距離閾值

圖4 修復(fù)正確率VS密度閾值

由上面4幅圖可以看出,SDORC算法相比其它算法在聚類精度和修復(fù)正確率上都有提高,先使用現(xiàn)有修復(fù)算法再使用本算法聚類精度和修復(fù)精度都有提高,驗(yàn)證該算法是現(xiàn)有修復(fù)算法的擴(kuò)展。

3.3 UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果及其分析

為了驗(yàn)證算法在真實(shí)數(shù)據(jù)集上的可行性,采用來(lái)自UCI上的4個(gè)真實(shí)數(shù)據(jù)集(見(jiàn)表3),實(shí)驗(yàn)以Windows7,Python為實(shí)驗(yàn)環(huán)境。在確定密度閾值和距離閾值情況下隨機(jī)選取成對(duì)約束,對(duì)數(shù)據(jù)集進(jìn)行10次實(shí)驗(yàn),取10次實(shí)驗(yàn)結(jié)果平均值作為最終結(jié)果。在0.1臟數(shù)據(jù)率下聚類精度對(duì)比見(jiàn)表4。由表4可知,本文算法的聚類精度相比其它現(xiàn)有算法有了一定程度的提升。

表3 UCI數(shù)據(jù)集

表4 聚類精度對(duì)比

4 結(jié)束語(yǔ)

現(xiàn)有的密度聚類對(duì)于臟數(shù)據(jù)的處理是簡(jiǎn)單丟棄,在丟棄的同時(shí)也損失了數(shù)據(jù)集本身的信息;現(xiàn)有的數(shù)據(jù)修復(fù)算法都是基于函數(shù)依賴等一些依賴關(guān)系對(duì)關(guān)系型數(shù)據(jù)庫(kù)進(jìn)行數(shù)據(jù)修復(fù),但是依賴關(guān)系的獲得要求對(duì)數(shù)據(jù)集要較好的理解,而且不適用于沒(méi)有函數(shù)依賴的簡(jiǎn)單數(shù)據(jù)集。本文提出的算法充分利用數(shù)據(jù)的密度信息,將密度聚類和數(shù)據(jù)修復(fù)相結(jié)合,加入了半監(jiān)督信息(成對(duì)約束信息)提出了SDORC算法,該算法適用于簡(jiǎn)單數(shù)據(jù)集,是現(xiàn)有修復(fù)算法的擴(kuò)展。實(shí)驗(yàn)結(jié)果表明,該算法有效提高了數(shù)據(jù)集的聚類精度和修復(fù)正確率。本文采用的成對(duì)約束是隨機(jī)選取的,如何選擇較好的成對(duì)約束以提高聚類和修復(fù)精度,將是進(jìn)一步探討的問(wèn)題。

猜你喜歡
正確率約束聚類
門(mén)診分診服務(wù)態(tài)度與正確率對(duì)護(hù)患關(guān)系的影響
約束離散KP方程族的完全Virasoro對(duì)稱
基于K-means聚類的車-地?zé)o線通信場(chǎng)強(qiáng)研究
基于高斯混合聚類的陣列干涉SAR三維成像
生意
品管圈活動(dòng)在提高介入手術(shù)安全核查正確率中的應(yīng)用
生意
基于Spark平臺(tái)的K-means聚類算法改進(jìn)及并行化實(shí)現(xiàn)
基于改進(jìn)的遺傳算法的模糊聚類算法
適當(dāng)放手能讓孩子更好地自我約束
新和县| 平山县| 德保县| 青河县| 牟定县| 平度市| 托克托县| 兴安盟| 靖安县| 大姚县| 来安县| 广水市| 剑川县| 霞浦县| 麦盖提县| 姜堰市| 广元市| 扶风县| 昌都县| 罗山县| 泰安市| 高安市| 凌云县| 邵阳县| 广饶县| 阜康市| 韶山市| 金平| 宾阳县| 河北区| 虞城县| 靖远县| 封开县| 新建县| 文昌市| 娱乐| 七台河市| 旬阳县| 中西区| 伽师县| 延庆县|