[發(fā)明專(zhuān)利]一種基于MapReduce的K近鄰數(shù)據(jù)預(yù)測(cè)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410803550.7
• 申請(qǐng)日: 2014-12-19
• 公開(kāi)（公告）號(hào): CN104573331B
• 公開(kāi)（公告）日: 2018-04-24
• 發(fā)明（設(shè)計(jì)）人: 薛濤;孫兵率
• 申請(qǐng)（專(zhuān)利權(quán)）人: 西安工程大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 西安弘理專(zhuān)利事務(wù)所61214
• 代理人: 羅笛

技術(shù)領(lǐng)域

本發(fā)明屬于數(shù)據(jù)挖掘技術(shù)領(lǐng)域，涉及一種基于MapReduce的K近鄰數(shù)據(jù)預(yù)測(cè)方法。

背景技術(shù)

線(xiàn)性回歸預(yù)測(cè)作為數(shù)據(jù)挖掘中的統(tǒng)計(jì)、預(yù)測(cè)方法之一，在科研、商業(yè)數(shù)據(jù)分析中占據(jù)著重要的地位。傳統(tǒng)的線(xiàn)性回歸預(yù)測(cè)屬于參數(shù)學(xué)習(xí)算法，其參數(shù)是固定不變的，而在實(shí)際應(yīng)運(yùn)中，數(shù)據(jù)的生成機(jī)制與線(xiàn)性回歸模型有很大偏差，這樣得出的分析數(shù)據(jù)往往與實(shí)際有很大出入，甚至是錯(cuò)誤的數(shù)據(jù)。局部加權(quán)線(xiàn)性回歸預(yù)測(cè)方法是一種非參數(shù)回歸技術(shù)，它允許線(xiàn)性回歸模型中的參數(shù)隨著自變量的不同取值而變化。在大數(shù)據(jù)時(shí)代，傳統(tǒng)的線(xiàn)性回歸預(yù)測(cè)方法和局部加權(quán)線(xiàn)性回歸預(yù)測(cè)方法，繁瑣的計(jì)算步驟和效率極低的單機(jī)串行計(jì)算，已經(jīng)無(wú)法繼續(xù)勝任對(duì)數(shù)據(jù)進(jìn)行挖掘和處理，對(duì)大規(guī)模數(shù)據(jù)的挖掘和處理能力存在著很大的局限性。

MapReduce編程模型是Google公司的核心計(jì)算模型，被應(yīng)用于大規(guī)模集群上的復(fù)雜的并行計(jì)算。Hadoop是Apache軟件基金會(huì)旗下的一個(gè)開(kāi)源分布式計(jì)算平臺(tái)，該平臺(tái)開(kāi)源實(shí)現(xiàn)了MapReduce編程模型。K近鄰(K-Nearest Neighbor)是一種簡(jiǎn)潔而有效的非參數(shù)學(xué)習(xí)方法。K近鄰方法對(duì)每一個(gè)輸入都會(huì)去訓(xùn)練數(shù)據(jù)集中去搜索與其最相似的K個(gè)數(shù)據(jù)對(duì)象，在K近鄰學(xué)習(xí)過(guò)程中，當(dāng)目標(biāo)函數(shù)值為連續(xù)值時(shí)，對(duì)待預(yù)測(cè)數(shù)據(jù)搜索出的K個(gè)近鄰點(diǎn)，分別給定一個(gè)距離加權(quán)，是一種簡(jiǎn)單可靠的變參回歸預(yù)測(cè)方法。當(dāng)訓(xùn)練數(shù)據(jù)達(dá)到海量規(guī)模時(shí)，K近鄰的搜索效率將很難達(dá)到實(shí)際需求，而且海量的數(shù)據(jù)對(duì)于目前的計(jì)算機(jī)處理速度和內(nèi)存空間也是一種挑戰(zhàn)。

發(fā)明內(nèi)容

