張立振，玄春艷，曹露潔

（1.中國海洋大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山東 青島266100；2.中國海洋大學(xué) 工程學(xué)院，山東 青島266100）

在實(shí)際工作中經(jīng)常遇到聚類問題，關(guān)于這方面的研究已取得一些很有價(jià)值的成果［1-6］。對于短時(shí)信號的聚類，在醫(yī)學(xué)等方面也有了很多的研究［7-8］，例如用儀器測量心音［7］或者靜息態(tài)功能磁共振成像［8］的數(shù)據(jù)均可以看作信號，但聚類方法僅限于將短時(shí)間內(nèi)所得數(shù)據(jù)進(jìn)行傳統(tǒng)的聚類，并根據(jù)時(shí)頻分析的結(jié)果來驗(yàn)證聚類的實(shí)際意義。

目前，關(guān)于超長離散信號的聚類研究很少見到，而如何快速高效地解決超長離散信號的聚類問題確實(shí)需要面對，例如全球有大約596個(gè)驗(yàn)潮站，每個(gè)驗(yàn)潮站都以1h為采樣間隔測得海面的高度。根據(jù)這些數(shù)據(jù)研究驗(yàn)潮站的潮型以及平均潮差對于港口航道通過能力具有積極的意義［9］，若將全球驗(yàn)潮站所處海域的潮型進(jìn)行分類，考慮到日月地的周期變化規(guī)律，至少應(yīng)該截取連續(xù)長度為期1a的數(shù)據(jù)才能合理、準(zhǔn)確地得出結(jié)論。假如將每個(gè)驗(yàn)潮站在同一年中的24×365=8 760個(gè)有序采樣值看成離散信號，這便屬于典型的超長離散信號的聚類問題。

按照傳統(tǒng)的聚類方法，自然是將每個(gè)驗(yàn)潮站同一年內(nèi)得到的離散信號看成是8 760維空間中的一個(gè)點(diǎn)，共有596的點(diǎn)。根據(jù)通常兩點(diǎn)間距離的定義，要計(jì)算8 760維空間中596個(gè)點(diǎn)中任意兩點(diǎn)之間的距離，其計(jì)算量還是相當(dāng)可觀的。下面針對超長離散信號的聚類問題，給出一種全新定義兩個(gè)離散信號之間距離的方法，以便快速有效地實(shí)現(xiàn)超長離散信號的聚類。然后，將新方法應(yīng)用于世界各驗(yàn)潮站海面波動信號的聚類，繪出全球潮型分布圖。

1 兩道超長離散信號之間廣義距離定義

1.1 長度為N 的超長離散信號空間到2L 維空間的映射（L?N）

對于有限離散實(shí)信號：｛x（kΔ）｜k=0，1，2，…，N-1｝，可簡記為

將X（fm）簡記為Xm。由式（2）知為離散信號的平均值，所以X0只反映信號平均值的大小，并不包含任何波動的信息。又因?yàn)椋鹸k｝為實(shí)信號，所以Xm具有性質(zhì)：

B）將選出的前L 項(xiàng)根據(jù)其下標(biāo)按從小到大的順序重新排列，得到數(shù)組：

式中，m1≤m2≤…≤mL。

將式（4）中的數(shù)組（Xm1，Xm2，…，XmL）稱為信號｛xk｝的L 主頻譜；將式（5）中的數(shù)組（fm1，fm2，…，fmL）稱為信號｛xk｝的L 主頻率；這樣每道長度為N 的離散信號｛xk｝在執(zhí)行完上述三步后都有2L 元數(shù)組（Xm1，Xm2，…，XmL，fm1，fm2，…，fmL）與之對應(yīng)。

為方便計(jì)，將長度為N 的離散信號構(gòu)成的空間記為U；將數(shù)組（Xm1，Xm2，…，XmL，fm1，fm2，…，fmL）構(gòu)成的2L 維空間記為V；建立從U 到V 的映射h：

