[發(fā)明專利]一種基于主成分分析和最近鄰圖的密度峰值聚類方法及系統(tǒng)

在審

• 申請?zhí)枺?/td>: 201610514546.8
• 申請日: 2016-06-30
• 公開（公告）號(hào): CN107563260A
• 公開（公告）日: 2018-01-09
• 發(fā)明（設(shè)計(jì)）人: 丁世飛;其他發(fā)明人請求不公開姓名
• 申請（專利權(quán)）人: 中國礦業(yè)大學(xué)
• 主分類號(hào): G06K9/00
• 分類號(hào): G06K9/00;G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

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

本發(fā)明涉及模式識(shí)別和機(jī)器學(xué)習(xí)領(lǐng)域，具體涉及一種基于主成分分析和最近鄰圖的密度峰值聚類方法及系統(tǒng)。

背景技術(shù)

聚類分析的密度是通過找出以“簇”的形式存在于數(shù)據(jù)集內(nèi)部的結(jié)構(gòu)，用以發(fā)現(xiàn)數(shù)據(jù)集的內(nèi)部組織。這一詞指的是由近似數(shù)據(jù)點(diǎn)組成的被分離開來的群。直覺上講，簇的分割具有簇內(nèi)相似及簇間相異的特點(diǎn)。因此，數(shù)據(jù)數(shù)據(jù)被分解成許多群，這些群有相似的對(duì)象構(gòu)成，同時(shí)不同的群包含了各不相同的元素。該方法論被廣泛的應(yīng)用于多元統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)。

傳統(tǒng)的聚類大致被分為4類：劃分聚類、層次聚類、密度聚類和模型聚類。每類方式都各有利弊，如，劃分聚類通常需要指定簇個(gè)數(shù)，且需要迭代；層次聚類同樣很難找到最優(yōu)的聚類個(gè)數(shù)；而傳統(tǒng)的密度聚類算法參數(shù)調(diào)節(jié)困難；模型聚類通常需要對(duì)數(shù)據(jù)的分布情況進(jìn)行假設(shè)。2014年，《Science》上發(fā)表了一篇全新的聚類方法，密度峰值聚類(Density Peaks Clustering，DPC)。密度峰值聚類具有如下特點(diǎn)：無需指定簇個(gè)數(shù)；適用于任意形狀的數(shù)據(jù)集；無需迭代，也不會(huì)陷入局部最優(yōu)；只有一個(gè)參數(shù)，易于調(diào)節(jié)控制；無需對(duì)數(shù)據(jù)集的分布進(jìn)行假設(shè)。算法簡單，易于實(shí)現(xiàn)。由于以上特點(diǎn)，密度聚類算法也受到了越來越多的關(guān)注，并被應(yīng)用于異常點(diǎn)檢測、圖像處理、文本處理等領(lǐng)域。密度峰值聚類算法給聚類問題的求解提供了新思路，能有效處理許多實(shí)際問題，其研究具有巨大的科研價(jià)值和應(yīng)用潛力。

但是密度峰值聚類依然存在一些問題。首先，該算法沒有考慮數(shù)據(jù)的局部結(jié)構(gòu)問題，原始DPC算法并不能檢測到所有簇；其次，該算法在高維數(shù)據(jù)上的表現(xiàn)很差，這是由于DPC算法過度的依賴于數(shù)據(jù)對(duì)間的距離，以及“維度災(zāi)難”。

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

為了解決上述問題，本發(fā)明提出一種基于主成分分析和最近鄰圖的密度峰值聚類方法及系統(tǒng)。首先，使用主成分分析對(duì)原始數(shù)據(jù)進(jìn)行特征轉(zhuǎn)化和特征提取，即對(duì)原始數(shù)據(jù)進(jìn)行降維，然后，使用改進(jìn)過的局部密度計(jì)算公式，即利用最近鄰圖取代原始方式，求解局部密度。再利用原始算法中的求解步驟找出聚類中心點(diǎn)，完成聚類。該方式充分考慮了高維數(shù)據(jù)以及數(shù)據(jù)中的局部結(jié)構(gòu)對(duì)算法的影響，具有較強(qiáng)的魯棒性和泛化能力。

本發(fā)明是通過以下方案實(shí)現(xiàn)的：

本發(fā)明涉及一種基于主成分分析和最近鄰圖的密度峰值聚類方法，通過主成分分析提取原始數(shù)據(jù)的主要特征，作為數(shù)據(jù)的預(yù)處理階段，應(yīng)對(duì)“維度災(zāi)難”問題。通過最近鄰圖的思想，改進(jìn)原始局部密度的求解方式，使整個(gè)聚類算法不僅考慮數(shù)據(jù)的全局結(jié)構(gòu)而且還考慮數(shù)據(jù)的局部結(jié)構(gòu)。最后在求解出簇中心點(diǎn)，輸出聚類結(jié)果。

本發(fā)明具體步驟如下：

步驟1，使用主成分分析技術(shù)將輸入數(shù)據(jù)集χ＝{x₁,x₂,…,x_n}(x_i∈R^d)轉(zhuǎn)化為新的形式χ″＝{x″₁,x″₂,…,x″_n}(x″_i∈R^d″)，其中d″＜d。

步驟1.1：對(duì)原始數(shù)據(jù)集χ＝{x₁,x₂,…,x_n}進(jìn)行預(yù)處理。使其所有特征值具有相同的均值與方差，新的數(shù)據(jù)集為χ′＝{x′₁,x′₂,…,x′_n}(x′_i∈R^d)。

步驟1.2：依據(jù)預(yù)處理的數(shù)據(jù)集計(jì)算協(xié)方差矩陣Σ：

步驟1.3：求解協(xié)方差矩陣Σ的特征值λ_i和特征向量u_i，經(jīng)過轉(zhuǎn)換的數(shù)據(jù)為：

x_rot,i＝U^Tx′_i。(2)

其中U是由特征向量堆疊而成的矩陣：

步驟1.4：對(duì)數(shù)據(jù)進(jìn)行降維，根據(jù)其主成分：

得到最終的降維數(shù)據(jù)，χ″＝{x″₁,x″₂,…,x″_n}(x″_i∈R^d″)。

步驟2，依據(jù)歐式距離公式計(jì)算相似度矩陣。

步驟3，根據(jù)相似度矩陣計(jì)算各個(gè)點(diǎn)的兩個(gè)重要數(shù)值：ρ_i和δ_i。

步驟3.1：求解各個(gè)數(shù)據(jù)點(diǎn)的前k個(gè)最近鄰，kNN(x_i)。