基于不均勻數(shù)據(jù)的密度偏差抽樣改進(jìn)算法

呂丹+龍華+高杰+邵玉斌+杜慶治

摘 要：針對(duì)不均勻數(shù)據(jù)集的抽樣問題，已有隨機(jī)抽樣算法、基于固定網(wǎng)格劃分的單維度算法、基于可變網(wǎng)格劃分的單維度算法，但仍無法更好地反映數(shù)據(jù)分布特征問題。在數(shù)據(jù)挖掘的實(shí)際應(yīng)用中，數(shù)據(jù)規(guī)模越來越大，數(shù)據(jù)類型也越來越復(fù)雜，存在系統(tǒng)整體開銷大、時(shí)間運(yùn)行成本高等問題。提出并實(shí)現(xiàn)了基于不均勻數(shù)據(jù)的密度偏差抽樣改進(jìn)算法（IDDS），通過引入網(wǎng)格單元密度和三角函數(shù)，從而達(dá)到較好的密度偏差抽樣效果。實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，IDDS算法抽樣效果更好，提取的樣本質(zhì)量更高，有效保證了不均勻數(shù)據(jù)的分布特征。與原始的密度偏差抽樣算法（DDS）相比，應(yīng)用IDDS算法的效率更高。

關(guān)鍵詞：密度偏差抽樣算法（DDS）；POI信息；數(shù)據(jù)挖掘；三角函數(shù)

DOIDOI：10.11907/rjdk.172395

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2018）002-0077-03

0 引言

在大數(shù)據(jù)挖掘過程中，數(shù)據(jù)挖掘效率是評(píng)估數(shù)據(jù)挖掘技術(shù)的關(guān)鍵因素之一，而效率的提高涉及到許多方面。面對(duì)海量數(shù)據(jù)，合理有效地利用采樣技術(shù)可以在丟失少量數(shù)據(jù)的同時(shí)，提高整體挖掘效率[1]。密度偏差抽樣方法（DDS）是一種新的抽樣方法[2]，具有良好的抽樣效果。它是根據(jù)原始數(shù)據(jù)的分布特征來確定樣本數(shù)據(jù)[3]，所建立的樣本較好地實(shí)現(xiàn)了樣本數(shù)據(jù)和原始數(shù)據(jù)一致的分布特征，樣本質(zhì)量高，抗噪聲能力強(qiáng)[4-5]。它能夠自由切換高密度區(qū)或低密度區(qū)，比隨機(jī)抽樣算法具有更好的約簡效果。目前，劃分原始數(shù)據(jù)集組時(shí)，從網(wǎng)格類型角度看[6]，可以分為固定網(wǎng)格和可變網(wǎng)格兩種類型。固定網(wǎng)格劃分技術(shù)比較簡單，隨著數(shù)據(jù)維度和數(shù)量的增加，系統(tǒng)開銷增加，可用性也因此減少；可變網(wǎng)格劃分技術(shù)非常靈活[7]，在劃分過程中，可以根據(jù)各維數(shù)據(jù)的分布特征進(jìn)行自動(dòng)劃分，不僅能有效地減少網(wǎng)格數(shù)，還能代表原始數(shù)據(jù)的分布特征[8]。鑒于此，本文在DDS算法基礎(chǔ)上，提出了一種基于可變網(wǎng)格改進(jìn)的密度偏差抽樣算法（IDDS），通過引入網(wǎng)格單元密度和三角函數(shù)，從而達(dá)到較好的密度偏差抽樣效果。仿真實(shí)驗(yàn)結(jié)果表明，IDDS算法抽樣效果更好，提取的樣本質(zhì)量更高，有效保證了不均勻數(shù)據(jù)的分布特征。

1 密度偏差抽樣（DDS）原理

DDS算法[9]將原始數(shù)據(jù)集T分為不同的組Di，每個(gè)組Di中的數(shù)據(jù)個(gè)數(shù)為該組的密度，然后根據(jù)以下原理抽樣：劃分后的同一組內(nèi)各數(shù)據(jù)點(diǎn)被等概率抽??；不同小組的抽樣概率由各組密度決定；樣本集的分布特征與原始數(shù)據(jù)集一致；預(yù)先設(shè)定樣本數(shù)量大小。

2 算法介紹

2.1 隨機(jī)抽樣算法（RS）

隨機(jī)抽樣算法是對(duì)調(diào)查對(duì)象的每個(gè)部分進(jìn)行同等概率的抽樣，這是一種基于機(jī)會(huì)平等原則的抽樣調(diào)查，稱為“等概率”[10]。其有4種形式，包括簡單隨機(jī)抽樣算法、等距抽樣算法、類型抽樣算法和整群抽樣算法。一般而言，如果一個(gè)總體包含N個(gè)個(gè)體，通過逐個(gè)抽取的方法從每個(gè)樣本中提取樣本，并且每次提取時(shí)每個(gè)個(gè)體被抽到的概率相等，則將這種方法稱為簡單隨機(jī)抽樣算法[11]。