式中，（Xm1，Xm2，…，XmL）為信號｛xk｝的L 主頻譜；（fm1，fm2，…，fmL）為信號｛xk｝的L 主頻率。

現(xiàn)設(shè)有n道信號｛xi，k｜k=0，1，2，…，N-1｝，i=1，2，…，n，采樣間隔均為Δ，長度皆為N。簡記為｛xi，k｝，k=0，1，2，…，N-1，i=1，2，…，n。根據(jù)式（6），信號｛xi，k｝（i=1，2，…，n）映像為

其中：

1.2 最小長度為N 的超長離散信號空間到2L 維空間的映射（L?N）

實(shí)踐中，除遇到具有相同采樣間隔和相同長度的超長離散信號聚類問題外，還經(jīng)常遇到具有相同采樣間隔，不同長度的超長離散信號的聚類問題。例如，在前面提到的潮型聚類問題中，理想情況是截取全球所有驗(yàn)潮站同一年內(nèi)的完整信號。但是，很可能有相當(dāng)一部分驗(yàn)潮站在那一年只有9個(gè)月或10個(gè)月的測量數(shù)據(jù)?，F(xiàn)設(shè)有采樣間隔均為Δ，長度分別為N1，N2，…，Nn的n 道信號｛xi，k｜k=0，1，2，…，Ni-1｝（i=1，2，…，n），簡記為｛xi，k｝，k=0，1，2，…，Ni-1，i=1，2，…，n。令N=min｛N1，N2，…，Nn｝，完全類似于前述，選取適當(dāng)?shù)恼麛?shù)L（L?N），對第i道信號執(zhí)行下面三步：a）將｛｜Xi，m｜｝，m=1，2，…，-1按從大到小的順序排列，選取前L 項(xiàng)；b）將選出的前L 項(xiàng)根據(jù)其下標(biāo)按從小到大的順序重新排列，得到數(shù)組：（Xi，mi，1，Xi，mi，2，…，Xi，mi，L），其中，

其中：

1.3 將V 空間上定義的距離作為U 空間上的廣義距離

對于?（Xi，mi，1，…，Xi，mi，L，fi，mi，1，…，fi，mi，L）∈V 和?（Xj，mj，1，…，Xj，mj，L，fj，mj，1，…，fj，mj，L）∈V，定義實(shí)函數(shù)：

簡記成：

因而稱di，j為空間V 上兩點(diǎn)（Xi，mi，1，…，Xi，mi，L，fi，mi，1，…，fi，mi，L）與（Xj，mj，1，…，Xj，mj，L，fj，mj，1，…，fj，mj，L）之間的距離。由映射式（7）或式（9）知di，j也可以看成U 空間上的函數(shù)，即di，j=d（｛xi，k｝，｛xj，k｝）。其中第i道信號｛xi，k｝與第j 道 信 號｛xj，k｝分 別 是V 中 兩 點(diǎn)（Xi，mi，1，…，Xi，mi，L，fi，mi，1，…，fi，mi，L）與（Xj，mj，1，…，Xj，mj，L，fj，mj，1，…，fj，mj，L）在U 中的原像。盡管di，j=d（｛xi，k｝，｛xj，k｝）作為U 上的函 數(shù)仍然滿足條件：（i）di，j≥0；（ii）di，j=dj，i；（iii）di，j≤di，k+dk，j。但是由di，j=0一般推不出第i道信號｛xi，k｝與第j道信號｛xj，k｝信號完全相同。所以，di，j并不能作為U 空間上兩道信號｛xi，k｝與｛xj，k｝之間的距離。但當(dāng)di，j=0時(shí)，由映射式（7）或式（9）意味著兩道信號｛xi，k｝與｛xj，k｝將有完全相同的L 主頻譜與L 主頻率，因而兩信號必近似相同。故將di，j作為U 空間上信號｛xi，k｝與｛xj，k｝之間的廣義距離是合適的。

2 超長離散信號聚類法

