模糊數(shù)學(xué)及其應(yīng)用(4-6講)

1、 聚類分析是用數(shù)學(xué)方法定量地確定樣本的親疏關(guān)系，從聚類分析是用數(shù)學(xué)方法定量地確定樣本的親疏關(guān)系，從而客觀地劃分類型。而事物之間的界限，有些是確切的，而客觀地劃分類型。而事物之間的界限，有些是確切的，有些則是模糊的。有些則是模糊的。例如：例如：人群中的面貌相像程度之間的界限是模糊的，人群中的面貌相像程度之間的界限是模糊的， 天氣陰、晴之間的界限也是模糊的。天氣陰、晴之間的界限也是模糊的。 當(dāng)聚類涉及事物之間的模糊界限時(shí)，需運(yùn)用當(dāng)聚類涉及事物之間的模糊界限時(shí)，需運(yùn)用模糊聚類分模糊聚類分析析方法。方法。 模糊聚類分析模糊聚類分析廣泛應(yīng)用在氣象預(yù)報(bào)、地質(zhì)、農(nóng)業(yè)、林業(yè)廣泛應(yīng)用在氣象預(yù)報(bào)、地質(zhì)、農(nóng)業(yè)、林業(yè)

2、等方面。等方面。第第二二章章 模糊聚類分析模糊聚類分析“物以類聚，人以群居物以類聚，人以群居”一一. . 模糊矩陣模糊矩陣 定義定義1 設(shè)設(shè)R = (rij)mn，若，若0rij1，則稱，則稱R為為模模糊矩陣糊矩陣. 當(dāng)當(dāng)rij只取只取0或或1時(shí)，稱時(shí)，稱R為為布爾布爾(Boole)矩陣矩陣. 當(dāng)模糊方陣當(dāng)模糊方陣R = (rij)nn的對(duì)角線上的元素的對(duì)角線上的元素rii都為都為1時(shí)，稱時(shí)，稱R為為模糊自反矩陣模糊自反矩陣.如如：0.10.20.30.10.40.5011為一個(gè)模糊矩陣為一個(gè)模糊矩陣。定義定義2 設(shè)設(shè)A=(aij)mn, ,B=(bij)mn都都是模糊矩陣，則是模糊矩陣，則相

3、等相等：A = B aij = bij；包含包含：AB aijbij；并并：AB = (aijbij)mn；交交：AB = (aijbij)mn；余余：Ac = (1- - aij)mn.0.1 0.20.3 0.4,0.5 0.70.2 0.8AB0.30.40.10.2,0.50.80.20.7ABAB例例1：則：則：二二. 模糊矩陣的合成（乘法）模糊矩陣的合成（乘法）定義定義3 設(shè)設(shè)A = (aik)ms，B = (bkj)sn，定義模糊矩陣，定義模糊矩陣A 與與B 的合成為：的合成為：A B = (cij)mn，其中其中cij = (aikbkj) | 1ks .10.70.4 0.7

4、0,0.4 0.610.8 0.500.3AB0.4 0.4 00.4 0.6 00.4 0.61 0.4 00.7 0.6 0.310.7A B例例2：則則三三. .模糊方陣的冪模糊方陣的冪定義定義4 設(shè)設(shè)A為為 n 階模糊方陣，定義階模糊方陣，定義A2 = A A，A3 = A2 A，Ak = Ak- -1 A. 如：如：7 . 04 . 03 . 03 . 07 . 04 . 03 . 01 . 07 . 04 . 03 . 03 . 07 . 04 . 03 . 01 . 07 . 04 . 03 . 01 . 07 . 04 . 03 . 01 . 07 . 04 . 03 . 01

