MAC 多原鏈的離散轉連續

MAC 多原鏈的離散轉連續

一．什麼是離散化？

數列是定義在自然數集合上的函數，稱之為離散型變數，與定義在區間上的連續函數既有差異，又有聯繫，研究連續性變數的問題可以運用微分學和積分學等工具進行處理，所以，常將離散型問題轉化為連續行問題進行研究。另一方面，離散型問題形式簡單，便於推證，有許多連續型問題所不具備的優越性，因此，許多連續型問題又需要轉化為離散型問題進行研究。

離散型問題與連續型問題的轉化途徑有些是直接進行變數替換，例如將n或1/n換成x，或通過[x]研究連續型問題；有些是思想方法的相互移植，例如研究離散型問題時，可以找出在形式上與其對應的連續型問題，將解決連續型問題的思想和方法移值到離散型問題上，反之亦然。

例1，設等差數列{An}與等差數列{bn}滿足，A0=B0>0, An=Bn>0,求證Σnn=0 An>ΣNn=0 Bn.

分析，顯然只需要證明AN >bn， (n=1,2,.....，N-1）.令A0 =B0 =a,An=Bn=b,於是{An} 的公差為d=b-1/N,{bn }的公比為

, 從而 AN =a+nd, bn =aqn （n= 1，2， .....N)。

直接證明An >bn 很困難，因此，把離散變數n換成連續變數x,考慮函數f(x)=a+dx,

