• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    基于屬性樹的并行化增量式動態(tài)屬性約簡算法

    2022-11-18 04:20:14秦廷楨丁衛(wèi)平鞠恒榮黃嘉爽陳悅鵬王海鵬
    模式識別與人工智能 2022年10期
    關(guān)鍵詞:決策表約簡子集

    秦廷楨 丁衛(wèi)平 鞠恒榮 李 銘 黃嘉爽 陳悅鵬 王海鵬

    近年來,隨著信息技術(shù)的發(fā)展,科學(xué)和工業(yè)等現(xiàn)實(shí)領(lǐng)域產(chǎn)生大量的數(shù)據(jù),而許多應(yīng)用程序處理的數(shù)據(jù)量通常大幅超過其承受閾值,計(jì)算需求也隨之增加.現(xiàn)代化信息技術(shù)蓬勃發(fā)展使記錄和數(shù)據(jù)收集變得越來越細(xì)粒度和多維度[1-2],導(dǎo)致海量數(shù)據(jù)的數(shù)據(jù)處理和知識發(fā)現(xiàn)一直是數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn).大數(shù)據(jù)可定義為超出傳統(tǒng)系統(tǒng)存儲和處理能力的數(shù)據(jù),包含巨大的潛在價(jià)值.然而,這些龐大而復(fù)雜的數(shù)據(jù)集往往伴隨著顯著的數(shù)據(jù)冗余[3-4],浪費(fèi)存儲空間.這種大規(guī)模數(shù)據(jù)集的產(chǎn)生也帶來數(shù)據(jù)存儲、計(jì)算效率和計(jì)算精度等諸多挑戰(zhàn).

    粗糙集理論(Rough Set Theory, RST)[5]是一種常用的分析決策不確定性信息的數(shù)學(xué)工具.粗糙集可通過不可辨識關(guān)系劃分不確定性知識概念,得到不同等價(jià)關(guān)系下的等價(jià)類集合,從而建立一個(gè)近似空間.RST現(xiàn)已成功應(yīng)用于圖像處理[6]、聚類分析[7]、模式識別[8]、機(jī)器學(xué)習(xí)[9-10]、特征選擇[11]、決策支持和數(shù)據(jù)挖掘[12-14]等多個(gè)研究領(lǐng)域.屬性約簡是粗糙集理論中的一個(gè)重要概念,成為近年來備受關(guān)注的一種重要的數(shù)據(jù)預(yù)處理工具,在知識發(fā)現(xiàn)、專家系統(tǒng)、決策支持、機(jī)器學(xué)習(xí)等研究領(lǐng)域中,可提高識別精度,發(fā)現(xiàn)潛在有用的知識.

    經(jīng)典的屬性約簡算法,如基于正區(qū)域的屬性約簡算法[15-16]、基于信息熵的屬性約簡算法[17-18]、基于差別矩陣的屬性約簡算法[19-20]等,是一次性將小數(shù)據(jù)集裝入單機(jī)主存中進(jìn)行約簡計(jì)算,因此無法處理海量數(shù)據(jù).隨著Hadoop[21]、MapReduce[22]等大數(shù)據(jù)技術(shù)的發(fā)展,使利用大數(shù)據(jù)技術(shù)進(jìn)行并行屬性約簡的研究成為人們關(guān)注的焦點(diǎn).為了解決串行算法的局限性,Zhang等[23]在MapReduce基礎(chǔ)上提出PLAR(Parall Large-Scale Attribute Reduction),得到與傳統(tǒng)方法相同的屬性約簡.Raza等[24]提出基于正區(qū)域的并行屬性約簡算法,可并行搜索所有正區(qū)域,大幅提升計(jì)算效率.Qian等[25-26]深入研究MapReduce框架中的屬性約簡過程,在并行階段計(jì)算等價(jià)類,經(jīng)過shuffle過程后,再通過約簡聚合相同鍵值的等價(jià)類,提出基于MapReduce的并行知識約簡算法.

    上述算法表明,在MapReduce上并行化傳統(tǒng)的屬性約簡算法,實(shí)現(xiàn)海量數(shù)據(jù)的屬性約簡是可行的.但是,由于MapReduce和傳統(tǒng)約簡算法存在一些固有的局限性,所以需要進(jìn)一步改進(jìn).近年來,對于解決靜態(tài)決策系統(tǒng)[27-28]的屬性約簡問題,學(xué)者們提出很多非增量約簡算法.然而,如今許多決策系統(tǒng)的對象集是動態(tài)變化的,決策系統(tǒng)可能也會隨著時(shí)間變化而變化.由于對象集是動態(tài)變化的,為了得到新的約簡,需要對決策系統(tǒng)進(jìn)行重新計(jì)算,耗費(fèi)大量的計(jì)算時(shí)間.

    顯然,這些屬性約簡算法在處理動態(tài)決策系統(tǒng)時(shí)效率低下,如何更新約簡是提高數(shù)據(jù)預(yù)處理效率的關(guān)鍵問題.增量學(xué)習(xí)是一種利用原有決策系統(tǒng)的結(jié)果以提高知識發(fā)現(xiàn)效率的有效方法.針對不同情形,學(xué)者們提出許多增量算法,用于處理動態(tài)數(shù)據(jù).對于對象集不斷變化的動態(tài)不完備決策表,Shu等[29]提出通過更新正區(qū)域以獲取約簡的增量方法.Liu等[30]提出通過構(gòu)造3個(gè)新矩陣(支持矩陣、精度矩陣和覆蓋矩陣)以獲取屬性約簡的增量方法.通過計(jì)算更新后的知識粒度,Jing等[31]提出相應(yīng)的增量式屬性約簡算法.錢進(jìn)等[32]根據(jù)屬性集的可辨識性和不可辨識性,給出可辨識對象對和不可辨識對象對的定義和相關(guān)性質(zhì),結(jié)合MapReduce技術(shù),設(shè)計(jì)適合大規(guī)模數(shù)據(jù)集的并行計(jì)算等價(jià)類的算法.Liang等[33]系統(tǒng)研究添加到?jīng)Q策表中一組對象的熵的性質(zhì),并提出有效的增量屬性約簡算法.

    顯然,上述方法主要側(cè)重于更新近似的角度進(jìn)行約簡,對大規(guī)模決策系統(tǒng)的簡化是低效的.因此本文深入研究Spark并行技術(shù),分析現(xiàn)有增量式約簡算法,同時(shí)融合Chen等[34]提出屬性組的概念與二叉樹的機(jī)制,結(jié)合Spark并行框架,設(shè)計(jì)增量式屬性約簡算法.首先,從屬性組概念入手,引入二叉樹機(jī)制尋找約簡,將所有條件屬性通過聚類劃分為多棵屬性樹.再在每輪屬性樹分支中挑選合適屬性樹進(jìn)行屬性評估,并在計(jì)算過程中加入分支閾值系數(shù)α,避免冗余計(jì)算,有效減少屬性評估數(shù)量,提高屬性約簡效率和精度.同時(shí)當(dāng)多個(gè)增量對象加入決策系統(tǒng)時(shí),可利用增量機(jī)制更新約簡,提出基于屬性樹的增量式屬性約簡算法(Incremental Dynamic Attribute Re-duction Algorithm Based on Attribute Tree, IARAT).在上述基礎(chǔ)上,結(jié)合Spark并行技術(shù),并行化數(shù)據(jù)處理,加快搜索效率,利用Spark框架進(jìn)行經(jīng)典屬性約簡算法并行化優(yōu)勢,提出基于屬性樹的并行化增量式動態(tài)屬性約簡算法(Parallel IARAT, PIARAT).在多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)表明,PIARAT在保持分類性能的同時(shí),提高動態(tài)變化數(shù)據(jù)集約簡的搜索效率,具有較好的性能優(yōu)勢.

    1 相關(guān)知識

    1.1 粗糙集

    定義1[5]給定決策表S=〈U,C∪D,V,f〉,對于每個(gè)屬性子集R?A,定義不可分辨關(guān)系:

    IND(R)={(x,y)∈U×U|?a∈R,f(x,a)=f(y,a)}.

    關(guān)系IND(R)構(gòu)成U的一個(gè)劃分,表示為U/IND(R),簡記為U/R.U/R中的任何元素

    [x]R={y|?a∈R,f(x,a)=f(y,a)}

    稱為等價(jià)類.不失一般性,假設(shè)決策表S僅有一個(gè)決策屬性D=j5i0abt0b,其決策屬性值映射為1,2,…,k,由D導(dǎo)出的U上的劃分為U/D={Z1,Z2,…,Zk},其中

    Zi={x∈U|f(x,D)=i},i=1,2,…,k.

    不可分辨關(guān)系是一種等價(jià)關(guān)系.

    定義2[35]給定決策表S=〈U,C∪D,V,f〉,對于每個(gè)子集X?U和不可分辨關(guān)系R,X的下近似集與上近似集分別可由R定義如下:

    1.2 知識粒度

    定義3[28]給定決策表S=〈U,C∪D,V,f〉,條件屬性集C對于U的劃分為

    U/C={X1,X2,…,Xn′},

    n′為劃分后的子集數(shù)量,則條件屬性集C的知識粒度定義為

    屬性集(C∪D)對于U的劃分為

    U/(C∪D)={Y1,Y2,…,Yh},

    h為劃分后的子集數(shù)量,則條件屬性集C相對于決策屬性集D的知識粒度定義為

    GPU(D|C)=GPU(C)-GPU(C∪D).

    定義4[28]給定決策表S=〈U,C∪D,V,f〉,條件屬性集C對于U的劃分為

    U/C={X1,X2,…,Xn′},

    n′為劃分后的子集數(shù)量,屬性集B?C,?a∈B,屬性a在B中相對于決策屬性集D的內(nèi)部屬性重要度定義為

    若?a∈(C-B),則屬性a在(C-B)中相對于決策屬性集D的外部屬性重要度定義為

    定義5[28]給定決策表S=〈U,C∪D,V,f〉,屬性集B?C.當(dāng)且僅當(dāng)滿足

    1)GPU(D|B)=GPU(D|C),

    2)?a∈B,GPU(D|(B-a))≠GPU(D|B),

    則稱B為決策表S的相對約簡.條件1)表示約簡后的屬性集B與所有條件屬性集C關(guān)于D的知識粒度相等,表現(xiàn)的意義是屬性集B與條件屬性集C對數(shù)據(jù)樣本U的分類能力相同,即找到的約簡集是合格的.條件2)表示若從B中剔除某個(gè)屬性之后,會降低分類能力,這意味著B中無任何冗余的屬性.這兩個(gè)條件共同作為屬性約簡的正確性標(biāo)準(zhǔn).

    定理1[25]給定決策表S=〈U,C∪D,V,f〉,令A(yù)?C,U/A表示為{A1,A2,…,Ar},U被劃分成多個(gè)數(shù)據(jù)子集{U1,U2,…,UL},

    Ui/A={Ai1,Ai2,…,Air},

    則最終約簡集

    證明如果關(guān)于A的任意兩個(gè)對象相同,可將它們合并為一個(gè)等價(jià)類.不同數(shù)據(jù)拆分之間的相同等價(jià)類可組合為更大的等價(jià)類.因此,對于

    U/A={A1,A2,…,Ar},Ui/A={Ai1,Ai2,…,Air},

    可得

    定理2[25]并行屬性約簡算法得到的約簡與相應(yīng)的串行方法得到的約簡相同.

    證明傳統(tǒng)的屬性約簡算法主要分為4個(gè)基本步驟:子集生成、子集評估、停止標(biāo)準(zhǔn)、結(jié)果驗(yàn)證.并行算法和串行算法之間的唯一區(qū)別是屬性子集評估過程,主要包括等價(jià)類和屬性重要度的計(jì)算.

    1)根據(jù)定理1,

    這意味著串行算法中的等價(jià)類與相應(yīng)并行算法中的等價(jià)類相同.

    2)由于串行算法中的等價(jià)類與相應(yīng)并行算法中的等價(jià)類相同,則它們計(jì)算所得的屬性重要度也相同.

    因此,并行算法得到的約簡與相應(yīng)的串行算法得到的約簡相同.

    1.3 Spark框架

    Hadoop MapReduce[36]是一個(gè)分布式計(jì)算框架,允許開發(fā)人員使用簡單的代碼在巨大的集群上實(shí)現(xiàn)大規(guī)模的數(shù)據(jù)計(jì)算.但由于磁盤I/O和網(wǎng)絡(luò)傳輸過多,不適合迭代計(jì)算和在線計(jì)算任務(wù).為了克服MapReduce的不足,學(xué)者們提出新一代集群計(jì)算引擎Spark.Apache Spark[37]是在MapReduce基礎(chǔ)上改進(jìn)的分布式計(jì)算框架,具有快速、易用、通用、兼容等優(yōu)點(diǎn).

    Spark的運(yùn)行流程主要分為如下步驟.

    1)首先啟動 SparkContext,并向Cluster Manager注冊,申請Executor資源,Cluster Manager為 Execu-

    tor分配資源并啟動進(jìn)程.

    2)SparkContext構(gòu)建有向無環(huán)圖(Directed Acyclic Graph, DAG),將DAG圖分解成多個(gè)階段,并發(fā)送給Task Scheduler.

    3)Executor向SparkContext申請Task,SparkCon-

    text將應(yīng)用程序代碼發(fā)放給Executor.

    4)Task在Executor上運(yùn)行完畢后,把執(zhí)行結(jié)果反饋給Task Scheduler和DAG Scheduler,并寫入數(shù)據(jù).最后,SparkContext注銷并釋放所有資源.

    彈性分布式數(shù)據(jù)集(Resilient Distributed Data-

    set, RDD)是Spark中基本的數(shù)據(jù)抽象.在代碼中是一個(gè)抽象類,表示一個(gè)彈性、不可變、可分區(qū)、里面的元素可并行計(jì)算的集合.RDD表示只讀的分區(qū)的數(shù)據(jù)集,改動RDD,只能通過RDD的轉(zhuǎn)換操作,然后得到新的RDD,并不會對原RDD有任何的影響.

    2 并行化增量式動態(tài)屬性約簡算法

    本文分析現(xiàn)有增量式約簡算法,同時(shí)融合屬性組[34]的概念與二叉樹的概念,并結(jié)合Spark并行框架,設(shè)計(jì)基于屬性樹的并行化增量式動態(tài)屬性約簡算法(PIARAT).首先,對原始數(shù)據(jù)進(jìn)行預(yù)處理操作,滿足算法的輸入要求,然后,提出基于屬性樹的增量式屬性約簡算法(IARAT),刪除冗余屬性,提出核心屬性,最后,將IARAT結(jié)合Spark并行機(jī)制,提出PIARAT,可有效加快動態(tài)屬性約簡的過程.

    2.1 原始數(shù)據(jù)并行預(yù)處理算法

    本文改進(jìn)傳統(tǒng)的并行數(shù)據(jù)預(yù)處理算法,使其更滿足后續(xù)算法的數(shù)據(jù)輸入要求,提出原始數(shù)據(jù)并行預(yù)處理算法,處理原始數(shù)據(jù)集,具體流程圖如圖1所示.具體算法步驟如下所示.

    圖1 原始數(shù)據(jù)并行預(yù)處理算法流程圖

    算法1原始數(shù)據(jù)并行預(yù)處理算法

    輸入原始決策表S_raw

    輸出處理后的決策表S

    step 1 在每個(gè)子節(jié)點(diǎn)slavei上讀取原始決策表,刪除其中含有缺失屬性值的樣本數(shù)據(jù).

    step 2 調(diào)用Spark計(jì)算引擎中的mapPartitions算子,將刪除后的數(shù)據(jù)對象轉(zhuǎn)換為鍵值對RDD數(shù)據(jù)集合.

    step 3 調(diào)用Spark計(jì)算引擎中的mapValues算子,對RDD數(shù)據(jù)集中的value部分進(jìn)行step 4的操作,消除決策表中重復(fù)樣本和不一致部分.

    step 4

    /*存在2個(gè)數(shù)據(jù)樣本的key值相同時(shí)*/

    Ifs1.key=s2.key, then

    Ifs1.value=s2.value

    Removes2;

    Else

    Removes2;

    s1.value←valueMAX+1;

    End

    End

    step 5 調(diào)用Spark計(jì)算引擎中的sortByKey算子,并對數(shù)據(jù)按屬性值進(jìn)行由小到大的排序,方便后續(xù)計(jì)算.

    step 6 返回處理后的決策表S.

    算法1的執(zhí)行過程具體如下.首先,由于原始數(shù)據(jù)集中包含許多無法參與計(jì)算的含有缺失值的數(shù)據(jù),而包含缺失值的數(shù)據(jù)會對后續(xù)約簡計(jì)算產(chǎn)生影響,需要刪除此類缺失值數(shù)據(jù).然后,將數(shù)據(jù)集轉(zhuǎn)化為所有條件屬性為key值,決策屬性為value值的k-v鍵值對.遍歷所有樣本,對于key和value相同的重復(fù)數(shù)據(jù)樣本,選擇刪除其一;而對于key相同、value不同的一對樣本(決策表不一致部分),刪除key值,并將后者的value值修改為決策表中最大value值加1.最后,對整個(gè)數(shù)據(jù)子集按屬性值進(jìn)行由小到大的sort排序,方便后續(xù)計(jì)算.

    2.2 基于屬性樹的增量式屬性約簡算法

    如今許多決策系統(tǒng)是隨著時(shí)間而動態(tài)變化的,為了得到新的約簡,需要重新對決策系統(tǒng)進(jìn)行約簡計(jì)算,耗費(fèi)大量時(shí)間.為了解決該問題,本文從屬性組的概念入手,引入二叉樹的機(jī)制,設(shè)計(jì)搜索策略尋找約簡,并且借助基于知識粒度的增量約簡算法[31],將知識粒度加入迭代停止準(zhǔn)則中,提出基于屬性樹的增量式屬性約簡算法(IARAT),具體算法步驟如下所示.

    算法2IARAT

    輸入原始樣本數(shù)據(jù)U,增量樣本數(shù)據(jù)U′,

    原約簡集B,分支閾值αmax

    輸出約簡子集R

    R←B,K←1;

    計(jì)算知識粒度GPU′(D|R)和GPU′(D|C);

    IfGPU′(D|R)=GPU′(D|C), then

    ReturnR

    End

    ClusterCinto{C1,C2,…,CN};

    /*C聚類成N個(gè)屬性樹根結(jié)點(diǎn)*/

    WhileGPU′(D|R)≠GPU′(D|C) andK<αmax:

    For eachtreei:

    treei.right.data←treei.data∩R;

    /*存在原約簡屬性,置于右節(jié)點(diǎn)*/

    treei.left.data←treei.data-treei.right.data;

    /*剩下的屬性置于左節(jié)點(diǎn)*/

    For each attributecbeing evaluated:

    /*評估無兄弟結(jié)點(diǎn)屬性樹*/

    Ifc是核心屬性 then

    treei.right.data←c;

    R←(R∪c);

    treei.left.data←treei.data-c;

    Break

    Else

    C←(C-c);

    End

    End

    End

    For eachtreei:

    Iftreei.left≠? then

    treei=treei.left;

    Else

    remove the tree;

    /*移除該樹*/

    K=K+1;

    End

    End

    End

    ReturnR

    IARAT首先需要對決策表進(jìn)行預(yù)先判斷:加入增量數(shù)據(jù)集后是否需要進(jìn)一步的約簡計(jì)算.若在增量數(shù)據(jù)集上,決策屬性D分別關(guān)于原約簡子集R與條件屬性集C的知識粒度相等(GPU′(D|R)和GPU′(D|C)),即在增量數(shù)據(jù)集上,約簡子集R依然可保持與條件屬性集C相同的分類能力,可知增量數(shù)據(jù)集的加入未影響原約簡結(jié)果,無需進(jìn)一步計(jì)算;若不相等,需要進(jìn)一步計(jì)算,得到新的約簡.根據(jù)相應(yīng)聚類算法,將所有條件屬性劃分為多個(gè)屬性樹根結(jié)點(diǎn)并進(jìn)行分支操作,在進(jìn)行每輪的屬性評估過程中,跳過與約簡集相關(guān)性較高的屬性樹,對剩下的屬性樹加以評估,同時(shí)根據(jù)評估結(jié)果的不同,進(jìn)行不同子結(jié)點(diǎn)的分支.在計(jì)算過程中引入分支系數(shù)α并設(shè)定閾值,方便跳出循環(huán),避免冗余計(jì)算和陷入死循環(huán).

    屬性樹結(jié)構(gòu)如下.根節(jié)點(diǎn)包含聚類算法劃分的條件屬性簇,在每輪屬性樹分支中,將核心屬性置于樹的右子結(jié)點(diǎn),其余部分劃分為左子結(jié)點(diǎn),在下次分支中,根據(jù)相應(yīng)策略對左子結(jié)點(diǎn)進(jìn)行再劃分.屬性樹的結(jié)構(gòu)及分支策略如圖2和圖3所示.

    圖2 單棵屬性樹結(jié)構(gòu)

    (a)單棵屬性樹

    在屬性樹的初始判別階段,通過增量機(jī)制減少屬性評估數(shù)量,提高屬性約簡的效率和精度,當(dāng)多個(gè)增量對象加入決策系統(tǒng)時(shí),可利用增量機(jī)制更新約簡.在屬性評估階段,采用Yin等[38]設(shè)計(jì)的核心屬性約簡算法代替?zhèn)鹘y(tǒng)的屬性重要度約簡算法,不僅在計(jì)算效率上擁有優(yōu)勢,而且避免二次循環(huán)評估,提高計(jì)算效率.該算法的優(yōu)化策略每次只判斷一個(gè)屬性是否為核心屬性,避免時(shí)間復(fù)雜度較高的正區(qū)域計(jì)算,減少獲取約簡子集所需的時(shí)間,時(shí)間復(fù)雜度僅為|C|.

    核心屬性約簡算法機(jī)制如下.在決策表S=〈U,C∪D,V,f〉中,對于某條件屬性ci,若刪除ci,存在2個(gè)數(shù)據(jù)樣本x、y的條件屬性值(即C-ci)相等,而決策屬性值不相等,則認(rèn)定屬性ci為核心屬性,否則,ci不是核心屬性.

    屬性樹分支策略如下.在預(yù)先判斷后得知決策屬性D分別關(guān)于原約簡子集R與條件屬性集C的知識粒度不相等,說明增量數(shù)據(jù)集的加入影響原約簡結(jié)果,原數(shù)據(jù)的約簡集已無法對現(xiàn)有增量數(shù)據(jù)保持有效的分類性能,所以需要進(jìn)一步進(jìn)行如下計(jì)算.

    1)對加入的增量數(shù)據(jù)集S′的條件屬性C執(zhí)行相應(yīng)的聚類算法.根據(jù)屬性與屬性之間相關(guān)性及屬性與屬性簇之間的相關(guān)性,將所有條件屬性集C劃分成多個(gè)屬性簇群{C1,C2,…,CN},目的是聚集具有較大依賴關(guān)系(冗余度高)的屬性,具有高相關(guān)性的每個(gè)屬性子集轉(zhuǎn)換成一棵屬性樹treei的根節(jié)點(diǎn).

    2)進(jìn)行逐棵屬性樹treei的分支.為了避免重復(fù)計(jì)算,利用原約簡集B,參與到分支過程中,把多棵屬性樹的根節(jié)點(diǎn)與原約簡集B中相交的部分置于右子結(jié)點(diǎn)treei.right.這一步是為了找出與原約簡集B存在相關(guān)性的屬性樹,在下輪分支時(shí)跳過該樹的屬性評估,其余部分劃分為左子結(jié)點(diǎn)treei.left,后續(xù)的分支計(jì)算在該結(jié)點(diǎn)上進(jìn)行.同時(shí)設(shè)置分支系數(shù)α并初始化為1,在每次分支之后進(jìn)行遞增,當(dāng)達(dá)到最大閾值時(shí)跳出循環(huán),閾值即屬性樹的最大分支深度.基于最壞的打算,為了避免冗余計(jì)算和陷入死循環(huán),一般設(shè)置為屬性樹根結(jié)點(diǎn)中最大的屬性數(shù)量.

    3)在每次分支過程中運(yùn)用核心屬性約簡算法逐個(gè)評估無兄弟結(jié)點(diǎn)屬性樹(即評估本輪與約簡集相關(guān)性較低的屬性樹).如果不是核心屬性,直接從節(jié)點(diǎn)中刪除,不再參與后續(xù)計(jì)算,繼續(xù)評估下一屬性,直到找出該屬性樹中第一個(gè)核心屬性;如果是核心屬性,加入約簡集R并停止本棵樹余下屬性的評估.

    直到所有屬性樹評估完成,該輪分支結(jié)束.

    4)屬性樹與約簡集的相關(guān)性度量取決于上一輪中約簡集是否加入某棵屬性樹中的屬性.每棵樹都是由聚類算法生成的屬性簇群,屬性之間存在較高相關(guān)性,若上一輪評估過程中添加某棵樹的屬性進(jìn)入約簡集,因?yàn)槠渌鼘傩詷渲写嬖诤诵膶傩缘目赡苄暂^高,所以可跳過對該樹的屬性評估,縮小搜索空間,提升檢索效率.

    5)在分支過程中,如果遇到某棵樹左節(jié)點(diǎn)為空,說明該屬性樹分支完成,所有屬性樹全部分支完成后,輸出新約簡集.

    2.3 基于屬性樹的并行化增量式動態(tài)屬性約簡

    算法

    本節(jié)首先引入IARAT,在此基礎(chǔ)上,融入Spark并行機(jī)制,實(shí)現(xiàn)分布式的內(nèi)存計(jì)算任務(wù),在不犧牲性能的情況下找出不同數(shù)據(jù)子集中的冗余屬性并行化數(shù)據(jù)處理,降低數(shù)據(jù)規(guī)模和計(jì)算時(shí)間,提高效率.由此,設(shè)計(jì)基于屬性樹的并行化增量式動態(tài)屬性約簡算法(PIARAT),流程圖如圖4所示.PIARAT具體步驟如下所示.

    圖4 PIARAT流程圖

    算法3PIARAT

    輸入原始數(shù)據(jù)集S_raw

    輸出約簡子集R

    step 1 將原始數(shù)據(jù)集S_raw存入HDFS文件系統(tǒng).

    step 2 在主節(jié)點(diǎn)master中讀取文件系統(tǒng)中的數(shù)據(jù)集.

    step 3 將數(shù)據(jù)集S_raw以1∶1的比例劃分成原決策表S和增量決策表S′.

    step 4 調(diào)用算法1對增量決策表S′進(jìn)行并行預(yù)處理操作.

    step 5 對原決策表S進(jìn)行屬性約簡計(jì)算,得到原約簡集B.

    step 6 將原決策表S和原約簡集B發(fā)送到所有子節(jié)點(diǎn)slavei上.

    step 7 將增量數(shù)據(jù)集切分成n份,分別發(fā)送到n個(gè)工作節(jié)點(diǎn)上.

    step 8 在所有子節(jié)點(diǎn)slavei上調(diào)用算法2進(jìn)行基于屬性樹的增量式屬性約簡,返回,得到各約簡子集{R1,R2,…,Rn}.

    step 9 將各個(gè)子節(jié)點(diǎn)slavei上得到的約簡子集{R1,R2,…,Rn}發(fā)送到主節(jié)點(diǎn)master上.

    step 10 對約簡子集Bi進(jìn)行并集操作,得到最終約簡集R.

    step 11 返回R.

    PIARAT首先將搜集的海量大規(guī)模數(shù)據(jù)集存入HDFS(Hadoop Distributed File System)文件系統(tǒng)[39].再按照比例將數(shù)據(jù)集劃分為原始數(shù)據(jù)集和增量數(shù)據(jù)集,PIARAT主要側(cè)重于增量數(shù)據(jù)集上的并行屬性約簡,所以主要對增量數(shù)據(jù)集進(jìn)行約簡計(jì)算.然后,對增量數(shù)據(jù)集進(jìn)行二次劃分,劃分成多個(gè)數(shù)據(jù)子集,并分發(fā)到對應(yīng)的多個(gè)工作節(jié)點(diǎn)上,采用基于屬性樹的增量式屬性約簡算法,在各子節(jié)點(diǎn)上并行處理數(shù)據(jù).最后,將處理完成的多個(gè)結(jié)果返回主節(jié)點(diǎn)進(jìn)行最終并集操作,得到最終約簡子集.

    2.4 時(shí)間復(fù)雜度分析

    為了進(jìn)一度凸顯算法優(yōu)勢,對IARAT和PIARAT進(jìn)行時(shí)間復(fù)雜度分析.給定決策表S=〈U,C∪D,V,f〉,設(shè)定U表示原始數(shù)據(jù)集樣本,U′表示增量數(shù)據(jù)集樣本,C表示所有條件屬性并聚集成k棵屬性樹,k?C,最終的約簡子集為R,并設(shè)置n個(gè)并行計(jì)算節(jié)點(diǎn).

    PIARAT在算法的初始判別階段,需要計(jì)算知識粒度并判斷是否需要進(jìn)一步約簡,時(shí)間復(fù)雜度為O(|C||U′|2).在step 8的屬性遍歷過程中,傳統(tǒng)算法是逐個(gè)計(jì)算屬性的重要性,導(dǎo)致大部分屬性的重復(fù)計(jì)算,時(shí)間復(fù)雜度為

    而PIARAT的時(shí)間復(fù)雜度僅為O(|C|),有效提升計(jì)算效率.

    最后, IARAT和PIARAT的時(shí)間復(fù)雜度分別為

    由此可得出,PIARAT的時(shí)間復(fù)雜度遠(yuǎn)低于傳統(tǒng)串行算法,具有良好的加速性能.

    3 實(shí)驗(yàn)及結(jié)果分析

    本文采用的實(shí)驗(yàn)平臺為PC(Intel(R) Core(TM) i5-10400H CPU@2.30 GHz,RAM 16 GB),Windows 10家庭中文版操作系統(tǒng),開發(fā)工具為JetBrains PyCharm,使用Python語言實(shí)現(xiàn)實(shí)驗(yàn)中相關(guān)算法.

    在Windows 10系統(tǒng)上搭建MapReduce Hadoop-2.7.1和Spark-3.0.0-preview的模擬環(huán)境平臺,集群運(yùn)行模式采用本地模式“l(fā)ocal”.

    在實(shí)驗(yàn)過程中,通過Spark框架中的Python API進(jìn)行編寫,將本地模式中的參數(shù)設(shè)置為local[*].

    3.1 實(shí)驗(yàn)數(shù)據(jù)集

    本文從UCI機(jī)器學(xué)習(xí)知識庫上選擇8個(gè)數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集,分為5個(gè)小型數(shù)據(jù)集和3個(gè)較大數(shù)據(jù)集.所有數(shù)據(jù)集的詳細(xì)信息如表1所示.

    表1 實(shí)驗(yàn)數(shù)據(jù)集

    小型數(shù)據(jù)集分別為Qsar、Mushroom、Nursery、Shuttle、Letter數(shù)據(jù)集,樣本量由幾千至幾萬不等.較大數(shù)據(jù)集為Poker Hand、KDD Cup、HIGGS數(shù)據(jù)集,擁有幾十個(gè)屬性,但包含百萬級的樣本量.

    3.2 實(shí)驗(yàn)設(shè)置

    首先對數(shù)據(jù)集進(jìn)行原始數(shù)據(jù)和增量數(shù)據(jù)的劃分,從表1中的每個(gè)決策系統(tǒng)中選取50%初始的數(shù)據(jù)樣本量作為原始數(shù)據(jù)集,然后從剩余的50%數(shù)據(jù)樣本量中分別選取20%,40%,60%,80%,100%的數(shù)據(jù)作為增量數(shù)據(jù)集填充.在原始決策系統(tǒng)中添加增量對象集時(shí),采用不同的增量約簡算法對各決策系統(tǒng)的約簡進(jìn)行更新并進(jìn)行對比討論.

    在屬性聚類階段,采用的聚類算法為K-means,對數(shù)據(jù)集采用肘部法則[40]分別確定K值.肘部法則使用的聚類評價(jià)指標(biāo)為:數(shù)據(jù)集上所有樣本點(diǎn)到其簇中心的距離之和的平方.肘部法則會畫出不同值的成本函數(shù).隨著值的增大,每類包含的樣本數(shù)會減少,于是樣本離其重心會更近,平均畸變程度會更小.而分支系數(shù)α的引入是為了引導(dǎo)算法達(dá)到最大閾值時(shí)跳出循環(huán),避免冗余計(jì)算和陷入死循環(huán).閾值的確定也就是屬性樹的最大分支深度,基于最壞的打算,一般設(shè)置為屬性樹根結(jié)點(diǎn)中最大的屬性數(shù)量.K值和分支系數(shù)α的選取如表2所示.

    表2 參數(shù)設(shè)置

    本文采用粗糙集中兩種常用指標(biāo)評估尋找的約簡子集質(zhì)量,分別為近似分類質(zhì)量(Approximate Classified Quality, AQ)和近似分類精度(Approximate Classified Precision, AP),并通過運(yùn)行時(shí)間和分類準(zhǔn)確率評估算法的加速性能和分類性能.

    定義6[41]給定決策表S=〈U,C∪D,V,f〉,決策屬性D對于U的劃分為U/D={Z1,Z2,…,Zm′},m′為劃分后的子集數(shù)量,則條件屬性集C關(guān)于決策屬性集D的近似分類精度為:

    定義7[41]給定決策表S=〈U,C∪D,V,f〉,條件屬性集C關(guān)于決策屬性集D的近似分類質(zhì)量為:

    如果約簡子集的AQ值和AP值與原決策系統(tǒng)相同,認(rèn)為該約簡子集與原決策系統(tǒng)具有相同的區(qū)分能力.

    3.3 實(shí)驗(yàn)結(jié)果

    3.3.1 計(jì)算時(shí)間對比

    為了驗(yàn)證IARAT在運(yùn)行時(shí)間和分類精度上的高效性和有效性,在表1所示的前5個(gè)不同的小型數(shù)據(jù)集上對比算法的計(jì)算時(shí)間.實(shí)驗(yàn)中選取的對比算法分別為IARC(An Incremental Algorithm for Redu-ct Computation Based on Knowledge Granularity)[31]、GIARC(A Group Incremental Algorithm for Reduct Computation)[33]、文獻(xiàn)[34]算法(Bucket and Attri-bute Group for Obtaining Reduct)、IARM(Incremen-

    tal Attribute Reduction Algorithm)[42]和文獻(xiàn)[43]算法.各算法在5個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間對比如圖5所示.由圖可見,隨著動態(tài)數(shù)據(jù)集的增加,各算法的運(yùn)行時(shí)間都在增加,而IARAT的運(yùn)行時(shí)間在各數(shù)據(jù)集上增幅均最小,在一定范圍內(nèi)隨著增量數(shù)據(jù)占比的增大,IARAT的運(yùn)行時(shí)間也在可控范圍內(nèi)平穩(wěn)增加.這表明IARAT可有效提高屬性約簡的計(jì)算效率,減少運(yùn)行時(shí)間.

    (a)Qsar

    3.3.2 有效性對比

    為了進(jìn)一步驗(yàn)證IARAT的有效性,說明其可在不損失分類性能的情況下有效提高搜索速度并找到可行的屬性約簡,進(jìn)行如下對比實(shí)驗(yàn).

    本文設(shè)置數(shù)據(jù)集上50%的樣本為增量數(shù)據(jù),并且通過CART(Classification and Regression Tree)和10倍交叉驗(yàn)證的方式計(jì)算分類準(zhǔn)確率.將樣本劃分為10個(gè)不相交的樣本組,在第一輪中設(shè)置第一組為測試集,剩下的樣本為訓(xùn)練集,第二輪中設(shè)置第二組為測試集,以此類推.這里的分類準(zhǔn)確率表現(xiàn)為:在多種約簡算法分別進(jìn)行屬性約簡之后,每種算法保留下來的核心屬性集各不相同,此時(shí)CART利用不同的核心屬性集對樣本進(jìn)行分類以計(jì)算分類準(zhǔn)確率.

    分類準(zhǔn)確率由CART預(yù)測正確的樣本數(shù)量在全部樣本中的占比決定,計(jì)算公式如下:

    其中,NCS表示算法預(yù)測正確樣本的數(shù)量,NAS表示所有預(yù)測樣本的總數(shù).

    為了更直觀地展示實(shí)驗(yàn)結(jié)果,計(jì)算加速比:

    其中,Tmax表示運(yùn)行時(shí)間最長的算法耗時(shí),TA表示算法耗時(shí).加速比越高,運(yùn)行時(shí)間越少,效率越高.

    各算法在5個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率和加速比如表3和表4所示.由表可看出,在大多數(shù)情況下,IARAT分類準(zhǔn)確率未下降,并且略高于其它算法.由于數(shù)據(jù)集的差異,IARAT的分類準(zhǔn)確率在個(gè)別情況下略有下降,但在可接受的范圍內(nèi),這表明該算法可在不犧牲分類準(zhǔn)確率的情況下有效減少耗時(shí).由此得到如下結(jié)論:IARAT是有效且高效的.

    表3 各算法在5個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率對比

    表4 各算法在5個(gè)數(shù)據(jù)集上的加速比對比

    3.3.3 加速性能對比

    為了更直觀地展現(xiàn)PIARAT在并行屬性約簡方面的加速效果,選取含有百萬數(shù)據(jù)樣本量的Pokerhand、KDD Cup、HIGGS這3個(gè)較大型數(shù)據(jù)集進(jìn)行對比實(shí)驗(yàn).

    IARAT和PIARAT的加速性能對比如表5所示,表中“-”表示IARAT無法運(yùn)行或運(yùn)行時(shí)間太長.由表可看出,相比IARAT,PIARAT在處理大規(guī)模數(shù)據(jù)集時(shí)總體運(yùn)行時(shí)間大幅縮短,對于IARAT無法運(yùn)行的數(shù)據(jù)集也可在可控的時(shí)間內(nèi)計(jì)算出約簡結(jié)果,這表明PIARAT具有良好的加速能力.在向決策系統(tǒng)中添加一些對象時(shí),IARAT和PIARAT劃分屬性子集的AP值和AQ值非常接近或相同,表現(xiàn)為1或0.99.這說明,經(jīng)過Spark并行機(jī)制加速后的增量算法生成的約簡與原算法生成的約簡具有幾乎相同的分辨能力,即算法3找到的約簡是可行的.

    表5 IARAT和PIARAT加速性能對比

    3.4 討論與分析

    本文在8組UCI數(shù)據(jù)集上進(jìn)行運(yùn)行時(shí)間、分類性能及加速性能的對比實(shí)驗(yàn).

    由圖5可看出,IARAT的運(yùn)行時(shí)間在不同數(shù)據(jù)集上均小于對比算法,而且在一定范圍內(nèi)隨著增量數(shù)據(jù)規(guī)模的增大,運(yùn)行時(shí)間也在可控范圍內(nèi)平穩(wěn)增加.例如,在Qsar數(shù)據(jù)集上,IARAT和GIRAC在增量數(shù)據(jù)不斷增大的過程中運(yùn)行時(shí)間始終保持平穩(wěn),而IARC和IARM在后半段運(yùn)行時(shí)間漲幅均存在明顯變大趨勢.而在樣本數(shù)最大的Letter數(shù)據(jù)集上,IARAT的計(jì)算優(yōu)勢更明顯,這主要是因?yàn)樵趯傩詷涿枯喎种н^程中只需要評估少量的候選屬性(取決于屬性樹的數(shù)量),由于搜索空間的減小,可縮短相應(yīng)的運(yùn)行時(shí)間.同時(shí),使用核心屬性約簡算法替代傳統(tǒng)約簡算法,避免每輪循環(huán)中非常耗時(shí)的屬性重要性的計(jì)算過程,進(jìn)一步縮短運(yùn)行時(shí)間.

    由表3和表4可得出,IARAT在縮短運(yùn)行時(shí)間的同時(shí),也保持算法的分類質(zhì)量及分類精度.這樣的結(jié)果表明,IARAT通過構(gòu)建屬性樹并進(jìn)行分支的策略可在不犧牲分類準(zhǔn)確率的情況下有效減少屬性約簡的計(jì)算時(shí)間.然而如下問題值得考慮:1)在屬性聚類階段,選擇K-means,不同聚類算法的選取是否會影響分類精度;2)在IARAT中,對于不同的數(shù)據(jù)集,并未相應(yīng)調(diào)整屬性樹的數(shù)量,如何找到最優(yōu)的聚類中心數(shù)量以達(dá)到最低的耗時(shí).這些問題依然值得繼續(xù)研究.

    由表5可看出,相比IARAT,PIARAT在處理大規(guī)模數(shù)據(jù)集時(shí)的總體運(yùn)行時(shí)間大幅縮短,IARAT無法運(yùn)行或運(yùn)行時(shí)間太長的數(shù)據(jù)也可進(jìn)行有效約簡計(jì)算,因此,通過Spark并行計(jì)算機(jī)制可有效提高算法2的計(jì)算效率,減少運(yùn)行時(shí)間.這主要是因?yàn)镾park計(jì)算引擎可對屬性約簡算法進(jìn)行并行化,以分布式計(jì)算的機(jī)制替代傳統(tǒng)的串行機(jī)制,由此實(shí)現(xiàn)海量數(shù)據(jù)的并行約簡計(jì)算.但是,在并行處理方面,本文算法的多棵樹分支策略和多節(jié)點(diǎn)并行機(jī)制的深度契合值得進(jìn)一步優(yōu)化,對于不同的數(shù)據(jù)集(不同樣本數(shù)量、不同屬性數(shù)量),如何進(jìn)行數(shù)據(jù)集的最優(yōu)劃分和子集的最優(yōu)分配將是今后工作的重點(diǎn).

    4 結(jié) 束 語

    本文針對傳統(tǒng)屬性約簡算法在處理大規(guī)模數(shù)據(jù)集時(shí)時(shí)間復(fù)雜度較高、效率較低等問題,從屬性組概念入手,引入二叉樹機(jī)制尋找約簡,提出基于屬性樹的增量式屬性約簡算法(IARAT).同時(shí)根據(jù)評估結(jié)果的不同進(jìn)行不同子結(jié)點(diǎn)分支,在計(jì)算過程中加入分支系數(shù),提高屬性約簡的效率和精度.同時(shí)結(jié)合Spark并行技術(shù),利用Spark框架在經(jīng)典屬性約簡算法上的并行優(yōu)勢,提出基于屬性樹的并行化增量式動態(tài)屬性約簡算法(PIARAT).實(shí)驗(yàn)表明本文算法在處理大規(guī)模動態(tài)數(shù)據(jù)集時(shí)是有效且高效的.今后工作重點(diǎn)是面對屬性增加和屬性值變化的增量問題時(shí),如何更新屬性約簡,在屬性聚類階段選擇更好的聚類算法及尋找最優(yōu)聚類中心數(shù)量,進(jìn)一步降低時(shí)間損耗,并對本文算法的多棵樹分支策略和多節(jié)點(diǎn)并行機(jī)制的深度契合進(jìn)行進(jìn)一步優(yōu)化.

    猜你喜歡
    決策表約簡子集
    由一道有關(guān)集合的子集個(gè)數(shù)題引發(fā)的思考
    基于決策表相容度和屬性重要度的連續(xù)屬性離散化算法*
    拓?fù)淇臻g中緊致子集的性質(zhì)研究
    關(guān)于奇數(shù)階二元子集的分離序列
    基于二進(jìn)制鏈表的粗糙集屬性約簡
    實(shí)值多變量維數(shù)約簡:綜述
    基于模糊貼近度的屬性約簡
    正反轉(zhuǎn)電機(jī)缺相保護(hù)功能的實(shí)現(xiàn)及決策表分析測試
    每一次愛情都只是愛情的子集
    都市麗人(2015年4期)2015-03-20 13:33:22
    一種改進(jìn)的分布約簡與最大分布約簡求法
    河南科技(2014年7期)2014-02-27 14:11:29
    精品一区二区三区四区五区乱码| 桃红色精品国产亚洲av| 国产精品久久久久久精品古装| 久久久国产精品麻豆| 午夜老司机福利片| 欧美国产精品va在线观看不卡| 久久久国产精品麻豆| 一本大道久久a久久精品| 欧美日韩福利视频一区二区| 天天躁夜夜躁狠狠躁躁| 亚洲色图 男人天堂 中文字幕| 久久久久久人人人人人| av福利片在线| 国产精品久久久av美女十八| 人人澡人人妻人| 91成年电影在线观看| 我要看黄色一级片免费的| 欧美成狂野欧美在线观看| 好男人电影高清在线观看| 欧美日韩视频精品一区| 欧美老熟妇乱子伦牲交| 美国免费a级毛片| 亚洲一卡2卡3卡4卡5卡精品中文| 午夜两性在线视频| 免费人妻精品一区二区三区视频| 老熟妇仑乱视频hdxx| 国产日韩一区二区三区精品不卡| 老司机影院毛片| 国产欧美日韩一区二区三区在线| 高潮久久久久久久久久久不卡| 香蕉国产在线看| 男人添女人高潮全过程视频| 一边摸一边抽搐一进一出视频| 黄色片一级片一级黄色片| 亚洲第一青青草原| 国产1区2区3区精品| 嫁个100分男人电影在线观看| 国产日韩欧美亚洲二区| 亚洲精品国产色婷婷电影| 精品国产一区二区久久| 久久影院123| 精品第一国产精品| 国产又色又爽无遮挡免| 下体分泌物呈黄色| 男女免费视频国产| 在线观看免费高清a一片| 777米奇影视久久| 亚洲av欧美aⅴ国产| 亚洲第一av免费看| 国产成+人综合+亚洲专区| 欧美国产精品一级二级三级| 久9热在线精品视频| 精品久久久久久久毛片微露脸 | 欧美精品高潮呻吟av久久| 美女国产高潮福利片在线看| 国产男女内射视频| 超色免费av| a级片在线免费高清观看视频| 丝袜脚勾引网站| 法律面前人人平等表现在哪些方面 | 少妇粗大呻吟视频| 久久综合国产亚洲精品| 国产亚洲欧美在线一区二区| 成人国产一区最新在线观看| 熟女少妇亚洲综合色aaa.| videosex国产| 999久久久精品免费观看国产| 午夜免费鲁丝| 亚洲免费av在线视频| 1024香蕉在线观看| 国产亚洲午夜精品一区二区久久| 高清视频免费观看一区二区| 国产又爽黄色视频| 丝瓜视频免费看黄片| 黄色视频在线播放观看不卡| 亚洲精品一卡2卡三卡4卡5卡 | 亚洲成人国产一区在线观看| 欧美激情极品国产一区二区三区| 欧美日本中文国产一区发布| 久久中文字幕一级| 亚洲欧美一区二区三区黑人| 午夜福利免费观看在线| 成人免费观看视频高清| 欧美激情高清一区二区三区| 国产精品久久久久久人妻精品电影 | 国产日韩欧美在线精品| 男人添女人高潮全过程视频| 欧美老熟妇乱子伦牲交| 女性生殖器流出的白浆| 欧美日韩亚洲综合一区二区三区_| 久久精品国产亚洲av高清一级| 亚洲精华国产精华精| 香蕉国产在线看| av片东京热男人的天堂| 国产成人欧美在线观看 | 男女床上黄色一级片免费看| 国产一区二区激情短视频 | 啦啦啦在线免费观看视频4| 色播在线永久视频| 免费日韩欧美在线观看| 侵犯人妻中文字幕一二三四区| 亚洲精品在线美女| 国产欧美日韩一区二区三区在线| 国产深夜福利视频在线观看| 久久毛片免费看一区二区三区| 亚洲人成77777在线视频| 交换朋友夫妻互换小说| 久9热在线精品视频| 日韩一卡2卡3卡4卡2021年| 大片电影免费在线观看免费| 伦理电影免费视频| 亚洲欧美日韩高清在线视频 | 在线十欧美十亚洲十日本专区| 一边摸一边做爽爽视频免费| 嫩草影视91久久| 国产又爽黄色视频| 日本黄色日本黄色录像| 亚洲人成77777在线视频| 十八禁人妻一区二区| 成人国产av品久久久| 免费高清在线观看日韩| 人人妻人人澡人人爽人人夜夜| 免费观看av网站的网址| 国产精品偷伦视频观看了| 麻豆国产av国片精品| 三级毛片av免费| 成年女人毛片免费观看观看9 | 色婷婷久久久亚洲欧美| 欧美精品啪啪一区二区三区 | 少妇 在线观看| 一边摸一边做爽爽视频免费| 三上悠亚av全集在线观看| 十八禁高潮呻吟视频| 啦啦啦免费观看视频1| 亚洲视频免费观看视频| www.av在线官网国产| 欧美精品人与动牲交sv欧美| 欧美亚洲 丝袜 人妻 在线| 国产国语露脸激情在线看| 国产亚洲欧美精品永久| 看免费av毛片| 一区二区三区四区激情视频| 亚洲av成人一区二区三| www日本在线高清视频| 黑人巨大精品欧美一区二区mp4| 黄色 视频免费看| 99国产极品粉嫩在线观看| 80岁老熟妇乱子伦牲交| 国产精品自产拍在线观看55亚洲 | 国产成人av激情在线播放| 久久久久网色| 热re99久久精品国产66热6| 欧美97在线视频| 一二三四社区在线视频社区8| 成在线人永久免费视频| 嫁个100分男人电影在线观看| 天堂中文最新版在线下载| 十八禁人妻一区二区| 欧美黄色淫秽网站| 丁香六月欧美| 亚洲久久久国产精品| 国产熟女午夜一区二区三区| 亚洲国产欧美在线一区| 天堂8中文在线网| 国产精品99久久99久久久不卡| 91成人精品电影| 午夜福利乱码中文字幕| 国产伦人伦偷精品视频| 在线观看免费午夜福利视频| 亚洲欧洲精品一区二区精品久久久| 咕卡用的链子| 另类精品久久| 日韩欧美一区视频在线观看| 精品久久久久久久毛片微露脸 | 热99re8久久精品国产| 久久人人爽av亚洲精品天堂| 九色亚洲精品在线播放| 日本91视频免费播放| 久久精品aⅴ一区二区三区四区| 国产一区二区三区在线臀色熟女 | 69精品国产乱码久久久| 国产成人av激情在线播放| 五月天丁香电影| 男女午夜视频在线观看| 成年美女黄网站色视频大全免费| 狂野欧美激情性xxxx| 99九九在线精品视频| 亚洲三区欧美一区| 啦啦啦免费观看视频1| 国内毛片毛片毛片毛片毛片| 女警被强在线播放| 中文字幕av电影在线播放| 啦啦啦啦在线视频资源| a级片在线免费高清观看视频| 永久免费av网站大全| 亚洲国产av新网站| 91精品国产国语对白视频| 男人爽女人下面视频在线观看| 极品少妇高潮喷水抽搐| 亚洲精品美女久久久久99蜜臀| 亚洲精品中文字幕一二三四区 | 日本av免费视频播放| 国产区一区二久久| 精品久久久精品久久久| 新久久久久国产一级毛片| 成年人免费黄色播放视频| 如日韩欧美国产精品一区二区三区| 中文字幕最新亚洲高清| 在线十欧美十亚洲十日本专区| 纯流量卡能插随身wifi吗| 国产欧美亚洲国产| 亚洲美女黄色视频免费看| 欧美大码av| 日韩中文字幕欧美一区二区| 日本精品一区二区三区蜜桃| 青草久久国产| av一本久久久久| 亚洲自偷自拍图片 自拍| 国产xxxxx性猛交| 男女下面插进去视频免费观看| 色综合欧美亚洲国产小说| 国产精品熟女久久久久浪| 国产亚洲av片在线观看秒播厂| 午夜福利一区二区在线看| 日韩人妻精品一区2区三区| 欧美少妇被猛烈插入视频| 亚洲国产精品成人久久小说| 国产主播在线观看一区二区| 欧美在线一区亚洲| 婷婷丁香在线五月| 美女国产高潮福利片在线看| 精品国产一区二区三区四区第35| 男女免费视频国产| 久久久久国产一级毛片高清牌| 亚洲av成人一区二区三| 波多野结衣av一区二区av| 国产精品av久久久久免费| 精品熟女少妇八av免费久了| 9色porny在线观看| 亚洲欧美精品综合一区二区三区| 精品视频人人做人人爽| 久久人妻熟女aⅴ| 午夜激情久久久久久久| 99国产精品一区二区三区| av在线老鸭窝| 51午夜福利影视在线观看| 最新在线观看一区二区三区| 欧美人与性动交α欧美软件| 亚洲成人免费av在线播放| 国产欧美日韩精品亚洲av| 成人手机av| 两个人看的免费小视频| 在线观看www视频免费| 国产欧美日韩一区二区三 | 亚洲精品国产色婷婷电影| 色婷婷久久久亚洲欧美| 国产日韩欧美在线精品| 狠狠狠狠99中文字幕| 男人操女人黄网站| √禁漫天堂资源中文www| 欧美日韩av久久| 国产精品香港三级国产av潘金莲| 亚洲av国产av综合av卡| 国产高清videossex| 手机成人av网站| 国产91精品成人一区二区三区 | 91国产中文字幕| 国产av精品麻豆| 日韩一卡2卡3卡4卡2021年| 国产成+人综合+亚洲专区| tube8黄色片| 亚洲国产欧美一区二区综合| 黄色a级毛片大全视频| 日韩制服丝袜自拍偷拍| 中文字幕人妻丝袜制服| 婷婷丁香在线五月| 亚洲成人免费电影在线观看| 午夜福利免费观看在线| 各种免费的搞黄视频| 午夜激情av网站| 日韩,欧美,国产一区二区三区| 国产极品粉嫩免费观看在线| 99九九在线精品视频| 日韩精品免费视频一区二区三区| 又大又爽又粗| 热re99久久国产66热| 亚洲国产看品久久| 午夜福利在线观看吧| 大码成人一级视频| 色老头精品视频在线观看| 美女高潮喷水抽搐中文字幕| 视频区图区小说| 亚洲精品国产av成人精品| 美女中出高潮动态图| 免费人妻精品一区二区三区视频| 91精品国产国语对白视频| 国产日韩欧美在线精品| 母亲3免费完整高清在线观看| 9色porny在线观看| 亚洲精品一区蜜桃| 成年美女黄网站色视频大全免费| 多毛熟女@视频| 日韩中文字幕欧美一区二区| 在线天堂中文资源库| 91麻豆av在线| 建设人人有责人人尽责人人享有的| 亚洲久久久国产精品| 一区二区av电影网| 99九九在线精品视频| 国产主播在线观看一区二区| 亚洲熟女精品中文字幕| 欧美日韩国产mv在线观看视频| 欧美黑人精品巨大| 久久精品亚洲av国产电影网| 一区二区三区四区激情视频| 国产野战对白在线观看| 一级片免费观看大全| av天堂久久9| 婷婷色av中文字幕| 久久久国产精品麻豆| 亚洲国产欧美在线一区| 午夜两性在线视频| 日韩熟女老妇一区二区性免费视频| 一级片'在线观看视频| 国产精品久久久久久精品古装| 免费高清在线观看日韩| 熟女少妇亚洲综合色aaa.| 飞空精品影院首页| 久久人妻熟女aⅴ| 国产日韩一区二区三区精品不卡| 日本五十路高清| 久久精品成人免费网站| 热re99久久国产66热| avwww免费| 日韩制服骚丝袜av| 欧美精品亚洲一区二区| 国产在线免费精品| 国产精品亚洲av一区麻豆| 亚洲成人免费电影在线观看| 中文字幕人妻丝袜制服| 久久人人爽av亚洲精品天堂| 无遮挡黄片免费观看| 久久性视频一级片| 我要看黄色一级片免费的| 亚洲av美国av| 两人在一起打扑克的视频| 亚洲精品在线美女| 亚洲欧美一区二区三区黑人| 50天的宝宝边吃奶边哭怎么回事| 女人高潮潮喷娇喘18禁视频| 久久精品亚洲av国产电影网| 无限看片的www在线观看| 考比视频在线观看| 日韩一卡2卡3卡4卡2021年| 性色av一级| 中文字幕人妻丝袜制服| 国产成人av激情在线播放| 日韩 欧美 亚洲 中文字幕| 女警被强在线播放| 九色亚洲精品在线播放| 黑丝袜美女国产一区| 亚洲欧洲精品一区二区精品久久久| 老熟女久久久| 高清黄色对白视频在线免费看| 午夜免费鲁丝| 久久狼人影院| 男人操女人黄网站| 女性被躁到高潮视频| 日韩三级视频一区二区三区| 久久久久久亚洲精品国产蜜桃av| 亚洲中文字幕日韩| 午夜福利在线免费观看网站| 黑人猛操日本美女一级片| 日本五十路高清| 黄片大片在线免费观看| 亚洲精品国产av成人精品| 十八禁网站网址无遮挡| 两人在一起打扑克的视频| 动漫黄色视频在线观看| 国产伦人伦偷精品视频| 日韩大片免费观看网站| 日韩中文字幕欧美一区二区| 中文字幕另类日韩欧美亚洲嫩草| 成人影院久久| 97在线人人人人妻| 1024视频免费在线观看| 国产99久久九九免费精品| 欧美97在线视频| 亚洲一卡2卡3卡4卡5卡精品中文| 不卡av一区二区三区| 亚洲精品美女久久av网站| 自拍欧美九色日韩亚洲蝌蚪91| 黑人巨大精品欧美一区二区蜜桃| 亚洲av国产av综合av卡| 女人爽到高潮嗷嗷叫在线视频| 91精品三级在线观看| 高清在线国产一区| 亚洲少妇的诱惑av| 亚洲av国产av综合av卡| 国产精品久久久久成人av| 午夜免费观看性视频| 久久这里只有精品19| 久久国产精品影院| 国产免费现黄频在线看| 国产精品一区二区在线不卡| 国产精品久久久av美女十八| 国产色视频综合| 下体分泌物呈黄色| 亚洲性夜色夜夜综合| 免费一级毛片在线播放高清视频 | 国产精品免费视频内射| 精品国产乱码久久久久久男人| 精品少妇久久久久久888优播| 欧美黑人精品巨大| 免费不卡黄色视频| 热re99久久精品国产66热6| 大型av网站在线播放| 中文字幕人妻熟女乱码| 99九九在线精品视频| 国产亚洲欧美在线一区二区| 国产高清国产精品国产三级| 国产日韩欧美在线精品| bbb黄色大片| 曰老女人黄片| 日韩欧美免费精品| xxxhd国产人妻xxx| 久久天堂一区二区三区四区| 国产区一区二久久| 女人被躁到高潮嗷嗷叫费观| 一级片免费观看大全| 国产精品av久久久久免费| 中文欧美无线码| 男人爽女人下面视频在线观看| 俄罗斯特黄特色一大片| 久久青草综合色| 亚洲国产精品999| √禁漫天堂资源中文www| av线在线观看网站| 国产成人影院久久av| 老司机亚洲免费影院| 精品国产乱码久久久久久男人| 亚洲av成人一区二区三| 在线精品无人区一区二区三| 欧美另类一区| 国产淫语在线视频| 成人国语在线视频| 999久久久国产精品视频| 成人手机av| 777久久人妻少妇嫩草av网站| 亚洲欧美一区二区三区黑人| 亚洲av成人一区二区三| 19禁男女啪啪无遮挡网站| 亚洲欧洲精品一区二区精品久久久| 国产一区有黄有色的免费视频| 菩萨蛮人人尽说江南好唐韦庄| 999精品在线视频| 中文欧美无线码| 水蜜桃什么品种好| 国产亚洲精品久久久久5区| 9191精品国产免费久久| 亚洲中文av在线| av在线播放精品| 国产欧美日韩一区二区三 | 五月天丁香电影| 午夜福利在线免费观看网站| 日日爽夜夜爽网站| 国产不卡av网站在线观看| 日本猛色少妇xxxxx猛交久久| 一个人免费看片子| 性少妇av在线| 在线亚洲精品国产二区图片欧美| tocl精华| 妹子高潮喷水视频| 欧美亚洲 丝袜 人妻 在线| 秋霞在线观看毛片| 亚洲精品日韩在线中文字幕| 一二三四在线观看免费中文在| 国产免费福利视频在线观看| 免费日韩欧美在线观看| 国产伦人伦偷精品视频| av不卡在线播放| 精品国产一区二区三区久久久樱花| 午夜福利视频精品| 久久久水蜜桃国产精品网| 50天的宝宝边吃奶边哭怎么回事| 另类亚洲欧美激情| 国产激情久久老熟女| 国产xxxxx性猛交| 成人国产av品久久久| 丝袜在线中文字幕| 制服诱惑二区| 飞空精品影院首页| 久久香蕉激情| 18禁观看日本| 一区二区av电影网| 黑人巨大精品欧美一区二区蜜桃| 精品熟女少妇八av免费久了| 女人被躁到高潮嗷嗷叫费观| 别揉我奶头~嗯~啊~动态视频 | av福利片在线| 女人被躁到高潮嗷嗷叫费观| 欧美人与性动交α欧美精品济南到| 亚洲精品中文字幕在线视频| 亚洲美女黄色视频免费看| 欧美亚洲日本最大视频资源| 欧美日韩视频精品一区| 欧美日韩亚洲高清精品| 国产亚洲精品久久久久5区| 老司机亚洲免费影院| 性色av乱码一区二区三区2| 色婷婷久久久亚洲欧美| 亚洲黑人精品在线| 美国免费a级毛片| 日本a在线网址| 丝袜脚勾引网站| 色精品久久人妻99蜜桃| 热99国产精品久久久久久7| 最近中文字幕2019免费版| 9191精品国产免费久久| 天天添夜夜摸| 亚洲欧美清纯卡通| 99精国产麻豆久久婷婷| 人妻人人澡人人爽人人| 欧美xxⅹ黑人| a 毛片基地| 最新的欧美精品一区二区| 免费在线观看影片大全网站| 99热国产这里只有精品6| 日韩欧美国产一区二区入口| 国产国语露脸激情在线看| 国产一级毛片在线| 欧美亚洲 丝袜 人妻 在线| 激情视频va一区二区三区| 美女主播在线视频| 天天躁夜夜躁狠狠躁躁| 国产精品秋霞免费鲁丝片| 自线自在国产av| 两人在一起打扑克的视频| 欧美精品高潮呻吟av久久| 国产亚洲欧美精品永久| 精品视频人人做人人爽| 日本猛色少妇xxxxx猛交久久| 日韩欧美一区视频在线观看| 亚洲精品国产色婷婷电影| 国产av一区二区精品久久| 久久午夜综合久久蜜桃| 深夜精品福利| 久久久久久久精品精品| videosex国产| 色播在线永久视频| 最近中文字幕2019免费版| 久久精品亚洲熟妇少妇任你| 欧美在线一区亚洲| 亚洲精品第二区| 制服诱惑二区| 亚洲专区中文字幕在线| 国产一区二区在线观看av| 新久久久久国产一级毛片| 久久久久视频综合| 国产精品香港三级国产av潘金莲| 欧美国产精品一级二级三级| 亚洲av美国av| 国产免费视频播放在线视频| 亚洲九九香蕉| 老司机在亚洲福利影院| 中亚洲国语对白在线视频| 欧美成人午夜精品| 麻豆国产av国片精品| 人人妻,人人澡人人爽秒播| 欧美黄色片欧美黄色片| av在线播放精品| 黑丝袜美女国产一区| 色婷婷久久久亚洲欧美| 久久免费观看电影| 丝袜在线中文字幕| 日本wwww免费看| 丝袜喷水一区| 国产激情久久老熟女| 黄片小视频在线播放| 91麻豆av在线| 久久天堂一区二区三区四区| 成人影院久久| 美女高潮到喷水免费观看| 国产成+人综合+亚洲专区| 男女边摸边吃奶| 精品国产超薄肉色丝袜足j| 午夜老司机福利片| 国产成人系列免费观看| 久久ye,这里只有精品| 美女高潮到喷水免费观看| 国产成+人综合+亚洲专区| 精品福利永久在线观看| 性色av一级| 精品国产一区二区久久| 999精品在线视频| 日本vs欧美在线观看视频| 午夜福利乱码中文字幕| 中国国产av一级| 91成年电影在线观看| 不卡av一区二区三区| 国产黄色免费在线视频| 亚洲国产欧美日韩在线播放| 99热网站在线观看| 国产av一区二区精品久久| 啦啦啦中文免费视频观看日本| 久久国产精品大桥未久av| 曰老女人黄片| 后天国语完整版免费观看| 成人av一区二区三区在线看 | 好男人电影高清在线观看| 一本色道久久久久久精品综合| 久久久欧美国产精品| 一级毛片精品| 国产福利在线免费观看视频| 欧美成人午夜精品|