[發(fā)明專利]一種基于均勻抽樣的二階差分聚類數(shù)確定方法

在審

• 申請?zhí)枺?/td>: 201611008315.6
• 申請日: 2016-11-16
• 公開（公告）號: CN106598916A
• 公開（公告）日: 2017-04-26
• 發(fā)明（設計）人: 陳艷;易葉青;陳光
• 申請（專利權(quán)）人: 東華大學
• 主分類號: G06F17/18
• 分類號: G06F17/18;G06K9/62
• 代理公司: 上海泰能知識產(chǎn)權(quán)代理事務所31233
• 代理人: 宋纓,錢文斌

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

本發(fā)明涉及大數(shù)據(jù)聚類技術(shù)領(lǐng)域，特別是涉及一種基于均勻抽樣的二階差分聚類數(shù)確定方法。

背景技術(shù)

在企業(yè)走向新一代數(shù)字化變革的旅途，大數(shù)據(jù)比過往成指數(shù)級的增長，涉及多個領(lǐng)域的應用，包括互聯(lián)網(wǎng)金融、醫(yī)療健康、社交、網(wǎng)絡游戲、教育、稅務、物流、餐飲、旅游、娛樂和航運等，大數(shù)據(jù)無處不在，同時也面臨著無法整合海量多維的數(shù)據(jù)，無法進行關(guān)聯(lián)性的數(shù)據(jù)分析及數(shù)據(jù)發(fā)現(xiàn)。因此靈活、快速和準確的處理這些大數(shù)據(jù)成為一項必不可少的工作。

聚類是一種無監(jiān)督的學習方法，關(guān)于聚類數(shù)目確定的方法有許多，大部分的方法都是在研究如何提高得到最佳聚類數(shù)，比如經(jīng)典的k-Means硬聚類算法，也有人提出一種若干標準隔離特定方面的性能的方法,如檢索固有結(jié)構(gòu),對重采樣的敏感性和穩(wěn)定性的結(jié)果的新數(shù)據(jù)。但是許多算法所固有的不足也逐漸顯露。

采用改進的二階差分的方式來自動確定聚類數(shù)，可以實現(xiàn)在完全沒有人工干預的條件下自動確定聚類數(shù)目，而且對各種數(shù)據(jù)集具有很好的適應性，但就算聚類數(shù)需要花費一定的時間，隨著社會的進步，無論在醫(yī)學、生物學，還是工業(yè)中來自不同過程的統(tǒng)計數(shù)據(jù)不斷產(chǎn)生，都面臨著數(shù)據(jù)龐大、結(jié)構(gòu)復雜且維度多樣的問題，此時如果不對這些大數(shù)據(jù)進行處理，而直接采用傳統(tǒng)的聚類方法，計算量會非常大。

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

本發(fā)明所要解決的技術(shù)問題是提供一種基于均勻抽樣的二階差分聚類數(shù)確定方法，能夠提高速率的同時達到理想的結(jié)果。

本發(fā)明解決其技術(shù)問題所采用的技術(shù)方案是：提供一種基于均勻抽樣的二階差分聚類數(shù)確定方法，包括以下步驟：

(1)利用均勻抽樣設計得到具有代表性的樣本子集；

(2)利用二階差分確定聚類數(shù)目，對目標函數(shù)求二階差分發(fā)現(xiàn)二階差分的極大值就是最佳聚類數(shù)。

所述步驟(1)具體包括以下子步驟：

(11)設置初始門限值A(chǔ)＞0，從大數(shù)據(jù)集合X中隨機抽取n₀個點，記作令n＝n₀，得到點集A_n的中心化L₂偏差CL₂為CL₂(A_n)²；

(12)在大數(shù)據(jù)集合X中讀取下一輪數(shù)據(jù)為y＝{y₁,…,y_i}，將y當作x_n+1，得到CL₂(A_n+1)²；

(13)得到α＝CL₂(A_n+1)²-CL₂(A_n)²，當α＜A，則y被選中，將A_n+1放入大數(shù)據(jù)集合X中，否則舍棄，令n＝n+1，再返回步驟(12)；當大數(shù)據(jù)集合X中的點被讀取完，抽樣結(jié)束，最終n為抽樣總數(shù)。

所述步驟(2)具體包括以下子步驟：

(21)設定目標函數(shù)為

(22)對目標函數(shù)進行一階差分后，再進行二階差分得到二階差分極大值所對應的點就是最佳聚類數(shù)；其中，λ₁和λ₂分別為類內(nèi)和類間所占的不同權(quán)值，S_W為類內(nèi)散度矩陣，c為聚類數(shù)目，S_B為類間散度矩陣，X為大數(shù)據(jù)集合，c為聚類數(shù)目，Z＝[z₁,…,z_c]表示聚類中心，1＜c＜n，代表第i類與第k類的類間距離的權(quán)重，利用步驟(1)中得到的樣本子集來代替大數(shù)據(jù)集合X。

有益效果

由于采用了上述的技術(shù)方案，本發(fā)明與現(xiàn)有技術(shù)相比，具有以下的優(yōu)點和積極效果：

本發(fā)明根據(jù)均勻抽樣設計，將多維性、稀疏性和動態(tài)性的大數(shù)據(jù)進行數(shù)值分析，用此方法挑選出來的樣本的均勻度、代表性等方面都要優(yōu)于隨機抽樣。

本發(fā)明采用二階差分算法確定精確的最佳聚類數(shù)k，傳統(tǒng)的聚類數(shù)目確定方法通常需要人工確定，而對于很難獲得先驗知識的數(shù)據(jù)集，聚類分析會受到很大的限制，利用二階差分方式自動確定聚類數(shù)，可以實現(xiàn)在完全沒有人工干預的條件下自動確定聚類數(shù)目。

本發(fā)明根據(jù)二階差分的算法得到最佳聚類數(shù)(k)，然后遍歷所有的數(shù)據(jù)，用歐式距離算出這些點與選取的k個中心點的距離，并將這些點分別歸入與之距離最小的中心點，這樣就精確的將所有的數(shù)據(jù)歸為了k類，而傳統(tǒng)的算法得到的只是大概的幾個類。