G（x)=aqx , 則由條件知 f(0)=g(0)=a, f (N）= g (N）=b, 因此，問題轉化為對任意

0<x<N，有 f(x)>g (x)或f (x）-g (x） >0.

證明，顯然f (x)=d, g(x)=a qx inq， gn (x)=aqx in2q>0, 於是g』(x) 在 [0,N]上嚴格單調增加，由拉格朗日中值定理得知，ξ€[0,N],使

二． 如果說今年這時候OIBH問得最多的問題是二分圖，那麼去年這時候問得最多算離散化了。對於「什麼是離散化」，有各種各樣的說法，「排序後處理」，「對坐標的近似處理」等等。

離散化是程序設計中一個非常有用的技巧，它可以有效地降低時間複雜度。其基本思想就是在眾多可能的情況中「只考慮我需要用的值」。下面我將用三個例子說明，如何運用離散化改進一個低效的，甚至根本不可能實現的演算法。

《演算法藝術與信息學競賽》中的計算幾何部分，黃亮舉了一個經典的例子，我認為很適合用來介紹離散化思想。

這個問題是UVA10173,題目意思是，給定平面上n個點的坐標，求更夠覆蓋這個點的最小矩形面積。

這裡的傾斜放置很不好處理，因為我們不知道這個矩形最終會傾斜多少度。假設我們知道這個矩形的傾角是a，那麼答案就很簡單了：矩形面積最小時四條邊一定都挨著某個點。也就是說，四條邊的斜率已經都知道了的話，只需要讓這些邊從外面不斷逼近這個點集直到碰到了某個點。你不必知道這個具體應該怎麼實現，只需要理解這可以通過某種方法計算出來，

畢竟我們的重點在下面的過程中。

我們的演算法很顯然了：枚舉矩形的傾角，對於每一個傾角。我們都能計算出最小的矩形面積，最後取一個最小值。

矩形的傾角是一個「連續的」變數，它是我們無法枚舉這個傾角的根本原因。我們需要一種方法，把這個』連續的」變數變成一個一個的值，變成一個「離散的」變數。這個過程就是所謂的離散化。

我們可以證明，最小面積的矩形不但要求四條邊上都有一個點，而且還要求至少一條邊上又兩個或兩個以上的點。試想，如果每條邊都只有一個點，則我們總可以把這個矩形旋轉一點使得這個矩形變「松」，從而有餘地的得到更小的矩形。於是我們發現，矩形的某條邊的斜率必然與某兩點的連線相同。

如果我們計算出了所有過兩點的直線的傾角，那麼a的取值只有可能是這些傾角或它減去90度後的角（直線按「」方向傾斜時），這麼C(n,2)種。我們說，這個「傾角」已經被我們「離散化」了。雖然這個演算法仍然有優化的餘地，但此時我們已經達到了本文開頭所說的目的。

對於某些坐標雖然已經是整數（已經是離散的了），但範圍極大的問題，我們也可以用離散化的思想縮小這個規模。

VOJ1056永遠是離散化的經典問題。大意是給定平面上的n個矩形（坐標為整數，矩形與矩形之間可能有重疊部分），求其覆蓋的面積。平常的想法就是開一個與二維坐標規模相當的二維Boolean數組模擬矩形的「覆蓋」。

然後將坐標「離散化」到1到200之間的數，於是一個200*200的二維數組就形成了。實現方法正如本文開頭所說的「排序後處理」。對橫坐標（縱坐標）進行一次排序並映射為1到2n的整數，同時記錄新坐標的每兩個相鄰坐標之間在離散化前實際的距離是多少。

三． DCT 離散餘弦變換

1.常用的信源編碼方法有算術編碼、矢量量化、預測編碼和變換編碼等多種方法，變換編碼就是經變換後的信號的樣值能更有效地編碼，也就是通過變換來解除或減弱信號源符號間的相關性，再將變換後的樣值進行標量量化，或採用對於獨立信源符號的編碼方法，以達到壓縮碼率的目的。

在實用中常用離散餘弦變換DCT，尤其是對視頻圖像信號，其統計特性接近一階馬爾可夫鏈，離散餘弦變換的正交矢量近似於相應的K-L變換的正交矢量。

餘弦變換的完備正交歸一函數是

對這些函數在（0，T）內取N個樣值，即得離散餘弦變換矩陣的元為

分別可得變換和反變換的矩陣形式。

1. DCT變換形式

2..1 DCT變換原理

基於DCT （離散餘弦變換）壓縮編碼演算法是有失真的壓縮編碼，圖2。1為DCT變換編碼原理圖。

2.2 DCT變換編碼的步驟

DCT變換編碼的主要步驟是：顏色空間轉換，正向離散餘弦變換 (FDCT),量化，熵編碼（哈達碼編碼和算術編碼）。

10DCT 變換

在進行DCT變換之前，先把圖像分成8×8的子塊。

將用P位表示的圖像數據（一般用8位表示一個像素的顏色分量），即在[0,2p-1]範圍內表示的無符號整數，變成[-2p-1,2p-1 -1]範圍內表示的有符號數，作為DCT變換的輸入量。經過DCTπ變換，將空域中表示的圖像數據轉換到頻域中進行表示，並獲得N個變換係數。變換公式為：

逆轉DCT 變換公式為

F(i,j)=

其中，

輸出係數排列 F (u，v）按 Zig-zag排序，其中直流量為DC係數，交流量為AC係數。排列後越往後0越多。

3. 程序調試以及運行結果分析

四．連續特徵

z-score標準化：這是最常見的特徵預處理方式，基本所有的線性模型在擬合的時候都會做 z-score標準化。具體的方法是求出樣本特徵x的均值mean和標準差std，然後用（x-mean)/std來代替原特徵。這樣特徵就變成了均值為0，方差為1了。在sklearn中，我們可以用StandardScaler來做z-score標準化。當然，如果我們是用pandas做數據預處理，可以自己在數據框裡面減去均值，再除以方差，自己做z-score標準化。

max-min標準化：也稱為離差標準化，預處理後使特徵值映射到[0,1]之間。具體的方法是求出樣本特徵x的最大值max和最小值min，然後用(x-min)/(max-min)來代替原特徵。如果我們希望將數據映射到任意一個區間[a,b]，而不是[0,1]，那麼也很簡單。用(x-min)(b-a)/(max-min)+a來代替原特徵即可。在sklearn中，我們可以用MinMaxScaler來做max-min標準化。這種方法的問題就是如果測試集或者預測數據里的特徵有小於min，或者大於max的數據，會導致max和min發生變化，需要重新計算。所以實際演算法中， 除非你對特徵的取值區間有需求，否則max-min標準化沒有 z-score標準化好用。

L1/L2範數標準化：如果我們只是為了統一量綱，那麼通過L2範數整體標準化也是可以的，具體方法是求出每個樣本特徵向量x的L2範數||x||2||x||2,然後用x/||x||2x/||x||2代替原樣本特徵即可。當然L1範數標準化也是可以的，即用x/||x||1x/||x||1代替原樣本特徵。通常情況下，範數標準化首選L2範數標準化。在sklearn中，我們可以用Normalizer來做L1/L2範數標準化。

五．離散特徵

對於離散的特徵基本就是按照one-hot編碼，該離散特徵有多少取值，就用多少維來表示該特徵。

1.使用one-hot編碼，將離散特徵的取值擴展到了歐式空間，離散特徵的某個取值就對應歐式空間的某個點。

2.將離散特徵通過one-hot編碼映射到歐式空間，是因為，在回歸，分類，聚類等機器學習演算法中，特徵之間距離的計算或相似度的計算是非常重要的，而我們常用的距離或相似度的計算都是在歐式空間的相似度計算，計算餘弦相似性，基於的就是歐式空間。

3.將離散型特徵使用one-hot編碼，確實會讓特徵之間的距離計算更加合理。比如，有一個離散型特徵，代表工作類型，該離散型特徵，共有三個取值，不使用one-hot編碼，其表示分別是x1=(1),x2=(2),x3=(3)x1=(1),x2=(2),x3=(3)。兩個工作之間的距離是，(x1,x2)=1,d(x2,x3)=1,d(x1,x3)=2(x1,x2)=1,d(x2,x3)=1,d(x1,x3)=2。那麼x1x1和x3x3工作之間就越不相似嗎？顯然這樣的表示，計算出來的特徵的距離是不合理。那如果使用one-hot編碼，則得到x1=(1,0,0),x2=(0,1,0),x3=(0,0,1)x1=(1,0,0),x2=(0,1,0),x3=(0,0,1)，那麼兩個工作之間的距離就都是sqrt(2)sqrt(2).即每兩個工作之間的距離是一樣的，顯得更合理

4.離散特徵進行one-hot編碼後，編碼後的特徵，其實每一維度的特徵都可以看做是連續的特徵。就可以跟對連續型特徵的歸一化方法一樣，對每一維特徵進行歸一化。比如歸一化到[-1,1]或歸一化到均值為0,方差為1。雖然大部分機器學習模型都需要做標準化和歸一化，也有不少模型可以不做做標準化和歸一化，主要是基於概率分布的模型，比如決策樹大家族的CART，隨機森林,bagging和boosting等。當然此時使用標準化也是可以的，大多數情況下對模型的泛化能力也有改進。基於參數的模型或基於距離的模型，都要進行標準化和歸一化

六．連續特徵的離散化

在工業界，很少直接將連續值作為邏輯回歸模型的特徵輸入，而是將連續特徵離散化為一系列0、1特徵交給邏輯回歸模型，這樣做的優勢有以下幾點：

1.離散特徵的增加和減少都很容易，易於模型的快速迭代

2.稀疏向量內積乘法運算速度快，計算結果方便存儲，容易擴展

3.離散化後的特徵對異常數據有很強的魯棒性：比如一個特徵是年齡>30是1，否則0。如果特徵沒有離散化，一個異常數據「年齡300歲」會給模型造成很大的干擾

4.邏輯回歸屬於廣義線性模型，表達能力受限；單變數離散化為N個後，每個變數有單獨的權重，相當於為模型引入了非線性，能夠提升模型表達能力，加大擬合

5.離散化後可以進行特徵交叉，由M+N個變數變為M*N個變數，進一步引入非線性，提升表達能力

6.特徵離散化後，模型會更穩定，比如如果對用戶年齡離散化，20-30作為一個區間，不會因為一個用戶年齡長了一歲就變成一個完全不同的人。當然處於區間相鄰處的樣本會剛好相反，所以怎麼劃分區間是門學問

7.特徵離散化以後，起到了簡化了邏輯回歸模型的作用，降低了模型過擬合的風險。

8.李沐曾經說過：模型是使用離散特徵還是連續特徵，其實是一個「海量離散特徵+簡單模型」 同 「少量連續特徵+複雜模型」的權衡。既可以離散化用線性模型，也可以用連續特徵加深度學習。就看是喜歡折騰特徵還是折騰模型了。通常來說，前者容易，而且可以n個人一起並行做，有成功經驗；後者目前看很贊，能走多遠還須拭目以待。

七．無監督方法

無監督方法都具有的問題就是都需要認為規定劃分區間這個參數，常用的方法有分箱法和直觀劃分，首先來說一下分箱法：

1.分箱法又分為等寬分箱法和等頻分箱法，其實從名字就能看出演算法的做法了，前者制定定長的間隔將特徵放入不同箱子內，後者根據頻率劃分箱子，這兩種做法都有一定的缺陷。等寬分箱法對異常點比較敏感，比如數據正常範圍是30-60，現在出現了一個特徵本來是30不小心讀取成了300，那麼寬度會被拉長，實例就主要集中在前面的箱體中，後面的箱體幾乎沒有實例，解決的方法主要是設立閾值移除閾值以外的實例。等頻分箱法的缺陷是完全按照頻率劃分會出現實例特徵相同卻不在同一個箱體內的情況，解決辦法也很簡單，在劃分完成後進行微調就可完成

2.直觀劃分法感覺就沒什麼技術了，這個演算法主要是根據經驗和美觀，常用的方法劃分出來肯定都是34267、64537這樣的數，但是人們一般都習慣看到30000、50000這樣的數，然後就是加上個人對數據的了解人為劃分。

3.個人感覺無監督方法的連續特徵離散化並不是很靠譜，原因就是不知道設計的目的單純考慮離散化對結果是更好還是更差這個不確定性太大了。

八．有監督方法

1R方法：這個方法是分箱法的有監督版本，把前6個實例放入箱子中，然後後面實例放入箱子時，對比當前實例標籤與箱子中大部分實例標籤是否相同，如果相同放入，如果不相同，那麼形成下一個6實例的新箱子，等到最後全部放入箱子中，將箱子中大多數實例標籤作為箱子的標籤，再將標籤相同的箱子合併

基於卡方的離散方法：首先將數值特徵的每個不同值看做一個區間對每對相鄰區間計算卡方統計量，如果大於閾值就合併，遞歸進行直到找不到卡方統計大於閾值的時候停止

基於熵的離散方法：其實就是照搬了決策樹的思路，使用合成的方法或者分裂的方法根據熵計算和閾值判定來決定合成或分裂。

九．數據離散的優點

離散化指把連續型數據切分為若干「段」，也稱bin，是數據分析中常用的手段。切分的原則有等距，等頻，優化，或根據數據特點而定。在營銷數據挖掘中，離散化得到普遍採用。究其原因，有這樣幾點：

①演算法需要。例如決策樹，NaiveBayes等演算法本身不能直接使用連續型變數，連續型數據只有經離散處理後才能進入演算法引擎。這一點在使用具體軟體時可能不明顯。因為大多數數據挖掘軟體內已經內建了離散化處理程序，所以從使用界面看，軟體可以接納任何形式的數據。但實際上，在運算決策樹或NaiveBayes模型前，軟體都要在後台對數據先作預處理。

②離散化可以有效地克服數據中隱藏的缺陷：使模型結果更加穩定。例如，數據中的極端值是影響模型效果的一個重要因素。極端值導致模型參數過高或過低，或導致模型被虛假現象「迷惑」，把原來不存在的關係作為重要模式來學習。而離散化，尤其是等距離散，可以有效地減弱極端值和異常值的影響，

③有利於對非線性關係進行診斷和描述：對連續型數據進行離散處理後，自變數和目標變數之間的關係變得清晰化。如果兩者之間是非線性關係，可以重新定義離散後變數每段的取值，如採取0，1的形式， 由一個變數派生為多個啞變數，分別確定每段和目標變數間的聯繫。這樣做，雖然減少了模型的自由度，但可以大大提高模型的靈活度。

即使在連續型自變數和目標變數之間的關係比較明確，例如可以用直線描述的情況下，對自變數進行離散處理也有若干優點。一是便於模型的解釋和使用，二是可以增加模型的區別能力。

等距:將連續型變數的取值範圍均勻劃成n等份，每份的間距相等。例如，客戶訂閱刊物的時間是一個連續型變數，可以從幾天到幾年。採取等距切分可以把1年以下的客戶劃分成一組，1-2年的客戶為一組，2-3年為一組..，以此類分，組距都是一年。

等頻:把觀察點均勻分為n等份，每份內包含的觀察點數相同。還取上面的例子，設該雜誌訂戶共有5萬人，等頻分段需要先把訂戶按訂閱時間按順序排列，排列好後可以按5000人一組，把全部訂戶均勻分為十段。

等距和等頻在大多數情況下導致不同的結果。等距可以保持數據原有的分布，段落越多對數據原貌保持得越好。等頻處理則把數據變換成均勻分布，但其各段內觀察值相同這一點是等距分割作不到的。

優化離散:需要把自變數和目標變數聯繫起來考察。切分點是導致目標變數出現明顯變化的折點。常用的檢驗指標有卡方，信息增益，基尼指數，或WOE(要求目標變數是兩元變數)離散連續型數據還可以按照需要而定。比如，當營銷的重點是19-24歲的大學生消費群體時，就可以把這部分人單獨划出。

離散化處理不免要損失一部分信息。很顯然，對連續型數據進行分段後，同一個段內的觀察點之間的差異便消失了。同時，進行了離散處理的變數有了新值。比如現在可以簡單地用1,2,3..這樣一組數字來標誌雜誌訂戶所處的段落。這組數字和原來的客戶訂閱雜誌的時間沒有直接的聯繫，也不再具備連續型數據可以運算的關係。例如，使用原來的數據，我們可以說已有兩年歷史的客戶訂閱時間是只有一年歷史客戶的兩倍，但經過離散處理後，我們只知道第2組的客戶的平均訂閱時間高於第一組客戶，但無法知道兩組客戶之間的確切差距。

十、MAC多原鏈的離散轉連續

離散轉連續由傳統離散型共識演算法投票確認，升級成為連續型隨機抽樣，只選取所有節點中的一部分來獲得一個結果，往複多輪取樣，實現全覆蓋。當隨機取樣的結果收斂到一個可信值，共識達成。共行共識提升非同步系統的運行效率，配合非同步系統多節點設計，進一步提升系統的並發性能。不需在共識機制中與大多數節點連接，並獲取投票，節省系統數據傳輸，降低節點對網體依賴，節點隨機選擇，使用隨機可計算函數，用戶根據計算得知其是否被選擇中，並將結果反饋和廣播給其他用戶。

推薦閱讀：