5、 . 03四四. .模糊矩陣的模糊矩陣的 - -截矩陣截矩陣 定義定義5 設(shè)設(shè)A = (aij)mn為模糊矩陣,對(duì)任意的對(duì)任意的 0, 1，稱，稱 A = (aij( )mn為模糊矩陣為模糊矩陣A的的 - - 截矩陣截矩陣, 其中其中 當(dāng)當(dāng)aij 時(shí)，時(shí)，aij( ) =1；當(dāng)；當(dāng)aij 時(shí)，時(shí)，aij( ) =0.注：注：A的的 - - 截矩陣為布爾矩陣截矩陣為布爾矩陣. ,18 . 03 . 008 . 011 . 02 . 03 . 01 . 015 . 002 . 05 . 01A例例3：11101100101100113.0A取=0.3，則定理定理1 1 對(duì)任意的對(duì)任意的 0, 1，

6、有：，有：性質(zhì)性質(zhì)1：AB A B ；性質(zhì)性質(zhì)2：(AB) = A B ，(AB) = A B ；性質(zhì)性質(zhì)3：( A B ) = A B ； 下面僅對(duì)性質(zhì)下面僅對(duì)性質(zhì)1做一證明：做一證明：下面證明性質(zhì)下面證明性質(zhì)1： AB A B 證明：證明： AB aijbij；當(dāng)當(dāng) aijbij時(shí)，時(shí)， aij( ) =bij( ) =1；當(dāng)當(dāng)aij bij時(shí)，時(shí)， aij( ) =0, bij( ) =1；當(dāng)當(dāng)aijbij 時(shí)，時(shí)， aij( ) = bij( ) =0；綜上知綜上知aij( )bij( )， 故故A B . 與模糊集是經(jīng)典集合的推廣一樣，模糊關(guān)系是普通與模糊集是經(jīng)典集合的推廣一樣，模糊

7、關(guān)系是普通關(guān)系的推廣關(guān)系的推廣. .定義定義6 設(shè)有論域設(shè)有論域X，Y，X Y 的一個(gè)模糊子集的一個(gè)模糊子集 R 稱為從稱為從 X 到到 Y 的的模糊關(guān)系模糊關(guān)系. 五五. .模糊關(guān)系模糊關(guān)系注注1：模糊子集模糊子集 R 的隸屬函數(shù)為映射的隸屬函數(shù)為映射 R : X Y 0,1. 并稱隸屬度并稱隸屬度R (x , y ) 為為 (x , y )關(guān)于模糊關(guān)關(guān)于模糊關(guān)系系 R 的相關(guān)程度的相關(guān)程度. 特別地，特別地，當(dāng)當(dāng) X =Y 時(shí)，時(shí)，稱之為稱之為 X 上各元素之上各元素之間的間的模糊關(guān)系模糊關(guān)系. 例例4 設(shè)設(shè)x,y指人，則指人，則“x和和y相像相像”這種關(guān)系是模糊關(guān)這種關(guān)系是模糊關(guān)系。如：

8、系。如：R(x,y)=0.80.8表示：兩人像的程度為表示：兩人像的程度為0.80.8。例例5 設(shè)設(shè)X=X1X2=(x,y)|xX1,yX2, 則模糊關(guān)系則模糊關(guān)系R：“x比比y大得多大得多” 的隸屬函數(shù)可以表示為：的隸屬函數(shù)可以表示為：20,1( ,),1001()xyR x yxyxy=注注2:模糊關(guān)系的運(yùn)算模糊關(guān)系的運(yùn)算 由于由于模糊關(guān)系模糊關(guān)系 R就是就是X Y 的一個(gè)模糊子集，因的一個(gè)模糊子集，因此模糊關(guān)系同樣具有模糊子集此模糊關(guān)系同樣具有模糊子集的運(yùn)算及性質(zhì)的運(yùn)算及性質(zhì).定理定理2 設(shè)設(shè)R，R1，R2均為從均為從 X 到到 Y 的的模糊關(guān)系模糊關(guān)系,則：則：相等相等：R1= R2

9、R1(x, y) = R2(x, y)；包含包含： R1 R2 R1(x, y)R2(x, y)；并并： R1R2 的隸屬函數(shù)為的隸屬函數(shù)為 (R1R2 )(x, y) = R1(x, y)R2(x, y)；交交： R1R2 的隸屬函數(shù)為的隸屬函數(shù)為(R1R2 )(x, y) = R1(x, y)R2(x, y)；余余：Rc 的隸屬函數(shù)為的隸屬函數(shù)為Rc (x, y) = 1- - R(x, y).注注3: (R1R2 )(x, y)表示表示(x, y)對(duì)模糊關(guān)系對(duì)模糊關(guān)系“R1或者或者R2”的的相關(guān)程度，相關(guān)程度， (R1R2 )(x, y)表示表示(x, y)對(duì)模糊關(guān)系對(duì)模糊關(guān)系“R1且且

10、R2”的相關(guān)程度，的相關(guān)程度，Rc (x, y)表示表示(x, y)對(duì)模糊關(guān)系對(duì)模糊關(guān)系“非非R”的相的相關(guān)程度關(guān)程度.注注4:模糊關(guān)系通常采用模糊矩陣表示模糊關(guān)系通常采用模糊矩陣表示 對(duì)于有限論域?qū)τ谟邢拚撚?X = x1, x2, , xm和和Y = y1, y2, , yn，則則X 到到Y(jié)的的 模糊關(guān)系模糊關(guān)系R可用可用mn 階模糊矩陣表示，即階模糊矩陣表示，即R = (rij)mn，其中其中rij = R (xi , yj )0, 1表示表示(xi , yj )關(guān)于模糊關(guān)系關(guān)于模糊關(guān)系R 的相的相關(guān)程度關(guān)程度. . 例例6 設(shè)身高論域設(shè)身高論域X =140, 150, 160, 170

11、, 180 (單位：?jiǎn)挝唬篶m), 體重論域體重論域Y =40, 50, 60, 70, 80(單位：?jiǎn)挝唬簁g), ,下表給出了身下表給出了身高與體重的模糊關(guān)系高與體重的模糊關(guān)系R R：40506070801400.90.80.20.101500.80.90.80.20.11600.20.80.90.80.21700.10.20.80.90.818000.10.20.80.9如：如：R（160,50）=0.8表示身高表示身高160cm與體重與體重50kg的相關(guān)程度為的相關(guān)程度為0.8即：此處模糊關(guān)系即：此處模糊關(guān)系R R可以表示為：可以表示為：0.90.80.20.100.80.90.80.

