本文關(guān)鍵詞：高維數(shù)據(jù)流上的K近鄰問題研究　出處：《山東大學(xué)》2016年博士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 高維數(shù)據(jù) 數(shù)據(jù)流 K近鄰 索引

【摘要】：隨著計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)的發(fā)展,數(shù)據(jù)收集變得越來越容易,數(shù)據(jù)的規(guī)模和復(fù)雜性越來越高,數(shù)據(jù)的維度(屬性)也越來越高。通常情況下各種類型的數(shù)據(jù),如Web文檔、圖片、基因表達(dá)數(shù)據(jù)及多媒體數(shù)據(jù)等,可以通過一些特征抽取的方法被表示成高維的向量(或者高維空間中的點(diǎn))。數(shù)據(jù)庫、信息檢索和數(shù)據(jù)挖掘等領(lǐng)域的一個(gè)常見操作,就是在一個(gè)對象集中找到某個(gè)查詢(或某個(gè)查詢集中所有查詢)的最相似的K個(gè)對象,如果用一個(gè)距離度量(如歐式距離)來衡量相似度,這個(gè)操作就可以轉(zhuǎn)化為求高維空間K近鄰(或K近鄰連接)的問題,即在一個(gè)對象集中查找離查詢點(diǎn)(或一個(gè)查詢集中的每個(gè)點(diǎn))距離最近的K個(gè)對象。目前高維空間中的K近鄰和K近鄰連接算法主要針對靜態(tài)的數(shù)據(jù)集,而越來越多的應(yīng)用需要在數(shù)據(jù)流上連續(xù)不斷地獲得查詢結(jié)果,這就對高維K近鄰(及連接)問題提出了新的挑戰(zhàn)。本文對高維數(shù)據(jù)流上的K近鄰相關(guān)問題進(jìn)行了研究。首先,我們研究了高維數(shù)據(jù)流上的連續(xù)K近鄰連接問題。由于被查詢點(diǎn)集在數(shù)據(jù)流上會(huì)不斷發(fā)生變化,因此查詢集的K近鄰連接結(jié)果需要實(shí)時(shí)更新。本文提出采用增量更新策略：先求解更新點(diǎn)的反向K近鄰結(jié)果,即查詢集中K近鄰結(jié)果會(huì)受更新點(diǎn)影響的那些查詢,然后只更新這一部分查詢的K近鄰結(jié)果,以避免重復(fù)計(jì)算。本文提出了一種新的索引結(jié)——HDR-樹,來提高求解更新點(diǎn)的反向K近鄰結(jié)果的效率。HDR-樹主要利用主成分分析(PCA)降維和聚類劃分的技術(shù)來提高查詢效率。進(jìn)一步地,由于在大多數(shù)的應(yīng)用下,求得近似K近鄰連接查詢結(jié)果也是可以接受的,本文研究了在高維數(shù)據(jù)流上近似地得到K近鄰連接結(jié)果的方法,以進(jìn)一步減少處理時(shí)間。本文提出了兩種近似K近鄰連接的索引結(jié)構(gòu)和算法：HDR*-樹和LSH-M。HDR*-樹結(jié)合了隨機(jī)投影降維和聚類技術(shù),由于隨機(jī)投影降維后的數(shù)據(jù)能夠近似保留原數(shù)據(jù)點(diǎn)之間的距離關(guān)系,HDR*-樹在求解受更新點(diǎn)影響的查詢點(diǎn)時(shí)具有更高的效率。LSH-M則利用了局部敏感哈希的思想來構(gòu)建索引,并提供有準(zhǔn)確率保障的快速檢索。本文分析了兩種方法的查詢準(zhǔn)確率,并用實(shí)驗(yàn)結(jié)果驗(yàn)證了它們的效率。最后,為了進(jìn)一步提高查詢效率和可擴(kuò)展性,本文研究了高維數(shù)據(jù)流上的分布式K近鄰(及連接)查詢的問題,并設(shè)計(jì)了分布式索引和查詢算法來提高查詢效率。本文提出了一個(gè)新的索引結(jié)構(gòu),叫作動(dòng)態(tài)環(huán)索引(Dynamic Bounded Rings Index),它首先找到一個(gè)參照點(diǎn)集,把數(shù)據(jù)流上的點(diǎn)分配到最近的參照點(diǎn),然后對每個(gè)參照點(diǎn)上的數(shù)據(jù)子集按照到參照點(diǎn)的距離進(jìn)一步劃分到更細(xì)粒度的有界環(huán)型內(nèi),環(huán)的邊界可以動(dòng)態(tài)維護(hù)以適應(yīng)數(shù)據(jù)流上點(diǎn)的不斷更新,并且由于每個(gè)動(dòng)態(tài)環(huán)可以分配到不同的節(jié)點(diǎn)上處理,它可以很容易地應(yīng)用到分布式環(huán)境中。在動(dòng)態(tài)環(huán)索引的基礎(chǔ)上,本文設(shè)計(jì)了分布式高維K近鄰查詢算法,該算法的主要優(yōu)點(diǎn)是在只進(jìn)行兩次迭代的情況下就能得到準(zhǔn)確的K近鄰結(jié)果,減少了在分布式環(huán)境中進(jìn)行K近鄰查詢的通信代價(jià)和計(jì)算代價(jià)。本文將提出的索引和算法在開源的分布式流處理平臺(tái)Apache Storm上進(jìn)行了實(shí)現(xiàn),在真實(shí)數(shù)據(jù)集和模擬數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果都顯示我們的算法對比已有的基準(zhǔn)方法在查詢效率上有很大提升。
[Abstract]:With the development of computer and network technology, data collection becomes more and more easy, the size of the data and more complex data, the dimensions (attributes) are increasingly high. Usually, various types of data, such as Web documents, pictures, gene expression data and multimedia data, through the method of characteristics the extraction is represented as a high-dimensional vector (or points in high dimensional space). A common operation database, information retrieval and data mining, is a focus to find a query (or a set of queries in all queries) is most similar to the K object, if a distance metric (e.g. Euclidean distance) to measure the similarity, this operation can be converted to a high dimensional space (K or K nearest neighbor neighbor connection) problem, namely in a focused search from the query point (each point or a query set distance) In the K object. At present in the high dimensional space of K nearest neighbor and K nearest neighbor joining algorithm is mainly based on the static data sets, and more and more applications in data stream continuously get the query results, the high dimensional K nearest neighbor (and connected) has brought new challenges. This paper study on related problems of K nearest neighbor flow on high dimensional data. Firstly, we study the continuous K nearest neighbor high dimensional data stream connection problem. Because the query point sets in data streams will change constantly, so the query K nearest neighbor set connection results need to be updated in real time. This paper proposed the incremental update strategy: the first is to update the reverse K nearest neighbor points, those queries that query results will be updated by the K nearest neighbors of the K nearest neighbor results and then update only this part of the query, to avoid repeated calculation. This paper proposes a new index node - H DR- tree, to improve the solution of reverse K nearest neighbor results point to the updating efficiency of.HDR- tree by using principal component analysis (PCA) dimension reduction clustering technology to improve query efficiency. Further, because in most applications, the approximate K nearest neighbor query results can also be connected to accept the method were studied in this paper. High dimensional data stream is approximately K neighbor connection results, to further reduce the processing time. This paper presents two kinds of index structure and algorithm of approximate K nearest neighbor connect: HDR*- tree and LSH-M.HDR*- tree with random projection dimensionality reduction and clustering technology, the random projection dimensionality reduction data can keep approximate distance between the original data points, the HDR*- tree by the update effect in solving the query point has higher efficiency of.LSH-M by using the locality sensitive hashing method to construct the index, and provide the accurate rate of insurance Fast retrieval system. This paper analyzes two methods of query accuracy, and verify their efficiency with the experimental results. Finally, in order to further improve the query efficiency and scalability, this paper studies the distributed K nearest neighbor on the high dimensional data stream (and connected) query, and design a distributed index and the query algorithm to improve the query efficiency. This paper proposes a new index structure, called dynamic ring index (Dynamic Bounded Rings Index), it is first to find a reference point set, the data flow on the points assigned to the nearest reference point, then for each subset of data points on the reference according to the reference point the distance is further divided into more fine-grained bounded ring, ring boundary can be maintained dynamically in order to adapt to the data flow on the update, and because each dynamic ring can be assigned to different nodes, it can be Easily applied to distributed environment. Based on dynamic ring index, this paper designs a distributed high dimensional K nearest neighbor query algorithm, the main advantage of this algorithm is in only two iterations can be obtained under the condition of K nearest neighbor accurate result, reduces the communication cost and computation cost for nearest neighbor queries in distributed K in the environment. This paper will put forward the index and algorithm in open distributed stream processing platform Apache Storm is achieved in real and synthetic data sets. The experimental results show our algorithm compared with the existing reference methods have greatly improved the efficiency of query processing.

