[發(fā)明專利]一種基于Elkan算法在小分類中的改進(jìn)方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710556383.4
• 申請(qǐng)日: 2017-07-10
• 公開（公告）號(hào): CN107506784A
• 公開（公告）日: 2017-12-22
• 發(fā)明（設(shè)計(jì)）人: 匡振曦;陳平華
• 申請(qǐng)（專利權(quán)）人: 廣東工業(yè)大學(xué)
• 主分類號(hào): G06K9/62
• 分類號(hào): G06K9/62
• 代理公司: 廣東廣信君達(dá)律師事務(wù)所44329
• 代理人: 楊曉松

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

本發(fā)明涉及數(shù)據(jù)挖掘中的k-means聚類方法，具體涉及在小分類數(shù)據(jù)集中基于以數(shù)據(jù)點(diǎn)為圓心的改進(jìn)k-means算法，改進(jìn)的算法是在Elkan提出的k-means算法基礎(chǔ)上。

背景技術(shù)

k-means算法在數(shù)據(jù)聚類上很受歡迎。大多數(shù)實(shí)現(xiàn)使用勞埃德算法，但它進(jìn)行許多不必要的距離計(jì)算。最近提出了幾種加速算法(Elkan's，Hamerly's，Heap等)，這些算法與勞埃德算法的結(jié)果完全相同，只是更快。k-means算法還會(huì)用于各種應(yīng)用，如矢量量化，密度估計(jì)，圖像壓縮和自動(dòng)主題識(shí)別等等。同時(shí)它也被確定為數(shù)據(jù)挖掘中十大算法之一。由于它被廣泛使用，所以k-means算法應(yīng)盡可能的快。

以下是勞埃德算法的兩個(gè)主要步驟：

1.For each每個(gè)數(shù)據(jù)點(diǎn)x：

For each每個(gè)質(zhì)心c(內(nèi)循環(huán))：

計(jì)算x與c之間的距離。

把x劃分給最近的質(zhì)心。

2.移動(dòng)每個(gè)質(zhì)心到分配給該質(zhì)心所有點(diǎn)的平均點(diǎn)。

這兩個(gè)步驟重復(fù)，直到算法收斂就能得出k個(gè)簇。現(xiàn)在我們提出一種搜索以數(shù)據(jù)點(diǎn)為圓心的圓內(nèi)質(zhì)心的加速算法，算法基礎(chǔ)是Elkan提出的k-means算法。經(jīng)典k-means中的大多數(shù)距離計(jì)算是冗余的。如果一個(gè)點(diǎn)遠(yuǎn)離中心，則不需要計(jì)算點(diǎn)與中心之間的精確距離，因?yàn)橹涝擖c(diǎn)不應(yīng)該分配給該中心。相反，如果一個(gè)點(diǎn)比任何其他點(diǎn)更靠近一個(gè)中心，則不需要計(jì)算精確距離就知道該點(diǎn)應(yīng)該被分配給第一個(gè)中心，這就是Elkan用三角不等式(如圖1所示)來消除冗余計(jì)算。

本文所改進(jìn)的算法能確保在小分類數(shù)據(jù)集中更優(yōu)于原始的Elkan所提出的算法，在大分類數(shù)據(jù)集中可以與原方法效率持平。

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

本發(fā)明采用的技術(shù)方案是，基于以數(shù)據(jù)點(diǎn)為圓心的加速k-means算法，具體按照以下步驟實(shí)施：

步驟0：采集數(shù)據(jù)

步驟1：初始化質(zhì)心

步驟2：初始化每點(diǎn)屬于哪個(gè)質(zhì)心

步驟3：循環(huán)判斷每點(diǎn)屬于哪個(gè)質(zhì)心

步驟4：結(jié)果分析

步驟0具體按照以下步驟實(shí)施：

首先導(dǎo)入任意數(shù)據(jù)集，而且數(shù)據(jù)集的維度是在小于50維和分類個(gè)數(shù)小于20個(gè)。

步驟1具體按照以下步驟實(shí)施：

首先利用k-means++初始化質(zhì)心的方法生成k個(gè)質(zhì)心，然后對(duì)是否收斂converge變量賦值為False，用于記錄每個(gè)點(diǎn)屬于哪個(gè)質(zhì)心的變量assignment[n+1]初始化為-1，用于記錄每個(gè)質(zhì)心有那幾個(gè)點(diǎn)的指針變量int**sumc初始化為NULL。

步驟2具體按照以下步驟實(shí)施：

利用兩層for循環(huán)計(jì)算分別每點(diǎn)與所有質(zhì)心的距離d，在第二層循環(huán)里就能利用if判斷出每點(diǎn)的上界u[x]和每點(diǎn)與所有質(zhì)心的下界l[x][i]，跳出第二層循環(huán)就能將最近的質(zhì)心索引賦值給每點(diǎn)的assignment變量，同時(shí)利用雙重指針在相應(yīng)的質(zhì)心c[i]的索引下添加點(diǎn)x[j]，到此第一次初始化點(diǎn)與質(zhì)心間的關(guān)系結(jié)束。

步驟3具體按照以下步驟實(shí)施：

這一步是本算法的核心。當(dāng)?shù)谝粚觙or循環(huán)下i：1->n，首先使用兩層for循環(huán)，對(duì)每個(gè)質(zhì)心間的距離逐一計(jì)算，用s[i][j]存儲(chǔ)這個(gè)距離，當(dāng)i≠j時(shí)會(huì)得出一個(gè)最小值s_small＝1/2min(s[i][j])，判斷u(x)是否小于s_small，若小于則continue，因此下面循環(huán)不用再做。遍歷屬于c[i]的所有數(shù)據(jù)點(diǎn)，得到之間距離最大的距離m(c[i])。

然后第二層for循環(huán)，j：1->k，先用以當(dāng)前數(shù)據(jù)點(diǎn)畫圓u(x)+d(c[i],x[j])≤1/2max(s[i][j])(如圖2所示)來判斷是否需要遍歷質(zhì)心c[j]，若滿足再判斷

u[i]<＝l[i][j])||u[i]<＝centerCenterDistDiv2[closest*k+j]),然后對(duì)