2.2 固定網(wǎng)格劃分的密度偏差抽樣方法（FMDDS）

固定網(wǎng)格劃分是將原始數(shù)據(jù)集T中的各個(gè)維度劃分成等長且互不相交的D個(gè)區(qū)間段，每個(gè)維度上劃分的區(qū)間數(shù)D相同（等長度網(wǎng)格劃分）。一般情況下，根據(jù)實(shí)驗(yàn)結(jié)果或用戶經(jīng)驗(yàn)設(shè)置D的大小。

2.3 可變網(wǎng)格劃分的密度偏差抽樣方法（VDDS）

可變網(wǎng)格比固定網(wǎng)格劃分更為靈活[12]，劃分后的網(wǎng)格更能代表原始數(shù)據(jù)的分布特性。其基本思想是，首先根據(jù)數(shù)值大小對(duì)原始數(shù)據(jù)集T中每個(gè)維度的數(shù)據(jù)進(jìn)行排序（降序或升序），其次是等深度劃分排序后的數(shù)據(jù)，劃分成多個(gè)網(wǎng)格單元，然后計(jì)算網(wǎng)格單元的密度信息，并通過比較合并各維度上相似密度的相鄰網(wǎng)格單元[13]。在此基礎(chǔ)上，使最后形成的網(wǎng)格空間中的網(wǎng)格個(gè)數(shù)有很大不同。

3 基于可變網(wǎng)格改進(jìn)的密度偏差抽樣算法（IDDS）

3.1 算法思想

在DDS原理中，參數(shù)k是控制全局的參數(shù)，其數(shù)值對(duì)最后采樣結(jié)果有著重要影響。根據(jù)現(xiàn)有相關(guān)文獻(xiàn)的研究結(jié)果來看，參數(shù)k通常默認(rèn)為固定值0.5。參數(shù)k的固定設(shè)置有很大的局限性，主要體現(xiàn)在難以適應(yīng)于各類數(shù)據(jù)集的固定參數(shù)。在本文中，通過引入網(wǎng)格密度和三角函數(shù)來優(yōu)化參數(shù)k，與固定值參數(shù)k相比，改進(jìn)后的參數(shù)k具有更好的抽樣效果。通過設(shè)置相應(yīng)函數(shù)，在s、t不變的情況下，根據(jù)網(wǎng)格密度mi來調(diào)整參數(shù)k大小，即網(wǎng)格單元密度越大，網(wǎng)格采樣樣本越多，修改的參數(shù)k如下：

3.2 算法實(shí)現(xiàn)

4 實(shí)驗(yàn)過程及結(jié)果

4.1 實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)環(huán)境

為了驗(yàn)證提出的IDDS算法的優(yōu)越性，基于Matlab2009b仿真工具對(duì)不均勻數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)和分析，實(shí)現(xiàn)密度偏差抽樣的計(jì)算。實(shí)驗(yàn)環(huán)境為一臺(tái)Windows 8.0操作系統(tǒng)的PC機(jī)，1.6GHz的Intel Core i5處理器和4GB的RAM。

實(shí)驗(yàn)中的不均勻數(shù)據(jù)集是通過Matlab中相關(guān)函數(shù)隨機(jī)產(chǎn)生的，產(chǎn)生了3組數(shù)據(jù)集，包括6 000條矩形數(shù)據(jù)集，9 000條三角形數(shù)據(jù)集，5 000條橢圓形數(shù)據(jù)集，總共20 000條數(shù)據(jù)，各數(shù)據(jù)集間密度都有差異。

4.2 實(shí)驗(yàn)過程

本文選取了隨機(jī)抽樣算法（RS）、基于可變網(wǎng)格劃分的單維密度偏差抽樣算法（VDDS）以及基于可變網(wǎng)格劃分改進(jìn)的單維密度偏差抽樣算法（IDDS）進(jìn)行實(shí)驗(yàn)分析，通過算法的運(yùn)行時(shí)間和抽樣結(jié)果比較，驗(yàn)證IDDS算法的有效性。除RS算法外，其余兩種算法在網(wǎng)格劃分前各維度都根據(jù)式（14）～（16）進(jìn)行歸一化處理，然后計(jì)算歸一化后的均方差，最后選取最小均方差維度劃分可變網(wǎng)格。根據(jù)改進(jìn)算法，通過仿真測試分析，本文中的s、t分別設(shè)置為0.5、0.8，改進(jìn)后的參數(shù)k為：ki=0.5-0.8cos（miπ2m），在VDDS算法中k設(shè)置為0.5。endprint

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