【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：TP311.13

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 賀玲;蔡益朝;楊征;;高維數(shù)據(jù)空間的一種網(wǎng)格劃分方法[J];計(jì)算機(jī)工程與應(yīng)用;2011年05期

2 李郁林;;高維數(shù)據(jù)分析中的降維研究[J];計(jì)算機(jī)光盤軟件與應(yīng)用;2012年17期

3 何進(jìn)榮;丁立新;胡慶輝;李照奎;;高維數(shù)據(jù)空間的性質(zhì)及度量選擇[J];計(jì)算機(jī)科學(xué);2014年03期

4 劉洪波,王秀坤,趙晶;高維數(shù)據(jù)空間金字塔技術(shù)研究[J];計(jì)算機(jī)工程與應(yīng)用;2003年16期

5 沈萍;;高維數(shù)據(jù)挖掘技術(shù)研究[J];電腦知識與技術(shù);2009年06期

6 謝楓平;;聚類分析中的高維數(shù)據(jù)降維方法研究[J];閩西職業(yè)技術(shù)學(xué)院學(xué)報(bào);2009年04期

7 余元輝;鄧瑩;;一種新的高維數(shù)據(jù)聚類自適應(yīng)算法的研究[J];沈陽化工大學(xué)學(xué)報(bào);2010年02期

