面向?qū)ο笞兓木植苦徲虼植诩隽扛滤惴?/h1>

2022-12-06 01:56:46時(shí)俊鵬張燕蘭

閩南師范大學(xué)學(xué)報(bào)(自然科學(xué)版)訂閱 2022年3期 收藏

關(guān)鍵詞：論域粗糙集鄰域

時(shí)俊鵬 ,張燕蘭*

（1.閩南師范大學(xué)計(jì)算機(jī)學(xué)院,福建漳州 363000；2.數(shù)據(jù)科學(xué)與智能應(yīng)用福建省高校重點(diǎn)實(shí)驗(yàn)室,福建漳州 363000）

波蘭學(xué)者Pawlak 提出的粗糙集理論[1]能被有效地用于定量處理和分析不確定、不協(xié)調(diào)、不完備等數(shù)據(jù).Pawlak 粗糙集在近似目標(biāo)概念時(shí)需要對論域中所有對象進(jìn)行計(jì)算，這種粗糙集被稱作全局粗糙集.而Qian等提出的局部粗糙集[2]，不需要用論域中的所有對象來近似目標(biāo)概念，只需要考慮目標(biāo)概念中的對象，為有限標(biāo)簽大數(shù)據(jù)集的知識發(fā)現(xiàn)提供了一種有效的方法.由于局部粗糙集的這一明顯特性，學(xué)者們著重研究了幾種針對不同信息系統(tǒng)的廣義局部粗糙集模型[3-5].其中，局部鄰域粗糙集[3]是一種處理數(shù)值型數(shù)據(jù)的重要模型.

隨著信息技術(shù)的發(fā)展，社會各領(lǐng)域的數(shù)據(jù)都在不斷變化.在粗糙集理論中，數(shù)據(jù)集的動態(tài)更新通常可以表示為信息系統(tǒng)的動態(tài)變化，這些變化主要體現(xiàn)在屬性值、對象集和屬性集的變化上.目前，已有很多關(guān)于動態(tài)信息系統(tǒng)的研究[6-18].Luo等[9-11]分別研究了在等價(jià)關(guān)系和特性關(guān)系下就對象變化時(shí)概率粗糙集近似集的更新問題，然后進(jìn)一步探索了特征值變化時(shí)決策粗糙集在不完備多尺度信息系統(tǒng)中近似算子的增量更新方法；Xu等[12-13]針對對象變化提出了概率粗糙集模型三支決策的增量更新算法，并進(jìn)一步給出一種流數(shù)據(jù)環(huán)境下的快速計(jì)算三支決策域動態(tài)變化方法；Zhang等[14]面向特征值改變的情況提出了動態(tài)的三支決策粗糙集；趙小龍等[15]針對對象集變化，研究了鄰域信息系統(tǒng)中鄰域?；瘲l件熵的動態(tài)更新方法，并提出了相應(yīng)的增量特征選擇算法；楊臻等[16]研究了混合型信息系統(tǒng)中對象變化時(shí)條件概率的變化關(guān)系，并提出了變精度粗糙集模型近似算子的增量式更新機(jī)制；孫海霞等[17]借鑒文獻(xiàn)[16]中關(guān)于變精度粗糙集的增量更新研究思路，構(gòu)造出鄰域信息系統(tǒng)中對象變化時(shí)決策粗糙集近似集的增量更新算法；Li等[18]在有序信息系統(tǒng)中研究了對象集變化時(shí)全局和局部多粒度粗糙集上近似算子動態(tài)更新的相關(guān)算法.總之，關(guān)于動態(tài)數(shù)據(jù)環(huán)境下粗糙集模型的增量更新算法研究，已經(jīng)取得了很多的成果.但是，這些研究成果大部分是基于全局粗糙集的，對局部粗糙集增量式更新的研究較少，且針對局部鄰域粗糙集還未有相關(guān)研究.

針對鄰域信息系統(tǒng)中對象集變化的情況，分析鄰域信息系統(tǒng)中對象的鄰域類與目標(biāo)概念之間包含度的關(guān)系，然后基于該關(guān)系給出局部近似集的增量更新公式，最后提出了相應(yīng)的增量更新算法.對比實(shí)驗(yàn)表明，所設(shè)計(jì)的增量更新算法在處理動態(tài)數(shù)值型數(shù)據(jù)時(shí)計(jì)算性能更高，有助于推動局部鄰域粗糙集理論在動態(tài)數(shù)值型數(shù)據(jù)下知識發(fā)現(xiàn)的應(yīng)用.