為了保證實(shí)驗(yàn)結(jié)果的公正性，對(duì)50次抽樣結(jié)果進(jìn)行平均值計(jì)算，實(shí)驗(yàn)結(jié)果如表1、圖2所示。

表1顯示了3種算法的抽樣結(jié)果，圖2則顯示了3種算法的運(yùn)行時(shí)間。由表1可知，IDDS算法的抽樣效果明顯比VDDS算法、RS算法好，抽取樣本質(zhì)量更高，有效保持了原始數(shù)據(jù)集的分布特征，且抗噪聲能力更強(qiáng)。由圖2可知，RS算法相比于其它算法，運(yùn)算量最小，所以運(yùn)行時(shí)間最短。另外，IDDS算法運(yùn)行時(shí)間大于VDDS算法。由此可見，改進(jìn)后的算法運(yùn)算量相對(duì)于未改進(jìn)前略大，運(yùn)算時(shí)間也略多。綜上述，本文提出的IDDS算法雖然在運(yùn)行時(shí)間上存在一定劣勢，但從樣本質(zhì)量看，仍具有一定的合理性和可行性。

5 結(jié)語

本文基于不均勻數(shù)據(jù)探索一種改進(jìn)的密度偏差抽樣算法（IDDS），使用Matlab中的相關(guān)函數(shù)隨機(jī)產(chǎn)生不均勻數(shù)據(jù)集，對(duì)其進(jìn)行歸一化處理，計(jì)算均方差，選取最小均方差維度劃分可變網(wǎng)格。在保證數(shù)據(jù)間關(guān)聯(lián)性不被破壞的同時(shí)，確保了樣本數(shù)據(jù)和原始數(shù)據(jù)的一致性分布特征，解決了不均勻數(shù)據(jù)集的抽樣問題，最后通過仿真實(shí)驗(yàn)驗(yàn)證并分析了算法的合理性。

參考文獻(xiàn)：

[1] 何苗.一種基于DBS的聚類算法[J].重慶電子工程職業(yè)學(xué)院學(xué)報(bào)，2009，18（3）：83-85.

[2] 余建橋，葛繼科，李婭.一種基于密度偏差抽樣的孤立點(diǎn)檢測算法[J].計(jì)算機(jī)科學(xué)，2004，31（10）：206-208.

[3] XIAO-BO CHI，XIN-CHUN JIA，QING-LONG HAN.Sampled-data stabilization for takagi-sugeno fuzzy systems using membership function deviations[C].IECON 2012-38th Annual Conference on IEEE Industrial Electronics Society，2012：2476-2481.

[4] PEIGUO FU，XIAOHUI HU.Biased-sampling of density-based local outlier detection algorithm[J].2016 12th International Conference on Natural Computation，F(xiàn)uzzy Systems and Knowledge Discovery （ICNC-FSKD），2016：1246-1253.

[5] KITTISAK KERDPRASOP，NITTAYA KERDPRASOP，JUNPING SUN.Density biased reservoir sampling for clustering[J].Artificial Intelligence and Applications，2005：95-100.

[6] 鄧杰.聚類算法在大規(guī)模高維數(shù)據(jù)集上的應(yīng)用研究[D].無錫：江南大學(xué)，2015.

[7] 盛開元，錢雪忠，吳秦.基于可變網(wǎng)格劃分的密度偏差抽樣算法[J].計(jì)算機(jī)應(yīng)用，2013，33（9）：2419-2422.

[8] 余波，朱東華，劉嵩，等.密度偏差抽樣技術(shù)在聚類算法中的應(yīng)用研究[J].計(jì)算機(jī)科學(xué)，2009，36（2）：207-210.

[9] 熊開玲，彭俊杰，楊曉飛，等.基于核密度估計(jì)的K-means聚類優(yōu)化[J].計(jì)算機(jī)技術(shù)與發(fā)展，2017，27（2）：1-5.

[10] 周慶元.PPS和簡單隨機(jī)抽樣估計(jì)效率的實(shí)證檢驗(yàn)[J].統(tǒng)計(jì)與決策，2014（1）：14-17.

[11] 劉愛芹.隨機(jī)抽樣中樣本容量確定的影響因素分析[J].山東財(cái)政學(xué)院學(xué)報(bào)，2006（5）：60-64.

[12] 潘春燕，吳有富，李方.一種基于可變網(wǎng)格劃分的密度偏差抽樣技術(shù)及其在聚類中的應(yīng)用研究[J].凱里學(xué)院學(xué)報(bào)，2017，35（3）：16-20.

[13] 胡志冬，任永功，楊雪.基于滑動(dòng)窗口密度聚類的數(shù)據(jù)流偏倚采樣算法[J].計(jì)算機(jī)科學(xué)，2013，40（9）：254-256.

[14] 紀(jì)良浩.基于密度偏差抽樣的聚類算法研究[J].重慶郵電大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，19（6）：729-732.endprint