有趣的中位數（median）及其應用（II）

2] 中位數的定義及其一些性質

“理論是灰色的，而生命之樹常青”

[Grau, teurer Freund, ist alle Theorie, Und grün des Lebens goldner Baum.]

 （[德]歌德）

“必也正名乎” （《論語·子路》）

科學工作者習慣於先把事情定義好再說話；否則就沒有互相交流的基礎了。

中位數的定義是：

一個有限數目的有序實數數字集合（數字集合，通稱“數集”），如果數集元素的個數是奇數，則中間那個數就是這個數集的中位數；如果數集元素的個數是偶數，則中間那2個數的算術平均值（即這2個數加起來除以2）就是這個數集的中位數。

（引用並修改自“維基百科”）

舉例：

數集{2,4,1,10,9}，按從小到大的順序排列，為{1,2,4,9,10}，這個數集的中位數就是4。

如果把這個數集中的數增加1個，使得數集的個數成為偶數6，例如{1,2,4,9,10,12}，它的中間2個數是4和9，因此新數集的中位數是（4+9）/2=6.5。

根據定義，可以知道如果要編寫一個求某個有限個數實數集的中位數的程序，需要有以下幾個步驟：

1] 把數集按大小順序排列；

2] 計算數集之中所有元素的個數，假設這個數集的元素個數是n；

3] 如果數集的元素個數n是奇數，那麼數集的中位數是位於第(n+1)/2的那個數；如果n是偶數，數集的中位數則是位於第n/2個和第(n/2)+1個這兩個數的算術平均數。

算術平均數大家都很熟悉，不多說了。

中位數的用處，大家特別是從中國大陸來的人可能理解得不深。

美加兩國各地的房價、各城市的人口、各州的稅負、各種行業的工資水平，人們的期望壽命，人體的各種數據（身高、體重、血壓、血脂、血糖），等等，各種數據都可以取樣組成各種有限的實數集，都是用中位數來說話，而很少用算術平均數。

因為以上這些實數集，都是離散的數量（離散量）。如果用算術平均數作代表，當數集中有少量極低端或極高端數據時，它們的算術平均數就會被扭曲，形成偏高或偏低的所謂“偏頗的（skewed）”平均數。

而把中位數作為離散數據的代表時，上述弊端就比較好地解決了。

尋找中位數，基本的工作就是把有限實數集排列次序。

排序算法已經有很多了。最有效的有以下3種：

1] 歸併排序（merge sort）：計算效率為 O(n log n)。1945年由John von Neumann [馮·諾·伊曼]（1903-1957）首次提出。該算法是採用分治法（Divide and Conquer）的一個非常典型的應用，且各層的分治的遞歸可以同時進行。

2] 堆排序 [又名“二叉樹排序”]（heapsort）：利用“堆”這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，同時滿足性質：其子結點的鍵值或索引總小於（或者大於）它的母節點。此算法的平均計算效率為 O(n log n) 。1964年由J. W. J. Williams發明，經R. W. Floyd（1936-2001）於同年改善並發表。

3] 快速排序（Quicksort）：由C. A. R. Hoare（1934-）所發展的一種排序算法。在平均狀況下，排序n個項目的計算效率為Ο(n log n)；最壞狀況下則為Ο(n2)，但那樣的狀況並不常見。事實上，快速排序通常明顯地比其他Ο(n log n)算法更快，因為它的內部循環（inner loop）可以在大部分架構上非常有效地實現。

再講一些中位數的性質，與有興趣者共同討論。

根據以上中位數的定義，立即可得出中位數的一個引理：

在一個有序的有限實數集中，同時刪去頭和尾的相同個數的元素，所得到的新數集的中位數仍是原來的中位數。

中位數還有一個有用的性質：

設一個有限的實數集的中位數是M。如果這個實數集刪去它之中的某些元素，可以形成它的許多子集。這些子集肯定各有自己的中位數。如果這些中位數分別有它們的最大值M(max)和最小值M(min)，則有M(min) <= M <= M(max)。