12、20.10.20.80.90.80.20.10.20.80.90.800.10.20.80.9R注注5: R是是X上上各元素之間的各元素之間的模糊關(guān)系，模糊關(guān)系， (1)(1)若若R(x, x) =1，則稱，則稱R具有具有自反性；自反性； (2)(2)若若R(x, y) =R(y, x)，則稱，則稱R具有具有對(duì)稱性；對(duì)稱性； (3)(3)若若R2 R，則稱，則稱R具有具有傳遞性；傳遞性； (4)(4)若若R具有自反性、對(duì)稱性、傳遞性，則稱具有自反性、對(duì)稱性、傳遞性，則稱R是是X上上的一個(gè)的一個(gè)模糊等價(jià)關(guān)系模糊等價(jià)關(guān)系. .如如：“相像關(guān)系相像關(guān)系”具有自反性、對(duì)稱性，但無傳具有自反性、對(duì)稱性，

13、但無傳遞性；遞性；“仇敵關(guān)系仇敵關(guān)系”不具自反性、傳遞性；不具自反性、傳遞性；“相相愛關(guān)系愛關(guān)系”不具對(duì)稱性不具對(duì)稱性注注6: 若模糊關(guān)系若模糊關(guān)系 R 是是 X 上各元素之間的上各元素之間的模糊關(guān)系，且模糊關(guān)系，且滿足：滿足： (1) 自反性：自反性：R( x , x ) = 1； (2) 對(duì)稱性：對(duì)稱性：R( x , y ) = R( y , x ) ； 則稱則稱模糊關(guān)系模糊關(guān)系 R 是是 X 上的一個(gè)上的一個(gè)模糊相似關(guān)系模糊相似關(guān)系. 定義定義1 1 若若R 是是n階模糊相似矩陣，則存在一個(gè)最小階模糊相似矩陣，則存在一個(gè)最小自然數(shù)自然數(shù) k (kn )，對(duì)于一切大于，對(duì)于一切大于k 的自

14、然數(shù)的自然數(shù) l，恒有，恒有Rl = Rk，即，即Rk 是模糊等價(jià)矩陣是模糊等價(jià)矩陣(R2k = Rk ). 此時(shí)稱此時(shí)稱Rk為為R的傳的傳遞閉包，記作遞閉包，記作 t ( R ) = Rk . 六六. .模糊矩陣的傳遞閉包模糊矩陣的傳遞閉包從一般的模糊從一般的模糊矩陣出發(fā)尋求矩陣出發(fā)尋求模糊等價(jià)矩陣模糊等價(jià)矩陣Transitive：傳遞的傳遞的上述定理表明，任一個(gè)模糊相似矩陣可誘導(dǎo)出一個(gè)上述定理表明，任一個(gè)模糊相似矩陣可誘導(dǎo)出一個(gè)模糊等價(jià)矩陣模糊等價(jià)矩陣. 通常采用通常采用二次平方法二次平方法求傳遞閉包求傳遞閉包 t (R)：RR2R4R8R16當(dāng)?shù)谝淮纬霈F(xiàn)當(dāng)?shù)谝淮纬霈F(xiàn)Rk Rk=Rk時(shí)（表

15、明時(shí)（表明Rk具有傳遞性），具有傳遞性）， Rk就就是所求的傳遞閉包是所求的傳遞閉包t(R).10.10.20.110.3 ,0.20.31R .t R210.1 0.210.1 0.210.2 0.20.110.30.110.30.210.3.0.2 0.310.2 0.310.2 0.31R RR 22210.2 0.210.2 0.210.2 0.20.210.3 0.210.30.210.3.0.2 0.310.2 0.310.2 0.31RRR 2R .t R例例1 設(shè)設(shè)求求R R的傳遞閉包的傳遞閉包解：解： 則則即為即為R的傳遞閉包的傳遞閉包七七. .模糊聚類的一般步驟：模糊聚類的

16、一般步驟： （1 1）構(gòu)建數(shù)據(jù)矩陣）構(gòu)建數(shù)據(jù)矩陣 設(shè)論域設(shè)論域X = x1, x2, , xn為被分類對(duì)象為被分類對(duì)象, ,每個(gè)對(duì)象又每個(gè)對(duì)象又由由m個(gè)指標(biāo)表示其形狀個(gè)指標(biāo)表示其形狀: :xi = xi1, xi2, , xim, i = 1, 2, , n于是于是, ,得到原始數(shù)據(jù)矩陣為：得到原始數(shù)據(jù)矩陣為：nmnnmmxxxxxxxxx.212222111211n個(gè)對(duì)象，個(gè)對(duì)象，m個(gè)指標(biāo)個(gè)指標(biāo)（2）數(shù)據(jù)標(biāo)準(zhǔn)化）數(shù)據(jù)標(biāo)準(zhǔn)化由于實(shí)際問題中，不同的數(shù)據(jù)一般有不同的量綱，為了由于實(shí)際問題中，不同的數(shù)據(jù)一般有不同的量綱，為了使具有不同量綱的量也能進(jìn)行比較，通常需要對(duì)數(shù)據(jù)作使具有不同量綱的量也能進(jìn)行比