8 王寅峰;劉昊;狄盛;胡昊宇;;一種支持高維數(shù)據(jù)查詢的并行索引機(jī)制[J];華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年S1期

9 周勇;盧曉偉;程春田;;非規(guī)則流中高維數(shù)據(jù)流典型相關(guān)性分析并行計(jì)算方法[J];軟件學(xué)報(bào);2012年05期

10 王素芳;;基于組件的高維數(shù)據(jù)降維方法研究[J];電腦與電信;2012年10期

相關(guān)會(huì)議論文 前6條

1 周煜人;彭輝;桂衛(wèi)華;;基于映射的高維數(shù)據(jù)聚類方法[A];04'中國企業(yè)自動(dòng)化和信息化建設(shè)論壇暨中南六省區(qū)自動(dòng)化學(xué)會(huì)學(xué)術(shù)年會(huì)專輯[C];2004年

2 梁俊杰;楊澤新;馮玉才;;大規(guī)模高維數(shù)據(jù)庫索引結(jié)構(gòu)[A];第二十三屆中國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2006年

3 陳冠華;馬秀莉;楊冬青;唐世渭;帥猛;;面向高維數(shù)據(jù)的低冗余Top-k異常點(diǎn)發(fā)現(xiàn)方法[A];第26屆中國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（A輯）[C];2009年

