本文選題：高維數(shù)據(jù) + 決策樹　； 參考：《中國科學(xué)技術(shù)大學(xué)》2017年碩士論文

【摘要】：從數(shù)據(jù)中挖掘知識和信息已成為解決許多實(shí)際問題的重要手段。決策樹是最常用的數(shù)據(jù)挖掘算法之一。但現(xiàn)有決策樹算法處理高維數(shù)據(jù)時存在計算量大、資源占用多的缺點(diǎn)。本論文面向高維數(shù)據(jù),研究決策樹的快速構(gòu)造方法。首先,為減少構(gòu)建決策樹的計算量,我們提出了基于混淆度的啟發(fā)式?jīng)Q策樹構(gòu)建算法。該算法利用父節(jié)點(diǎn)的計算結(jié)果估計部分子節(jié)點(diǎn)的上界,從而削減了找到子節(jié)點(diǎn)最優(yōu)解的計算量。實(shí)驗(yàn)結(jié)果表明無論是單棵決策樹還是集成決策樹,該算法都不會對決策樹的模型準(zhǔn)確度、概念簡潔性造成負(fù)面影響,并且在數(shù)據(jù)維度大于1000的高維情形下可以降低約70%的計算量。其次,為優(yōu)化決策樹構(gòu)建過程中的資源占用和磁盤負(fù)載,我們提出了一種基于橫縱劃分的決策樹并行構(gòu)造方式。和傳統(tǒng)方法相比,該方法的集群內(nèi)存占用量從O(T)降為O(√T),其中T是并行進(jìn)程數(shù)。對應(yīng)的單并行進(jìn)程的內(nèi)存占用量從O(1)降至O(1/√T),即集群的擴(kuò)大和并行數(shù)的增加可以降低單進(jìn)程的內(nèi)存占用量。數(shù)學(xué)分析和實(shí)驗(yàn)結(jié)果表明,該方法對網(wǎng)絡(luò)通信量、磁盤讀寫量、計算量沒有負(fù)面影響,并且在不同規(guī)模的集群上都取得了良好的并行效率。
[Abstract]:Mining knowledge and information from data has become an important means to solve many practical problems. Decision tree is one of the most commonly used data mining algorithms. However, the existing decision tree algorithms have the disadvantages of large computation and large resource consumption in dealing with high dimensional data. In this paper, the fast construction method of decision tree is studied for high dimensional data. Firstly, in order to reduce the computational cost of constructing decision tree, we propose a heuristic decision tree construction algorithm based on degree of confusion. In this algorithm, the upper bound of some child nodes is estimated by the result of the calculation of the parent node, thus reducing the computational cost of finding the optimal solution of the child node. The experimental results show that neither single decision tree nor integrated decision tree has a negative effect on the model accuracy and conciseness of the decision tree. And the computation can be reduced by about 70% when the data dimension is larger than 1000. Secondly, in order to optimize the resource occupation and disk load in the process of constructing decision tree, we propose a parallel construction method of decision tree based on horizontal and vertical partition. Compared with the traditional method, the cluster memory footprint of the proposed method is reduced from OT to O (T ~ 2, where T is the number of parallel processes). The memory footprint of the corresponding single parallel process is reduced from O1) to O1 / m2, that is, the expansion of cluster and the increase of parallel number can reduce the memory footprint of single process. The mathematical analysis and experimental results show that the proposed method has no negative effect on network traffic, disk read and write, and computation, and achieves good parallel efficiency on clusters of different scales.
【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP311.13

【相似文獻(xiàn)】

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

1 肖化昆;;一種高維數(shù)據(jù)類模板的設(shè)計方法與應(yīng)用[J];計算機(jī)科學(xué);2006年08期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 本報記者 李雙藝;引領(lǐng)高維數(shù)據(jù)分析先河[N];吉林日報;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 路梅;面向高維數(shù)據(jù)的特征學(xué)習(xí)理論與應(yīng)用研究[D];蘇州大學(xué);2016年

5 徐微微;高維數(shù)據(jù)降維可視化研究及其在生物醫(yī)學(xué)中的應(yīng)用[D];武漢大學(xué);2016年

6 連亦e，

本文編號：1803981