17、較，通常需要對(duì)數(shù)據(jù)作適當(dāng)?shù)淖儞Q（無量綱化處理）。適當(dāng)?shù)淖儞Q（無量綱化處理）。即使這樣，得到的數(shù)據(jù)也不一定在區(qū)間即使這樣，得到的數(shù)據(jù)也不一定在區(qū)間0,1上，因此，上，因此，還需要對(duì)數(shù)據(jù)標(biāo)準(zhǔn)化。還需要對(duì)數(shù)據(jù)標(biāo)準(zhǔn)化。 數(shù)據(jù)標(biāo)準(zhǔn)化通常需要作如下變換：數(shù)據(jù)標(biāo)準(zhǔn)化通常需要作如下變換：（）平移）平移 標(biāo)準(zhǔn)差變換標(biāo)準(zhǔn)差變換：),.,2 , 1,.,2 , 1(mjnisxxxjjijij其中其中nijijjniijjxxnsxnx121)(1,1無量綱化無量綱化樣本均值樣本均值樣本標(biāo)準(zhǔn)差樣本標(biāo)準(zhǔn)差（）相似系數(shù)）相似系數(shù) -夾角余弦法夾角余弦法mkjkmkikmkjkikijxxxxr12121線性代數(shù)中向量線

18、性代數(shù)中向量x與與y的的夾角余弦夾角余弦 |,cosyxyx（3）建立模糊相似矩陣）建立模糊相似矩陣首先確定每?jī)蓚€(gè)對(duì)象間的相似程度：首先確定每?jī)蓚€(gè)對(duì)象間的相似程度：( , )ijiirR x y一般的，常用距離法確定一般的，常用距離法確定rij :rij=1-cd(xi,xj)選取適當(dāng)?shù)倪x取適當(dāng)?shù)腸，使，使0rij1.d(xi,xj)為為xi與與xj間的距離，間的距離，常用的距離如下：常用的距離如下：1(,)|mijikjkkd xxxx21(,)()mijikjkkdxxxx()()海明（海明（HammingHamming）距離：）距離：()()歐氏歐氏(Euclid)(Euclid)距離：

19、距離：最后建立模糊相似矩陣最后建立模糊相似矩陣R=(rij)nn()切比雪夫切比雪夫(Chebyshev)距離距離:d (xi, xj ) = | xik- xjk | , 1km（4）求模糊相似矩陣）求模糊相似矩陣R的傳遞閉包的傳遞閉包t(R)t(R)便為所求的模糊等價(jià)矩陣便為所求的模糊等價(jià)矩陣. （5）設(shè)定閾值）設(shè)定閾值，進(jìn)行分類，進(jìn)行分類的取值可根據(jù)實(shí)際問題而定的取值可根據(jù)實(shí)際問題而定. .閾閾：門檻，界限：門檻，界限弟子規(guī)弟子規(guī)-謹(jǐn)謹(jǐn)：“勿踐勿踐閾閾，勿跛，勿跛倚，勿箕踞，勿搖髀倚，勿箕踞，勿搖髀”例例2 現(xiàn)有現(xiàn)有5座城市座城市12345,x x x x x可由污染物在空氣可由污染物在

20、空氣(y(y1 1) )、水分、水分(y(y2 2) )、土壤、土壤(y(y3 3) )、作物、作物(y(y4 4) )四個(gè)要素中的含量進(jìn)行評(píng)價(jià)。詳細(xì)數(shù)據(jù)如下：四個(gè)要素中的含量進(jìn)行評(píng)價(jià)。詳細(xì)數(shù)據(jù)如下：這五座城市的污染狀況這五座城市的污染狀況 y1 y2 y3 y4 x1x2x3X4x5 5 5 3 2 2 3 4 5 5 5 2 3 1 5 3 1 2 4 5 1請(qǐng)將這請(qǐng)將這5座城市按座城市按污染狀況污染狀況進(jìn)行分類進(jìn)行分類。解：解：第一步第一步. .構(gòu)造數(shù)據(jù)矩陣：構(gòu)造數(shù)據(jù)矩陣：55322345552315312451第二步第二步. 將數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化將數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化：11,1,mijikjkk

21、ijrcxxij0.1,4, ,1,2, 5.cmi j 設(shè)設(shè)其中：其中： 10.10.80.50.30.110.10.20.40.80.110.30.10.50.20.310.60.30.40.10.61R第三步第三步. 建立模糊相似矩陣：建立模糊相似矩陣： 第四步：利用第四步：利用二次平方法二次平方法，求，求R的傳遞閉包：的傳遞閉包：210.3 0.8 0.5 0.50.310.2 0.4 0.40.8 0.210.5 0.30.5 0.4 0.510.60.5 0.4 0.3 0.61R RRR224210.40.80.50.50.410.40.40.40.8 0.410.50.50.5