4 劉運(yùn)濤;鮑玉斌;吳丹;冷芳玲;孫煥良;于戈;;CBFrag-Cubing:一種基于壓縮位圖的高維數(shù)據(jù)立方創(chuàng)建算法(英文)[A];第二十二屆中國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2005年

5 劉文慧;;PCA與PLS用于高維數(shù)據(jù)分類的比較性研究[A];2011年中國衛(wèi)生統(tǒng)計(jì)學(xué)年會(huì)會(huì)議論文集[C];2011年

6 劉喜蘭;馮德益;王公恕;朱成喜;馮雯;;臉譜分析在中進(jìn)期地震跟蹤預(yù)報(bào)中的應(yīng)用[A];中國地震學(xué)會(huì)第四次學(xué)術(shù)大會(huì)論文摘要集[C];1992年

相關(guān)重要報(bào)紙文章 前1條

1 本報(bào)記者 李雙藝;引領(lǐng)高維數(shù)據(jù)分析先河[N];吉林日報(bào);2013年

相關(guān)博士學(xué)位論文 前10條

1 劉勝藍(lán);余弦度量下的高維數(shù)據(jù)降維及分類方法研究[D];大連理工大學(xué);2015年

2 黃曉輝;高維數(shù)據(jù)的若干聚類問題及算法研究[D];哈爾濱工業(yè)大學(xué);2015年

3 楊崇;高維數(shù)據(jù)流上的K近鄰問題研究[D];山東大學(xué);2016年

4 楊風(fēng)召;高維數(shù)據(jù)挖掘中若干關(guān)鍵問題的研究[D];復(fù)旦大學(xué);2003年

5 陳黎飛;高維數(shù)據(jù)的聚類方法研究與應(yīng)用[D];廈門大學(xué);2008年

6 吳慶耀;高維數(shù)據(jù)的若干分類問題及算法研究[D];哈爾濱工業(yè)大學(xué);2013年

7 樓巍;面向大數(shù)據(jù)的高維數(shù)據(jù)挖掘技術(shù)研究[D];上海大學(xué);2013年

8 黃健美;高維數(shù)據(jù)索引及其查詢處理技術(shù)研究[D];東北大學(xué);2009年

9 任亞洲;高維數(shù)據(jù)上的聚類方法研究[D];華南理工大學(xué);2014年

10 董道國;高維數(shù)據(jù)索引結(jié)構(gòu)研究[D];復(fù)旦大學(xué);2005年

相關(guān)碩士學(xué)位論文 前10條

1 沈江炎;基于軟子空間的高維數(shù)據(jù)樹形索引研究[D];昆明理工大學(xué);2015年

2 侯小麗;高維數(shù)據(jù)聚類中的神經(jīng)網(wǎng)絡(luò)降維方法研究[D];蘭州大學(xué);2015年

3 趙俊琴;基于Lasso的高維數(shù)據(jù)線性回歸模型統(tǒng)計(jì)推斷方法比較[D];山西醫(yī)科大學(xué);2015年

4 何熒;高維數(shù)據(jù)下的特征選擇與聚類方法研究[D];西南大學(xué);2015年

5 胡昌杰;基于Autoencoder的高維數(shù)據(jù)降維方法研究[D];蘭州大學(xué);2015年

6 楊代君;基于進(jìn)化算法的高維數(shù)據(jù)聚類研究[D];西安電子科技大學(xué);2014年

7 王宏霞;交通高維數(shù)據(jù)邏輯整合與降解研究[D];重慶交通大學(xué);2015年

8 楊庭庭;基于信息熵的高維數(shù)據(jù)流聚類及其應(yīng)用研究[D];重慶交通大學(xué);2015年

9 孫喜利;高維數(shù)據(jù)的降維及聚類方法研究[D];蘭州大學(xué);2016年

10 吳佳妮;基于SVM的質(zhì)譜細(xì)胞儀高維數(shù)據(jù)分析在AML早期診斷方面的應(yīng)用研究[D];山東大學(xué);2016年

，

本文編號：1365336