1 局部鄰域粗糙集模型

在粗糙集研究領(lǐng)域中，將數(shù)據(jù)集表示成信息系統(tǒng)IS=(U,AT)，其中U是非空有限對象集，稱為論域，AT是非空有限屬性集.如果屬性集AT=C∪D且C∩D=?，則C是條件屬性集，D是決策屬性集，那么此信息系統(tǒng)也被稱為決策信息系統(tǒng).對于?x∈U和?a∈AT，將對象x在屬性a下的屬性值表示為a(x).若條件屬性值均為數(shù)值型數(shù)據(jù)時(shí)，那么該信息系統(tǒng)又稱為鄰域信息系統(tǒng).

為了在鄰域信息系統(tǒng)中進(jìn)行高效的知識發(fā)現(xiàn)，Wang 等將鄰域關(guān)系引入局部粗糙集模型[2]中，提出了局部鄰域粗糙集[3]，下面給出相關(guān)定義.

定義1[3]設(shè)鄰域信息系統(tǒng)IS=(U,C∪D)，定義屬性集A?C下的鄰域關(guān)系為

定義?x∈U在鄰域關(guān)系下的鄰域類為

其中，δ為非負(fù)常數(shù)，稱之為鄰域半徑.dA(x,y)表示對象x與y之間的距離，采用閔可夫斯基距離，定義為

基于鄰域的思想，Wang等[3]提出了局部近似集及局部鄰域粗糙集的定義.

定義2[3]設(shè)鄰域信息系統(tǒng)IS=(U,C∪D)，屬性集A?C.定義對象集X?U關(guān)于鄰域關(guān)系NA的局部下近似和局部上近似為

其中，0≤β＜α≤1,D(X|δA(x))表示對象x的鄰域類關(guān)于集合X的包含度，定義為

性質(zhì)1[3]設(shè)鄰域信息系統(tǒng)IS=(U,C∪D)，屬性集A?C.那么，對于任何X,Y?U，0≤β＜α≤1，下列性質(zhì)成立：

2 局部鄰域粗糙集的增量更新公式

本節(jié)研究鄰域信息系統(tǒng)中對象增加時(shí)局部鄰域粗糙集的增量式更新公式.鄰域類與目標(biāo)概念之間包含度的計(jì)算是局部鄰域粗糙集模型的基礎(chǔ)，首先探究對象增加時(shí)包含度的關(guān)系.

記鄰域信息系統(tǒng)為IS=(U,C∪D)，屬性集A?C.當(dāng)鄰域信息系統(tǒng)中增加對象x+，記新的鄰域信息系統(tǒng)為IS+=(U+=U∪{x+},C∪D).將對象x∈U在論域U下的鄰域類記為，將對象x∈U+在論域U+下的鄰域類記為.

命題1設(shè)X,Y?U，X+,Y+?U+且X+=X∪{x+}，Y+=Y，那么：

命題1 給出鄰域信息系統(tǒng)的對象增加后，新信息系統(tǒng)中各對象的鄰域類在目標(biāo)概念下的包含度的關(guān)系，以這種關(guān)系為基礎(chǔ)，可以得到局部下近似集的增量式更新公式.

定理1已知X,Y?U關(guān)于屬性集A?C的局部下近似集.設(shè)X+,Y+?U+并且X+=X∪{x+}，Y+=Y，則

3 局部鄰域粗糙集的增量更新算法

基于第2 節(jié)給出的局部近似集的增量更新公式，本節(jié)提出相對應(yīng)的增量更新算法并通過例子闡述該算法.

算法1對象增加時(shí)局部鄰域粗糙集的增量更新算法

對于算法1，步驟①至步驟③是信息系統(tǒng)增加一個(gè)對象時(shí)局部鄰域下近似集的動態(tài)更新算法.如果對增加的對象集合ΔU中的對象按步驟①至步驟③進(jìn)行迭代，則可在對象集增加時(shí)動態(tài)更新局部鄰域下近似集.算法在迭代過程中需計(jì)算增加對象的鄰域類和一些與該鄰域類有關(guān)系的對象的鄰域類.設(shè)條件屬性集的個(gè)數(shù)為|C|，第j次迭代需計(jì)算的鄰域類個(gè)數(shù)為sj+1.則第j次迭代算法的時(shí)間復(fù)雜度為O((sj+1)||U|+j||C|).設(shè)|ΔU|次迭代需重新計(jì)算的鄰域類總數(shù)為S，則算法1的時(shí)間復(fù)雜度為