22、 0.40.510.60.5 0.40.5 0.61RRRR44410.40.80.50.50.410.40.40.40.80.410.50.50.50.40.510.60.50.40.50.61RRR這樣便得到這樣便得到R的傳遞閉包為的傳遞閉包為R4，記為，記為R*.第五步：設(shè)閾值第五步：設(shè)閾值=0.8(=0.8(八分像八分像) )，則：，則：*1010001000101000001000001R13245, , , , .xxxxx從而分類結(jié)果為：從而分類結(jié)果為：最佳分類的確定最佳分類的確定:在模糊聚類分析中，對(duì)于各個(gè)不同的在模糊聚類分析中，對(duì)于各個(gè)不同的 0,10,1，可得，可得到不同的

23、分類，從而形成一種動(dòng)態(tài)聚類圖，這對(duì)全面到不同的分類，從而形成一種動(dòng)態(tài)聚類圖，這對(duì)全面了解樣本分類情況是比較形象和直觀的了解樣本分類情況是比較形象和直觀的. . 但在許多實(shí)際問題中，需要給出樣本的一個(gè)具體但在許多實(shí)際問題中，需要給出樣本的一個(gè)具體分類，這就提出了如何確定最佳分類的問題分類，這就提出了如何確定最佳分類的問題. . 設(shè)設(shè)X = (xij)nm為為n個(gè)元素個(gè)元素m個(gè)指標(biāo)的原始數(shù)據(jù)個(gè)指標(biāo)的原始數(shù)據(jù)矩陣矩陣. 為總體樣本的中心向量為總體樣本的中心向量.x 對(duì)應(yīng)于對(duì)應(yīng)于 值的分類數(shù)為值的分類數(shù)為r，第，第 j 類的樣本數(shù)為類的樣本數(shù)為nj，第，第 j 類的樣本標(biāo)記為類的樣本標(biāo)記為.,.,)(

24、)(2)(1jnjjjxxx第第 j 類樣本的中心向量為類樣本的中心向量為( ).jx), 1()/(|) 1/(|112)()(12)(rnrFrnxxrxxnFrjnkjjkrjjjj作作F- - 統(tǒng)計(jì)量：統(tǒng)計(jì)量： 如果滿足不等式如果滿足不等式FF ( r - -1, n - -r )的的F值不值不止一個(gè)，則可根據(jù)實(shí)際情況選擇一個(gè)滿意的分類，止一個(gè)，則可根據(jù)實(shí)際情況選擇一個(gè)滿意的分類，或者進(jìn)一步考查差或者進(jìn)一步考查差 ( F - - F )/F 的大小，從較大的大小，從較大者中找一個(gè)滿意的者中找一個(gè)滿意的F值即可值即可. 實(shí)際上，最佳分類的確定方法與聚類方法無實(shí)際上，最佳分類的確定方法與聚

25、類方法無關(guān)，但是選擇較好的聚類方法，可以較快地找到關(guān)，但是選擇較好的聚類方法，可以較快地找到比較滿意的分類比較滿意的分類. .例例3 2000 2000年網(wǎng)易杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽年網(wǎng)易杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽 （DNADNA序列分類）序列分類） DNA(Deoxyribonucleic acid)，中文譯名為，中文譯名為脫氧核脫氧核糖核酸糖核酸，是，是染色體染色體的主要的主要化學(xué)成分，同時(shí)也是化學(xué)成分，同時(shí)也是基因基因組成的，有時(shí)被稱為組成的，有時(shí)被稱為“遺遺傳微粒傳微?！薄NA是一種分是一種分子，可組成遺傳指令，以子，可組成遺傳指令，以引導(dǎo)生物發(fā)育與生命機(jī)能引導(dǎo)生物發(fā)育與生命機(jī)能運(yùn)作。

26、運(yùn)作。 o 2000年年6月，人類基因組計(jì)劃中月，人類基因組計(jì)劃中DNA全序全序列草圖完成，預(yù)計(jì)列草圖完成，預(yù)計(jì)2001年可以完成精確的年可以完成精確的全序列圖，此后人類將擁有一本記錄著自身全序列圖，此后人類將擁有一本記錄著自身生老病死及遺傳進(jìn)化的全部信息的生老病死及遺傳進(jìn)化的全部信息的“天書天書”。這本大自然寫成的這本大自然寫成的“天書天書”是由是由4個(gè)字符個(gè)字符A，T，C，G按一定順序排成的長(zhǎng)約按一定順序排成的長(zhǎng)約30億的序億的序列，其中沒有列，其中沒有“斷句斷句”也沒有標(biāo)點(diǎn)符號(hào)，除也沒有標(biāo)點(diǎn)符號(hào)，除了這了這4個(gè)字符表示個(gè)字符表示4種堿基以外，人們對(duì)它種堿基以外，人們對(duì)它包含的包含的“內(nèi)容

27、內(nèi)容”知之甚少，難以讀懂。知之甚少，難以讀懂。 破譯這部世界上最巨量信息的破譯這部世界上最巨量信息的“天書天書”是二是二十一世紀(jì)最重要的任務(wù)之一。在這個(gè)目標(biāo)中，十一世紀(jì)最重要的任務(wù)之一。在這個(gè)目標(biāo)中，研究研究DNA全序列具有什么結(jié)構(gòu)，由這全序列具有什么結(jié)構(gòu)，由這4個(gè)字個(gè)字符排成的看似隨機(jī)的序列中隱藏著什么規(guī)律，符排成的看似隨機(jī)的序列中隱藏著什么規(guī)律，又是解讀這部天書的基礎(chǔ)，是生物信息學(xué)又是解讀這部天書的基礎(chǔ)，是生物信息學(xué)（Bioinformatics）最重要的課題之一。）最重要的課題之一。 雖然人類對(duì)這部雖然人類對(duì)這部“天書天書”知之甚少，但也發(fā)知之甚少，但也發(fā)現(xiàn)了現(xiàn)了DNA序列中的一些規(guī)律性

28、和結(jié)構(gòu)。例序列中的一些規(guī)律性和結(jié)構(gòu)。例如，在全序列中有一些是用于編碼蛋白質(zhì)的如，在全序列中有一些是用于編碼蛋白質(zhì)的序列片段，即由這序列片段，即由這4個(gè)字符組成的個(gè)字符組成的64種不同種不同的的3字符串，其中大多數(shù)用于編碼構(gòu)成蛋白字符串，其中大多數(shù)用于編碼構(gòu)成蛋白質(zhì)的質(zhì)的20種氨基酸。又例如，在不用于編碼種氨基酸。又例如，在不用于編碼蛋白質(zhì)的序列片段中，蛋白質(zhì)的序列片段中，A和和T的含量特別多的含量特別多些，于是以某些堿基特別豐富作為特征去研些，于是以某些堿基特別豐富作為特征去研究究DNA序列的結(jié)構(gòu)也取得了一些結(jié)果。序列的結(jié)構(gòu)也取得了一些結(jié)果。 此外，利用統(tǒng)計(jì)的方法還發(fā)現(xiàn)序列的某些片此外，利用統(tǒng)

29、計(jì)的方法還發(fā)現(xiàn)序列的某些片段之間具有相關(guān)性，等等。這些發(fā)現(xiàn)讓人們段之間具有相關(guān)性，等等。這些發(fā)現(xiàn)讓人們相信，相信，DNA序列中存在著局部的和全局性序列中存在著局部的和全局性的結(jié)構(gòu)，充分發(fā)掘序列的結(jié)構(gòu)對(duì)理解的結(jié)構(gòu)，充分發(fā)掘序列的結(jié)構(gòu)對(duì)理解DNA全序列是十分有意義的。目前在這項(xiàng)研究中全序列是十分有意義的。目前在這項(xiàng)研究中最普通的思想是省略序列的某些細(xì)節(jié)，突出最普通的思想是省略序列的某些細(xì)節(jié)，突出特征，然后將其表示成適當(dāng)?shù)臄?shù)學(xué)對(duì)象。特征，然后將其表示成適當(dāng)?shù)臄?shù)學(xué)對(duì)象。 這種被稱為模型化的方法往往有助于研究規(guī)律性和結(jié)構(gòu)。這種被稱為模型化的方法往往有助于研究規(guī)律性和結(jié)構(gòu)。 作為研究作為研究DNA序列的結(jié)