前文在U 空間上定義了兩道信號之間的廣義距離，接下來便可根據(jù)傳統(tǒng)定義類與類之間距離的方法，如①最短距離法；②最長距離法；③中間距離法；④重心法；⑤類平均法；⑥可變類平均法；⑦離差平方和法等方法［7］對U 空間里的點(diǎn)進(jìn)行聚類。

3 超長離散信號聚類法在全球驗(yàn)潮站潮型分布中的應(yīng)用

“海平面聯(lián)合檔案”（JASL）是夏威夷大學(xué)、美國國家海洋學(xué)數(shù)據(jù)中心（NOAC）與世界海洋學(xué)數(shù)據(jù)中心（WDC-A）共同協(xié)作的成果，收錄了全球約596個(gè)驗(yàn)潮站的海面波動信號資料。在采樣間隔為1h的數(shù)據(jù)文件中發(fā)現(xiàn)1996年收錄了326個(gè)驗(yàn)潮站，為歷年最多。而在這一年，有181個(gè)驗(yàn)潮站收錄了全部24×366=8 784個(gè)數(shù)據(jù)。對這些驗(yàn)潮站采用1.1節(jié)方法，將181個(gè)長度為8 784的海面波動信號映射到32維空間（這里L(fēng)=16），得到每個(gè)信號的主頻譜和主頻率，然后在式（11）中取λ1=λ2=…λ16=及φ=1，采用類間平均距離進(jìn)行聚類，得到了全球181個(gè)驗(yàn)潮站潮型分布圖（圖1）。

圖1 1996年181個(gè)驗(yàn)潮站潮型分布圖Fig.1 The distribution of tidal stencils based on the data sets from 181tide stations in 1996

如果將1996年有數(shù)據(jù)記錄的所有326個(gè)驗(yàn)潮站皆考慮在內(nèi)，則需要運(yùn)用采用1.2節(jié)方法，將最小長度僅為970的326列海面波動信號映射到32維空間，得到它們的主頻譜和主頻率，在式（11）中同樣取λ1=λ2=…λ16=及φ=1采用類間平均距離法進(jìn)行聚類，便可得到全球326個(gè)驗(yàn)潮站潮型分布圖（圖2）。

根據(jù)方國洪等［10］相關(guān)資料得出的結(jié)論：在太平洋，正規(guī)全日潮及混合潮（不正規(guī)全日潮、不正規(guī)半日潮）較多，正規(guī)半日潮相對較少。在太平洋赤道與40°S之間的大部分地區(qū)，大洋中部的島嶼，巴拿馬灣、阿拉斯加半島沿岸，東海西側(cè)，以及澳大利亞東岸等地都為正規(guī)半日潮；阿留申群島東南、新幾內(nèi)亞（伊里安島）東北岸、加羅林群島等地為正規(guī)全日潮；西岸大部、北美沿岸及其余地區(qū)都是混合潮。大西洋的潮汐多屬半日潮。西歐沿岸為正規(guī)半日潮，美洲東側(cè)中部的加勒比海沿岸大部分為不正規(guī)半日潮；有些地方為不正規(guī)全日潮；墨西哥灣沿岸，除東部為不正規(guī)半日潮外，其余地區(qū)都是正規(guī)全日潮或不正規(guī)全日潮。印度洋的孟加拉灣、查戈斯群島、莫桑比克、克羅澤群島附近海區(qū)和澳大利亞西北近海，為正規(guī)半日潮；阿拉伯海、蘇門答臘及爪哇島近海都是不正規(guī)半日潮；澳大利亞西岸及南岸，屬不正規(guī)全日潮，西南近海是正規(guī)全日潮。北冰洋的潮汐主要是由大西洋的潮波傳入而引起的。除泰米爾半島頂端及喀拉海東部沿岸為不正規(guī)半日潮外，其余沿岸地區(qū)均為正規(guī)半日潮。南大洋的潮波自東向西圍繞南極大陸傳播，以全日潮型為主，間有混合潮。羅斯海為全日潮，威德爾海為半日潮和全日潮。將這些結(jié)論與圖1、圖2給出的聚類結(jié)果比對發(fā)現(xiàn)兩者吻合得很好。由此可見超長離散信號聚類方法的有效性。

