分類型數(shù)據(jù)的聚類算法研究.pdf

1、作為數(shù)據(jù)挖掘中重要的技術(shù)——聚類分析，它按照相似原則將數(shù)據(jù)進(jìn)行分類.在無監(jiān)督學(xué)習(xí)下，聚類的最終結(jié)果是將海量的數(shù)據(jù)有效地劃分為各個(gè)子類，使得同一個(gè)類別中數(shù)據(jù)對(duì)象的相異度盡可能低，不同類別中數(shù)據(jù)對(duì)象的相異度盡可能高.目前，數(shù)值型數(shù)據(jù)的聚類已經(jīng)取得較好的成果了，如經(jīng)典的k-means算法已得到廣泛的應(yīng)用和推廣.然而在實(shí)際生活中，存在大量的分類型數(shù)據(jù).由于分類型數(shù)據(jù)不具有數(shù)值型數(shù)據(jù)的幾何特性，所以無法直接進(jìn)行數(shù)值運(yùn)算.于是，分類型數(shù)據(jù)的聚類相對(duì)

2、來說就變得比較復(fù)雜，它是學(xué)習(xí)算法中重要而又棘手的問題之一.近年來，許多學(xué)者針對(duì)分類型數(shù)據(jù)的聚類進(jìn)行了探索和改進(jìn).
　　針對(duì)k-means算法不適用于分類型數(shù)據(jù)這一問題，k-modes算法在此基礎(chǔ)上進(jìn)行了拓展.本文針對(duì)了k-modes聚類算法中的若干問題進(jìn)行了研究，并對(duì)比和分析了現(xiàn)有的各種改進(jìn)后的k-modes算法.傳統(tǒng)的k-modes算法采用0-1匹配方法定義每兩個(gè)對(duì)象屬性之間的距離，不僅沒有將整個(gè)數(shù)據(jù)集的分布考慮進(jìn)來，而且忽視了

3、屬性間的相互關(guān)系對(duì)距離的影響，導(dǎo)致差異度度量不夠準(zhǔn)確.針對(duì)以上問題，本文的研究成果主要有以下幾個(gè)方面:
　　(1)從互信息的角度出發(fā)，基于相互依存冗余理論定義了同一屬性下不同屬性值之間的距離，進(jìn)一步改進(jìn)了Hongjia提出的距離公式.改進(jìn)后的距離由內(nèi)部距離和外部距離兩個(gè)部分決定，內(nèi)部距離體現(xiàn)了每兩個(gè)對(duì)象屬性值本身的差異度，外部距離體現(xiàn)了其他屬性對(duì)該屬性的影響程度.
　　(2)本文將基于相互依存冗余的距離應(yīng)用于k-modes算

4、法中，并分析了改進(jìn)后算法的時(shí)間復(fù)雜度.與基于其他距離度量的k-modes算法進(jìn)行實(shí)驗(yàn)比較，結(jié)果表明基于相互依存冗余度量的k-modes算法不僅能有效處理大規(guī)模數(shù)據(jù)，而且能有效提高算法的聚類精度.
　　(3)從屬性值共現(xiàn)的思想出發(fā)，基于結(jié)構(gòu)相似性計(jì)算模型給出一種新的相異度度量方法，并將其應(yīng)用于傳統(tǒng)的k-modes算法，同時(shí)分析了改進(jìn)后算法的時(shí)間復(fù)雜度.該方法不僅考慮了屬性值它們本身的異同，而且考慮了它們?cè)谄渌麑傩韵滤幍臓顟B(tài).實(shí)驗(yàn)結(jié)