30、構(gòu)的嘗試，提出以下對(duì)序列集合序列的結(jié)構(gòu)的嘗試，提出以下對(duì)序列集合進(jìn)行分類的問題：進(jìn)行分類的問題： 下面有下面有20個(gè)已知類別的人工制造的序列（見下頁(yè)），其個(gè)已知類別的人工制造的序列（見下頁(yè)），其中序列標(biāo)號(hào)中序列標(biāo)號(hào)110 為為A類，類，11-20為為B類。類。 請(qǐng)從中提取特征，構(gòu)造分類方法，并用這些已知類別的序請(qǐng)從中提取特征，構(gòu)造分類方法，并用這些已知類別的序列，衡量你的方法是否足夠好。列，衡量你的方法是否足夠好。 然后用你認(rèn)為滿意的方法，對(duì)另外然后用你認(rèn)為滿意的方法，對(duì)另外20個(gè)未標(biāo)明類別的人個(gè)未標(biāo)明類別的人工序列（標(biāo)號(hào)工序列（標(biāo)號(hào)2140）進(jìn)行分類，把結(jié)果用序號(hào)（按從）進(jìn)行分類，把結(jié)果用序

31、號(hào)（按從小到大的順序）標(biāo)明它們的類別（無法分類的不寫入）：小到大的順序）標(biāo)明它們的類別（無法分類的不寫入）： A類類 ； B類類 。1.aggcacggaaaaacgggaataacggaggaggacttggcacggcattacacggaggacgaggtaaaggaggcttgtctacggccggaagtgaagggggatatgaccgcttgg2.cggaggacaaacgggatggcggtattggaggtggcggactgttcggggaattattcggtttaaacgggacaaggaaggcggctggaacaaccggacggtggcagcaaagga3.gggacg

32、gatacggattctggccacggacggaaaggaggacacggcggacatacacggcggcaacggacggaacggaggaaggagggcggcaatcggtacggaggcggcgga4.atggataacggaaacaaaccagacaaacttcggtagaaatacagaagcttagatgcatatgttttttaaataaaatttgtattattatggtatcataaaaaaaggttgcga5.Cggctggcggacaacggactggcggattccaaaaacggaggaggcggacggaggctacaccaccgtttcggcggaaaggc

