[發(fā)明專利]一種改進(jìn)的全局最優(yōu)化k?中心點(diǎn)聚類方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710178344.5
• 申請(qǐng)日: 2017-03-23
• 公開(kāi)（公告）號(hào): CN107122794A
• 公開(kāi)（公告）日: 2017-09-01
• 發(fā)明（設(shè)計(jì)）人: 朱川;肖依永
• 申請(qǐng)（專利權(quán)）人: 北京航空航天大學(xué)
• 主分類號(hào): G06K9/62
• 分類號(hào): G06K9/62
• 代理公司: 北京慧泉知識(shí)產(chǎn)權(quán)代理有限公司11232
• 代理人: 王順榮,唐愛(ài)華

1.一種改進(jìn)的全局最優(yōu)化k-中心點(diǎn)聚類方法，其特征在于：其步驟如下：

步驟一：數(shù)據(jù)預(yù)處理準(zhǔn)備

1.1對(duì)需要被聚類分組的n個(gè)物體進(jìn)行編號(hào)，編號(hào)值從1到n；以V_ir表示對(duì)象i在屬性r上的值；

1.2按下面方法計(jì)算每?jī)蓚€(gè)對(duì)象i和j之間的距離d_ij，以獲得距離矩陣D＝{d_ij}：

1)計(jì)算對(duì)象i和j在屬性r上的標(biāo)準(zhǔn)化距離，以d_ijr表示；

2)當(dāng)屬性r為數(shù)字型屬性時(shí)，令

3)當(dāng)屬性k為分類型屬性時(shí)，令

4)令其中w_r為屬性r的權(quán)重；

步驟二：建立線性數(shù)學(xué)規(guī)劃模型

依據(jù)聚類問(wèn)題的特點(diǎn)并為了避免傳統(tǒng)聚類方法對(duì)于初始解過(guò)于敏感的缺點(diǎn)，本發(fā)明建立了線性數(shù)學(xué)規(guī)劃模型，該線性數(shù)學(xué)規(guī)劃模型由目標(biāo)函數(shù)與約束條件構(gòu)成，其構(gòu)成情況如下：

目標(biāo)函數(shù):

min F(Ω)=Σi=1nΣj=1ndij·ωij]]>

約束條件：

(1)

(2)

(3)ω_ij≤ω_jj

其中，上列線性數(shù)學(xué)規(guī)劃模型中的符號(hào)即目標(biāo)函數(shù)與約束條件中的符號(hào)，其含義如下所述：

上述約束條件中，約束條件(1)表示每一個(gè)對(duì)象i都必須且僅能分屬于某一個(gè)聚類j，滿足有ω_ij＝1；約束條件(2)表示必須有m個(gè)聚類；約束條件(3)表示僅當(dāng)對(duì)象j為聚類中心時(shí)，ω_ij才允許取1，否則只能取0；

上述數(shù)學(xué)規(guī)劃模型是線性的，具備求解可行性；

步驟三：線性數(shù)學(xué)規(guī)劃模型求解

其中線性數(shù)學(xué)規(guī)劃模型指的是上文中所述，為包含目標(biāo)函數(shù)與約束條件的線性數(shù)學(xué)規(guī)劃模型；對(duì)該線性數(shù)學(xué)規(guī)劃模型最優(yōu)化求解，考慮下列已有的求解方式：

(1)直接運(yùn)用單純形法、分支定界方法、割平面法等對(duì)模型進(jìn)行最優(yōu)求解；

(2)利用求解軟件，如Lingo和AMPL對(duì)模型進(jìn)行最優(yōu)化求解；

具體求解方法如下：(1)若直接運(yùn)用單純形法、分支定界方法和割平面法對(duì)模型進(jìn)行最優(yōu)求解，則直接手工演算求解，不再贅述；(2)若利用求解軟件，如Lingo和AMPL對(duì)模型進(jìn)行最優(yōu)化求解，則建立用于求解的執(zhí)行腳本文件(*.dat)，并將已知數(shù)據(jù)與線性數(shù)學(xué)規(guī)劃模型相應(yīng)的數(shù)據(jù)文件(*.dat)與模型文件(*.mod)，一并帶入軟件進(jìn)行求解，得到求解結(jié)果；

步驟四：求解結(jié)果輸出

求解軟件完成對(duì)線性數(shù)學(xué)規(guī)劃模型求解計(jì)算后，獲得求解結(jié)果Ω，并對(duì)其進(jìn)行解析，獲得聚類結(jié)果以及各類的中心點(diǎn)；方法如下：

1)對(duì)于所有i∈N判斷ω_ii，如果ω_ii＝1，則表示對(duì)象i代表一個(gè)聚類且代表該類的中心點(diǎn)；

2)如果ω_ii＝1，則對(duì)所有j∈N判斷ω_ij，如果ω_ij＝1，則表對(duì)象j隸屬于對(duì)象i所代表的類；

根據(jù)上述方法，獲得最終的聚類分組結(jié)果以及總簇內(nèi)距離；

通過(guò)以上步驟，達(dá)到了對(duì)一組數(shù)據(jù)進(jìn)行聚類分組的效果，使得同組數(shù)據(jù)的相似度大，非同組數(shù)據(jù)的相似度??；在聚類過(guò)程中，解決了傳統(tǒng)聚類方法必須給出初始解，并且對(duì)于初始解過(guò)于敏感的問(wèn)題；本發(fā)明能在不給出初始解的情況下，直接獲得最優(yōu)聚類結(jié)果，大大提高了聚類過(guò)程的便利性與準(zhǔn)確性。