[發(fā)明專利]一種譜聚類算法中心點(diǎn)的選取方法和裝置

在審

• 申請?zhí)枺?/td>: 201811155117.1
• 申請日: 2018-09-30
• 公開（公告）號: CN110969179A
• 公開（公告）日: 2020-04-07
• 發(fā)明（設(shè)計(jì)）人: 孫顥寧
• 申請（專利權(quán)）人: 北京國雙科技有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N3/00
• 代理公司: 北京集佳知識產(chǎn)權(quán)代理有限公司 11227
• 代理人: 王寶筠

本發(fā)明公開了一種譜聚類算法中心點(diǎn)的選取方法和裝置。方法包括：采用萊維飛行策略生成一個(gè)步長；判斷步長是否大于預(yù)設(shè)閾值；如果大于，采用預(yù)設(shè)的第一公式更新種群中各個(gè)粒子的速度；如果不大于，采用預(yù)設(shè)的第二公式更新種群中各個(gè)粒子的速度，其中所述步長不引入所述第一公式和所述第二公式；依據(jù)種群中各個(gè)粒子更新后的速度，確定各個(gè)粒子的位置；針對種群中的每一個(gè)粒子，將該粒子的位置代入預(yù)設(shè)的目標(biāo)函數(shù)，計(jì)算得到該粒子的適應(yīng)度值；判斷當(dāng)前是否滿足終止條件；如果滿足，將種群中適應(yīng)度值最優(yōu)的粒子確定為譜聚類算法中心點(diǎn)。本發(fā)明能夠保證收斂速度快且最終收斂值較小。

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

本發(fā)明涉及數(shù)據(jù)處理技術(shù)領(lǐng)域，尤其涉及一種譜聚類算法中心點(diǎn)的選取方法和裝置。

背景技術(shù)

聚類是為了將數(shù)據(jù)樣本劃分為幾組類簇，屬于同類簇的數(shù)據(jù)樣本在設(shè)定規(guī)則下更為相似，而不同類簇的數(shù)據(jù)樣本在設(shè)定規(guī)則下被區(qū)分開來。而因?yàn)閿?shù)據(jù)的多樣性使得許多數(shù)據(jù)的維度具有不相關(guān)性，因此傳統(tǒng)的聚類算法面對多樣性的數(shù)據(jù)時(shí)聚類效果變差。

譜聚類算法用于解決數(shù)據(jù)維度不相關(guān)導(dǎo)致的聚類效果變差的問題，但是譜聚類算法的中心點(diǎn)選擇對聚類結(jié)果具有非常大的影響。

目前對于譜聚類算法中心點(diǎn)的選取方法采用布谷鳥搜索算法或粒子群算法等群智能算法。然而，使用布谷鳥搜索算法搜索聚類算法初始化中心點(diǎn)，雖然最終收斂值較小，但存在后期收斂速度慢的問題，而粒子群算法雖然收斂速度快，但最終收斂值較大。

因此，目前急需一種能夠同時(shí)保證收斂速度快且最終收斂值較小的譜聚類算法中心點(diǎn)的選取方法。

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

鑒于上述問題，提出了本發(fā)明以便提供一種克服上述問題或者至少部分地解決上述問題的一種譜聚類算法中心點(diǎn)的選取方法和裝置。技術(shù)方案如下：

基于本發(fā)明的一方面，本發(fā)明提供一種譜聚類算法中心點(diǎn)的選取方法，所述選取方法包括：

采用萊維飛行策略生成一個(gè)步長；

判斷所述步長是否大于預(yù)設(shè)閾值；

如果大于，采用預(yù)設(shè)的第一公式更新種群中各個(gè)粒子的速度；

如果不大于，采用預(yù)設(shè)的第二公式更新種群中各個(gè)粒子的速度，其中所述步長不引入所述第一公式和所述第二公式；

依據(jù)種群中各個(gè)粒子更新后的速度，確定各個(gè)粒子的位置；

針對種群中的每一個(gè)粒子，將該粒子的位置代入預(yù)設(shè)的目標(biāo)函數(shù)，計(jì)算得到該粒子的適應(yīng)度值；

判斷當(dāng)前是否滿足終止條件；

如果滿足，將種群中適應(yīng)度值最優(yōu)的粒子確定為譜聚類算法中心點(diǎn)。

可選地，所述第一公式為

所述第二公式為

其中，D表示D維向量，表示第k+1代粒子i的速度，表示第k代粒子i的速度，D、k均為正整數(shù)；l_factor為預(yù)設(shè)的局部影響因子，g_factor為預(yù)設(shè)的全局影響因子，其中，c₁、c₂為學(xué)習(xí)因子；r₁、r₂取值范圍是[0,1]區(qū)間內(nèi)均勻分布的偽隨機(jī)數(shù)；p^k_iD為第k代粒子i經(jīng)歷過的歷史最好位置，為第k代粒子i的位置，g^k_iD為第k代種群內(nèi)全部粒子歷史最佳位置。

可選地，所述依據(jù)種群中各個(gè)粒子更新后的速度，確定各個(gè)粒子的位置包括：

采用公式確定各個(gè)粒子的位置；

其中，為第k+1代粒子i的位置，為第k代粒子i的位置。

可選地，所述判斷當(dāng)前是否滿足終止條件包括：