33、ggagggctggcaggaggctcattacggggag6.atggaaaattttcggaaaggcggcaggcaggaggcaaaggcggaaaggaaggaaacggcggatatttcggaagtggatattaggagggcggaataaaggaacggcggcaca7.atgggattattgaatggcggaggaagatccggaataaaatatggcggaaagaacttgttttcggaaatggaaaaaggactaggaatcggcggcaggaaggatatggaggcg8.atggccgatcggcttaggctggaaggaacaaataggcggaa

34、ttaaggaaggcgttctcgcttttcgacaaggaggcggaccataggaggcggattaggaacggttatgagg9.atggcggaaaaaggaaatgtttggcatcggcgggctccggcaactggaggttcggccatggaggcgaaaatcgtgggcggcggcagcgctggccggagtttgaggagcgcg10.tggccgcggaggggcccgtcgggcgcggatttctacaagggcttcctgttaaggaggtggcatccaggcgtcgcacgctcggcgcggcaggaggcacgcgggaaaaaacg A A

35、類類11.gttagatttaacgttttttatggaatttatggaattataaatttaaaaatttatattttttaggtaagtaatccaacgtttttattactttttaaaattaaatatttatt12.gtttaattactttatcatttaatttaggttttaattttaaatttaatttaggtaagatgaatttggttttttttaaggtagttatttaattatcgttaaggaaagttaaa13.gtattacaggcagaccttatttaggttattattattatttggattttttttttttttttttttaagtta

36、accgaattattttctttaaagacgttacttaatgtcaatgc14.gttagtcttttttagattaaattattagattatgcagtttttttacataagaaaatttttttttcggagttcatattctaatctgtctttattaaatcttagagatatta15.gtattatatttttttatttttattattttagaatataatttgaggtatgtgtttaaaaaaaatttttttttttttttttttttttttttttttaaaatttataaatttaa16.gttatttttaaatttaattttaattttaaa

37、atacaaaatttttactttctaaaattggtctctggatcgataatgtaaacttattgaatctatagaattacattattgat17.gtatgtctatttcacggaagaatgcaccactatatgatttgaaattatctatggctaaaaaccctcagtaaaatcaatccctaaacccttaaaaaacggcggcctatccc18.gttaattatttattccttacgggcaattaattatttattacggttttatttacaattttttttttttgtcctatagagaaattacttacaaaacgttattttac

38、atactt19.gttacattatttattattatccgttatcgataattttttacctcttttttcgctgagtttttattcttactttttttcttctttatataggatctcatttaatatcttaa20.gtatttaactctctttactttttttttcactctctacattttcatcttctaaaactgtttgatttaaacttttgtttctttaaggattttttttacttatcctctgttat B B類類21.tttagctcagtccagctagctagtttacaatttcgacaccagtttcgcaccatcttaaa

39、tttcgatccgtaccgtaatttagcttagatttggatttaaaggatttagattga22.tttagtacagtagctcagtccaagaacgatgtttaccgtaacgtqacgtaccgtacgctaccgttaccggattccggaaagccgattaaggaccgatcgaaaggg 23.cgggcggatttaggccgacggggacccgggattcgggacccgaggaaattcccggattaaggtttagcttcccgggatttagggcccggatggctgggaccc24.tttagctagctactttagctatttttagt

40、agctagccagcctttaaggctagctttagctagcattgttctttattgggacccaagttcgacttttacgatttagttttgaccgt25.gaccaaaggtgggctttagggacccgatgctttagtcgcagctggaccagttccccagggtattaggcaaaagctgacgggcaattgcaatttaggcttaggcca26.gatttactttagcatttttagctgacgttagcaagcattagctttagccaatttcgcatttgccagtttcgcagctcagttttaacgcgggatctttagcttc

41、aagctttttac 27.ggattcggatttacccggggattggcggaacgggacctttaggtcgggacccattaggagtaaatgccaaaggacgctggtttagccagtccgttaaggcttag28.tccttagatttcagttactatatttgacttacagtctttgagatttcccttacgattttgacttaaaatttagacgttagggcttatcagttatggattaatttagcttattttcga29.ggccaattccggtaggaaggtgatggcccgggggttcccgggaggatttaggctgacg

42、ggccggccatttcggtttagggagggccgggacgcgttagggc30.cgctaagcagctcaagctcagtcagtcacgtttgccaagtcagtaatttgccaaagttaaccgttagctgacgctgaacgctaaacagtattagctgatgactcgta未知未知31.ttaaggacttaggctttagcagttactttagtttagttccaagctacgtttacgggaccagatgctagctagcaatttattatccgtattaggcttaccgtaggtttagcgt32.gctaccgggcagtctttaacgtagc

43、taccgtttagtttgggcccagccttgcggtgtttcggattaaattcgttgtcagtcgctctrtgggtttagtcattcccaaaagg33.cagttagctgaatcgtttagccatttgacgtaaacatgattttacgtacgtaaattttagccctgacgtttagctaggaatttatgctgacgtagcgatcgactttagcac34.cggttagggcaaaggttggatttcgacccagggggaaagcccgggacccgaacccagggctttagcgtaggctgacgctaggcttaggttggaacccg

