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

    基于維度分組降維的高維數(shù)據(jù)近似k近鄰查詢

    2021-04-01 03:40:08胡晏銘郝曉紅張麗平郝忠孝
    關(guān)鍵詞:項(xiàng)集降維序號(hào)

    李 松 胡晏銘 郝曉紅 張麗平 郝忠孝

    (哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150080)

    (lisongbeifen@163.com)

    隨著計(jì)算機(jī)技術(shù)以及傳感器技術(shù)的不斷發(fā)展,基于位置的服務(wù)得到了廣泛的應(yīng)用,其中最近鄰查詢作為基于位置服務(wù)中重要的支持性技術(shù)之一,在許多領(lǐng)域都有廣泛的應(yīng)用.目前國(guó)內(nèi)外學(xué)者針對(duì)最近鄰查詢問題進(jìn)行了廣泛研究,為了更好地解決現(xiàn)實(shí)問題,學(xué)者們提出了一系列的變形,例如概率最近鄰查詢[1]、反向最近鄰查詢[2]、連續(xù)最近鄰查詢[3]、組最近鄰查詢[4]、強(qiáng)鄰近對(duì)查詢[5]、k近鄰(knearest neighbor,kNN)查詢[6-7]、反向k近鄰查詢[8]等,其中k近鄰查詢問題一直吸引學(xué)者們的目光.

    kNN查詢問題作為最近鄰查詢問題的擴(kuò)展形式,在現(xiàn)實(shí)生活中具有廣泛的應(yīng)用.例如送餐員在接單時(shí)會(huì)選擇距離他最近的k個(gè)訂單;外出旅行時(shí)游客通過手機(jī)地圖查找最近的k個(gè)酒店;新聞網(wǎng)站通過分析與某用戶最相似的k個(gè)用戶的瀏覽歷史為該客戶進(jìn)行新聞推薦等.kNN查詢技術(shù)除了被應(yīng)用在現(xiàn)實(shí)生活中,也被廣泛應(yīng)用到了科研等領(lǐng)域,然而與多數(shù)現(xiàn)實(shí)生活中處理的低維數(shù)據(jù)相反,科研領(lǐng)域要處理的數(shù)據(jù)多為高維數(shù)據(jù).例如天文學(xué)中,在宇宙環(huán)境中查找與地球最相似的k個(gè)星球,不僅要考慮大小、溫度,還需要考慮自轉(zhuǎn)速度、大氣組成成分等眾多維度數(shù)據(jù);在計(jì)算機(jī)的模式識(shí)別領(lǐng)域?qū)D像進(jìn)行基于kNN分類時(shí),需要處理的圖像數(shù)據(jù)的維度可高達(dá)成千上萬(wàn)維.由于數(shù)據(jù)維度的增長(zhǎng),低維空間中的kNN查詢算法的效率隨之下降,甚至不如線性掃描,因此學(xué)者們提出了近似k近鄰(approximateknearest neighbor, AkNN)查詢,通過損失一定的精度來提升查詢效率,并給出一系列算法.

    雖然現(xiàn)有的方法能夠解決AkNN查詢問題,但是在進(jìn)行查詢的過程中大多不考慮數(shù)據(jù)維度間的關(guān)聯(lián)關(guān)系,對(duì)數(shù)據(jù)的所有維度進(jìn)行統(tǒng)一的分析計(jì)算,影響了查詢的準(zhǔn)確率和效率.以基于局部敏感哈希(locality sensitive hashing, LSH)的算法為例,應(yīng)用m個(gè)Hash函數(shù)對(duì)大小為n的d維數(shù)據(jù)集進(jìn)行索引時(shí),計(jì)算數(shù)據(jù)集的索引值的時(shí)間復(fù)雜度為O(dnm),可以看出其時(shí)間復(fù)雜度與維度成正相關(guān).因此,為了提高查詢的效率,本文提出了一種基于維度間的關(guān)聯(lián)關(guān)系進(jìn)行維度分組并降維的AkNN查詢的算法.

    本文主要貢獻(xiàn)有3個(gè)方面:

    1) 針對(duì)已有的高維數(shù)據(jù)近似k近鄰查詢算法不考慮數(shù)據(jù)維度值分布情況,面對(duì)0值維度個(gè)數(shù)遠(yuǎn)大于非0值維度個(gè)數(shù)的數(shù)據(jù)空間、查詢效率降低、運(yùn)算性能浪費(fèi)等問題,提出了一種基于維度間關(guān)聯(lián)規(guī)則進(jìn)行分組降維的思想,并設(shè)計(jì)了基于LSH的維度分組降維算法,降低了維度值分布對(duì)查詢的影響,提高了運(yùn)算性能.

    2) 針對(duì)基于維度間關(guān)聯(lián)規(guī)則的維度分組降維過程中維度間關(guān)聯(lián)規(guī)則挖掘效率低、挖掘關(guān)聯(lián)的頻繁維度耗時(shí)高的問題,本文基于單向頻繁模式樹提出了一個(gè)新的頻繁項(xiàng)集挖掘算法,通過該算法能快速挖掘出頻繁維度,實(shí)現(xiàn)維度間的關(guān)聯(lián)規(guī)則高效挖掘,為高維數(shù)據(jù)的維度分組降維提供支持.

    3) 針對(duì)傳統(tǒng)的LSH編碼方式查詢高維數(shù)據(jù)近似k近鄰存在漢明距離準(zhǔn)確率低、Hash函數(shù)內(nèi)存消耗大等問題,本文提出了基于信息熵對(duì)編碼函數(shù)進(jìn)行篩選和動(dòng)態(tài)權(quán)重賦值,并通過加權(quán)漢明距離返回結(jié)果集的高維數(shù)據(jù)近似k近鄰查詢算法,提高了查詢性能和效率.

    1 相關(guān)工作

    在低維空間下,針對(duì)kNN查詢問題,研究者們提出一系列的查詢方法.文獻(xiàn)[9]針對(duì)大數(shù)據(jù)下查找k近鄰效率低的問題,提出了一種基于最優(yōu)三角不等式檢測(cè)策略的精確k近鄰快速搜索方法.在低維障礙空間中,文獻(xiàn)[10]基于Voronoi圖提出了解決障礙空間組反k近鄰查詢算法OGRkNN,利用Voronoi圖的特性,過濾掉大量的非候選數(shù)據(jù),有效地解決了靜態(tài)障礙物環(huán)境和動(dòng)態(tài)障礙物環(huán)境下的組反k近鄰問題.針對(duì)障礙空間下連續(xù)反向k近鄰查詢問題,文獻(xiàn)[11]根據(jù)數(shù)據(jù)點(diǎn)到查詢區(qū)間的最大距離和數(shù)據(jù)點(diǎn)到障礙物的最小外包矩形的最小距離的關(guān)系對(duì)障礙物進(jìn)行剪枝,同時(shí)應(yīng)用R-tree對(duì)保留的障礙物進(jìn)行索引,最后進(jìn)行精煉和數(shù)據(jù)更新,得到最終結(jié)果.在低維路網(wǎng)環(huán)境中,文獻(xiàn)[12]提出了一個(gè)平衡的搜索樹索引結(jié)構(gòu)G-tree,基于該索引結(jié)構(gòu)解決了路網(wǎng)環(huán)境下的k近鄰查詢問題.文獻(xiàn)[13]對(duì)時(shí)變路網(wǎng)環(huán)境下的k近鄰查詢問題進(jìn)行了研究,提出了基于Voronoi圖的二級(jí)索引樹結(jié)構(gòu)——V-tree,該文獻(xiàn)根據(jù)時(shí)間找出了邊界點(diǎn)作為Voronoi圖的邊,然后結(jié)合G-tree對(duì)Voronoi區(qū)進(jìn)行索引,通過遍歷樹結(jié)構(gòu)得到最終結(jié)果.

    以上研究主要是處理低維空間環(huán)境下的k近鄰查詢問題及其變種,但隨著維度的增長(zhǎng),算法查詢效率隨之下降.以R-tree索引結(jié)構(gòu)為例,當(dāng)數(shù)據(jù)維度大于20時(shí),查詢效率不如線性掃描,因此如何高效高質(zhì)量地解決高維空間近似k近鄰查詢問題是目前研究的重點(diǎn).

    文獻(xiàn)[14]為每個(gè)維度分配1個(gè)素?cái)?shù)作為底數(shù),每個(gè)維度上的值作為指數(shù)進(jìn)行計(jì)算,并通過取對(duì)數(shù)的方式避免維度增長(zhǎng)導(dǎo)致計(jì)算結(jié)果過大的缺陷,最終通過將計(jì)算結(jié)果求和的方式將高維數(shù)據(jù)降維到1維.針對(duì)高維大數(shù)據(jù)環(huán)境下絕大多數(shù)索引結(jié)構(gòu)規(guī)模較大、內(nèi)存不足以存儲(chǔ)的問題,文獻(xiàn)[15]基于Hilbert空間填充曲線和B+-tree設(shè)計(jì)了新的數(shù)據(jù)結(jié)構(gòu)RDB-tree(reference distance B+-tree),同時(shí)基于RDB-tree提出了HD-index(high dimensional-index),基于該索引能夠以較高的時(shí)空效率和準(zhǔn)確率進(jìn)行AkNN查詢,但是存在空間填充曲線的并行通信的控制較為復(fù)雜、實(shí)現(xiàn)難度大的問題.文獻(xiàn)[16]提出了基于RP-forests(random projection forests)進(jìn)行k近鄰查詢的算法,該算法不僅適用于低維空間,還適用于高維空間,但是RP-tree(random projection-tree)的分裂次數(shù)和劃分左右節(jié)點(diǎn)的閾值難以選擇,多個(gè)RP-tree也會(huì)占用大量的空間.針對(duì)動(dòng)態(tài)的大規(guī)模的二進(jìn)制數(shù)據(jù)集,文獻(xiàn)[17]提出了HWT(Hanmming weight trees)索引結(jié)構(gòu),該索引利用二進(jìn)制碼及其子串的漢明權(quán)值來劃分二進(jìn)制字符串的特征空間,進(jìn)而基于HWT進(jìn)行AkNN查詢.針對(duì)算法參數(shù)固定導(dǎo)致查詢的高延遲問題,文獻(xiàn)[18]通過建立和訓(xùn)練梯度增強(qiáng)決策樹模型來學(xué)習(xí)和預(yù)測(cè)何時(shí)停止查詢,使算法在保持高精確度的前提下降低延遲,但是針對(duì)不同的數(shù)據(jù)集需要重復(fù)學(xué)習(xí).文獻(xiàn)[19]提出了基于HNSW(hierarchical navigable small world)索引結(jié)構(gòu)的AkNN查詢算法,該算法完全基于圖,從而避免了近鄰圖的粗搜索階段所需的額外的搜索結(jié)構(gòu),同時(shí)使用啟發(fā)式來選擇近鄰圖的鄰居以使提高查詢性能.

    針對(duì)以上算法實(shí)現(xiàn)難度大和結(jié)構(gòu)復(fù)雜的問題,Piotr Indyk提出的LSH被廣泛應(yīng)用于高維空間下近似k近鄰查詢問題.針對(duì)原始LSH根據(jù)數(shù)據(jù)集直接劃分Hash桶導(dǎo)致查詢準(zhǔn)確率低的問題,文獻(xiàn)[20]采用基于查詢點(diǎn)的Hash值為基準(zhǔn)進(jìn)行桶的劃分的方法,減小了與查詢點(diǎn)相鄰的數(shù)據(jù)點(diǎn)被劃分到相鄰?fù)暗母怕剩岣吡瞬樵兘Y(jié)果的準(zhǔn)確率.文獻(xiàn)[21]結(jié)合了基于漢明距離檢索方法速度快的優(yōu)勢(shì)和基于查找表檢索方法的結(jié)果準(zhǔn)確的優(yōu)勢(shì),提出了KMH(kmeans hashing)算法,該算法不僅提高了查詢的準(zhǔn)確率,同時(shí)也提高了查詢速度.針對(duì)現(xiàn)有的通過機(jī)器學(xué)習(xí)的方式獲得Hash函數(shù)的算法的相似指標(biāo)過于粗糙的問題,文獻(xiàn)[22]提出了一種新的細(xì)粒度相似度指標(biāo)量化距離,提供了項(xiàng)之間相似度的更多信息,并提出基于該量化距離的查詢算法,查詢性能得到明顯提升.文獻(xiàn)[23]提出了沖突計(jì)數(shù)算法結(jié)構(gòu),應(yīng)用歐氏空間中常用的基于2-范數(shù)的局部敏感Hash函數(shù)進(jìn)行索引,算法能夠很好地處理大數(shù)據(jù)環(huán)境下的高維空間近似k近鄰查詢.針對(duì)IO性能瓶頸的問題,文獻(xiàn)[24]提出的O2LSH(optimal order LSH)算法將空間填充曲線作為復(fù)合Hash鍵值并建立線序排序,使鄰近候選點(diǎn)更多地分布在相同或相鄰的磁盤,進(jìn)而提高IO性能和準(zhǔn)確率,但是也面臨著填充曲線難以實(shí)現(xiàn)的問題.文獻(xiàn)[25]在索引階段將數(shù)據(jù)對(duì)象映射到多個(gè)2維投影空間,并在每個(gè)2維空間構(gòu)造一組B+-tree進(jìn)行索引,有效地降低了IO開銷.針對(duì)LSH無法為候選點(diǎn)提供準(zhǔn)確的距離估計(jì),導(dǎo)致在檢查不必要的點(diǎn)時(shí)產(chǎn)生額外的計(jì)算開銷從而降低了查詢處理性能的問題,文獻(xiàn)[26]提出的PMLSH(pivotiny M-tree LSH)查詢框架通過建立可調(diào)的置信區(qū)間實(shí)現(xiàn)精確的距離估計(jì),實(shí)現(xiàn)對(duì)候選集的縮減,降低了額外的計(jì)算開銷.

    目前現(xiàn)有的高維數(shù)據(jù)近似最近鄰查詢算法都是預(yù)先將原始數(shù)據(jù)集進(jìn)行處理,然后建立索引結(jié)構(gòu),根據(jù)索引進(jìn)行AkNN查詢.對(duì)原始高維數(shù)據(jù)的預(yù)處理過程中,大多不考慮維度間的關(guān)聯(lián)關(guān)系對(duì)查詢效率和準(zhǔn)確率的影響.因此,本文提出了基于維度間的關(guān)聯(lián)規(guī)則進(jìn)行維度分組的高維數(shù)據(jù)降維方法,應(yīng)用該方法對(duì)高維數(shù)據(jù)進(jìn)行預(yù)處理后,采用二進(jìn)制編碼的方式進(jìn)行查詢,同時(shí)基于信息熵篩選編碼函數(shù)、權(quán)重的動(dòng)態(tài)設(shè)定等方式優(yōu)化查詢方法.

    2 主要定義

    定義1.頻繁序列.設(shè)temp1

    在頻繁項(xiàng)集挖掘的過程中,通過UFP-tree[27]找出所有的頻繁序列就可得到所有的頻繁項(xiàng)集,本文中如不特殊聲明,頻繁項(xiàng)集和頻繁序列等價(jià).

    定義2.近似k近鄰.設(shè)d維數(shù)據(jù)集X={x1,x2,…,xm},其中xi∈Rd,X經(jīng)過降維和編碼后得到數(shù)據(jù)集X′,對(duì)于給定查詢點(diǎn)q∈Rd,經(jīng)過相同的降維方式和編碼后為q′,近似k近鄰查詢AkNN(q)返回1個(gè)數(shù)據(jù)集合P={p1,p2,…,pk},其中pi∈X′,數(shù)據(jù)集合P中的數(shù)據(jù)滿足的條件為

    定義3.局部敏感Hash函數(shù)[28].給定距離r和近似比率c,若一個(gè)Hash函數(shù)族H={h:Rd→Rd′}對(duì)給定的任意2個(gè)數(shù)據(jù)q,p滿足2個(gè)條件:

    1) 若dist(q,p)≤r,則Pr[h(q)=h(p)]≥P1;

    2) 若dist(q,p)≥cr,則Pr[h(q)=h(p)]≤P2;

    則稱H是(r,cr,P1,P2)-敏感的,其中c>1,P1>P2,P1和P2是概率.

    定義4.信息熵[29].信息熵是一種用于度量系統(tǒng)不確定性的度量方法,其香農(nóng)計(jì)算公式為

    (1)

    其中,E(x)表示的是隨機(jī)變量x的熵,x∈{a1,a2,…,an},p(ai)表示取值為ai的概率.

    3 高維數(shù)據(jù)近似k近鄰查詢

    在高維數(shù)據(jù)中,由于維度的激增,對(duì)查詢時(shí)效影響越來越大.本文通過算法1和算法2首先對(duì)數(shù)據(jù)維度之間的關(guān)聯(lián)規(guī)則進(jìn)行挖掘,并通過算法3對(duì)前件具有交集的強(qiáng)正相關(guān)的維度集進(jìn)行分組;進(jìn)一步根據(jù)每組的維度分配Hash函數(shù),算法4將數(shù)據(jù)維度按組進(jìn)行Hash降維;最后將降維后得到的數(shù)據(jù)應(yīng)用候選的局部敏感Hash函數(shù)進(jìn)行編碼,算法5根據(jù)編碼后的各Hash函數(shù)的熵值篩選得到編碼函數(shù)和數(shù)據(jù)的編碼結(jié)果.進(jìn)行查詢時(shí),將查詢點(diǎn)按相同的方式進(jìn)行維度分組降維,并用相同的編碼函數(shù)進(jìn)行編碼,然后根據(jù)編碼后的漢明距離返回候選集,計(jì)算候選集中各編碼位的熵值并根據(jù)熵值進(jìn)行動(dòng)態(tài)加權(quán),最終算法6返回加權(quán)漢明距離最小的k個(gè)數(shù)據(jù)作為結(jié)果.整個(gè)過程可以分為基于維度分組的Hash降維、基于Hash編碼的動(dòng)態(tài)加權(quán)近似k近鄰查詢2個(gè)部分.

    3.1 基于維度分組的Hash降維

    3.1.1 基于維度間關(guān)聯(lián)規(guī)則的維度分組

    本節(jié)基于UFP-tree提出了新的頻繁項(xiàng)集挖掘算法MFIA_UFP_tree和維度分組算法Group_PAR.算法MFIA_UFP_tree通過邏輯“與”運(yùn)算高效地挖掘出所有的頻繁項(xiàng)集.算法Group_PAR基于相關(guān)系數(shù)對(duì)得到的頻繁項(xiàng)集進(jìn)行正相關(guān)關(guān)聯(lián)規(guī)則(positive association rule, PAR)挖掘,進(jìn)一步根據(jù)不同關(guān)聯(lián)規(guī)則的前件是否有交集進(jìn)行維度的分組.為了支持算法MFIA_UFP_tree和提高頻繁項(xiàng)集挖掘效率,本節(jié)給出結(jié)構(gòu)體Struct_info定義.

    定義5.結(jié)構(gòu)體Struct_info.

    Struct_info{

    seq;*項(xiàng)轉(zhuǎn)換后的序號(hào)*

    count;*頻繁度計(jì)數(shù)*

    r_code;*包含序號(hào)seq的路徑編碼*

    },

    其中路徑編碼根據(jù)起始節(jié)點(diǎn)的位置來定,本文采用從0開始,從左到右依次加1的方式進(jìn)行編碼.

    在進(jìn)行基于支持度和置信度[30]的頻繁項(xiàng)集挖掘時(shí),首先對(duì)給定d維數(shù)據(jù)集Q={q|q∈Rd}進(jìn)行二值化,對(duì)應(yīng)維度有值的用“1”標(biāo)記,沒有值的用“0”標(biāo)記,得到二值化后的數(shù)據(jù)集Q′;然后掃描二值化后的數(shù)據(jù)集Q′,去除支持度小于給定閥值的維度,對(duì)剩余維度建立序號(hào)-項(xiàng)集轉(zhuǎn)換表,并構(gòu)建UFP-tree.針對(duì)頻繁項(xiàng)集挖掘過程中統(tǒng)計(jì)支持度和項(xiàng)集剪枝的資源消耗問題,本文根據(jù)結(jié)構(gòu)體的定義,進(jìn)一步給出結(jié)構(gòu)體數(shù)組的定義.

    定義6.結(jié)構(gòu)體數(shù)組S[].給定一個(gè)UFP-tree,設(shè)結(jié)構(gòu)體數(shù)組S[],當(dāng)且僅當(dāng)其滿足的條件為:

    1) 對(duì)于任意以序號(hào)i為起點(diǎn)、根節(jié)點(diǎn)為終點(diǎn)的路徑,其序號(hào)集為Seq={seq1,seq2,…,seql},其中l(wèi)為數(shù)組S[]的長(zhǎng)度;

    2)S[j].count的值為S[j].seq對(duì)應(yīng)的節(jié)點(diǎn)在從i到根節(jié)點(diǎn)的路徑上的頻繁度計(jì)數(shù)和;

    3)S[j].r_code的編碼位數(shù)為從i到根節(jié)點(diǎn)所有路徑的個(gè)數(shù);

    4)S[j].r_code的每位編碼上的值為S[j].seq對(duì)應(yīng)節(jié)點(diǎn)在該路徑上的頻繁度計(jì)數(shù);

    稱S[]為序號(hào)i對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組.

    為保證所有的頻繁序列都能根據(jù)序號(hào)對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組挖掘得到,本文根據(jù)結(jié)構(gòu)數(shù)組和UFP-tree給出定理1.

    定理1.給定UFP-tree,設(shè)序列FSeq={seq1,seq2,…,seqi},若FSeq是頻繁序列,則序列FSeq一定屬于序號(hào)seqi對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組S[].

    證明. 定理1可以通過反證法進(jìn)行證明.假設(shè)以序號(hào)seqi為結(jié)尾的頻繁序列FSeq不屬于seqi對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組S[],由UFP-tree的結(jié)構(gòu)可知,任意以seqi為結(jié)尾的頻繁序列一定屬于以序號(hào)seqi對(duì)應(yīng)的節(jié)點(diǎn)為起點(diǎn)、根節(jié)點(diǎn)為終點(diǎn)的1條或多條路徑,根據(jù)結(jié)構(gòu)體數(shù)組的定義可知,任意1條從序號(hào)seqi對(duì)應(yīng)的節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑都是序號(hào)seqi對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組的子集,所以序列FSeq也屬于序號(hào)seqi對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組,與假設(shè)矛盾.

    證畢.

    在進(jìn)行基于UFP-tree頻繁項(xiàng)集挖掘時(shí),根據(jù)結(jié)構(gòu)體數(shù)組S[]來進(jìn)行以序號(hào)i為終止端點(diǎn)的頻繁序列挖掘,進(jìn)而得到對(duì)應(yīng)的頻繁項(xiàng)集.因此根據(jù)結(jié)構(gòu)數(shù)組S[],進(jìn)一步給出定理2~4.

    定理2.在序號(hào)i對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組S[]中,若S[t].count小于最小支持度計(jì)數(shù)countmin,則以序號(hào)i為終止端點(diǎn)的所有頻繁序列一定不包含序號(hào)S[t].seq.

    證明. 以反證法進(jìn)行證明.假設(shè)S[t].count

    證畢.

    推論1.若有序序列{temp1,temp2,…,tempj}不是頻繁序列,則該序列的超集也不是頻繁序列.

    定理3.在UFP-tree上,從序號(hào)i對(duì)應(yīng)的樹節(jié)點(diǎn)到樹根的路徑頻繁度計(jì)數(shù)等于該路徑上序號(hào)i的頻繁度計(jì)數(shù).

    證明. 根據(jù)UFP-tree構(gòu)建的過程和定義,顯然每條子樹的葉節(jié)點(diǎn)的頻繁度計(jì)數(shù)小于等于其父節(jié)點(diǎn)的頻繁度計(jì)數(shù),從序號(hào)i對(duì)應(yīng)的樹節(jié)點(diǎn)到樹根的路徑可以看成以序號(hào)i對(duì)應(yīng)的樹節(jié)點(diǎn)為葉節(jié)點(diǎn)的子樹,在這棵子樹中,顯然序號(hào)i的頻繁度計(jì)數(shù)最小,所以該子樹的頻繁度計(jì)數(shù)為序號(hào)i的頻繁度計(jì)數(shù),所以定理3得證.

    證畢.

    應(yīng)用定理3可快速得到每條路徑的頻繁度計(jì)數(shù).

    定理4.設(shè)序列{temp1,temp2,…,tempj}是以序號(hào)tempj為終止序號(hào)的序列,當(dāng)且僅當(dāng)序列對(duì)應(yīng)數(shù)組節(jié)點(diǎn)中的編碼進(jìn)行“與”運(yùn)算的結(jié)果C中各位的和不小于最小支持度計(jì)數(shù)時(shí),該序列為頻繁序列.

    C=S[t1].r_code&…&S[tj].r_code,

    (2)

    其中,ti為序號(hào)tempi在數(shù)組S[]中對(duì)應(yīng)的下標(biāo).

    證明. 根據(jù)結(jié)構(gòu)體Struct_info的定義可知,路徑編碼r_code為序號(hào)seq在各路徑上頻繁度計(jì)數(shù)的分配情況,當(dāng)序列中的某些序號(hào)出現(xiàn)在同一條路徑下時(shí),這些序號(hào)在該路徑對(duì)應(yīng)的編碼位的數(shù)值相同,未在同一條路徑的其余序號(hào)在該路路徑對(duì)應(yīng)的編碼位的數(shù)值為0.即結(jié)構(gòu)體數(shù)組中任意2個(gè)元素的路徑編碼進(jìn)行“&”運(yùn)算的結(jié)果可根據(jù)式(3)獲得:

    (3)

    其中,r_codeit表示結(jié)構(gòu)體數(shù)組中下標(biāo)為i元素對(duì)應(yīng)的路徑編碼第t位的值,ct表示C的第t位數(shù)值.由于各序號(hào)對(duì)應(yīng)的編碼位進(jìn)行“與”運(yùn)算得到的結(jié)果為序列中各序號(hào)共同出現(xiàn)在各路徑下的情況,結(jié)果各位數(shù)值進(jìn)行求和計(jì)算,結(jié)果為序列的頻繁度計(jì)數(shù).

    證畢.

    進(jìn)一步給出頻繁項(xiàng)集挖掘算法MFIA_UFP_tree,如算法1所示,首先倒序遍歷序號(hào),得到每個(gè)序號(hào)對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組,然后調(diào)用算法2(MiningFS)進(jìn)行頻繁項(xiàng)集的挖掘.

    算法1.MFIA_UFP_tree(UFP_tree,countmin).

    輸入:UFP_tree為UFP-tree、最小支持度計(jì)數(shù)countmin;

    輸出:所有頻繁項(xiàng)集FP.

    ①S[]←?,FP←?;*初始化結(jié)構(gòu)體數(shù)組S[]和頻繁項(xiàng)集FP*

    ② fori=max_ordertoldo

    ③ 將i的指針賦值給臨時(shí)變量Tp和tp;

    ④ while (Tp≠NULL)

    ⑤j←0;

    ⑥ if (!S.contain(tp)) then

    ⑦j←j+1;

    ⑧ 將tp指向的序號(hào)的結(jié)構(gòu)體添加到結(jié)構(gòu)體數(shù)組S[];

    ⑨ else then

    ⑩S[tmp].count←S[tmp].count+tp.count;*tmp為序號(hào)tp在結(jié)構(gòu)體數(shù)組S[]內(nèi)的下標(biāo)*

    算法1倒序遍歷序號(hào),求得以每個(gè)序號(hào)為起點(diǎn)、根節(jié)點(diǎn)為終點(diǎn)的所有路徑的結(jié)構(gòu)體數(shù)組(行②~),首先遍歷每條路徑上的節(jié)點(diǎn)(行③,行~),進(jìn)一步判斷數(shù)組中是否含有該節(jié)點(diǎn),當(dāng)不含時(shí),將節(jié)點(diǎn)添加到S[]中,并將S[]的長(zhǎng)度j加1(行⑦~⑨),否則找到該節(jié)點(diǎn)在S[]中的位置,更新結(jié)構(gòu)體信息(行~),獲得對(duì)應(yīng)的結(jié)構(gòu)體數(shù)組S[]后,調(diào)用算法2對(duì)每條路徑進(jìn)行頻繁項(xiàng)集的挖掘(行).算法2如下:

    算法2.MiningFS(S[],j).

    輸入:結(jié)構(gòu)體數(shù)組S[]、數(shù)組長(zhǎng)度j;

    輸出:頻繁項(xiàng)集FP.

    ①Length←j;

    ②FP←FP∪{S[0].seq};

    ③NFP[]←?;*記錄所有長(zhǎng)度為2的非頻繁序列的第2個(gè)序號(hào)*

    ④ fori=0 tojdo

    ⑤ if(S[i].count

    ⑥ 刪除S[i];

    ⑦Length←Length-1;

    ⑧ end if

    ⑨ end for

    ⑩ forF_len=2 toLength+1 then

    算法2根據(jù)結(jié)構(gòu)體數(shù)組S[]進(jìn)行頻繁序列挖掘,首先記錄所有長(zhǎng)度為2的非頻繁序列(行③),應(yīng)用定理2進(jìn)行剪枝(行④~⑨),進(jìn)一步根據(jù)剪枝后的頻繁序列候選集的長(zhǎng)度進(jìn)行頻繁序列的挖掘(行⑩~).

    挖掘出所有的頻繁序列后,對(duì)頻繁序列進(jìn)行關(guān)聯(lián)規(guī)則挖掘.本文基于相關(guān)系數(shù)挖掘正相關(guān)無冗余關(guān)聯(lián)規(guī)則,其中相關(guān)系數(shù)計(jì)算:

    (4)

    其中,supp()為支持度,A和B分別是要挖掘的關(guān)聯(lián)規(guī)則的前件和后件.

    根據(jù)關(guān)聯(lián)規(guī)則的定義可知,當(dāng)關(guān)聯(lián)規(guī)則A→B是強(qiáng)關(guān)聯(lián)時(shí),說明前件A的出現(xiàn)對(duì)后件B的出現(xiàn)起到了促進(jìn)作用,即有很大的可能當(dāng)A出現(xiàn)時(shí)B也出現(xiàn),因此給出定理5作為維度分組依據(jù).

    定理5.正相關(guān)關(guān)聯(lián)規(guī)則A→B,若conf(A→B)=1,則前件A出現(xiàn)時(shí)后件B必然出現(xiàn).(conf(A→B)表示關(guān)聯(lián)規(guī)則A→B的置信度)

    證明. 當(dāng)conf(A→B)=1時(shí),則count(A∪B)=count(A),即前件A和后件B共同出現(xiàn)的次數(shù)等于前件A出現(xiàn)的次數(shù),即前件A出現(xiàn)后件B必然出現(xiàn).

    證畢.

    通過算法1獲得頻繁項(xiàng)集后,基于相關(guān)系數(shù)進(jìn)行關(guān)聯(lián)規(guī)則的挖掘,并依據(jù)定理5將相關(guān)聯(lián)的維度合并到1個(gè)分組,當(dāng)不同關(guān)聯(lián)規(guī)則的前件有交集時(shí),相關(guān)的維度分組進(jìn)行合并.進(jìn)一步給出分組算法Group_PAR,如算法3所示:

    算法3.Group_PAR(FP,ρmin).

    輸入:維度頻繁項(xiàng)集FP、最小相關(guān)系數(shù)ρmin;

    輸出:維度分組情況Group.

    ①PAR←?,Group←?,j=0;

    Group記錄分組情況*

    ② forX∈FPdo

    ③ 根據(jù)式(4)計(jì)算所有由頻繁序列X生成規(guī)則的相關(guān)系數(shù)ρAB,其中A∪B=X,A∩B=?;

    ④ if (ρAB≥ρmin) then

    ⑤ if (conf(A→B)≥1) then

    ⑥PAR←PAR∪{A→B};

    ⑦ end if

    ⑧ end if

    ⑨ end for

    ⑩ forY∈PARdo*Y的格式為A→B*

    算法3先遍歷頻繁項(xiàng)集,對(duì)每個(gè)項(xiàng)集進(jìn)行關(guān)聯(lián)規(guī)則的挖掘,生成關(guān)聯(lián)規(guī)則(行②~⑨),然后刪除冗余規(guī)則(行⑩~),對(duì)生成的正相關(guān)無冗余規(guī)則應(yīng)用定理5進(jìn)行分組,最終得到分組情況Group(行~).

    3.1.2 基于維度分組的Hash降維

    本節(jié)對(duì)維度分組后的數(shù)據(jù)集進(jìn)行Hash降維,同時(shí)提出符號(hào)位的概念并給出定義.當(dāng)組內(nèi)維度個(gè)數(shù)大于1時(shí),通過LSH函數(shù)進(jìn)行降維,同時(shí)在新生成的維度上保持著原維度上的相對(duì)位置關(guān)系.本文采用的Hash函數(shù)是2-穩(wěn)定分布LSH函數(shù)[31],其碰撞概率為

    (5)

    由于數(shù)據(jù)被Hash函數(shù)映射后數(shù)據(jù)位置關(guān)系發(fā)生偏移,本文對(duì)Hash降維后的數(shù)據(jù)設(shè)置了符號(hào)位,并給出符號(hào)位的定義.

    (6)

    根據(jù)符號(hào)位的定義和2-穩(wěn)定分布LSH函數(shù)的性質(zhì),進(jìn)一步得出性質(zhì)1,并根據(jù)性質(zhì)1來篩選候選集,提高查詢的準(zhǔn)確率.

    性質(zhì)1.2個(gè)距離相近的數(shù)據(jù)經(jīng)過相同的LSH函數(shù)映射后,落入相鄰的Hash桶中的數(shù)據(jù)對(duì)應(yīng)符號(hào)位相同.

    設(shè)Δ=|a·q+b|%w,t=ha(q),當(dāng)Δ<0.5w時(shí),由圖1可知,ha(q)的概率分布向左偏移,點(diǎn)q經(jīng)過Hash函數(shù)映射后有較大概率落入t-1桶的右半部分,即t-1桶中符號(hào)位為|t-1|+0.5的數(shù)據(jù)中存在點(diǎn)q的映射結(jié)果.同理Δ≥0.5w時(shí),t+1桶中符號(hào)位為|t+1|-0.5的數(shù)據(jù)中存在點(diǎn)q的映射結(jié)果.

    Fig. 1 Schematic diagram of sign bit identical probability圖1 符號(hào)位相同概率示意圖

    通過算法3得到維度分組情況后,算法4首先根據(jù)分組結(jié)果中每個(gè)組中包含的項(xiàng)數(shù)來初始化Hash函數(shù),隨后對(duì)數(shù)據(jù)進(jìn)行Hash降維,根據(jù)每個(gè)組中包含的維度個(gè)數(shù)分配Hash函數(shù),并將每組中的維度看成1個(gè)向量并進(jìn)行計(jì)算,進(jìn)一步根據(jù)式(6)計(jì)算符號(hào)位數(shù)值,最終返回降維后的數(shù)據(jù)集.因此,給出維度分組后進(jìn)行降維的算法Reduce_dim,如算法4所示:

    算法4.Reduce_dim(w,Group,X).

    輸入:桶寬w、數(shù)據(jù)維度分組情況Group={g1,g2,…,gm}、原始數(shù)據(jù)集X={x1,x2,…,xn};

    輸出:降維后的數(shù)據(jù)集X′.

    ①X′←?;

    ② fori=0 tomdo

    ④ 為每個(gè)維度組初始化Num_func個(gè)Hash函數(shù);

    ⑤ end for

    ⑥ fori=0 tondo

    ⑦ 對(duì)xi進(jìn)行Hash降維;

    ⑩ end for

    3.2 基于動(dòng)態(tài)加權(quán)的近似k近鄰查詢

    數(shù)據(jù)經(jīng)過維度分組和Hash降維后,為了提高計(jì)算速度,本文將降維后的數(shù)據(jù)進(jìn)行編碼,即x∈{0,1}l.根據(jù)編碼后的數(shù)據(jù),應(yīng)用熵理論對(duì)Hash編碼函數(shù)進(jìn)行篩選.本文應(yīng)用2-穩(wěn)定分布LSH進(jìn)行編碼,方法為

    (7)

    其中,a是服從2穩(wěn)定分布的隨機(jī)函數(shù)產(chǎn)生的一個(gè)D-|Z|維向量,D為降維后的數(shù)據(jù)維度,Z為符號(hào)位,|Z|是符號(hào)位的長(zhǎng)度.根據(jù)信息熵和Hash編碼的特性,進(jìn)一步給出定理6.

    定理6.若Hash函數(shù)將數(shù)據(jù)對(duì)象映射成0和1的概率越相近,那么該Hash函數(shù)的散列效果就越好.

    證明. 根據(jù)式(7)對(duì)數(shù)據(jù)進(jìn)行0,1編碼,其中Hash函數(shù)相當(dāng)于二元信源,0和1為二元信源符號(hào),二元信源熵的計(jì)算公式為

    entropy(Y)=E(Y)=-ωlgω-? lg ?,

    (8)

    其中,E(Y)是ω的函數(shù),ω為信源符號(hào)概率.

    根據(jù)式(8)可知,當(dāng)信源符號(hào)出現(xiàn)的概率越接近,信息熵越大,即Hash函數(shù)編碼結(jié)果越不確定,散列效果越好.因此得證.

    證畢.

    由于二進(jìn)制編碼的長(zhǎng)度對(duì)查詢準(zhǔn)確率有著顯著的影響,為提高編碼質(zhì)量,本文基于定理6篩選出熵值大的函數(shù)作為映射函數(shù)進(jìn)行編碼.數(shù)據(jù)經(jīng)過算法4進(jìn)行維度分組降維預(yù)處理后,應(yīng)用算法5對(duì)其進(jìn)行編碼.

    算法5.Hash_code(X′,l).

    輸出:編碼后的數(shù)據(jù)集X_c.

    ①X_c←?;

    ② 初始化2l個(gè)Hash編碼函數(shù);*隨機(jī)變量維度為D-|Z|維*

    ③ fori=0 tondo

    ⑤ end for

    ⑥ fori=0 to 2ldo

    ⑦ 根據(jù)式(8)計(jì)算每個(gè)編碼Hash函數(shù)的熵;

    ⑧ end for

    ⑨ 選擇出熵為前l(fā)大的函數(shù)作為編碼函數(shù);

    ⑩ fori=0 tondo

    算法5先隨機(jī)生成2l個(gè)Hash函數(shù),進(jìn)一步根據(jù)式(7)進(jìn)行Hash(行①~⑤),編碼后對(duì)編碼函數(shù)進(jìn)行篩選,計(jì)算每個(gè)編碼函數(shù)對(duì)應(yīng)的熵值,選擇出熵值為前l(fā)的函數(shù)作為編碼函數(shù)(行⑥~⑨),最終將多余的編碼刪除得到最終編碼數(shù)據(jù)集(行⑩~),因此時(shí)間復(fù)雜度為O(ln).

    當(dāng)進(jìn)行查詢時(shí),將查詢點(diǎn)q進(jìn)行相同處理,通過與編碼后的數(shù)據(jù)集X_c中的數(shù)據(jù)進(jìn)行比較,返回漢明距離在小于給定閾值dismin的數(shù)據(jù)作為候選集CS,進(jìn)一步根據(jù)性質(zhì)1篩選候選集,基于候選集中的每位編碼與查詢點(diǎn)對(duì)應(yīng)位的編碼相同的概率,對(duì)編碼位進(jìn)行權(quán)重賦值,然后計(jì)算查詢點(diǎn)q與候選集CS中數(shù)據(jù)的加權(quán)漢明距離,根據(jù)加權(quán)距離進(jìn)行排序

    并返回前k個(gè)數(shù)據(jù).由二元信源熵函數(shù)可知,相同編碼位的編碼相同的概率越大,對(duì)應(yīng)編碼位的可信度就越高,權(quán)重越大.根據(jù)熵權(quán)法對(duì)第i位設(shè)定權(quán)重:

    (9)

    其中,ei為第i位的信息熵值.

    當(dāng)對(duì)數(shù)據(jù)集進(jìn)行編碼后,輸入查詢點(diǎn)進(jìn)行相同的維度分組降維以及編碼后,基于加權(quán)漢明距離進(jìn)行查詢,同時(shí)查詢過程中動(dòng)態(tài)調(diào)整權(quán)值.查詢算法如算法6所示:

    算法6.DWAkNN(X_c,q,dismin).

    輸出:q的近似k近鄰.

    ①CS←?;*CS為候選集*

    ②q′←Reduce_dim(w,Group,q);

    ③q″←Hash_code(q′,l);

    ④ fori=0 tondo

    ⑦ end if

    ⑧ end for

    ⑨ 根據(jù)式(8)計(jì)算候選集CS中每位編碼的熵;*概率為與查詢點(diǎn)q對(duì)應(yīng)編碼位相同的概率*

    ⑩ 根據(jù)式(9)計(jì)算候選集CS中每位編碼的權(quán)重;

    算法6先將查詢對(duì)象q進(jìn)行降維并進(jìn)行編碼(行②③),然后遍歷編碼后的數(shù)據(jù)集X_c,返回漢明距離小于dismin的數(shù)據(jù)并添加到候選集CS(行④~⑧),計(jì)算候選集中數(shù)據(jù)的每位編碼位的熵值,進(jìn)一步根據(jù)熵值計(jì)算編碼位的權(quán)重(行⑨⑩),最后計(jì)算加權(quán)漢明距離并進(jìn)行升序排序,當(dāng)加權(quán)漢明距離相同時(shí),根據(jù)符號(hào)位相同的個(gè)數(shù)進(jìn)行排序,最終返回前k個(gè)數(shù)據(jù)作為查詢結(jié)果(行~).

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

    為了評(píng)估算法性能,分別測(cè)試了自身參數(shù)對(duì)算法性能的影響以及與對(duì)比算法的性能.

    4.1 參數(shù)分析

    本節(jié)實(shí)驗(yàn)分析關(guān)聯(lián)規(guī)則最小支持度min_s、頻繁項(xiàng)集最小支持度min_s_r和l對(duì)算法準(zhǔn)確率的影響以及數(shù)據(jù)維度對(duì)算法查詢時(shí)間的影響.準(zhǔn)確率Ratio其值為近似k近鄰距離與真實(shí)k近鄰距離之比的平均數(shù),其值越接近1說明算法查詢質(zhì)量越高,準(zhǔn)確率Ratio計(jì)算方式為

    (10)

    本節(jié)實(shí)驗(yàn)使用的數(shù)據(jù)集為真實(shí)數(shù)據(jù)集和人工數(shù)據(jù)集.分別是由IBM Almaden Quest研究小組的生成器生成的數(shù)據(jù)集T40I10D100K和由Roberto Bayardo從PUMSB中提供的pumsb數(shù)據(jù)集和由Claudio Lucchese等人通過爬蟲得到的網(wǎng)絡(luò)文檔數(shù)據(jù)集webdocs_samping.數(shù)據(jù)集是從FIMI信息庫(kù)下載得到(1)http:fimi.uantwerpen.bedata.3個(gè)數(shù)據(jù)集被廣泛應(yīng)用于頻繁項(xiàng)集挖掘試驗(yàn).由于數(shù)據(jù)集webdocs過大,從原始數(shù)據(jù)集中隨機(jī)選取10萬(wàn)條數(shù)據(jù)作為數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),并對(duì)數(shù)據(jù)信息進(jìn)行了適當(dāng)調(diào)整和優(yōu)化.該數(shù)據(jù)集記為webdocs_samping.數(shù)據(jù)集屬性如表1所示:

    Table 1 Attribute Sheet of Experimental Data Set forParameter Analysis

    在實(shí)驗(yàn)中,分別從各數(shù)據(jù)集隨機(jī)抽取5 000條事務(wù)作為查詢點(diǎn)進(jìn)行查詢,最后計(jì)算平均時(shí)間和準(zhǔn)確率作為比較.

    實(shí)驗(yàn)1.首先分析參數(shù)min_s和min_s_r對(duì)本文所提算法的準(zhǔn)確性的影響.其中k=50,編碼長(zhǎng)度l=32 b,Hash函數(shù)的桶寬w=4.由于數(shù)據(jù)集T40I10D100K是一個(gè)稀疏數(shù)據(jù)集,因此分析了參數(shù)min_s從0.5%~4%變化過程中對(duì)算法準(zhǔn)確率的影響;數(shù)據(jù)集pumsb和webdocs_sampling相對(duì)稠密,因此分析了參數(shù)min_s從60%~95%的變化過程對(duì)算法正確率的影響,同時(shí)參數(shù)min_s_r的取值為60%,70%,80%,90%.參數(shù)影響分別如圖2~4所示.

    Fig. 2 Experimental result on dataset T40I10D100K圖2 在數(shù)據(jù)集T40I10D100K上實(shí)驗(yàn)結(jié)果

    Fig. 3 Experimental result on dataset pumsb圖3 在數(shù)據(jù)集pumsb上實(shí)驗(yàn)結(jié)果

    Fig. 4 Experimental result on dataset webdocs_sampling圖4 在數(shù)據(jù)集webdocs_sampling上實(shí)驗(yàn)結(jié)果

    通過圖2~4可知,在3個(gè)數(shù)據(jù)集上當(dāng)min_s_r固定時(shí),Ratio隨著min_s的增大呈現(xiàn)上升的趨勢(shì),由Ratio的計(jì)算公式可知,當(dāng)Ratio偏離1越遠(yuǎn),算法的查詢結(jié)果的準(zhǔn)確性越低,因此當(dāng)min_s_r的值固定時(shí),算法在3個(gè)數(shù)據(jù)集上的查詢準(zhǔn)確性隨min_s的增大而降低.這是由于當(dāng)min_s_r固定時(shí),隨著頻繁項(xiàng)集最小支持度min_s的增大,導(dǎo)致在進(jìn)行分組降維的過程中忽略的項(xiàng)增多,致使降維后的誤差大.同時(shí)在3個(gè)數(shù)據(jù)集上當(dāng)min_s固定時(shí),Ratio總體上隨min_s_r的增大而更趨近于1,即算法的準(zhǔn)確性隨min_s_r的增大而增大,這是由于在分組降維過程中,關(guān)聯(lián)規(guī)則的質(zhì)量影響著維度的分組,min_s_r越大說明關(guān)聯(lián)規(guī)則的前后件關(guān)系越緊密,組內(nèi)的非零值維度越多,減少了Hash函數(shù)中隨機(jī)變量的維度和Hash函數(shù)的個(gè)數(shù),降低了降維后的誤差.

    實(shí)驗(yàn)2.分析參數(shù)l對(duì)查詢準(zhǔn)確率的影響.在本實(shí)驗(yàn)中,設(shè)在數(shù)據(jù)集T40I10D100K中min_s=2%,另外2個(gè)數(shù)據(jù)集中為75%,設(shè)min_s_r在3個(gè)數(shù)據(jù)集中都為90%,k和w分別為50和4,分析l的值為8,16,32,48,64對(duì)查詢準(zhǔn)確率的影響,結(jié)果如圖5所示:

    Fig. 5 Effect of l on Ratio圖5 l對(duì)Ratio的影響

    由圖5可知,在3個(gè)數(shù)據(jù)集上Ratio都隨著編碼長(zhǎng)度l的增大而更趨近于1,即算法的查詢準(zhǔn)確性隨著l的增大而增大,當(dāng)編碼位數(shù)大于32 b時(shí),編碼位數(shù)對(duì)查詢結(jié)果的提升幅度變小,這是由于算法在將數(shù)據(jù)從歐氏空間映射到漢明空間時(shí)本身信息缺失導(dǎo)致的.

    通過實(shí)驗(yàn)1和實(shí)驗(yàn)2可以看出,本算法能以較高的正確率返回k近鄰,在稀疏和稠密數(shù)據(jù)集上表現(xiàn)都比較優(yōu)異.

    4.2 算法對(duì)比

    本節(jié)通過與對(duì)比算法比較不同k下查詢結(jié)果的準(zhǔn)確率和查詢時(shí)間進(jìn)一步評(píng)估本文算法性能.

    1) 數(shù)據(jù)集.本節(jié)應(yīng)用真實(shí)數(shù)據(jù)進(jìn)行對(duì)比實(shí)驗(yàn),所用的數(shù)據(jù)集分別是Mnist,Sun,Trevi,Nus,Deep,BlackFriday.其中前5個(gè)數(shù)據(jù)集通過GitHub網(wǎng)站獲取(2)https:github.comDBWangGroupUNSWnns_benchmark,被廣泛應(yīng)用于現(xiàn)有的AkNN查詢實(shí)驗(yàn).原始BlackFriday數(shù)據(jù)集是從Kaggle平臺(tái)(全球數(shù)據(jù)科學(xué)競(jìng)賽在線平臺(tái))獲取(3)https:www.kaggle.comsdolezelblack-friday,由于原始數(shù)據(jù)集包含不相關(guān)的屬性,因此對(duì)其進(jìn)行了數(shù)據(jù)清洗,只保留了每個(gè)用戶的購(gòu)物信息.數(shù)據(jù)集屬性如表2所示.在查詢時(shí),我們從每個(gè)數(shù)據(jù)集中隨機(jī)選取500個(gè)數(shù)據(jù)點(diǎn)作為查詢點(diǎn),每個(gè)查詢點(diǎn)重復(fù)查詢50次,k分別取值為10,30,50,70,90,默認(rèn)k=50,取查詢時(shí)間和查詢準(zhǔn)確率的平均值作為算法的性能指標(biāo).

    2) 對(duì)比算法.我們選擇HD-Index查詢算法[15]、HWT查詢算法[17]和QALSH(query-aware LSH)查詢算法[20]與本文所提出的DWAkNN查詢算法進(jìn)行對(duì)比.所選算法分別基于Hilbert空間填充曲線、漢明加權(quán)樹和LSH實(shí)現(xiàn).

    Table 2 Comparison the Experimental Data Sets表2 對(duì)比實(shí)驗(yàn)數(shù)據(jù)集

    3) 參數(shù)設(shè)置.本文算法的參數(shù)min_s,min_s_r,w分別設(shè)置為0.04,0.9,4,編碼長(zhǎng)度l=32 b.根據(jù)文獻(xiàn)[15]的實(shí)驗(yàn)結(jié)果,將算法HD-Index的參數(shù)m,τHD-Index,α,βHD-Index分別設(shè)置為10,16(在數(shù)據(jù)集Trevi和BlackFriday上值分別設(shè)為64和60)、4 096和4 096,其中m為參考點(diǎn)個(gè)數(shù),τHD-Index為RDB-tree的個(gè)數(shù),α為經(jīng)過RDB-tree剪枝獲得候選集個(gè)數(shù),βHD-Index為經(jīng)過三角不等式進(jìn)行進(jìn)一步過濾的候選集個(gè)數(shù).根據(jù)文獻(xiàn)[17]的實(shí)驗(yàn)過程,算法HWT的參數(shù)τHWT設(shè)為1 000,同樣應(yīng)用LSH將數(shù)據(jù)集的實(shí)值向量映射到二進(jìn)制碼,在本文中設(shè)置二進(jìn)制長(zhǎng)度為32 b.

    Fig. 6 Influence of k on query time圖6 k值對(duì)查詢時(shí)間的影響

    首先測(cè)試k值對(duì)查詢時(shí)間的影響.實(shí)驗(yàn)結(jié)果如圖6所示.由圖6可以看出4個(gè)測(cè)試算法在6個(gè)數(shù)據(jù)集上的查詢時(shí)間都是隨著k的增大呈上升趨勢(shì),本文算法效率優(yōu)于算法QALSH和HD-Index,當(dāng)k=50時(shí),查詢效率分別提高了25.0%~72.8%和20.0%~63.0%.但是查詢時(shí)間略高于算法HWT.這是由于本文算法在進(jìn)行查詢時(shí)會(huì)動(dòng)態(tài)設(shè)置編碼位的權(quán)重,然后進(jìn)行加權(quán)排序,導(dǎo)致查詢時(shí)間略高于算法HWT.根據(jù)圖6(b)(d)可以看出,隨著數(shù)據(jù)規(guī)模的增大(Sun數(shù)據(jù)集和Nus數(shù)據(jù)集維度相差不大,規(guī)模相差1個(gè)數(shù)量級(jí)),4個(gè)算法的查詢時(shí)間也都增大.

    Fig. 7 Influence of k on Ratio圖7 k值對(duì)Ratio的影響

    其次測(cè)試k值對(duì)查詢準(zhǔn)確率的影響.實(shí)驗(yàn)結(jié)果如圖7所示.由圖7可以看出除了在數(shù)據(jù)集Black-Friday,算法QALSH的Ratio接近1,查詢質(zhì)量最高,算法DWAkNN次之,算法HD-Index和算法HWT相差不大,略高于算法DWAkNN,在數(shù)據(jù)集BlackFriday上,算法DWAkNN最優(yōu).這是由于算法DWAkNN通過對(duì)維度間的關(guān)聯(lián)規(guī)則進(jìn)行分組降維后再進(jìn)行編碼,減少了數(shù)據(jù)信息的丟失,然而除購(gòu)物信息數(shù)據(jù)集BlackFriday外,其他數(shù)據(jù)集都是圖像類型,數(shù)據(jù)維度間的關(guān)聯(lián)性不穩(wěn)定,維度分組降維對(duì)算法的查詢準(zhǔn)確率提升小于在BlackFriday數(shù)據(jù)集上的提升,因此在表2的前5個(gè)數(shù)據(jù)集上的查詢質(zhì)量略低于QALSH算法,但是與同樣應(yīng)用LSH對(duì)數(shù)據(jù)進(jìn)行編碼的HWT算法相比,算法DWAkNN的查詢質(zhì)量更優(yōu).同時(shí)結(jié)合圖6的查詢時(shí)間結(jié)果圖可以看出,在相同數(shù)據(jù)集上,本文所提算法DWAkNN能夠以較低的查詢時(shí)間返回更接近真實(shí)k近鄰的近似結(jié)果,算法的綜合性能更優(yōu).

    最后測(cè)試本文算法與線性掃描(LineScan)查詢算法在高維數(shù)據(jù)集下的性能對(duì)比(高維空間線性掃描算法效率高于低維查詢算法).實(shí)驗(yàn)結(jié)果如表3所示,可以看出本文算法的效率遠(yuǎn)高于LineScan算法.

    Table 3 High-Dimensional Data Set Query Time and Efficiency Improvement Table

    通過實(shí)驗(yàn)可得,本文所提算法DWAkNN能夠以較低查詢時(shí)間返回較高質(zhì)量的AkNN查詢結(jié)果,與目前先進(jìn)AkNN查詢算法相比,綜合性能更為優(yōu)越,尤其提高了維度間關(guān)聯(lián)關(guān)系明顯的數(shù)據(jù)集下AkNN查詢的準(zhǔn)確率,同時(shí)與傳統(tǒng)的低維空間下的查詢算法相比較,算法DWAkNN在高維空間下的查詢效率得到大幅度的提升.

    5 總 結(jié)

    本文對(duì)高維空間下近似k近鄰查詢問題進(jìn)行了研究,針對(duì)高維數(shù)據(jù)降維過程不考慮維度間的關(guān)聯(lián)關(guān)系的問題,提出基于關(guān)聯(lián)規(guī)則的維度分組降維算法Reduce_dim,進(jìn)一步提出了Hash_code算法,該算法基于LSH對(duì)降維后的數(shù)據(jù)進(jìn)行編碼,并應(yīng)用信息熵理論篩選編碼函數(shù),最終提出了動(dòng)態(tài)加權(quán)漢明距離近似k近鄰查詢算法DWAkNN,算法應(yīng)用符號(hào)位對(duì)候選集進(jìn)行篩選,提高了查詢準(zhǔn)確率.實(shí)驗(yàn)結(jié)果表明,本文提出的算法具有較好的性能.未來研究重點(diǎn)主要集中在基于神經(jīng)網(wǎng)絡(luò)的高維空間近似k近鄰查詢問題等方面.

    猜你喜歡
    項(xiàng)集降維序號(hào)
    Three-Body’s epic scale and fiercely guarded fanbase present challenges to adaptations
    降維打擊
    海峽姐妹(2019年12期)2020-01-14 03:24:40
    技術(shù)指標(biāo)選股
    技術(shù)指標(biāo)選股
    技術(shù)指標(biāo)選股
    技術(shù)指標(biāo)選股
    關(guān)聯(lián)規(guī)則中經(jīng)典的Apriori算法研究
    卷宗(2014年5期)2014-07-15 07:47:08
    拋物化Navier-Stokes方程的降維仿真模型
    基于特征聯(lián)合和偏最小二乘降維的手勢(shì)識(shí)別
    一種頻繁核心項(xiàng)集的快速挖掘算法
    麻豆乱淫一区二区| 国产 一区精品| 极品人妻少妇av视频| 最近中文字幕高清免费大全6| 亚洲欧美中文字幕日韩二区| 天天影视国产精品| 久久女婷五月综合色啪小说| bbb黄色大片| 久久青草综合色| 久久人人爽人人片av| 精品人妻一区二区三区麻豆| 欧美激情极品国产一区二区三区| 免费在线观看黄色视频的| 91老司机精品| 亚洲成人一二三区av| 日韩精品免费视频一区二区三区| 亚洲七黄色美女视频| 亚洲美女视频黄频| 国产av国产精品国产| 亚洲精品中文字幕在线视频| 亚洲精品美女久久av网站| 91国产中文字幕| www.熟女人妻精品国产| 亚洲三区欧美一区| 亚洲在久久综合| 久久天躁狠狠躁夜夜2o2o | 亚洲精品久久午夜乱码| 久久久精品区二区三区| 久久人人97超碰香蕉20202| 国产精品蜜桃在线观看| 99re6热这里在线精品视频| 欧美日韩亚洲综合一区二区三区_| 十八禁人妻一区二区| 日本一区二区免费在线视频| 国产精品人妻久久久影院| 一级毛片电影观看| 一二三四中文在线观看免费高清| 色婷婷久久久亚洲欧美| 飞空精品影院首页| 在线观看一区二区三区激情| 精品视频人人做人人爽| 国产又爽黄色视频| 久久精品aⅴ一区二区三区四区| 亚洲,欧美精品.| 欧美日韩综合久久久久久| 国产精品国产三级专区第一集| 又大又黄又爽视频免费| 久久性视频一级片| 欧美日韩成人在线一区二区| 99热国产这里只有精品6| 国产男人的电影天堂91| 国产成人av激情在线播放| 国产成人av激情在线播放| 国产乱来视频区| 熟女av电影| 日韩一本色道免费dvd| 成人毛片60女人毛片免费| 免费黄网站久久成人精品| 老汉色∧v一级毛片| 丝袜在线中文字幕| 高清在线视频一区二区三区| 国产日韩欧美在线精品| 午夜免费男女啪啪视频观看| 90打野战视频偷拍视频| 欧美日韩一区二区视频在线观看视频在线| 久久鲁丝午夜福利片| 国产免费福利视频在线观看| 91aial.com中文字幕在线观看| 国产极品天堂在线| 如日韩欧美国产精品一区二区三区| 99香蕉大伊视频| 成年女人毛片免费观看观看9 | 日韩精品免费视频一区二区三区| 人人妻人人澡人人爽人人夜夜| 国产福利在线免费观看视频| 日本av免费视频播放| 一本色道久久久久久精品综合| 国产视频首页在线观看| 精品少妇内射三级| 日韩一区二区三区影片| 嫩草影视91久久| 亚洲国产看品久久| 国产一卡二卡三卡精品 | 一级片免费观看大全| 日韩大码丰满熟妇| 中国三级夫妇交换| 精品少妇内射三级| 狠狠精品人妻久久久久久综合| 亚洲精华国产精华液的使用体验| 日韩 欧美 亚洲 中文字幕| 亚洲图色成人| 国产精品香港三级国产av潘金莲 | 免费看不卡的av| 日韩,欧美,国产一区二区三区| 一本一本久久a久久精品综合妖精| 国产又色又爽无遮挡免| 亚洲成人av在线免费| 一级毛片黄色毛片免费观看视频| 国产女主播在线喷水免费视频网站| 黄片无遮挡物在线观看| 亚洲伊人久久精品综合| 亚洲 欧美一区二区三区| 在线免费观看不下载黄p国产| 亚洲第一av免费看| videosex国产| 午夜日本视频在线| 一本—道久久a久久精品蜜桃钙片| 国产高清国产精品国产三级| 精品久久久精品久久久| 黄网站色视频无遮挡免费观看| 久久国产精品男人的天堂亚洲| 大香蕉久久网| 国产女主播在线喷水免费视频网站| 国产 一区精品| 亚洲国产中文字幕在线视频| 男女国产视频网站| 日本av手机在线免费观看| 精品国产国语对白av| 成年人午夜在线观看视频| 国产 精品1| 侵犯人妻中文字幕一二三四区| 老司机靠b影院| 久久毛片免费看一区二区三区| 你懂的网址亚洲精品在线观看| 国产 一区精品| 午夜激情久久久久久久| 精品一区在线观看国产| 亚洲婷婷狠狠爱综合网| 久久精品亚洲熟妇少妇任你| 下体分泌物呈黄色| 飞空精品影院首页| 欧美97在线视频| 岛国毛片在线播放| 制服诱惑二区| 国产亚洲欧美精品永久| 丝袜美足系列| 国产亚洲av高清不卡| 一区福利在线观看| 制服丝袜香蕉在线| 国产一区二区在线观看av| 毛片一级片免费看久久久久| 久久久久久人人人人人| 日韩一区二区视频免费看| 久久精品国产亚洲av高清一级| 日韩大片免费观看网站| av卡一久久| 国产欧美日韩一区二区三区在线| 男女床上黄色一级片免费看| 青草久久国产| 丰满乱子伦码专区| 在线 av 中文字幕| 午夜福利视频在线观看免费| 人人妻人人澡人人爽人人夜夜| 国产精品无大码| 午夜久久久在线观看| 一边摸一边抽搐一进一出视频| 一个人免费看片子| 国产在线免费精品| 国产精品成人在线| 欧美精品av麻豆av| 日韩欧美精品免费久久| 悠悠久久av| 99国产精品免费福利视频| 免费高清在线观看日韩| av免费观看日本| svipshipincom国产片| 高清欧美精品videossex| 超碰97精品在线观看| 久久亚洲国产成人精品v| 这个男人来自地球电影免费观看 | 老司机影院成人| 乱人伦中国视频| 午夜福利一区二区在线看| 波野结衣二区三区在线| 亚洲人成电影观看| av网站在线播放免费| 中文字幕精品免费在线观看视频| 亚洲精品一区蜜桃| 国产精品.久久久| 国产 一区精品| 在线观看国产h片| 国产乱来视频区| 久久久精品免费免费高清| 久久人妻熟女aⅴ| 最新的欧美精品一区二区| 亚洲国产av影院在线观看| 大码成人一级视频| 精品少妇久久久久久888优播| 老司机亚洲免费影院| 97在线人人人人妻| www.av在线官网国产| 欧美精品一区二区大全| 亚洲欧洲国产日韩| 一区二区三区四区激情视频| 少妇 在线观看| 亚洲第一av免费看| 满18在线观看网站| 欧美国产精品一级二级三级| 一二三四在线观看免费中文在| 另类亚洲欧美激情| 香蕉国产在线看| 少妇猛男粗大的猛烈进出视频| 丰满饥渴人妻一区二区三| 亚洲国产毛片av蜜桃av| 你懂的网址亚洲精品在线观看| 久久免费观看电影| 成人国语在线视频| 黄色毛片三级朝国网站| 精品国产超薄肉色丝袜足j| 欧美精品高潮呻吟av久久| 国产免费现黄频在线看| 亚洲一卡2卡3卡4卡5卡精品中文| 黄片播放在线免费| 久久精品久久久久久久性| 人人妻人人爽人人添夜夜欢视频| 最新的欧美精品一区二区| 少妇的丰满在线观看| 美女福利国产在线| 国产精品一二三区在线看| 日韩电影二区| 久久精品国产亚洲av高清一级| 一本—道久久a久久精品蜜桃钙片| 亚洲国产精品成人久久小说| 午夜免费观看性视频| 欧美xxⅹ黑人| 久久久久视频综合| 高清欧美精品videossex| 亚洲国产毛片av蜜桃av| 最近最新中文字幕大全免费视频 | 午夜av观看不卡| 人人妻人人添人人爽欧美一区卜| 午夜激情av网站| 午夜影院在线不卡| 51午夜福利影视在线观看| 成人国产av品久久久| 在现免费观看毛片| 国产成人午夜福利电影在线观看| 国产精品人妻久久久影院| 欧美日韩亚洲高清精品| 亚洲人成电影观看| 美女国产高潮福利片在线看| 久久女婷五月综合色啪小说| 成人18禁高潮啪啪吃奶动态图| 久久久国产欧美日韩av| 国产一区二区在线观看av| 亚洲欧美激情在线| 久久久久久久久久久久大奶| 2021少妇久久久久久久久久久| 老汉色av国产亚洲站长工具| 成人影院久久| 久久久精品免费免费高清| 免费不卡黄色视频| 国产欧美日韩一区二区三区在线| 亚洲美女黄色视频免费看| 99久国产av精品国产电影| 国产成人精品福利久久| 久久人人爽av亚洲精品天堂| 亚洲视频免费观看视频| 男女边吃奶边做爰视频| 日韩 欧美 亚洲 中文字幕| 亚洲av成人精品一二三区| 97精品久久久久久久久久精品| 你懂的网址亚洲精品在线观看| 亚洲色图综合在线观看| 久久av网站| 又粗又硬又长又爽又黄的视频| 18禁观看日本| 亚洲美女黄色视频免费看| a 毛片基地| 精品国产露脸久久av麻豆| 日本爱情动作片www.在线观看| 午夜免费观看性视频| 成人国产av品久久久| 操出白浆在线播放| 婷婷色av中文字幕| 成人手机av| 丝袜脚勾引网站| 精品国产一区二区三区久久久樱花| 久久久久久久精品精品| 亚洲第一青青草原| 黑人猛操日本美女一级片| 波多野结衣av一区二区av| 日本一区二区免费在线视频| 女的被弄到高潮叫床怎么办| 欧美日韩视频精品一区| 亚洲精品在线美女| 国产精品成人在线| 久久久精品区二区三区| 亚洲精品,欧美精品| 老司机在亚洲福利影院| 欧美xxⅹ黑人| 国产精品熟女久久久久浪| 夫妻性生交免费视频一级片| 91精品国产国语对白视频| 亚洲国产精品999| 黑人猛操日本美女一级片| 日本欧美视频一区| 一本色道久久久久久精品综合| 免费黄网站久久成人精品| 91aial.com中文字幕在线观看| 国产精品免费视频内射| 美女大奶头黄色视频| 精品久久久精品久久久| 久久女婷五月综合色啪小说| 丝袜美足系列| 亚洲av电影在线进入| 啦啦啦中文免费视频观看日本| 宅男免费午夜| 久久久久人妻精品一区果冻| 久久久欧美国产精品| 色综合欧美亚洲国产小说| 在线观看人妻少妇| 亚洲av男天堂| www.自偷自拍.com| 国产欧美日韩综合在线一区二区| 999久久久国产精品视频| 中文欧美无线码| 久热爱精品视频在线9| 国产女主播在线喷水免费视频网站| av电影中文网址| 午夜福利免费观看在线| 王馨瑶露胸无遮挡在线观看| 90打野战视频偷拍视频| 国产免费视频播放在线视频| videosex国产| 99久久99久久久精品蜜桃| 久久精品国产亚洲av涩爱| 久久午夜综合久久蜜桃| 国产不卡av网站在线观看| 大片电影免费在线观看免费| 精品一区二区三卡| 欧美中文综合在线视频| 日韩精品免费视频一区二区三区| 亚洲国产欧美在线一区| 一个人免费看片子| 精品午夜福利在线看| 免费黄频网站在线观看国产| 99热网站在线观看| 亚洲成人免费av在线播放| 国产麻豆69| 亚洲美女搞黄在线观看| 久久久精品国产亚洲av高清涩受| 亚洲国产精品国产精品| 性少妇av在线| tube8黄色片| 最新在线观看一区二区三区 | 国产av一区二区精品久久| 亚洲av福利一区| 日本91视频免费播放| 七月丁香在线播放| 伊人久久国产一区二区| 操美女的视频在线观看| 国产精品麻豆人妻色哟哟久久| 亚洲免费av在线视频| 极品少妇高潮喷水抽搐| 亚洲精品乱久久久久久| 美女午夜性视频免费| av又黄又爽大尺度在线免费看| 午夜福利视频在线观看免费| 国产男人的电影天堂91| 日韩一区二区视频免费看| 日韩av免费高清视频| 精品国产一区二区三区四区第35| 一边亲一边摸免费视频| 午夜免费男女啪啪视频观看| 亚洲情色 制服丝袜| 人妻一区二区av| 亚洲成国产人片在线观看| 久久久久久人人人人人| 国产麻豆69| 97在线人人人人妻| av又黄又爽大尺度在线免费看| 一级爰片在线观看| 国产男女内射视频| 一区二区日韩欧美中文字幕| 久久久久精品国产欧美久久久 | 精品国产超薄肉色丝袜足j| 国产黄频视频在线观看| 妹子高潮喷水视频| 久久精品久久久久久噜噜老黄| 亚洲精品国产av蜜桃| 亚洲欧洲国产日韩| 国产亚洲av片在线观看秒播厂| 桃花免费在线播放| 国产日韩欧美在线精品| 熟女少妇亚洲综合色aaa.| 午夜免费观看性视频| 丰满乱子伦码专区| 亚洲久久久国产精品| 久久青草综合色| 美女高潮到喷水免费观看| 久久 成人 亚洲| 成人免费观看视频高清| 天堂8中文在线网| 精品少妇黑人巨大在线播放| 久久 成人 亚洲| 国产成人精品在线电影| 亚洲综合精品二区| 高清黄色对白视频在线免费看| 丝袜脚勾引网站| 1024视频免费在线观看| 国产精品久久久久久精品古装| 国产一区二区三区av在线| 悠悠久久av| 亚洲av成人精品一二三区| 女人高潮潮喷娇喘18禁视频| 自拍欧美九色日韩亚洲蝌蚪91| 青春草视频在线免费观看| 欧美国产精品一级二级三级| 国产精品二区激情视频| 91精品伊人久久大香线蕉| 波野结衣二区三区在线| 欧美国产精品va在线观看不卡| 人成视频在线观看免费观看| 日韩一区二区三区影片| 最黄视频免费看| 天天躁夜夜躁狠狠躁躁| 亚洲成国产人片在线观看| 久久狼人影院| 欧美久久黑人一区二区| 成人免费观看视频高清| 2021少妇久久久久久久久久久| 天天操日日干夜夜撸| 97精品久久久久久久久久精品| 91国产中文字幕| 久久久久久人人人人人| 最近最新中文字幕免费大全7| 国产xxxxx性猛交| 夫妻午夜视频| 中文字幕人妻丝袜一区二区 | 成人毛片60女人毛片免费| 国产精品免费视频内射| 国产熟女午夜一区二区三区| 男女午夜视频在线观看| 一边亲一边摸免费视频| 人人妻人人爽人人添夜夜欢视频| 99久久综合免费| 肉色欧美久久久久久久蜜桃| 国产 精品1| 街头女战士在线观看网站| 国产爽快片一区二区三区| 十分钟在线观看高清视频www| 亚洲国产看品久久| 亚洲情色 制服丝袜| 五月开心婷婷网| 国产在视频线精品| 1024视频免费在线观看| 欧美精品av麻豆av| 午夜av观看不卡| 丝袜脚勾引网站| 人成视频在线观看免费观看| 老司机在亚洲福利影院| 国产毛片在线视频| 国产精品欧美亚洲77777| 免费少妇av软件| 亚洲av成人精品一二三区| 热re99久久精品国产66热6| 亚洲欧美一区二区三区黑人| 一级毛片我不卡| 51午夜福利影视在线观看| 国产片特级美女逼逼视频| 国产av码专区亚洲av| av卡一久久| 成人亚洲精品一区在线观看| 色视频在线一区二区三区| 欧美黑人欧美精品刺激| 天堂8中文在线网| 国产午夜精品一二区理论片| 亚洲精品国产色婷婷电影| 欧美av亚洲av综合av国产av | 国产亚洲av高清不卡| 亚洲精品aⅴ在线观看| 成人三级做爰电影| 久久狼人影院| 国产成人欧美在线观看 | 嫩草影院入口| 一区二区日韩欧美中文字幕| 欧美少妇被猛烈插入视频| 一级爰片在线观看| 中文字幕色久视频| 乱人伦中国视频| 精品国产一区二区久久| 国产乱人偷精品视频| 日本wwww免费看| 精品亚洲乱码少妇综合久久| 国产一区二区在线观看av| 九九爱精品视频在线观看| 欧美人与性动交α欧美精品济南到| 亚洲成人一二三区av| 91aial.com中文字幕在线观看| 建设人人有责人人尽责人人享有的| 这个男人来自地球电影免费观看 | 超色免费av| 亚洲欧美日韩另类电影网站| 免费高清在线观看视频在线观看| 久热爱精品视频在线9| 久久免费观看电影| 热re99久久精品国产66热6| 1024视频免费在线观看| 在线免费观看不下载黄p国产| 欧美日韩成人在线一区二区| 水蜜桃什么品种好| 成年美女黄网站色视频大全免费| 欧美日韩av久久| 欧美精品一区二区大全| 日本欧美国产在线视频| 中文字幕人妻丝袜制服| 91精品国产国语对白视频| 免费观看人在逋| 夜夜骑夜夜射夜夜干| 满18在线观看网站| 国产精品99久久99久久久不卡 | 9热在线视频观看99| 最近最新中文字幕大全免费视频 | 国产精品国产三级国产专区5o| 国产精品成人在线| 国产精品一二三区在线看| 两性夫妻黄色片| 晚上一个人看的免费电影| 久久免费观看电影| 午夜日韩欧美国产| 男女免费视频国产| 最近手机中文字幕大全| 天天添夜夜摸| 午夜福利影视在线免费观看| 高清视频免费观看一区二区| 少妇猛男粗大的猛烈进出视频| 国产成人午夜福利电影在线观看| 欧美精品av麻豆av| 人妻一区二区av| 人人妻人人添人人爽欧美一区卜| 考比视频在线观看| 观看美女的网站| 国产在线视频一区二区| 国产视频首页在线观看| 欧美黄色片欧美黄色片| 久久韩国三级中文字幕| 欧美日韩亚洲综合一区二区三区_| 婷婷色综合www| 男女下面插进去视频免费观看| 日本欧美国产在线视频| 午夜福利网站1000一区二区三区| 中文乱码字字幕精品一区二区三区| 亚洲欧美精品自产自拍| 国产在视频线精品| 国产免费福利视频在线观看| 亚洲欧美中文字幕日韩二区| 国产精品 国内视频| 国产精品国产三级国产专区5o| 国产精品偷伦视频观看了| 老司机靠b影院| 人人妻人人澡人人看| 国产亚洲精品第一综合不卡| 大码成人一级视频| 80岁老熟妇乱子伦牲交| 91老司机精品| 国产成人精品福利久久| 最近手机中文字幕大全| 1024视频免费在线观看| 欧美日韩亚洲高清精品| 一本—道久久a久久精品蜜桃钙片| 精品人妻在线不人妻| 亚洲av电影在线观看一区二区三区| 女人久久www免费人成看片| 不卡av一区二区三区| 18在线观看网站| 久久久久久久国产电影| 中文字幕色久视频| 1024香蕉在线观看| 最近中文字幕高清免费大全6| 国产精品av久久久久免费| 亚洲欧美中文字幕日韩二区| 天天躁夜夜躁狠狠久久av| 少妇人妻精品综合一区二区| 男女边摸边吃奶| 性色av一级| av福利片在线| 久久久国产欧美日韩av| 国产精品免费大片| 久久亚洲国产成人精品v| 丁香六月欧美| 在线天堂最新版资源| 亚洲一区中文字幕在线| 亚洲人成电影观看| 在线亚洲精品国产二区图片欧美| 精品久久久久久电影网| 天天躁狠狠躁夜夜躁狠狠躁| 多毛熟女@视频| 国产成人一区二区在线| 国产av国产精品国产| 香蕉丝袜av| a 毛片基地| 国产 一区精品| 91成人精品电影| svipshipincom国产片| 十八禁网站网址无遮挡| 天天躁日日躁夜夜躁夜夜| 久久99一区二区三区| 久久久精品区二区三区| 精品国产一区二区久久| 美女中出高潮动态图| 精品一区二区三区av网在线观看 | 久久久久精品久久久久真实原创| 热99久久久久精品小说推荐| 亚洲自偷自拍图片 自拍| 日本午夜av视频| 午夜福利一区二区在线看| 欧美人与性动交α欧美软件| 久久久久精品久久久久真实原创| 黄片小视频在线播放| 下体分泌物呈黄色| 国产97色在线日韩免费| 岛国毛片在线播放| 一区二区三区激情视频| 国产激情久久老熟女|