亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        一種優(yōu)化初始聚類中心的K-means聚類算法*

        2011-05-12 02:47:02周愛武崔丹丹
        關(guān)鍵詞:數(shù)據(jù)挖掘聚類對象

        周愛武,崔丹丹,潘 勇

        (安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,安徽 合肥 230039)

        數(shù)據(jù)挖掘技術(shù)研究不斷深入與發(fā)展,作為數(shù)據(jù)挖掘技術(shù)中的聚類分析,也越來越被人們關(guān)注與研究。聚類分析是數(shù)據(jù)挖掘中一個(gè)非?;钴S的研究領(lǐng)域,并且具有廣泛的應(yīng)用。聚類就是將數(shù)據(jù)集劃分成若干簇或者類的一個(gè)過程[1]。經(jīng)過聚類之后,使得同一簇中的數(shù)據(jù)對象相似度最大,而不同簇之間的相似度最小。

        聚類是一種無監(jiān)督的學(xué)習(xí)算法,即把數(shù)據(jù)對象聚成不同的類簇,從而使不同類之間的數(shù)據(jù)相似度低,而同一個(gè)類中的相似度高,并且將要劃分的類是之前不知道的,其形成由數(shù)據(jù)驅(qū)動。聚類算法[1]分成基于劃分的、密度的、分層的、網(wǎng)格的、模型的。其中基于劃分的聚類算法中的K-均值算法(K-means算法)是最常用的一種聚類算法,同時(shí)也是應(yīng)用最廣泛的一種算法。K-means聚類算法主要針對處理大數(shù)據(jù)集時(shí)[2],處理快速簡單,并且算法具有高效性和可伸縮性。但是K-means算法也有一定的局限性[3],如K值必須事先給定,只能處理數(shù)值型數(shù)據(jù),初始聚類的中心是隨機(jī)選擇的,而其聚類結(jié)果的好壞直接取決于初始聚類中心的選擇。并且由于初始聚類中心隨機(jī)選擇,容易造成算法陷入局部最優(yōu)解。因此初始聚類中心的選擇十分重要。

        本文針對隨機(jī)選擇初始聚類中心的缺點(diǎn),提出了一種新的改進(jìn)的K-means聚類算法。該算法產(chǎn)生的初始聚類中心不是隨機(jī)的,能夠很好地體現(xiàn)數(shù)據(jù)的分布情況,使得初始中心盡可能地趨向于比較密集的范圍內(nèi),從而進(jìn)行更好的聚類,最終消除了傳統(tǒng)K-means算法中由于初始聚類中心選擇是隨機(jī)的而產(chǎn)生的缺點(diǎn)。最后實(shí)驗(yàn)證明了這種算法的有效性與可行性。

        1 傳統(tǒng)K-means算法

        1.1 傳統(tǒng)K-means算法的思想

        傳統(tǒng)的K-means算法具體描述如下[5]:

        輸入:k,data[n];

        輸出:K個(gè)簇的集合。

        (1)任意選擇k個(gè)對象作為初始中心點(diǎn),例如c[0]=data[0],…c[k-1]=data[k-1]。

        (2)根據(jù)簇中對象的均值,將每個(gè)對象指派給最相似的簇。

        (3)更新簇均值,即計(jì)算每個(gè)簇中對象的均值。(4)重復(fù)步驟(2)、(3),直到不再發(fā)生變化。

        1.2 傳統(tǒng)K-means算法的局限性

        傳統(tǒng)的K-means算法中對于K個(gè)中心點(diǎn)的選取是隨機(jī)的[3],而初始點(diǎn)選取的不同會導(dǎo)致不同的聚類結(jié)果。為了減少這種隨機(jī)選取初始聚類中心而導(dǎo)致的聚類結(jié)果的不穩(wěn)定性,本文提出了一種關(guān)于初始聚類中心選取的方法,用來改變這種不穩(wěn)定性。

        2 優(yōu)化初始聚類中心的改進(jìn)K-means算法

        2.1 基本定義

        設(shè)需要聚類的數(shù)據(jù)集:X={xi|xi∈R P,i=1,2,…,n),k個(gè)聚類中心分別用 z1,z2,z3,…zk表示。 有如下定義:

        定義 1 2 個(gè) p 維向 量 xi=(xi1,xi2,…,xip)T和 xj=(xj1,xj2,…,xjp)T數(shù)據(jù)對象間的距離用歐氏距離[6]表示:

        定義 2 二維數(shù)據(jù)樣本點(diǎn)中心 center(xi,xj)[6]:

        定義3 樣本點(diǎn)之間的平均距離Meandist:

        即所有樣本點(diǎn)的兩兩之間的距離之和除以樣本點(diǎn)n的組合數(shù)。

        2.2 改進(jìn)算法流程

        本算法的改進(jìn)建立在沒有離群點(diǎn)的數(shù)據(jù)集上,針對沒有離群點(diǎn)的數(shù)據(jù)進(jìn)行分析。

        輸入:樣本點(diǎn),初值 k。

        輸出:k個(gè)簇的聚類結(jié)果,使平方誤差準(zhǔn)則最小。

        步驟:

        (1)求出兩兩樣本點(diǎn)之間的距離存入矩陣D中。

        (2)初始化集合A以及中心點(diǎn)集合 Center,最小距離的樣本點(diǎn)放入集合A中,并求出其中心最為第一個(gè)初始的聚類中心z1。

        (3)求出次小距離的樣本點(diǎn)的中心,然后求出此中心與z1之間的距離,與Meandist進(jìn)行判斷。如果小于Meandist,則將此樣本點(diǎn)加入A中,再求第三距離小的樣本點(diǎn),重復(fù)步驟(3);如果大于Meandist,則求出此中心存入Center。

        (4)Until集合 Center中的個(gè)數(shù)等于 k,初始聚類中心全部找到。

        (5)用找到的初始聚類中心進(jìn)行K-means聚類。

        算法舉例:

        如圖1所示,假設(shè)有20個(gè)點(diǎn)數(shù)據(jù)集,并且已經(jīng)將孤立點(diǎn)排除,需要將其聚成k=3類。首先計(jì)算兩兩之間的距離,利用定義 2求出 Meandist,并找出最小的距離(如圖中的x1、x2);然后求出其中心,用紅色表示;找出距離次小的距離(如圖中的 x3、x4),計(jì)算出 x3、x4的中心,并加一步判斷。如果這個(gè)中心與前面求出的一個(gè)聚類中心之間的距離小于Meandist,那么就排除這個(gè)聚類中心,接著執(zhí)行找第三小的距離,并求其中心,直到找到K個(gè)初始聚類中心為止;反之,則求下一個(gè)初始聚類中心,直到找到k個(gè)初始聚類中心為止。

        圖1 改進(jìn)算法聚類舉例

        3 實(shí)驗(yàn)分析

        為了便于分析與計(jì)算,本文采用的是二維數(shù)據(jù),并且數(shù)據(jù)類型是實(shí)型的,實(shí)驗(yàn)環(huán)境為MATLAB。為了進(jìn)行對比,分別采用了傳統(tǒng)的K-means算法與本文改進(jìn)的K-means算法進(jìn)行比較。

        本文實(shí)驗(yàn)采用了兩組實(shí)驗(yàn)進(jìn)行驗(yàn)證,一組是隨機(jī)數(shù)據(jù),一組是標(biāo)準(zhǔn)數(shù)據(jù)庫集。

        (1)采用隨機(jī)數(shù)據(jù)

        本文用隨機(jī)產(chǎn)生的80個(gè)樣本分別采用傳統(tǒng)的K-means算法進(jìn)行聚類與本文的改進(jìn)算法進(jìn)行聚類,比較其聚類結(jié)果圖。

        傳統(tǒng)算法采用隨機(jī)選取初始聚類中心有 (0.950 1,0.794 8)、(0.231 1,0.956 8)、(0.606 8,0.522 6), 其聚類結(jié)果如圖2所示。

        采用改進(jìn)算法的初始聚類中心有 (0.339 9、0.028 4),(0.2007,0.5914)、(0.7248,0.3819),其聚類結(jié)果如圖 3 所示。

        圖2 針對隨機(jī)數(shù)據(jù)的傳統(tǒng)的K-means聚類結(jié)果

        圖3 針對隨機(jī)數(shù)據(jù)的改進(jìn)算法聚類結(jié)果

        圖4 Iris數(shù)據(jù)集傳統(tǒng)K-means算法聚類結(jié)果

        圖5 Iris數(shù)據(jù)集改進(jìn)算法聚類結(jié)果

        表1 兩種算法不同數(shù)據(jù)集的執(zhí)行時(shí)間比較

        (2)采用標(biāo)準(zhǔn)數(shù)據(jù)集:Iris數(shù)據(jù)集

        本文采用了Iris數(shù)據(jù)集,它是UCI數(shù)據(jù)庫中的一個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集。Iris數(shù)據(jù)集包含有4個(gè)屬性,150個(gè)數(shù)據(jù)對象,可分為三類。選用Iris數(shù)據(jù)集前二維的數(shù)據(jù)進(jìn)行聚類。分別用傳統(tǒng)算法和改進(jìn)算法進(jìn)行聚類,其中分別用實(shí)心點(diǎn)、圈實(shí)心點(diǎn)以及五角星表示這三類。

        傳統(tǒng)算法采用隨機(jī)選取初始聚類中心有 (0.950 1,0.582 8),(0.231 1,0.423 5)、(0.606 8,0.515 5), 其聚類結(jié)果如圖4所示。

        采用改進(jìn)算法的初始聚類中心有(0.009 9,0.015 0)、(0.294 2,0.639 2)、(0.651 2,0.190 5),其聚類結(jié)果如圖 5所示。

        對比這兩幅圖的聚類結(jié)果可以看出,采用改進(jìn)算法產(chǎn)生聚類結(jié)果比較穩(wěn)定準(zhǔn)確。

        運(yùn)用K-means算法和本文改進(jìn)算法針對隨機(jī)數(shù)據(jù)和Iris數(shù)據(jù)分別實(shí)驗(yàn)得出的時(shí)間如表1所示。

        K-means算法是應(yīng)用最為廣泛的一種基于劃分的算法,但是由于其初始中心的選擇是隨機(jī)的,從而影響了聚類結(jié)果,使得聚類結(jié)果不穩(wěn)定。本文主要是針對傳統(tǒng)K-means算法的這一缺點(diǎn),提出了一種新的改進(jìn)算法,即基于平均距離的思想,進(jìn)行初始聚類中心的選擇。實(shí)驗(yàn)證明,該算法是切實(shí)可行的,與傳統(tǒng)的K-means算法比較,有較好的聚類結(jié)果以及較短的運(yùn)行時(shí)間。但本文算法是基于先將噪聲點(diǎn)排除掉之后應(yīng)用此改進(jìn)算法進(jìn)行聚類、且是在點(diǎn)的分布比較均勻的前提下應(yīng)用,才有良好的效果。如果對于具有噪聲點(diǎn)的數(shù)據(jù)集有一定的局限性、而且是比較密集的點(diǎn)的情況下,這將在以后的學(xué)習(xí)研究中進(jìn)行探討。

        [1]HAN J,KAMBER M.數(shù)據(jù)挖掘概念與技術(shù)[M].范明,盂小峰,等譯.北京:機(jī)械工業(yè)出版社,2006.

        [2]孟海東,張玉英,宋飛燕.一種基于加權(quán)歐氏距離聚類方法的研究[J].計(jì)算機(jī)應(yīng)用,2006,26(22):152-153.

        [3]包穎.基于劃分的聚類算法研究與應(yīng)用[D].大連:大連理工大學(xué),2008:18-20.

        [4]李業(yè)麗,秦臻.一種改進(jìn)的K-means算法[J].北京印刷學(xué)院學(xué)報(bào),2007,15(2):63-65.

        [5]張玉芳,毛嘉莉,熊忠陽.一種改進(jìn)的K-means算法[J].計(jì)算機(jī)應(yīng)用,2003,23(8):31-33.

        [6]袁方,周志勇,宋鑫.初始聚類中心優(yōu)化的k-means算法[J].計(jì)算機(jī)工程,2007,33(3):65-66.

        猜你喜歡
        數(shù)據(jù)挖掘聚類對象
        神秘來電
        睿士(2023年2期)2023-03-02 02:01:09
        探討人工智能與數(shù)據(jù)挖掘發(fā)展趨勢
        攻略對象的心思好難猜
        意林(2018年3期)2018-03-02 15:17:24
        基于DBSACN聚類算法的XML文檔聚類
        電子測試(2017年15期)2017-12-18 07:19:27
        基于并行計(jì)算的大數(shù)據(jù)挖掘在電網(wǎng)中的應(yīng)用
        電力與能源(2017年6期)2017-05-14 06:19:37
        基于熵的快速掃描法的FNEA初始對象的生成方法
        區(qū)間對象族的可鎮(zhèn)定性分析
        基于改進(jìn)的遺傳算法的模糊聚類算法
        一種基于Hadoop的大數(shù)據(jù)挖掘云服務(wù)及應(yīng)用
        一種層次初始的聚類個(gè)數(shù)自適應(yīng)的聚類方法研究
        成年男女免费视频网站点播| 亚洲人成无码网站久久99热国产| 无码国产精品第100页| 久久久精品国产亚洲av网| 澳门蜜桃av成人av| 美女张开腿让男人桶爽| 无码专区中文字幕DVD| 男女性搞视频网站免费| 精品亚洲第一区二区三区| 男人进去女人爽免费视频| 亚洲精品国产综合一线久久| 日本女同伦理片在线观看| 24小时在线免费av| 亚欧色一区w666天堂| 水蜜桃久久| 亚洲色图第一页在线观看视频| 中文字幕在线乱码一区| 中国人妻被两个老外三p| 国产xxxxx在线观看免费 | 一本色道加勒比精品一区二区| 欧美成人秋霞久久aa片| 国产露脸精品产三级国产av| 久久亚洲精品成人综合| 日本一区二区在线高清| 帮老师解开蕾丝奶罩吸乳视频 | 人妻精品无码一区二区三区| 国产码欧美日韩高清综合一区 | 亚洲永久精品ww47| 国产av无码专区亚洲aⅴ| 亚洲中文字幕九色日本| 狠狠综合久久av一区二区 | 色爱av综合网站| 亚洲欧美日韩高清专区一区| 大香蕉久久精品一区二区字幕| 中文乱码字幕精品高清国产| 亚洲第一av导航av尤物| 精品人妻丰满久久久a| 亚洲熟妇av一区二区在线观看 | 成人免费毛片内射美女-百度 | 国产av人人夜夜澡人人爽麻豆| 日本a级大片免费观看|