44、gaaa35.gcggaagggcgtaggtttgggatgcttagccgtaggctagctttcgacacgatcgattcgcaccacaggataaaagttaagggaccggtaagtcgcggtagcc36.ctagctacgaacgctttaggcgcccccgggagtagtcgttaccgttagtatagcagtcgcagtcgcaattcgcaaaagtccccagctttagccccagagtcgacg37.gggatgctgacgctggttagctttaggcttagcgtagctttagggccccagtctgcaggaaatgcccaaaggaggccca

45、ccgggtagatgccasagtgcaccgt38.aacttttagggcatttccagttttacgggttattttcccagttaaactttgcaccattttacgtgttacgatttacgtataatttgaccttattttggacactttagtttgggttac39.ttagggccaagtcccgaggcaaggaattctgatccaagtccaatcacgtacagtccaagtcaccgtttgcagctaccgtttaccgtacgttgcaagtcaaatccat40.ccattagggtttatttacctgtttattttttcccgagacctta

46、ggtttaccgtactttttaacggtttacctttgaaatttttggactagcttaccctggatttaacggccagttt未知未知二十種氨基酸分類表二十種氨基酸分類表名稱名稱英文簡(jiǎn)稱英文簡(jiǎn)稱單字符號(hào)單字符號(hào)可能的堿基組成可能的堿基組成苷氨酸苷氨酸GlyGggt、ggc、ggg、gga丙氨酸丙氨酸AlaAgct、gcc、gcg、gca纈氨酸纈氨酸ValVgtt、gtc、gtg、gta亮氨酸亮氨酸LcuLttg、tta、ctt、ctc、ctg、cta異亮氨酸異亮氨酸HeIatt、atc、ata苯丙氨酸苯丙氨酸PheFttt、ttc酪氨酸酪氨酸TyrYtat、tac色氨酸色氨

47、酸TrpWtgg絲氨酸絲氨酸ScrStct、tcc、tcg、tca、agt、agc蘇氨酸蘇氨酸ThrTact、acc、acg、aca天冬氨酸天冬氨酸AspDgat、gac谷氨酸谷氨酸GluEgag、gaa天冬酰胺天冬酰胺AsnNaag、aaa谷氨酰胺谷氨酰胺GlnQcag、caa精氨酸精氨酸ArgRcgt、cgc、cgg、cga脯氨酸脯氨酸ProPcct、cc、ccg、cca半胱氨酸半胱氨酸CysCtgt、tgc甲硫氨酸甲硫氨酸MctMatg組氨酸組氨酸HisHcat、cac賴氨酸賴氨酸LysKaag、aaa解：解： 第一步第一步. 問題的分析問題的分析由于由于DNA序列均是由序列均是由A、T

48、、C、G組成，且長(zhǎng)短不一，組成，且長(zhǎng)短不一，所以采用提取所以采用提取DNA序列中序列中A、T、C、G的百分率序列的百分率序列進(jìn)行分類。進(jìn)行分類。表表1和表和表2分別列出了已知分別列出了已知DNA和未知和未知DNA序列中含序列中含A、T、C、G的個(gè)數(shù)（的個(gè)數(shù)（A類編號(hào)為類編號(hào)為1-10，B類編號(hào)為類編號(hào)為11-20；未知未知DNA序列編號(hào)為序列編號(hào)為21-40.）表表1 已知已知DNA序列含堿基（序列含堿基（A、T、C、G）的個(gè)數(shù)）的個(gè)數(shù)已知序列已知序列No.12345678910 11 12 13 14 15 16 17 18 19 20A33 30 30 47 26 39 39 31 23

49、20 39 36 28 33 32 40 39 32 24 22T15 17 732 12 14 21 21 17 15 55 55 57 55 71 51 29 55 62 62C19 18 24 12 26 14 11 18 23 30 5311 90927 13 16 19G44 46 50 20 47 44 40 41 48 45 11 16 14 13 710 15 10 87表表2 未知未知DNA序列含堿基（序列含堿基（A、T、C、G）的個(gè)數(shù)）的個(gè)數(shù)No. 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40A 31

50、 30 18 24 26 25 24 30 15 31 27 19 30 24 25 24 22 26 29 23T 41 23 19 47 23 44 24 52 19 27 40 36 37 17 21 22 21 51 25 50 C 22 25 26 22 24 24 21 17 22 26 20 25 21 24 22 32 26 20 30 23G 19 26 39 22 32 21 35 18 45 23 25 29 23 37 35 27 34 20 22 20未知序列未知序列第二步第二步. DNA序列的模糊聚類序列的模糊聚類提取已知類別的提取已知類別的1-20和未知類別的和未知類別的21-40共共40條條DNA序列中序列中A、T、C、G的百分率構(gòu)成如下數(shù)據(jù)的百分率構(gòu)成如下數(shù)據(jù)矩陣：矩陣：X=(xij)404,其中其中xi1,xi2,xi3,xi4分別表示第分別表示第i條條DNA序列中的序列中的A、T、C、G的百分率（的