[發(fā)明專利]一種基于尺度劃分和區(qū)域生長(zhǎng)的聚類方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202110237844.8
• 申請(qǐng)日: 2021-03-04
• 公開(kāi)（公告）號(hào): CN112836766A
• 公開(kāi)（公告）日: 2021-05-25
• 發(fā)明（設(shè)計(jì)）人: 賈云偉;郝晨翔;吳江波;王坤;姚城斌
• 申請(qǐng)（專利權(quán)）人: 天津理工大學(xué)
• 主分類號(hào): G06K9/62
• 分類號(hào): G06K9/62
• 代理公司: 天津耀達(dá)律師事務(wù)所 12223
• 代理人: 侯力

本發(fā)明涉及一種基于尺度劃分和區(qū)域生長(zhǎng)的聚類方法，該方法是：1)獲得原始數(shù)據(jù)點(diǎn)并將原始數(shù)據(jù)點(diǎn)通過(guò)一定的規(guī)則映射到圖中；2)將該圖通過(guò)降采樣的方式劃分成不同的尺度，并選出合適的尺度；3)在合適的尺度下獲取初始種子點(diǎn)并進(jìn)行區(qū)域生長(zhǎng)完成聚類。本發(fā)明方法與其它方法相比，明顯提升了聚類精度。

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

本發(fā)明屬于信息技術(shù)領(lǐng)域。

背景技術(shù)

二十一世紀(jì)是一個(gè)信息爆炸的時(shí)代，在計(jì)算機(jī)互聯(lián)網(wǎng)技術(shù)飛速發(fā)展的基礎(chǔ)上，信息采集技術(shù)和數(shù)據(jù)庫(kù)的應(yīng)用不斷發(fā)展，從海量的數(shù)據(jù)中快速、準(zhǔn)確地獲取有用信息已經(jīng)成為研究的熱點(diǎn)。我們可以用聚類或分類的機(jī)器學(xué)習(xí)方法來(lái)從海量的數(shù)據(jù)中獲取有用的信息。聚類分析是一種沒(méi)有訓(xùn)練過(guò)程的無(wú)監(jiān)督機(jī)器學(xué)習(xí)方法，主要通過(guò)最大化同簇間元素之間的相似性以及最小化非同簇間元素之間的相似性來(lái)進(jìn)行劃分。與聚類過(guò)程不同的是分類過(guò)程屬于有監(jiān)督的學(xué)習(xí)，而且必須首先明確類別的信息。聚類方法是海量數(shù)據(jù)預(yù)處理的常用方法，同時(shí)也是數(shù)據(jù)挖掘的核心內(nèi)容，聚類方法的研究對(duì)推動(dòng)人工智能的發(fā)展具有很重要的作用。

目前，已有大量的聚類算法被提出并廣泛應(yīng)用于圖像分割、生物、電子商務(wù)、互聯(lián)網(wǎng)等領(lǐng)域。如：k-means算法、FCM算法、DBSCAN算法、DPC算法等。K-Means算法受到輸入?yún)?shù)的影響且僅適用于凸形數(shù)據(jù)集。主要的原因是其在算法起始必須選取K 個(gè)樣本點(diǎn)作為初始的聚類中心，然后根據(jù)樣本點(diǎn)與聚類中心之間的距離將每個(gè)樣本點(diǎn)都分配到距離其最近的聚類中心。之后再進(jìn)行聚類中心更新和迭代。在迭代的過(guò)程中聚類中心的位置可以發(fā)生變化，但是簇個(gè)數(shù)不會(huì)增加。而實(shí)際應(yīng)用中，經(jīng)常無(wú)法根據(jù)原始數(shù)據(jù)推斷聚類的數(shù)目，此時(shí)如果初始值K選取較小，則聚類必然失敗。此外，K-Means算法單純依據(jù)樣本點(diǎn)與聚類中心之間的距離將樣本點(diǎn)分配到不同的簇，這導(dǎo)致K-Means 算法主要適用于凸形數(shù)據(jù)集，不適用于非凸形數(shù)據(jù)集，并且當(dāng)簇與簇之間的間距較近時(shí)，簇邊界的點(diǎn)容易被誤分配；FCM算法引入了隸屬度的概念，但不準(zhǔn)確的隸屬度會(huì)影響簇中心的選擇，同時(shí)FCM算法的計(jì)算量較大；DBSCAN算法無(wú)法識(shí)別出含有多個(gè)密度的簇；DPC算法和DBSCAN算法類似，也是無(wú)法識(shí)別出具有多個(gè)密度的簇。

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

本發(fā)明的目的是解決現(xiàn)有聚類方法不能適用于所有類型的數(shù)據(jù)集且聚類精度較低的問(wèn)題，為此提出一種基于尺度劃分和區(qū)域生長(zhǎng)的聚類方法。利用尺度劃分和區(qū)域生長(zhǎng)思想提出的聚類方法可以在無(wú)需初始參數(shù)的情況下對(duì)低維或者高維數(shù)據(jù)集進(jìn)行聚類，并獲得更加準(zhǔn)確的聚類效果。

本發(fā)明的技術(shù)方案如下：

一種基于尺度劃分和區(qū)域生長(zhǎng)的聚類方法，該方法主要包括兩個(gè)階段：初始階段，將數(shù)據(jù)點(diǎn)通過(guò)一定的規(guī)則映射到圖中，然后將該圖通過(guò)降采樣的方式劃分成不同的尺度，并選出合適的尺度。第二階段，在合適的尺度下進(jìn)行區(qū)域生長(zhǎng)完成聚類。

具體步驟如下：

步驟1：構(gòu)造一個(gè)W×H的零矩陣，該零矩陣可以看作是亮度值為0，分辨率為W× H的圖片，記作A，本發(fā)明中W＝1000，H＝1000；

步驟2：映射；從數(shù)據(jù)庫(kù)中獲取數(shù)據(jù)集并將數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的初始坐標(biāo)通過(guò)如下公式(1)所示的規(guī)則映射到圖片A中，

在公式(1)中，x₀和y₀分別表示的是數(shù)據(jù)點(diǎn)的原始橫坐標(biāo)和縱坐標(biāo)，x_min和x_max分別表示的是數(shù)據(jù)點(diǎn)原始橫坐標(biāo)的最小值和最大值，y_max和y_min分別表示的是數(shù)據(jù)點(diǎn)原始縱坐標(biāo)的最大值和最小值，x和y分別表示的是圖片A中對(duì)應(yīng)映射點(diǎn)的橫坐標(biāo)和縱坐標(biāo)， D_x，y表示的是在圖片A中的(x，y)處的亮度值，經(jīng)過(guò)映射之后，圖片A中的亮度值發(fā)生了變化，將亮度值發(fā)生變化的圖片A標(biāo)記為C1；

步驟3：劃分尺度；通過(guò)步驟2獲得的C1記為第一尺度，其它尺度的計(jì)算公式如公式(2)所示，