[證明留給有興趣的網友做。據說用反證法即可證明。]

我認為這個性質的用處很大。在我看來，至少有以下這些特點：

1] 根據這個性質，可以用“逐步逼近”的方法找出數集的中位數，或中位數所在的範圍，或中位數的近似值。

2] 由於中位數的特性（極端值對於中位數影響很小）和這個性質，對於尋找中位數所使用的取樣樣本的要求（樣本的大小等）很低。基本上隨機取得的樣本都能得到中位數，或中位數所在的範圍，或中位數的近似值。

3] 由這個性質得到的大量的中位數（可因此得到一個中位數數據庫），可以使得研究的數據形成非常好的擬合曲線，從而可以近似地把大量的離散數量看成連續量。

4] 尋找中位數是數據處理的基本功。在經常有新數據加入的海量數據的情況下，尋找中位數是一個計算量非常龐大而又枯燥的工作。有了上述這個中位數的性質定理，可以減少許多計算量，

5] 更重要的是，這個定理可以用於處理無限數集數據。這基於以下2個想法：

1）由於無限數集可以看作是由無限個有限數集組成的，因此可以把某一無限數集之中的一部分有限數集截取出來作為這個無限數集的某一部分（或某幾個部分）的代表。

2）中位數是一個數集的分布狀況的代表，因此就可以把一個中位數作為它的“出生地”的那個有限數集的代表，即把一個有限數集“濃縮”成一個中位數，然後根據1）就可以把無限數集（即無限個有限數集）轉變為全部由中位數組成的一個有限數集。顯然，有限數集及其中位數在無限數集之中截取的個數和部位越多，越能更好地體現所研究的無限數集的特性。

寫到這裡，我想再把上一篇文章中的那個定理拿出來複習一下：

The median minimizes the sum of absolute deviations

[一個有限實數集的中位數，與數集之中各元素的差的絕對值（absolute deviations）之和為最小。]

[見以下連接網頁的第3個證明]

http://math.stackexchange.com/questions/113270/the-median-minimizes-the-sum-of-absolute-deviations

把那個定理的算式與微積分中的“極值定理”[Extreme value theorem]相比，可以看出它們非常相像。這裡如果把“中位數與數集之中其他元素之差的絕對值”看成類似連續函數可微分的條件（即中位數這點與它相鄰元素的差趨於0），把離散的數量近似地看成連續的量（無非就是一個數集中的各個元素互相靠得非常緊密，以致連成一條線了），就容易理解了。

這裡類似“極值定理”條件中的閉區間就是中位數所在的那個有限實數數集，類似的極值顯然就是中位數，而對應中位數的自變量則就是中位數所處的那個位置，最中間！

好了，中位數可以成為離散量與連續量連通的橋梁之一了。

[附]微積分“極值定理”[Extreme value theorem]：

如果實函數f在閉區間[a,b]上是連續函數，則它一定在[a,b]內存在至少一個最大值和至少一個最小值。

除了把離散量向連續量推廣以外，中位數還可以從一維或二維向N維推廣。其基本要求是，維與維之間是互相獨立的（如果維與維之間有關係，又如何處理？）。這裡的維可以是X、Y、Z的三維空間，加上時間、速度、溫度、濕度等維。尋找每個維中各分量/元素的中位數，使之具有最大的分布的代表性。

想不出無限維中位數的應用。不過理論上的推廣好像不難。

一些胡思亂想：

1] 基因的研究發現，人體中有很大比例（據說占90%以上）是“垃圾基因（junk genes）”。人們至今不知道這些基因有什麼作用，也不知道它們是如何產生的。這麼大數量的基因，是否可以從處理它們各種生化指標的中位數入手，作為揭開它們真面目的第一步。

2] 較新的一門邊緣學科生物信息學（bioinformatics），是利用應用數學、信息學、統計學和計算機科學的方法研究生物學（特別是有關人體基因）的問題。見

https://en.wikipedia.org/wiki/Bioinformatics

呵呵，中位數在其中是必須要尋找的。

扯遠了，打住！