圖2 1996年326個(gè)驗(yàn)潮站潮型分布圖Fig.2 The distribution of tidal stencils based on the data sets from 326tide stations in 1996

4 結(jié) 論

本文借助有限離散信號的Fourier變換，通過將超長離散信號空間映射到低維空間，并由低維空間上的距離誘導(dǎo)出超長離散信號空間上的廣義距離，實(shí)現(xiàn)了對超長離散信號的聚類。利用“廣義距離”聚類雖然不如用“距離”更為精準(zhǔn)。但是，采用廣義距離將使計(jì)算量大大減少。就文中所提潮型聚類問題，若用傳統(tǒng)的聚類方法需要計(jì)算8 784維空間任意兩點(diǎn)之間的距離，而用本文所述方法只需計(jì)算32維空間里的距離。若僅考慮計(jì)算兩點(diǎn)之間的距離一次，就能減少8 784-32=8 752次減法運(yùn)算和8 752次乘方運(yùn)算以及8 752次加法運(yùn)算。像文中考慮326個(gè)驗(yàn)潮站潮型聚類問題，共需計(jì)算326×325×2=52 975次兩點(diǎn)之間的距離，由此可見，利用新方法所減少的計(jì)算量是十分可觀的。當(dāng)兩個(gè)超長離散信號的廣義距離為0時(shí)，雖然得不出兩個(gè)超長離散信號完全一致，但也可推知兩者的主頻譜和主頻率是完全相同的，這對于許多超長離散信號的聚類問題來說足可得出較為滿意的聚類結(jié)果。

：

［1］ GONZALEZ T.Clustering to minimize and maximum intercluster distance［J］.Theoretical Computer Science，1985，38（2-3）：293-306.

［2］ PAL N R，BEZDEK J C.On cluster validity for the fuzzy c-means model［J］.IEEE Transactions on Fuzzy Systems，1995，3（3）：370-379.

［3］ DOUGLAS S，MICHAEL J B.Initializing k-means batch clustering：a critical evaluation of several techniques［J］.Journal of Classification，2007，24（1）：99-121.

［4］ WU Z，LEATHY R.An optimal graph theoretic to data clustering：theory and its application to image segmentation［J］.IEEE Transactions on Pattern Anal.Machine Intelligence，1993，15（11）：1101-1113.

［5］ HUANG Z X.Extensions to the k-means algorithm for clustering large data sets with categorical values［J］.Data Mining and Knowledge Discovery，1998，2（9）：283-304.

［6］ CHAVENT M.A monothetic clustering method［J］.Pattern Recognition Letters，1998，19（11）：989-996.

［7］ GUY A，NOAM G，NATHAN I.Cluster analysis and classification of heart sounds［J］.Biomedical Signal Processing and Control，2009，（4）：26-36.

［8］ AVIV M，YOSSI Y.Cluster analysis of resting-state fMRI time series［J］.NeuroImage，2009，45（4）：1117-1125.

［9］ SONG X Q，ZHANG P P，TANG G L，et al.The influence on fairwang trough capacity because of the number of regular semidiurnal tide and the average tidal range［J］.China Water Transport，2011，11（7）：70-72.宋向群，張培培，唐國磊，等.正規(guī)半日潮的潮型數(shù)及平均潮差對港口航道通過能力的影響［J］.中國水運(yùn)，2011，11（7）：70-72.

［10］ FANG G H，ZHENG W Z，CHEN Z Y，et al.Analysis and prediction of tides and tidal currents［M］.Beijing：China Ocean Press，1986.方國洪，鄭文振，陳宗鏞，等.潮汐和潮流的分析和預(yù)報(bào)［M］北京：海洋出版社，1986.

［11］ ZHANG Y T.Multivariate statistical analysis［M］.Beinig：China Statistics Press，2002.張堯庭.多元統(tǒng)計(jì)分析選講［M］.北京：中國統(tǒng)計(jì)出版社，2002.