[發(fā)明專利]一種基于邊界環(huán)收縮的聚類系統(tǒng)及方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202110477832.2
• 申請(qǐng)日: 2021-04-30
• 公開(kāi)（公告）號(hào): CN113486916A
• 公開(kāi)（公告）日: 2021-10-08
• 發(fā)明（設(shè)計(jì)）人: 馬弢
• 申請(qǐng)（專利權(quán)）人: 中國(guó)航天空氣動(dòng)力技術(shù)研究院
• 主分類號(hào): G06K9/62
• 分類號(hào): G06K9/62
• 代理公司: 中國(guó)航天科技專利中心 11009
• 代理人: 胡健男

1.一種基于邊界環(huán)收縮的聚類系統(tǒng)，其特征在于包括：邊界點(diǎn)檢測(cè)模塊、邊界聚合模塊和邊界環(huán)收縮模塊：

邊界點(diǎn)檢測(cè)模塊，對(duì)于待聚類的數(shù)據(jù)點(diǎn)，采用邊界點(diǎn)檢測(cè)算法確定屬于邊界點(diǎn)的數(shù)據(jù)點(diǎn)，形成邊界點(diǎn)集合P，從而獲取聚類邊界點(diǎn)；

邊界聚合模塊，對(duì)邊界點(diǎn)檢測(cè)模塊得到的邊界點(diǎn)集合P，根據(jù)聚類數(shù)目k對(duì)邊界點(diǎn)集合P進(jìn)行邊界聚合，即將邊界點(diǎn)集合P，根據(jù)聚類數(shù)目k，劃分為若干的新集合，每個(gè)新集合為每個(gè)聚類的邊界,為每個(gè)新集合分配一個(gè)標(biāo)簽，且每個(gè)新集合分配的標(biāo)簽不同；

邊界環(huán)收縮模塊,對(duì)于各個(gè)新集合形成的邊界內(nèi)的未標(biāo)記點(diǎn)進(jìn)行標(biāo)簽分配，完成對(duì)該新集合所有待聚類的數(shù)據(jù)點(diǎn)的標(biāo)簽分配，從而實(shí)現(xiàn)聚類。

2.根據(jù)權(quán)利要求1所述的一種基于邊界環(huán)收縮的聚類系統(tǒng)，其特征在于：邊界點(diǎn)集合P表示為{p₁,p₂,...,p_n}，從而獲取聚類邊界點(diǎn)；p₁,p₂,...,p_n分別為第1個(gè)邊界點(diǎn)、第2個(gè)邊界點(diǎn)、…、第n個(gè)邊界點(diǎn)；n小于等于待聚類的數(shù)據(jù)點(diǎn)的總數(shù)。

3.根據(jù)權(quán)利要求1所述的一種基于邊界環(huán)收縮的聚類系統(tǒng)，其特征在于：根據(jù)聚類數(shù)目k，劃分為若干的新集合，每個(gè)新集合為每個(gè)聚類的邊界,為每個(gè)新集合分配一個(gè)標(biāo)簽，且每個(gè)新集合分配的標(biāo)簽不同；具體如下：

當(dāng)已知聚類數(shù)目k時(shí)，采用分層聚類算法將邊界點(diǎn)集合P中的邊界點(diǎn)根據(jù)聚類數(shù)目k進(jìn)行聚合，形成k個(gè)新集合，每個(gè)新集合中為聚類數(shù)目k中一類的邊界點(diǎn)，為每個(gè)新集合分配一個(gè)標(biāo)簽，且每個(gè)新集合分配的標(biāo)簽不同；

當(dāng)聚類數(shù)目未知時(shí)，采用圖論的方法，將邊界點(diǎn)集合P中的邊界點(diǎn)作為圖的節(jié)點(diǎn)，將圖的節(jié)點(diǎn)中的任意兩個(gè)之間距離的倒數(shù)作為邊的權(quán)值，然后使用最大流最小割的方法將圖的所有節(jié)點(diǎn)即對(duì)應(yīng)的邊界點(diǎn)劃分為若干新集合，每個(gè)新集合分配一個(gè)標(biāo)簽，且每個(gè)新集合分配的標(biāo)簽不同；新集合的數(shù)目即為聚類數(shù)目k。

4.根據(jù)權(quán)利要求1所述的一種基于邊界環(huán)收縮的聚類系統(tǒng)，其特征在于：邊界環(huán)收縮模塊,對(duì)于各個(gè)新集合形成的邊界內(nèi)的未標(biāo)記點(diǎn)進(jìn)行標(biāo)簽分配，對(duì)其中任意一個(gè)新集合形成的邊界內(nèi)的未標(biāo)記點(diǎn)進(jìn)行標(biāo)簽分配，具體如下：

1)對(duì)任意一個(gè)新集合中每個(gè)邊界點(diǎn)i都找到與其距離最近的未標(biāo)記點(diǎn)，該未標(biāo)記點(diǎn)不為邊界點(diǎn)，將該未標(biāo)記點(diǎn)進(jìn)行標(biāo)簽分配，即對(duì)未標(biāo)記點(diǎn)分配與邊界點(diǎn)i相同的類別標(biāo)簽，形成新的標(biāo)記點(diǎn)；這些新的標(biāo)記點(diǎn)形成的環(huán)作為新的邊界環(huán)，新的邊界環(huán)中的標(biāo)記點(diǎn)形成邊界環(huán)點(diǎn)集合；i取1至該新集合中的邊界點(diǎn)總數(shù)；

2)判斷是否存在未標(biāo)記點(diǎn)，若存在，則用邊界環(huán)點(diǎn)集合替換步驟1)中的新集合，更新新集合，重復(fù)步驟1)，即實(shí)現(xiàn)邊界環(huán)收縮；若不存在，完成對(duì)該新集合所有待聚類的數(shù)據(jù)點(diǎn)的標(biāo)簽分配，從而實(shí)現(xiàn)聚類。

5.一種基于邊界環(huán)收縮的聚類方法，其特征在于步驟如下：

(1)對(duì)于待聚類的數(shù)據(jù)點(diǎn)，采用邊界點(diǎn)檢測(cè)算法確定屬于邊界點(diǎn)的數(shù)據(jù)點(diǎn)，形成邊界點(diǎn)集合P，從而獲取聚類邊界點(diǎn)；

(2)對(duì)步驟(1)得到的邊界點(diǎn)集合P，根據(jù)聚類數(shù)目k對(duì)邊界點(diǎn)集合P進(jìn)行邊界聚合，即將邊界點(diǎn)集合P，根據(jù)聚類數(shù)目k，劃分為若干的新集合，每個(gè)新集合為每個(gè)聚類的邊界,為每個(gè)新集合分配一個(gè)標(biāo)簽，且每個(gè)新集合分配的標(biāo)簽不同；

(3)對(duì)于步驟(2)各個(gè)新集合形成的邊界內(nèi)的未標(biāo)記點(diǎn)進(jìn)行標(biāo)簽分配，完成對(duì)該新集合所有待聚類的數(shù)據(jù)點(diǎn)的標(biāo)簽分配，從而實(shí)現(xiàn)聚類。

6.根據(jù)權(quán)利要求5所述的一種基于邊界環(huán)收縮的聚類方法，其特征在于：邊界點(diǎn)集合P表示為{p₁,p₂,...,p_n}，從而獲取聚類邊界點(diǎn)；p₁,p₂,...,p_n分別為第1個(gè)邊界點(diǎn)、第2個(gè)邊界點(diǎn)、…、第n個(gè)邊界點(diǎn)；n小于等于待聚類的數(shù)據(jù)點(diǎn)的總數(shù)。