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

在審

• 申請(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)（專(zhuān)利權(quán)）人: 北京航空航天大學(xué)
• 主分類(lèi)號(hào): G06K9/62
• 分類(lèi)號(hào): G06K9/62
• 代理公司: 北京慧泉知識(shí)產(chǎn)權(quán)代理有限公司11232
• 代理人: 王順榮,唐愛(ài)華

一、所屬技術(shù)領(lǐng)域：

本發(fā)明提供一種改進(jìn)的全局最優(yōu)化k-中心點(diǎn)聚類(lèi)方法，k-中心點(diǎn)是指從數(shù)據(jù)對(duì)象中選擇k個(gè)對(duì)象為類(lèi)的代表中心；本發(fā)明一種最優(yōu)化的k-中心點(diǎn)聚類(lèi)方法，解決了一般的k-中心點(diǎn)聚類(lèi)方法具有初始解敏感性以及不能保證獲得最優(yōu)聚類(lèi)結(jié)果的缺點(diǎn)；本方法屬于數(shù)據(jù)統(tǒng)計(jì)與分析領(lǐng)域，能幫助數(shù)據(jù)分析人員在數(shù)據(jù)模式識(shí)別中獲得更好的聚類(lèi)效果。

二、背景技術(shù)：

聚類(lèi)(Clustering)是指將若干數(shù)據(jù)對(duì)象的按照同類(lèi)間相似度最大且異類(lèi)間相似性最小的原則劃分若干類(lèi)的過(guò)程。在數(shù)據(jù)分析與數(shù)據(jù)挖掘領(lǐng)域，聚類(lèi)是一種重要的數(shù)據(jù)分析方法，是挖掘隱藏在大量數(shù)據(jù)中的數(shù)據(jù)分布模式的主要手段之一，具有廣泛用途。k-中心點(diǎn)聚類(lèi)是要求在聚類(lèi)結(jié)果必須以原數(shù)據(jù)對(duì)象為聚類(lèi)中心點(diǎn)的一種特殊聚類(lèi)分析方法，即從數(shù)據(jù)對(duì)象中選擇k個(gè)對(duì)象為類(lèi)的代表中心，使類(lèi)成員達(dá)到該中心點(diǎn)的距離之和最小化。傳統(tǒng)的k-中心聚類(lèi)方法，即圍繞中心點(diǎn)的聚類(lèi)方法(簡(jiǎn)稱PAM方法)，是基于非線性整數(shù)規(guī)劃模型的方法，有兩個(gè)明顯的缺陷：(1)計(jì)算結(jié)果有可能會(huì)止于局部最優(yōu)解，使聚類(lèi)結(jié)果達(dá)不到全局最優(yōu)；(2)方法對(duì)初始中心點(diǎn)的選擇比較敏感，選擇不同的初始中心點(diǎn)可能導(dǎo)致不同的計(jì)算結(jié)果。

本發(fā)明所提出的方法是基于線性化的整數(shù)規(guī)劃方法，該方法可以直接獲得全局最的聚類(lèi)結(jié)果，不會(huì)陷入局部最優(yōu)結(jié)果，且不依賴與初始中心點(diǎn)的選擇。本方法能夠?qū)Χ噙_(dá)1000個(gè)數(shù)據(jù)對(duì)象的中等規(guī)模k-中心聚類(lèi)問(wèn)題提供全局最優(yōu)的聚類(lèi)結(jié)果。

三、發(fā)明內(nèi)容：

3.1發(fā)明目的

本發(fā)明的目的在于改進(jìn)現(xiàn)有k-中心點(diǎn)聚類(lèi)方法(即PAM方法)的缺點(diǎn)，提供一種全局化最優(yōu)化的聚類(lèi)方法，為大數(shù)據(jù)分析和數(shù)據(jù)模式識(shí)別等相關(guān)工作提供具有更好聚類(lèi)效果的聚類(lèi)方法。

3.2技術(shù)方案

首先，本發(fā)明要解決的問(wèn)題描述如下：假定有n個(gè)對(duì)象和m個(gè)屬性，這n個(gè)對(duì)象需要按照其屬性值的相似程度劃分為k個(gè)聚類(lèi)，使同類(lèi)對(duì)象之間盡可能地相似。其中任意兩個(gè)對(duì)象i和j，以d_ij表示它們之間的區(qū)分度。區(qū)分度越大，相似度越小。這里的d_ij以兩點(diǎn)之間的距離來(lái)表示且為已知。對(duì)于每一個(gè)聚類(lèi)，其中的某一個(gè)成員對(duì)象將被選擇為該類(lèi)的中心點(diǎn)，代表該類(lèi)的整體性質(zhì)。屬于同一聚類(lèi)的所有物體與該類(lèi)的類(lèi)中心之間的距離之總和被定義為簇內(nèi)距離，反映了同族成員之間差異。k-中心點(diǎn)聚類(lèi)的目標(biāo)即為使各組組內(nèi)距離之和最小。

為最優(yōu)地解決上述問(wèn)題，本發(fā)明方法的技術(shù)實(shí)現(xiàn)方案由四個(gè)步驟組成。各步驟中用到的數(shù)學(xué)符號(hào)預(yù)先介紹如下：

本發(fā)明一種改進(jìn)的全局最優(yōu)化k-中心點(diǎn)聚類(lèi)方法，其步驟如下：

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

1.1對(duì)需要被聚類(lèi)分組的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為分類(lèi)型屬性時(shí)，令

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

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

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

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

約束條件：

(1)

(2)

(3)

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

N 對(duì)象的集合

n 對(duì)象集N所包含的對(duì)象的個(gè)數(shù)，n＝card(N)

i,j 對(duì)象的標(biāo)號(hào)i,j∈N

d_ij對(duì)象i和對(duì)象j之間的距離，d_ij∈D

M 屬性的集合

m 屬性集M所包含的屬性的個(gè)數(shù)，m＝card(M)

r 屬性的標(biāo)號(hào)，r∈M

k 聚類(lèi)的個(gè)數(shù)

ω_ij 0/1決策變量，當(dāng)i所在類(lèi)中心為j時(shí)取1；否則取0.

Ω變量ω_ij組成的集合，ω_ij∈Ω