【正文】 的元素。不過，根據(jù)歸一化的規(guī)定，一個數(shù)據(jù)集的隸屬度的總和等于 1： (22)1,2,.cijun??FCM 目標(biāo)函數(shù)的一般化形式為： (23)2111(,.)cmiijJUAJud??這里 uij 介于 0 到 1 之間；A i 為模糊組 i 的聚類中心，d ij=||cixj||為第 i 個聚類中心與第 j 個數(shù)據(jù)點(diǎn)間的歐氏距離； 是一個加權(quán)指數(shù)，一般取 m=2。??,??構(gòu)造如下新的目標(biāo)函數(shù)，可求得使(23)式達(dá)到最小值的必要條件： (24)111121(,.,.)(,.)()?????nccjijcmijjijiJJUAuud??這里 ?j(j=1, 2, …, n)是式(23)的 n 個約束式的拉格朗日乘子。對所有輸入?yún)⒘壳髮?dǎo)，使式(23)達(dá)到最小的必要條件為：中南大學(xué)碩士學(xué)位論文 第二章 話務(wù)量預(yù)測的聚類預(yù)處理技術(shù)15 (25)1??nmij=iijuxA和 (26)2/(1)1??????ij mcijp=ud由上述兩個必要條件，F(xiàn)CM 聚類算法是一個簡單的迭代過程。在批處理方式運(yùn)行時，F(xiàn)CM 用下列步驟確定聚類中心 Ai 和隸屬矩陣 U：Step1：用值在 0 到 1 之間的隨機(jī)數(shù)初始化隸屬矩陣 U，使其滿足式(22)中的約束條件。Step2：用式(25)計算 c 個聚類中心 Ai，i=1, 2, …, c。Step3：根據(jù)式(23)計算目標(biāo)函數(shù)。如果它小于某個確定的閥值，或它相對上次目標(biāo)函數(shù)值的改變量小于某個閥值，則算法停止。Step4：用(26)計算新的 U 矩陣。返回 Step2。上述算法也可以先初始化聚類中心，然后再執(zhí)行迭代過程。由于不能確保FCM 收斂于一個最優(yōu)解，算法的性能往往依賴于初始聚類中心。 加權(quán) FCM 聚類算法如上節(jié)所述，從公式(23)可以看出，F(xiàn)CM聚類算法是基于歐氏距離來計算樣本間相似度的，而歐氏距離假定了每一個輸入維度在聚類過程中的重要性是相同的。但由于在話務(wù)量樣本中各輸入維度的重要性并不完全相同，如歷史話務(wù)量有“近大遠(yuǎn)小”的相關(guān)性。因此需要為每個輸入維度賦予一個權(quán)重，以避免影響聚類結(jié)果。傳統(tǒng)的相似性度量方法有歐氏距離、相關(guān)系數(shù)法、兩夾角余弦等。這里定義一種靈活可變的基于歐氏距離的相似性度量： (27)()()1???wij wijd??是[0, 1]的一個常數(shù)，期望能通過調(diào)整 使得 的值近似均勻地分布在[0, 1]??()wij?內(nèi)，因而 可按下式確定： (28)()??????ijijnd式(28)中 為普通的歐氏距離，而式(27) 中 是基于屬性權(quán)重的歐氏距離，ijd()wijd定義如下：()wij中南大學(xué)碩士學(xué)位論文 第二章 話務(wù)量預(yù)測的聚類預(yù)處理技術(shù)16 (29)()221()???Dwijkijkdx式(29)中 w=(w1, w2, …, wD)是與輸入屬性相對應(yīng)的一個權(quán)重矢量， 描[0,1]kw?述第 k 維屬性在聚類中的重要性。通過調(diào)整 wk 的值，數(shù)據(jù) i 與數(shù)據(jù) j 間的相似度在不斷變化。當(dāng) w=(1, 1, …, 1)D 時，數(shù)據(jù)位于原始空間，即球形空間，所有屬性的重要性相等，數(shù)據(jù)間的相似度基于普通的歐氏距離 dij，此時的相似度記作 ，稱 為原始相似度；當(dāng)權(quán)重分量不全等于 1 時，數(shù)據(jù)出于壓縮后()wij?ijij?的空間，即橢球空間， 成為基于屬性權(quán)重相似度。當(dāng) wk=1 時，第 k 維屬性()wij對應(yīng)的坐標(biāo)軸在數(shù)據(jù)空間中不變，在聚類過程中發(fā)揮其全部作用；w k 的值越小，該屬性對應(yīng)的坐標(biāo)軸被壓縮的程度也就越大，在聚類過程中發(fā)揮的作用就越?。划?dāng) wk=0 時，該屬性從數(shù)據(jù)空間中消失，在聚類過程中不發(fā)揮任何作用。 根據(jù)信息論的觀點(diǎn)可知：當(dāng)數(shù)據(jù)間的相似度在 附近時，模糊性較大；當(dāng)數(shù)據(jù)的相似度遠(yuǎn)離 時，模糊性較小。而一個好的聚類結(jié)果應(yīng)該具有模糊性小的性質(zhì)，即數(shù)據(jù)間的相似度應(yīng)該遠(yuǎn)離 。通過調(diào)整屬性權(quán)重，使相似數(shù)據(jù)間的距離靠近，不相似數(shù)據(jù)間的距離拉大，即 或 1，這樣得到的聚類結(jié)()0?wij?果模糊性小，而且類內(nèi)相似性大，類間相似性小。根據(jù)以上分析，定義一個作為屬性評價的函數(shù)。 (210)() ()21()loglog))?????????wwijijij ijijCFuzinesw?式(210)的設(shè)計來源于下面的函數(shù)： (,)log(l()fxyxy (0,1)xy? (211)函數(shù)滿足 Deluca 提出的熵函數(shù)的幾條性質(zhì) [37]，即uzines(1) = =，函數(shù) 取得最大值，即 =1。()wij?ij ()CFuzinesw()CFuzinesw(2) ( = )=0 或 1，函數(shù) 取得最小值，即=0。)CFzies(3) 對于任兩個整數(shù) i，j，有兩個模糊集 S 和 S’，如果或 ，那么()()39。?wijij?()()39。?wijijs?；39。suzneCFuzne(4) 當(dāng) 0 ， ，函數(shù) 單調(diào)遞增；當(dāng)()wijij ()CFuzinesw1 ， ，函數(shù) 單調(diào)遞減。()wijij ()is極小化函數(shù) 得到的屬性權(quán)重使得相似的數(shù)據(jù)( )更相似(zie ij?)，不相似的數(shù)據(jù)( )更不相似( )。通過學(xué)習(xí)后 或()1?ij?ij?()0?wij?)0w1，所以學(xué)習(xí)后的數(shù)據(jù)分布清晰，模糊性小，聚類結(jié)果能夠得到改善。選用常見的梯度遞減算法極小化 函數(shù)，得到屬性的權(quán)重矢量(CFuzinesw，進(jìn)而可以得到加權(quán)后的歐氏距離。此時新的目標(biāo)函數(shù)變?yōu)椋褐心洗髮W(xué)碩士學(xué)位論文 第二章 話務(wù)量預(yù)測的聚類預(yù)處理技術(shù)17 (212)2()1(,)??wijijJUAd其中c為聚類個數(shù)。極小化式(212) 可得到模糊劃分矩陣U ={Uij}和聚類中心A={Ai}。 (213)2/(1))1????????ij mwcijpd (214)1nijjimijjUXA??加權(quán) FCM 聚類算法的步驟按照以下步驟進(jìn)行：(1) 使用梯度遞減算法學(xué)習(xí)輸入維度的權(quán)重a) 通過公式(28)確定 值。?b) 在 內(nèi)初始化權(quán)重 w=(w1, w2, …, wD)。)?????c) 計算權(quán)重的修正量 。其中 為學(xué)習(xí)率，(j jCFuzines??????為式(210) 所示。()CFuzineswd) 當(dāng) 時，更新權(quán)重 。0jj??jjj??e) 重復(fù) b)、 c)、d)步驟直到收斂，即 的值小于給定的閾值，()uzinesw或者迭代的次數(shù)達(dá)到定義的值。(2) 給定初始聚類數(shù) c，設(shè)定迭代停止條件 e，初始化聚類中心矩陣 A=A(0)和模糊矩陣 U=U(0)，設(shè)置迭代計數(shù)器 b’=0；(3) 按下式更新模糊劃分矩陣 U(b’)： (215)(39。)2/(1)39。)39。1?????????bij mbcijpd其中 為加權(quán)后的歐氏距離。d(4) 按下式更新聚類中心矩陣 A(b’+1)： (216)(39。1)(39。1)(39。)???nbmijjjbi ijjUXA(5) 若 ，停止并輸出模糊劃分矩陣 U 和聚類中心矩陣 A；(39。)(39。1)???be否則令 b’=b’+1，轉(zhuǎn)至步驟(3)。其中 為矩陣范數(shù)。.可以看出，加權(quán) FCM 聚類算法與普通 FCM 聚類 算法的區(qū)別在于表示數(shù)據(jù)間相似度的歐氏距離的不同，而權(quán)重則通過上述步驟學(xué)習(xí)得到。中南大學(xué)碩士學(xué)位論文 第二章 話務(wù)量預(yù)測的聚類預(yù)處理技術(shù)18 基于加權(quán) FCM 的話務(wù)量聚類 話務(wù)量聚類的意義電信話務(wù)量影響因素的不確定性繁多且復(fù)雜，多個話務(wù)量影響因素與預(yù)測對象之間呈現(xiàn)十分復(fù)雜的非線性關(guān)系，用任意話務(wù)量樣本不加選擇，均作為輸入樣本訓(xùn)練模型，會導(dǎo)致預(yù)測模型的泛化能力降低。另外，由于各種特殊節(jié)假日具有年周期性，故原始訓(xùn)練集中至少需要包含一年的樣本才能通過學(xué)習(xí)獲取其話務(wù)量的變化規(guī)律，而要預(yù)測的話務(wù)量是以小時為單位產(chǎn)生的，總樣本數(shù)將達(dá)到 8760(36524)個 。本文使用 SVM 回歸算法預(yù)測話務(wù)量，然而，標(biāo)準(zhǔn) SVM 對大樣本量訓(xùn)練集求解復(fù)雜，而且由于迭代誤差的積累，也會導(dǎo)致算法精度難以接受。因此，設(shè)計適用于大樣本集的算法已成為近年來 SVM 研究的重要內(nèi)容。目前對于大樣本訓(xùn)練，最具代表性的是基于分解思想 [38, 39]的 SMO 算法 [40]，該算法把較大的二次規(guī)劃問題轉(zhuǎn)化為一系列最小的二次規(guī)劃子問題，再進(jìn)行解析求解。但 SMO 算法為了尋找最優(yōu)解，需要反復(fù)迭代，往往會出現(xiàn)收斂速度慢的情況，因此仍難獲得滿意的訓(xùn)練速度。根據(jù)支持向量機(jī)理論，決策函數(shù)最終取決于訓(xùn)練樣本中部分特殊樣本點(diǎn)，通常稱這些樣本點(diǎn)為支持向量(SV)。然而在優(yōu)化學(xué)習(xí)過程中，將大量時間花費(fèi)在非SV 樣本的優(yōu)化上了，若能預(yù)先去除這些不重要的樣本點(diǎn)，必將大大的減少計算量，加快 SVM 的訓(xùn)練速度。另外，由于話務(wù)量趨勢具有明顯的周期性，則原始樣本集中必然有相似度很高的多個樣本，但這些樣本所隱含的話務(wù)量變化規(guī)律卻是基本相同的，因此只需提取當(dāng)中具有代表性的樣本作為訓(xùn)練樣本即可?；谝陨峡紤]，有必要對原始樣本集進(jìn)行預(yù)處理，減少訓(xùn)練樣本。應(yīng)用模糊聚類分析的基本原理，依據(jù)輸入樣本的相似度選擇訓(xùn)練樣本，即選用同類特征數(shù)據(jù)作為預(yù)測輸入，保證了數(shù)據(jù)特征的一致性，強(qiáng)化了歷史數(shù)據(jù)規(guī)律。由于只采用與預(yù)測樣本特征相似的樣本作為訓(xùn)練樣本建立支持向量技預(yù)測模型，減少了計算量，提高預(yù)測精度和速度。 加權(quán) FCM 話務(wù)量聚類 流程設(shè) X=(x1, x2, ..., xn) 為 n 個具有 D 維的話務(wù)量原始樣本集, 對于預(yù)測樣本?Rxi = (xi1, xi2, ..., xiD)T Rn， yi R 為相應(yīng)的話務(wù)量實測值。 FCM 聚類分析就是將 X?劃分為 c 個子集 X1, X2, ..., Xc，使得：中南大學(xué)碩士學(xué)位論文 第二章 話務(wù)量預(yù)測的聚類預(yù)處理技術(shù)19 (217)12.,1???????????cikiXXki用隸屬函數(shù) 表示樣本 與子集 的隸屬關(guān)系，則()xikik??kx(1)ic?。X 的模糊 c 劃分可以用 c 個子集的特征函數(shù)值構(gòu)成的模糊聚類矩陣[0,1]ik?來表示。矩陣 U 中的第 i 行為第 i 個子集的特征函數(shù)，而第 k 列為iU?樣本 相對于 c 個子集的隸屬函數(shù)。故 X 的模糊 c 劃分空間為：kx (218)11{|[0,]。,。0,}f ikikikMRi i???????????模糊聚類可以得到樣本屬于各個類別的不確定性程度，建立對于不同類別的不確定性描述。用 表示第 i 個聚類中心。聚12(,.)(,2.)TniiiDARic類中心矩陣表示為 。FCM 聚類分析的目標(biāo)函數(shù)如式 (24)，?cc其中 d ij 替換為式(29)所示的加權(quán)后歐氏距離 。()wijdFCM 話務(wù)量聚類的處理流程如圖 23 所示：結(jié)束輸入原始數(shù)據(jù) ， 進(jìn)行數(shù)據(jù)清洗和歸一化等預(yù)處理工作使用加權(quán) F C M 算法將 X 劃分為 c 個子集 ， 并搜索最佳的模糊聚類參數(shù)對 （ m , c ）選取與待預(yù)測樣本距離最小的聚類中心所屬的數(shù)據(jù)作為初始訓(xùn)練集在初始訓(xùn)練集內(nèi)部再次進(jìn)行加權(quán)模糊 子聚類 ， 獲取子聚類后的聚類中心作為 S V M 的訓(xùn)練樣本開始圖 23 話務(wù)量預(yù)測預(yù)處理的基本流程話務(wù)量模糊聚類的一般步驟為：先用模糊聚類分析方法對歷史數(shù)據(jù)序列進(jìn)行聚類，將原始話務(wù)量樣本分成若干子集，以合適的模糊集和模糊隸屬度刻畫出各類的環(huán)境因素特征和話務(wù)量變化序列模型；然后，當(dāng)給定未來預(yù)測樣本的輸入時，匹配出與未來話務(wù)量變化序列狀態(tài)特征值相似的樣本進(jìn)行預(yù)測。話務(wù)中南大學(xué)碩士學(xué)位論文 第二章 話務(wù)量預(yù)測的聚類預(yù)處理技術(shù)20量聚類預(yù)處理的具體步驟為：Step1: 對歷史話務(wù)量數(shù)據(jù)和相關(guān)輸入維度數(shù)據(jù)進(jìn)行初始預(yù)處理，主要包括對丟失數(shù)據(jù)進(jìn)行填補(bǔ)、清除不完整的數(shù)據(jù)、合并重復(fù)數(shù)據(jù)等數(shù)據(jù)清洗以及數(shù)據(jù)歸一化等。Step2: 首先使用 加權(quán)聚類算法學(xué)習(xí)每個輸入維度的權(quán)重，然后求出 Uij 和Ai， 將數(shù)據(jù)集 X 劃分為 c 個子集 X1, X2, ..., Xc。聚類個數(shù) c 在(10, 11, ..., 26)中搜索最佳值，并通過聚類有效性指標(biāo)驗證