即O(S|C|(|U||ΔU|+|ΔU|2+|ΔU|)).

以下通過一個(gè)例子，分析并闡述鄰域信息系統(tǒng)的對象增加后，如何利用本節(jié)所提出的更新算法，來實(shí)現(xiàn)局部下近似集的增量式更新.

例1表1是一個(gè)鄰域信息系統(tǒng)IS=(U,C∪D)，C={a1,a2,a3,a4}是條件屬性集，D=j5i0abt0b是決策屬性集，設(shè)鄰域半徑δ=1.5，α=0.5，令屬性集A=C.

表1 鄰域信息系統(tǒng)Tab.1 A neighborhood information system

論域U關(guān)于決策屬性集D的劃分為U/D={D1={x1,x2},D2={x3}}.

假設(shè)將表2中的對象集加入到表1中，并利用定理1對局部下近似集進(jìn)行增量式更新計(jì)算.

表2 新增數(shù)據(jù)對象Tab.2 A new data object

步驟1將x4添加到原信息系統(tǒng)IS中，新信息系統(tǒng)記為IS+=(U+,C∪D)，其中U+=U∪{x4}.

步驟2鄰域信息系統(tǒng)IS+中論域U+關(guān)于決策屬性集D的劃分更新為，并計(jì)算新增對象x4的鄰域類={x1,x4}.

4 實(shí)驗(yàn)分析

本節(jié)通過實(shí)驗(yàn)來驗(yàn)證所提出的算法1的高效性和有效性.

表3 中列出了實(shí)驗(yàn)中使用的數(shù)據(jù)集，這些數(shù)據(jù)集都是從UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中下載的.實(shí)驗(yàn)的操作環(huán)境為：1)CPU為Intel(R)Core(TM)i5-8250U CPU，1.60 GHz；2)操作系統(tǒng)為Windows 10 64位；3)內(nèi)存為8.0 GB；4)開發(fā)平臺為Eclipse IDE 2018-12，Java，JDK 1.8.0.

表3 數(shù)據(jù)集描述Tab.3 Descriptions of datasets

由于表3 中的6 組UCI 數(shù)據(jù)集是靜態(tài)不變的，為模擬現(xiàn)實(shí)生活中數(shù)據(jù)的動態(tài)變化，本實(shí)驗(yàn)做如下處理：將表中的每份數(shù)據(jù)集分為10 份對象數(shù)相等且不相交的子數(shù)據(jù)集，繼而逐步合并子數(shù)據(jù)集模擬現(xiàn)實(shí)中的動態(tài)數(shù)據(jù)集.針對信息系統(tǒng)中對象增加的情況，選擇一份子數(shù)據(jù)集作為原始信息系統(tǒng)，然后選擇其他的子數(shù)據(jù)集添加到原始信息系統(tǒng)中，構(gòu)造出一次信息系統(tǒng)的動態(tài)變化過程.通過將10 份子數(shù)據(jù)集逐一合并，構(gòu)造出9 次信息系統(tǒng)的動態(tài)變化過程.實(shí)驗(yàn)中對各數(shù)據(jù)集的屬性值進(jìn)行歸一化處理，設(shè)定閾值α=0.5.文獻(xiàn)[19]經(jīng)過多次實(shí)驗(yàn)確定參數(shù)δ在[0.2，0.4]之間取值較為理想，故本實(shí)驗(yàn)設(shè)定鄰域半徑δ=0.2.

對于表3 中的六組不同的UCI 數(shù)據(jù)集，圖1 分別比較了信息系統(tǒng)中對象添加時(shí)增量算法和非增量算法[3]的性能，實(shí)驗(yàn)重復(fù)進(jìn)行5次取平均結(jié)果.圖1中，橫坐標(biāo)表示數(shù)據(jù)集的動態(tài)變化次數(shù)，縱坐標(biāo)表示算法的計(jì)算耗時(shí).從圖1 可以看出，增量算法的效率比非增量算法更高.隨著鄰域信息系統(tǒng)中動態(tài)變化次數(shù)的逐漸增加，增量算法和非增量算法的耗時(shí)均呈現(xiàn)逐漸增加的趨勢.然而，非增量算法的耗時(shí)逐漸增加且增長率逐漸變大.和非增量算法相比，增量式算法的效率更加穩(wěn)定，而且非增量算法與增量式算法的耗時(shí)差值隨數(shù)據(jù)集動態(tài)變化次數(shù)的增加而逐漸增大.這驗(yàn)證了增量算法能有效地利用原信息系統(tǒng)中已有的知識，減小知識發(fā)現(xiàn)過程中的計(jì)算量.實(shí)驗(yàn)結(jié)果驗(yàn)證了在求解動態(tài)數(shù)值型數(shù)據(jù)的局部近似集時(shí)，設(shè)計(jì)的增量算法比非增量算法具有更好的性能和更高的效率.

