[發(fā)明專利]對含噪聲點的實時數(shù)據(jù)流進(jìn)行聚類和聚類邊界界定的方法

無效

• 申請?zhí)枺?/td>: 201110318352.8
• 申請日: 2011-10-19
• 公開（公告）號: CN102495938A
• 公開（公告）日: 2012-06-13
• 發(fā)明（設(shè)計）人: 張曉龍;梁小波;曾偉
• 申請（專利權(quán)）人: 武漢科技大學(xué)
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 武漢開元知識產(chǎn)權(quán)代理有限公司 42104
• 代理人: 樊戎

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

本發(fā)明屬于數(shù)據(jù)流的數(shù)據(jù)處理技術(shù)領(lǐng)域。具體涉及一種對含噪聲點的實時數(shù)據(jù)流進(jìn)行聚類和聚類邊界界定的方法。

背景技術(shù)

對含噪聲點的實時數(shù)據(jù)流進(jìn)行聚類和聚類邊界界定的方法能夠提高聚類的精度和數(shù)據(jù)分類的精度，能快速發(fā)現(xiàn)實時數(shù)據(jù)流中的聚類和聚類邊界，也可對工業(yè)生產(chǎn)中的實時生產(chǎn)工藝數(shù)據(jù)進(jìn)行監(jiān)測，有助于生產(chǎn)設(shè)備和產(chǎn)品質(zhì)量監(jiān)控。目前，有關(guān)數(shù)據(jù)聚類邊界點的界定和檢測技術(shù)存在以下缺陷：(1)現(xiàn)有算法僅針對靜態(tài)數(shù)據(jù)集，提取界定聚類的邊界點，沒有針對實時數(shù)據(jù)流的聚類邊界的界定方法；(2)把聚類和邊界檢測兩者分開，分別進(jìn)行處理；(3)在大型數(shù)據(jù)處理中算法的復(fù)雜度高。

BORDER是一個有代表性的基于靜態(tài)數(shù)據(jù)集的聚類邊界點檢測算法，它利用數(shù)據(jù)的反向k-近鄰性質(zhì)來檢測邊界點。該算法首先計算數(shù)據(jù)集中每一個數(shù)據(jù)點的反向k-近鄰個數(shù)，然后根據(jù)每個對象的反向k-近鄰個數(shù)按從小到大的順序排列整個數(shù)據(jù)集中的數(shù)據(jù)點，把前n個數(shù)據(jù)點作為聚類的邊界點。BORDER算法在不含噪聲點的數(shù)據(jù)集中能夠檢測出聚類的邊界點，但其缺點是：(1)在含有噪聲的數(shù)據(jù)集中不能正確地識別出邊界點，因為噪聲點的反向k-近鄰個數(shù)比聚類邊界點的反向k-近鄰個數(shù)更少；(2)該算法要找出每個對象的k個最近鄰，進(jìn)而計算出每個對象的反向k-近鄰個數(shù)，算法的執(zhí)行效率不高；(3)需要用戶有先驗知識，給出數(shù)據(jù)集的邊界點個數(shù)n。

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

本發(fā)明能克服現(xiàn)有技術(shù)缺陷，目的是提供一種能對含噪聲點的實時數(shù)據(jù)流進(jìn)行任意形狀、任意大小、不同密度的聚類和聚類邊界界定的方法，該方法聚類效率高，邊界界定效果好。

為實現(xiàn)上述目的，本發(fā)明采用的技術(shù)方案是：先將本方法中所涉及到的標(biāo)記統(tǒng)一說明如下：

D是含噪聲點的實時數(shù)據(jù)流；λ是衰減因子；β是閾值調(diào)節(jié)系數(shù)；k是數(shù)據(jù)空間每一維的區(qū)間個數(shù)；δ是相似閾值；X是含噪聲點的實時數(shù)據(jù)流D中的數(shù)據(jù)點；G是數(shù)據(jù)空間中的所有網(wǎng)格；g表示數(shù)據(jù)點X能夠映射到的網(wǎng)格；g_h是高密度網(wǎng)格；g_l是低密度網(wǎng)格；g_max是還沒有聚類的具有最大密度值的高密度網(wǎng)格，g_max∈g_h；g_l’是大于或等于相似閾值δ的低密度網(wǎng)格，g_l’∈g_l；g_l”是小于相似閾值δ的低密度網(wǎng)格，g_l-g_l’＝g_l”，g_l’∪g_l”＝g_l；speed是數(shù)據(jù)流的流速；N是數(shù)據(jù)空間中網(wǎng)格的總數(shù)；g_grid是聚類網(wǎng)格，g_h∪g_l’＝g_grid；g_boundary是聚類邊界網(wǎng)格，g_boundary∈g_grid；t_next是下一次聚類請求時刻。

對含噪聲點的實時數(shù)據(jù)流進(jìn)行聚類和聚類邊界界定的步驟是：

步驟1、先把含噪聲點的實時數(shù)據(jù)流D中的數(shù)據(jù)點X能夠映射到的網(wǎng)格g中，更新數(shù)據(jù)點X能夠映射到的網(wǎng)格g的密度，更新后的密度為

Density(g,tn)=λtn-tlDensity(g,tl)+1---(1)]]>

式(1)中：t_n-當(dāng)前時刻；