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

        ?

        一種基于屬性值權(quán)重的k-modes 聚類分析算法*

        2023-08-31 08:41:12郝榮麗胡立華
        計算機與數(shù)字工程 2023年5期
        關(guān)鍵詞:度量權(quán)重聚類

        郝榮麗 胡立華

        (太原科技大學計算機科學與技術(shù)學院 太原 030024)

        1 引言

        聚類分析是數(shù)據(jù)挖掘和機器學習等領(lǐng)域中的主要研究內(nèi)容之一,它是將物理或抽象的數(shù)據(jù)對象根據(jù)某種相似準則劃分成多個對象類的過程,使得同一個類中的對象之間具有較高的相似性,而不同簇中的對象具有較高的相異性[1],并已經(jīng)廣泛地應用在基因分類[2]、股市波動的特征分析[3]、天光光譜特征分析[4]、文檔的分類[5]、圖像處理[6]等許多領(lǐng)域。聚類分析主要分為劃分聚類[7]、層次聚類[8]、密度聚類[9]和網(wǎng)格聚類[10]。k-means算法[11]是一種經(jīng)典、常用的劃分聚類算法,具有簡單高效,易于理解和實現(xiàn)等優(yōu)點,但在實際應用中,由于存在大量的分類型數(shù)據(jù),k-means 方法不能處理包含分類屬性的數(shù)據(jù)集,限制了其實際應用領(lǐng)域。

        k-modes[12]作為k-means 聚類分析算法的一種擴展,可適用于含有分類屬性的數(shù)據(jù)集,具有計算簡單、復雜度低等優(yōu)點,但該聚類算法采用簡單匹配差異法,未能充分體現(xiàn)數(shù)據(jù)集的分布特征,將所有屬性視為同等地位,忽略了屬性之間的重要性差異,若頻率最高的屬性值有多個,傳統(tǒng)k-modes 算法無法選出最恰當?shù)膶傩灾底鳛樵摯啬J健1疚睦么植诩械牡葍r類計算屬性值權(quán)重的思想,提出了一種k-modes 聚類分析算法。由于該算法充分利用了屬性值在數(shù)據(jù)集中的分布特征與屬性值自身的差異,有效地解決了屬性值之間的差異性度量,并利用屬性值頻率和各屬性值的權(quán)重,給出一種聚類中心更新途徑,從而有效地提高了聚類分析的效果。本文主要貢獻為

        1)利用屬性值之間的差異和屬性值的權(quán)重,重新定義了相異度度量公式;

        2)采用屬性值頻率和各屬性值的權(quán)重,給出了一種聚類中心更新迭代公式;

        3)提出了一種基于屬性值權(quán)重的k-modes 聚類算法。

        2 相關(guān)工作

        k-modes 作為k-means 算法的一種擴展,根據(jù)分類數(shù)據(jù)的特點,采用簡單的0-1 匹配法來度量分類數(shù)據(jù)間的距離,用模式代替均值,但是這種采用簡單匹配差異法忽略了屬性之間的差異性,導致差異性度量不準確。對k-modes 改進的典型成果為:He[13]等使用屬性值在類內(nèi)出現(xiàn)的頻率提出新的類內(nèi)屬性距離計算公式;Hsu[14]等提出一種基于概念層次的方法來計算屬性值之間的距離,但該方法需要專家經(jīng)驗;賈彬[15]等使用信息熵為屬性加權(quán)來解決屬性之間的差異問題,但是該方法在確定屬性權(quán)重時只考慮了某一屬性的分布,沒有考慮相關(guān)屬性對其的影響;白亮[16]等利用粗糙集中的上、下近似提出了一種新的相似性度量,改善了聚類效果,卻提高了計算的復雜度;趙亮[17]等基于樸素貝葉斯分類器中間運算結(jié)果計算屬性值之間的距離;黃苑華[18]等基于相互依存的冗余理論提出一種新的距離公式,采用內(nèi)部距離和外部距離共同衡量兩個對象屬性值之間的距離,在進行外部距離計算時,僅從相關(guān)屬性的角度對屬性值在整個數(shù)據(jù)集上的分布情況進行描述,導致差異性度量不準確,這些算法不能夠準確應用屬性空間中數(shù)據(jù)間的關(guān)系,因而會丟失數(shù)據(jù)間的相似關(guān)系。針對傳統(tǒng)k-modes 算法中的模式問題,賈彬[15]提出了多屬性值modes 的相異度度量方法,每個屬性都保留全部屬性值和其出現(xiàn)頻率,但這樣也使得數(shù)據(jù)對象與modes 之間的距離計算變得復雜化。

        綜上所述,k-modes 雖然將k-means 聚類分析算法應用范圍擴展到了分類數(shù)據(jù)集,但其多種距離度量都無法有效地度量分類數(shù)據(jù)之間的距離,未能充分體現(xiàn)分類變量間的差異,以及在整個數(shù)據(jù)集中的分布特征。

        3 聚類目標函數(shù)與多屬性權(quán)重

        為適用于分類數(shù)據(jù)的聚類分析,Huang 等于1998年提出了k-modes聚類算法,給定一組分類數(shù)據(jù)對象X={x1,x2,…,xn}和整數(shù)k(k≤n),數(shù)據(jù)集隨機初始劃分成k個互斥的簇,對數(shù)據(jù)對象迭代重定位簇,最終搜索得到使簇內(nèi)平方誤差和,即目標函數(shù)F最小化的k個互斥的簇,參照文獻[12],其目標函數(shù)定義如下:

        聚類目標函數(shù)為

        在式(1)中,W是一個n×k的{0 ,1} 矩陣,n表示數(shù)據(jù)集U中數(shù)據(jù)點的個數(shù),k表示聚類的個數(shù),Z={z1,z2,…,zk},zl為第l 個類的中心點,zl={zl1,zl2,…,zlm} ,zlm是第l個類的第m個屬性上出現(xiàn)頻率最高的屬性值,d(xi,zl)為簡單的0-1匹配計算得出的分類變量間的距離。

        多屬性值權(quán)重是屬性值在屬性空間中分布特征的體現(xiàn),可從本地屬性和相關(guān)屬性兩個角度,來有效地刻畫屬性值在屬性空間上的分布特征。則參照文獻[19],相關(guān)概念如下:

        對于任意ai∈A,設(shè)xki∈Vai,從本地屬性ai的角度度量xki的單屬性權(quán)重為

        從相關(guān)屬性aj的角度度量xki的多屬性權(quán)重為

        結(jié)合本地屬性和相關(guān)屬性定義屬性值的權(quán)重為

        其中:[xk]ai表示數(shù)據(jù)對象xk在屬性ai的等價類,表示屬性值xki和xkj的共現(xiàn)次數(shù)。屬性值權(quán)重W(xki)體現(xiàn)了屬性值在整個屬性空間中的分布特征。

        4 基于屬性值權(quán)重的k-mode 聚類分析

        兩個數(shù)據(jù)對象同一屬性下兩個值之間是否相似既取決于屬性值本身,又取決于其所處的環(huán)境,即屬性值所處的屬性空間[16]??衫脤傩灾档臋?quán)重來表示屬性空間的分布特征對屬性值相異度的影響,即外部相異度;同時,也需考慮屬性值本身之間的差異性,即內(nèi)部相異度。因此,數(shù)據(jù)對象屬性值之間的相異度是由外部相異度和內(nèi)部相異度共同決定,其相異度越大,距離也越大。

        設(shè)xi和xj為數(shù)據(jù)集中的任意兩個數(shù)據(jù)對象,at為任一屬性,則參照文獻[18],數(shù)據(jù)對象xi和數(shù)據(jù)對象xj在屬性at上的相異度度量公式重新定義如下:

        在式(5)中,d1(xit,xjt)表示兩個數(shù)據(jù)對象屬性值本身的差異度,即內(nèi)部相異度;d2(xit,xjt)表示兩個數(shù)據(jù)對象在整個屬性空間中分布的差異度,即外部相異度;1 2 表示兩種差異度的重要性相當,共同決定了屬性值之間的距離,差異度越高,距離越遠。

        參照文獻[18],數(shù)據(jù)對象xi和數(shù)據(jù)對象xj在屬性at上的內(nèi)部相異度的度量公式如下:

        在式(6)中,使用簡單0-1 匹配來計算兩個屬性值間的內(nèi)部相異度。

        由式(4)引入的屬性值權(quán)重,可得出第i個數(shù)據(jù)對象和第j個數(shù)據(jù)對象在屬性at上的外部相異度的度量公式如下:

        式中W(xit),W(xjt)分別代表屬性值xit和xjt對應的權(quán)重,用權(quán)重的差值來表示他們之間的外部相異度。

        傳統(tǒng)的k-modes 算法在每個簇的每個屬性上選擇出現(xiàn)次數(shù)最多的屬性值作為該簇中心點在該屬性上的值,但是屬性上出現(xiàn)頻率高的屬性值有多個的話難以獲得最合適的中心點,因此,利用屬性取值的頻率以及屬性值的權(quán)重,重新描述類中心,并找出類中心對應的平均權(quán)重,從而可有效提高聚類精度。聚類族中心和對應的平均權(quán)重定義如下:

        定義1 類l中某屬性at上某一屬性值的平均權(quán)重為該類中屬性at對應的該屬性值的所有權(quán)重之和的平均值。

        定義2 類l的中心為zl={zl1,zl2,…,zlm} ,其中zlm為類l中數(shù)據(jù)對象在屬性am上出現(xiàn)頻率最高的,且具有最高平均權(quán)重的屬性值。每一個中心點對應一個平均權(quán)重集平均權(quán)重集代表模式中每個屬性值在屬性空間中的分布情況。

        5 基于屬性值權(quán)重的k-mode 聚類算法

        根據(jù)第3 節(jié)和第4 節(jié)的描述,在分類型數(shù)據(jù)集中,采用重新定義的相異度度量方式以及聚類簇中心選擇的聚類分析基本步驟為利用粗糙集中的等價類,計算數(shù)據(jù)集中所有數(shù)據(jù)對象的屬性值的屬性權(quán)重;隨機選擇數(shù)據(jù)集U中k個數(shù)據(jù)點作為初始的聚類中心;計算數(shù)據(jù)集中所有數(shù)據(jù)對象與k個聚類中心之間的相異度,然后將每個對象分配到與其相異度最小的聚類中心所在的簇中;在得到的k個簇中,更新簇的中心點及其對應的權(quán)重;重復上述兩個步驟,直到目標函數(shù)達到最小值,k個簇的類中心不再發(fā)生變化為止。算法偽代碼描述如下:

        算法:MCAMAW(K-modes clustering algorithm based on multiple attribute weights)

        輸入:分類數(shù)據(jù)集,簇的個數(shù)k

        輸出:聚類簇

        1)for(int i=0;i<n;i++){

        2)for(int j=0;j<m;j++){

        3) 利用xit在屬性at上的等價類,根據(jù)式(2)~(4)計算出屬性值xit的屬性權(quán)重W( )xit。

        4)}

        5)}

        6)隨機初始找出k個簇中心,平均權(quán)重集為其對應的屬性值的權(quán)重

        7)for(int i=0;i<n;i++){

        8) for(int cu=0;cu<k;cu++){

        9) for(int j=0;j<m;j++){

        10) 根據(jù)式(5)~(7)計算出所有數(shù)據(jù)對象與簇中心之間的距離,然后將各個數(shù)據(jù)對象

        11) 分配到離其最近的簇中。

        12)}}}

        13)for(int cu=0;cu<k;cu++){

        14) 根據(jù)定義1 和定義2 更新各個簇的中心及其平均權(quán)重集

        15)}

        16)重復第7)步到第17)步,直至式(3)達到最小值,k個簇的類中心不再發(fā)生變化為止

        17)返回聚類簇

        6 實驗結(jié)果及分析

        為了驗證所提MCAMAW 算法的有效性,從UCI數(shù)據(jù)集中選取Mushroom、Vote、Breast-cancer三個數(shù)據(jù)集,詳見表1 所示。采用python 語言實現(xiàn)了MCAMAW 算法、傳統(tǒng)k-modes 算法[12]和基于相互依存冗余度量k-modes 算法[18],并分別從分類正確率、分類精度和召回率三個指標進行評價。

        表1 UCI數(shù)據(jù)集

        表2~4 給出了MCAMAW 算法與傳統(tǒng)k-modes算法[12]和基于相互依存冗余度量k-modes 算法[18]的實驗比較結(jié)果??梢钥闯鲈贛ushroom、Vote、Breast-cancer數(shù)據(jù)集上MCAMAW 算法的三個指標均有所提高,聚類效果也優(yōu)于其他兩個算法。其主要原因是MCAMAW 算法充分利用數(shù)據(jù)對象在數(shù)據(jù)集中的空間特征,準確地描述了數(shù)據(jù)對象之間的關(guān)系,有效地避免了其他兩個對比算法中分類數(shù)據(jù)對象之間距離度量不準確的問題。

        表2 Mushroom數(shù)據(jù)集

        表3 Vote數(shù)據(jù)集

        表4 Breast-cancer數(shù)據(jù)集

        7 結(jié)語

        本文采用多屬性權(quán)重,提出了一種k-modes 聚類算法。該算法從本地屬性和相關(guān)屬性兩個角度,描述了數(shù)據(jù)對象的屬性空間分布特征。在度量數(shù)據(jù)對象間的距離時,不僅考慮了數(shù)據(jù)對象本身的差異性,而且考慮了數(shù)據(jù)對象在整個屬性空間結(jié)構(gòu)中的差異性。此外,在屬性值分布過于分散或相對均等時,可以根據(jù)屬性值的平均權(quán)重進一步確定模式中的屬性值,以便能夠找到更恰當?shù)膶傩灾底鳛樵擃惖哪J?,從而有效地提高聚類效果?/p>

        猜你喜歡
        度量權(quán)重聚類
        有趣的度量
        模糊度量空間的強嵌入
        權(quán)重常思“浮名輕”
        當代陜西(2020年17期)2020-10-28 08:18:18
        迷向表示分為6個不可約直和的旗流形上不變愛因斯坦度量
        為黨督政勤履職 代民行權(quán)重擔當
        基于DBSACN聚類算法的XML文檔聚類
        電子測試(2017年15期)2017-12-18 07:19:27
        基于公約式權(quán)重的截短線性分組碼盲識別方法
        電信科學(2017年6期)2017-07-01 15:44:57
        地質(zhì)異常的奇異性度量與隱伏源致礦異常識別
        基于改進的遺傳算法的模糊聚類算法
        一種層次初始的聚類個數(shù)自適應的聚類方法研究
        国产美女在线精品免费观看网址| 东京热加勒比国产精品| 成人自拍偷拍视频在线观看| 经典三级免费看片天堂| 欧洲美女熟乱av| 日本成本人三级在线观看| 国产目拍亚洲精品一区二区 | 无码一区二区三区不卡AV| 水蜜桃视频在线观看免费18| 精品久久免费国产乱色也| av手机在线观看不卡| 日本边添边摸边做边爱喷水| 岳毛多又紧做起爽| 女同亚洲女同精品| 国产三级视频一区二区| 国产色av一区二区三区| 亚洲精品无码不卡| 少妇装睡让我滑了进去| 国产午夜福利不卡在线观看视频| 日韩精品一区二区三区四区| 亚洲av永久综合网站美女| 东风日产车是不是国产的| 噜噜噜噜私人影院| 亚洲欧洲无码一区二区三区| 2021年国产精品每日更新| 国产女主播免费在线观看| 亚洲av狠狠爱一区二区三区| 亚洲深深色噜噜狠狠网站| 国产网红主播无码精品| 久久久久亚洲av无码a片软件| 国产精品女同一区二区久久| 男男互吃大丁视频网站| 五月激情四射开心久久久| 国产爆乳无码一区二区麻豆| v一区无码内射国产| 精品国产网红福利在线观看| 激情五月婷婷久久综合| 你懂的视频网站亚洲视频 | 性感美女脱内裤无遮挡| 久久人妻av一区二区软件| 97夜夜澡人人爽人人喊中国片|