本發(fā)明的目的是提供一種基于MapReduce的K近鄰數(shù)據(jù)預(yù)測(cè)方法，解決了傳統(tǒng)預(yù)測(cè)方法參數(shù)固定，數(shù)據(jù)處理精準(zhǔn)度差以及對(duì)大規(guī)模數(shù)據(jù)的回歸預(yù)測(cè)處理能力存在局限性的問(wèn)題。

本發(fā)明所采用的技術(shù)方案是，一種基于MapReduce的K近鄰數(shù)據(jù)預(yù)測(cè)方法，包括如下步驟：

步驟1、確定訓(xùn)練數(shù)據(jù)和待測(cè)試數(shù)據(jù)，并將訓(xùn)練數(shù)據(jù)上傳至Hadoop分布式集群，分散至各集群節(jié)點(diǎn)中存儲(chǔ)；

步驟2、在Hadoop分布式集群中各個(gè)節(jié)點(diǎn)的Mapper端，設(shè)計(jì)Map函數(shù)：根據(jù)歐式距離計(jì)算公式，計(jì)算出待預(yù)測(cè)數(shù)據(jù)與本節(jié)點(diǎn)部分訓(xùn)練數(shù)據(jù)樣本之間的距離；

步驟3、在Mapper端，將步驟2所得距離值發(fā)送至集群節(jié)點(diǎn)的Combiner端，設(shè)計(jì)Combine函數(shù)：進(jìn)行本地排序，選出局部距離最小的K個(gè)最近鄰點(diǎn)，得到局部K-最近鄰子集；

步驟4、在Combiner端，將步驟3所得的所有局部K-最近鄰子集，發(fā)送至Hadoop分布式集群各Reducer端，設(shè)計(jì)Reduce函數(shù)：對(duì)所有局部K-最近鄰子集進(jìn)行重新排序，得到全局K-最近鄰子集；利用距離加權(quán)方法，根據(jù)權(quán)重函數(shù)計(jì)算全局K-最近鄰子集中訓(xùn)練數(shù)據(jù)對(duì)待預(yù)測(cè)數(shù)值影響的權(quán)重大小；利用回歸函數(shù)，將所得權(quán)重值定義為回歸系數(shù)，計(jì)算得出待預(yù)測(cè)數(shù)據(jù)的預(yù)測(cè)值；

步驟5、將步驟4處理后的數(shù)據(jù)存儲(chǔ)在HDFS文件系統(tǒng)中，可用Hadoop相關(guān)查看工具查看或下載至本地。

本發(fā)明的特征還在于，

步驟2中，設(shè)計(jì)Map函數(shù)的過(guò)程為：函數(shù)輸入定義為<LongWritable key，Text text>，key為訓(xùn)練數(shù)據(jù)行號(hào)，text為記錄數(shù)據(jù)；輸出函數(shù)定義為<Context context>，定義類(lèi)Sample()，存儲(chǔ)數(shù)據(jù)間距離和此條訓(xùn)練數(shù)據(jù)目標(biāo)函數(shù)實(shí)際值；遍歷所有訓(xùn)練數(shù)據(jù)和待預(yù)測(cè)數(shù)據(jù)，計(jì)算其距離，并將距離值和訓(xùn)練數(shù)據(jù)的目標(biāo)函數(shù)值存入Sample()；輸出context.write(key’，sample())，key’為待預(yù)測(cè)數(shù)據(jù)行號(hào)。

步驟3中，設(shè)計(jì)Combine函數(shù)具體過(guò)程為：將函數(shù)輸入定義為<LongWritable key，Sample sample>，輸出定義為<Context context>；把所有的sample存入一個(gè)鏈表結(jié)構(gòu)里，arrayList.add(sample)；對(duì)arrayList進(jìn)行局部排序，執(zhí)行sort(arrayList)；從排好順序的arrayList中僅取出前K個(gè)sample，并輸出context.write(key，arrayList.get())。