圖1 增量算法與非增量算法計(jì)算耗時(shí)對比圖Fig.1 Comparison chart of calculation time consumption of incremental algorithm and non-incremental algorithm

5 結(jié)論

動態(tài)數(shù)值型數(shù)據(jù)的分析與處理已成為數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)重要研究課題.針對動態(tài)數(shù)值型數(shù)據(jù)，提出了一種針對對象變化的局部鄰域粗糙集的增量更新算法.首先，給出了鄰域信息系統(tǒng)的對象增加時(shí)局部鄰域粗糙集中包含度的關(guān)系，并在此基礎(chǔ)上提出了局部近似算子的增量更新公式.然后，針對鄰域信息系統(tǒng)中添加對象的情況，設(shè)計(jì)了局部近似集的增量更新算法.所設(shè)計(jì)的算法可以避免重復(fù)計(jì)算，利用已有結(jié)果高效地求解局部近似集.

在仿真實(shí)驗(yàn)中，選取六組UCI 數(shù)據(jù)集，對非增量算法和所設(shè)計(jì)的增量算法計(jì)算近似集的耗時(shí)進(jìn)行對比.實(shí)驗(yàn)結(jié)果驗(yàn)證了所設(shè)計(jì)的增量更新算法計(jì)算效率更高，并且增量算法的性能受數(shù)據(jù)集動態(tài)變化次數(shù)的影響較小.在下一步工作中，將研究當(dāng)鄰域信息系統(tǒng)的屬性集和屬性值發(fā)生變化時(shí)局部鄰域粗糙集模型的更新問題.

猜你喜歡

論域粗糙集鄰域

基于Pawlak粗糙集模型的集合運(yùn)算關(guān)系

科教導(dǎo)刊·電子版(2021年6期)2021-05-06 05:05:10

基于變論域模糊控制的Taylor逼近型內(nèi)模PID算法

成都信息工程大學(xué)學(xué)報(bào)(2021年6期)2021-02-12 03:00:52

稀疏圖平方圖的染色數(shù)上界

吉林大學(xué)學(xué)報(bào)(理學(xué)版)(2020年3期)2020-05-29 06:32:16

變論域自適應(yīng)模糊PID控制系統(tǒng)仿真與應(yīng)用

測控技術(shù)(2018年10期)2018-11-25 09:35:52

基于鄰域競賽的多目標(biāo)優(yōu)化算法

自動化學(xué)報(bào)(2018年7期)2018-08-20 02:59:04

多?；植诩再|(zhì)的幾個(gè)充分條件

廈門理工學(xué)院學(xué)報(bào)(2016年3期)2016-11-10 09:39:14

關(guān)于-型鄰域空間

周口師范學(xué)院學(xué)報(bào)(2016年5期)2016-10-17 06:36:47

雙論域粗糙集在故障診斷中的應(yīng)用

廣東石油化工學(xué)院學(xué)報(bào)(2016年3期)2016-05-17 05:17:10

微生物燃料電池的變論域自適應(yīng)模糊控制研究

電源技術(shù)(2016年2期)2016-02-27 09:04:56

兩個(gè)域上的覆蓋變精度粗糙集模型

四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版)(2015年1期)2015-02-28 14:07:21

閩南師范大學(xué)學(xué)報(bào)(自然科學(xué)版)2022年3期

閩南師范大學(xué)學(xué)報(bào)(自然科學(xué)版)的其它文章

《閩南師范大學(xué)學(xué)報(bào)（自然科學(xué)版）》征稿簡則

環(huán)境污染治理的多種群演化博弈分析

地方高?？萍计诳l(fā)展的思考

社區(qū)體育適老性服務(wù)問題與改進(jìn)策略

輪椅冰壺項(xiàng)目競技能力結(jié)構(gòu)特征研究

3個(gè)馬拉巴栗葉色突變體色素含量與光合特性分析