拓撲數據分析 - 持續同調（二）

01-26

單純形，單純復形和 VR復形

接下來我們開始寫代碼。一般來說，我的文章都會涉及到代碼，而且非常實用，但是拓撲數據分析並不簡單，一個人必須理解基礎的數學才能取得進展。

我們將學習如何從 $mathbb R^2$ 中一個圓形的模擬數據中構建一個VR復形。

我們從這個形狀中隨機取樣，假設它是我們的原始點雲數據。許多真正的數據是由循環過程產生的，所以這只是一次不現實的練習。我們將使用我們的點雲數據依照上面的描述構建一個 VR 復形。然後我們要用更多的數學方法來確定復形的同調群。

回想一下，生成圓的點集的參數形式如下:

$x=a+rcos(θ), y=b+rsin(θ)$ ，其中 $(a, b)$ 是圓心， $θ$ 是 0 到 $2π$ 的參數，而 $r$ 是半徑。

下面的代碼將生成並繪製採樣圓的離散點

import numpy as npimport matplotlib.pyplot as pltn = 30 #number of points to generate#generate space of parametertheta = np.linspace(0, 2.0*np.pi, n) a, b, r = 0.0, 0.0, 5.0x = a + r*np.cos(theta)y = b + r*np.sin(theta)#code to plot the circle for visualizationplt.plot(x, y)plt.show()

好吧，讓我們從這個(有點)完美的圓圈中隨機取樣，順便加點誤差。

x2 = np.random.uniform(-0.75,0.75,n) + x #add some "jitteriness" to the pointsy2 = np.random.uniform(-0.75,0.75,n) + yfig, ax = plt.subplots()ax.scatter(x2,y2)plt.show()

很明顯，生成的點看起來是「圓」，因為在這裡它是有一個洞的明顯的循環的圈，所以我們想要我們的單純復形捕捉到這個屬性。

讓我們用以下步驟慢慢分解VR復形的結構：

定義距離函數 $d(a,b) = sqrt{(a_1-b_1)^2+(a_2-b_2)^2}$ （歐幾里得距離）
為構建VR復形建立參數 $?$
建立一個點雲數據的集合（用python的list，最接近集合的結構），這將是 0 維單純形的復形。
掃描每一對點，計算點之間的距離。如果兩點距離小於 $?$ ，我們就給這兩個點連一條線，這時我們會獲得一個1維復形。
如果我們計算了所有距離並畫好一個圖，我們可以遍歷每一個頂點，識別它們的鄰點並嘗試遞增地建立高維復形（在 1 維復形中加入所有 2 維復形，再加入所有維復形，依此類推）。

有很多演算法可以從數據中構建一個單純復形（除了VR復形，還有很多其他類型的單純復形）。不幸的是，以我了解，這世上沒有從點數據中創建一個完整的（不是向下採樣的）單純復形的多項式時間複雜度的演算法。因此，無論如何，一旦我們開始處理真正的大數據集，構建復形將變成計算代價相當高的行為(甚至令人望而卻步)。在這方面，我們需要做更多的工作。

我們將使用 Afra Zomorodian 的「快速構建VR復形」的演算法。這個演算法有兩個主要步驟。

1. 構造點集數據的鄰域圖。領域圖是無向加權圖 $(G, w)$ ，其中 $G=(V, E)$ ， $V$ 是頂點集， $E$ 是邊集，而 $w:E→mathbb R$ （ $w$ 是每個邊到實數的映射，這是權重）。我們的邊是通過連接一些我們曾互相定義過距離（用參數 $epsilon$ ）的點創造的。特別的，

$E_{epsilon} = {{u,v} mid d(u,v) leq epsilon, u eq v in V}$

其中 $d(u, v)$ 是兩個點 $u, v∈V$ 的度量/距離函數。而權重函數簡單地將每條邊的權值設為等於邊的兩個點之間的距離。也就是， $w({u,v}) = d(u,v), forall {u,v} in E_{epsilon}(V)$ 。

2. 在第一步生成的領域圖形成VR擴張。給定一個領域圖 $(G, w)$ ，VR復形 $(R(G), w)$ （其中 $R$ 是 VR復形）權重過濾通過下列方式給定：

$R(G) = V cup E cup { sigma mid left ({sigma}above 0pt {2} ight ) subseteq E } ,$

對於 $σ∈R(G)$ ，

$w(sigma) = left{ egin{array}{ll} 0, & sigma = {v},v in V, \ w({u,v}), & sigma = {u,v} in E \ displaystyle operatorname*{max}_{ m au subset sigma} w( au), & otherwise. end{array} ight}$

這是什麼意思？在這個簡單的例子中，我們準備從我們的領域圖（左）中獲得 VR 復形（右）：

所以上面的演算法是說維VR復形是領域圖中所有頂點和邊線並的集合，也是所有在E的單純形 $sigma$ 中每種兩個頂點可能的組合的並。

下面的部分給所有VR復形的每個單純形，從單個0維單純形到高維單純形，定義了權重函數。如果單純形是 0 維單純形（只有頂點），那麼單純形的權重是 0。如果單純形是1維單純形（有邊），那麼權重是兩點之間的距離。如果單純形是高維單純形，如2維單純形（三角形），那麼權重是單純形中最長邊的權重。

在我們計算我們「圈形」數據的VR復形之前，讓我們給上面出現過的單純形進行一個全面檢查。我們先在 $mathbb R^2$ 中嵌入頂點，然後嘗試先去構建領域圖。

raw_data = np.array([[0,2],[2,2],[1,0],[1.5,-3.0]]) #embedded 3 vertices in R^2plt.axis([-1,3,-4,3])plt.scatter(raw_data[:,0],raw_data[:,1]) #plotting just for clarityfor i, txt in enumerate(raw_data): plt.annotate(i, (raw_data[i][0]+0.05, raw_data[i][1])) #add labels

我們將用原始數據數組中的索引號來表示我們單純復形中的每個頂點。例如點 $[0, 2]$ 出現在我們數據數組的開頭，因此我們把它當作單純復形中的參考點。

#Build neighorbood graphnodes = [x for x in range(raw_data.shape[0])] #initialize node set, reference indices from original data arrayedges = [] #initialize empty edge arrayweights = [] #initialize weight array, stores the weight (which in this case is the distance) for each edgeeps = 3.1 #epsilon distance parameterfor i in range(raw_data.shape[0]): #iterate through each data point for j in range(raw_data.shape[0]-i): #inner loop to calculate pairwise point distances a = raw_data[i] b = raw_data[j+i] #each simplex is a set (no order), hence [0,1] = [1,0]; so only store one if (i != j+i): dist = np.linalg.norm(a - b) #euclidian distance metric if dist <= eps: edges.append({i,j+i}) #add edge weights.append([len(edges)-1,dist]) #store index and weightprint("Nodes: " , nodes)print("Edges: " , edges)print("Weights: ", weights)Nodes: [0, 1, 2, 3]Edges: [{0, 1}, {0, 2}, {1, 2}, {2, 3}]Weights: [[0, 2.0], [1, 2.2360679774997898], [2, 2.2360679774997898], [3, 3.0413812651491097]]

完美。現在我們有一個結點集，邊集和一個權重集，這所有構成了我們的領域圖 $(G, w)$ 。我們的下一個任務是用鄰域圖構建高維單純形。在這種情況下，我們只有一個額外的2維單純形（三角形）。我們需要設置一些基礎的方法。

def lower_nbrs(nodeSet, edgeSet, node): return {x for x in nodeSet if {x,node} in edgeSet and node > x}def rips(nodes, edges, k): VRcomplex = [{n} for n in nodes] for e in edges: #add 1-simplices (edges) VRcomplex.append(e) for i in range(k): for simplex in [x for x in VRcomplex if len(x)==i+2]: #skip 0-simplices #for each u in simplex nbrs = set.intersection(*[lower_nbrs(nodes, edges, z) for z in simplex]) for nbr in nbrs: VRcomplex.append(set.union(simplex,{nbr})) return VRcomplex

好的，讓我們來試試它能不能用。假設我們要將所有的單純形都提升到 $3$ 維。

theComplex = rips(nodes, edges, 3)theComplex

[{0}, {1}, {2}, {3}, {0, 1}, {0, 2}, {1, 2}, {2, 3}, {0, 1, 2}]

嗯，看起來很完美。

現在我們想看看它是什麼樣的。我寫了一些代碼，它能根據我們VR演算法的輸出繪製單純復形。但這對於理解 TDA 並不重要(大多數情況下，我們不會嘗試可視化單純復形，因為它們太過高維)，因此我不會嘗試解釋繪製圖形的代碼。

plt.clf()plt.axis([-1,3,-4,3])plt.scatter(raw_data[:,0],raw_data[:,1]) #plotting just for clarityfor i, txt in enumerate(raw_data): plt.annotate(i, (raw_data[i][0]+0.05, raw_data[i][1])) #add labels#add lines for edgesfor edge in [e for e in theComplex if len(e)==2]: pt1,pt2 = [raw_data[pt] for pt in [n for n in edge]] print(pt1,pt2) line = plt.Polygon([pt1,pt2], closed=None, fill=None, edgecolor="r") plt.gca().add_line(line) #add trianglesfor triangle in [t for t in theComplex if len(t)==3]: pt1,pt2,pt3 = [raw_data[pt] for pt in [n for n in triangle]] line = plt.Polygon([pt1,pt2,pt3], closed=False, color="blue",alpha=0.3, fill=True, edgecolor=None) plt.gca().add_line(line)plt.show()

[ 0. 2.] [ 2. 2.][ 0. 2.] [ 1. 0.][ 2. 2.] [ 1. 0.][ 1. 0.] [ 1.5 -3. ]

現在我們對我們非常簡單的VR復形有一個很好的描述。現在我們知道該怎麼做。我們需要了解單純同調，一種關於單純形和復形拓撲不變數的研究。特別是，我們希望用數學方法辨認 $n$ 維連通的組件，圈和孔。為了幫助這些工作，我重新打包了我們在上面使用的代碼作為一個單獨的文件，這樣我們就可以直接導入它，並方便地使用我們的數據上的函數。你可以在這裡下載最新的代碼：<https://github.com/outlace/OpenTDA/blob/master/SimplicialComplex.py>

在這裡，我將從我們從一個圓中取樣的(抖動的)點上壓縮我們的 $x$ 和 $y$ 坐標，這樣我們就可以用它來構建一個更複雜的單純復形。

newData = np.array(list(zip(x2,y2)))import SimplicialComplexgraph = SimplicialComplex.buildGraph(raw_data=newData, epsilon=3.0)ripsComplex = SimplicialComplex.rips(nodes=graph[0], edges=graph[1], k=3)SimplicialComplex.drawComplex(origData=newData, ripsComplex=ripsComplex)

整潔如約！很明顯，我們已經複製了採樣點的圓形空間。注意，這裡有1維單純形和更高維的單純形，但它形成了用單個洞連接的組件。

如果我們將半徑參數 $epsilon$ 減短過多，就會變成下圖的樣子：

同調群

既然我們已經知道什麼是單純復形，以及如何從原始數據中生成它們，我們就需要進一步計算這些單純復形有趣的拓撲特徵。

以計算同調為形式的拓撲數據分析給了我們一種在我們基於數據集建立的拓撲空間（通常是單純復形）中識別組件和 $n$ 維「孔」（如圓中間的孔）的數量的方法。

在我們繼續之前，我想去描述一種可以加在我們已經用過的單純復形上的額外屬性。我們可以給它一個定向的性質。一個定向的單純形 $σ=u_1, u_2, u_3, …u_n$ 是通過它的頂點順序定義的。因此，定向單純形 ${a, b, c}$ 和定向單純形 ${c, b, a}$ 是不同的。在繪製低維圖像時，我們可以通過將邊緣變成箭頭來描述它。

現在，嚴格地說一個數學集合(用曲線括弧表示)是一個無序的對象集合，所以為了在單純形上加入方向，我們需要增加一些額外的數學結構，如通過在元素間加入二元的≤關係使頂點的集合成為有序集。但這並不值得深入研究，我們只需要假設頂點集是有序的，不需要大張旗鼓地聲明額外的結構必須精確定義其順序。

回頭看看上面的兩個單純形，我們可以發現這兩個單純形箭頭的方向是相反的。假設左邊那個單純形是 $σ_1$ ，右邊那個單純形是 $σ_2$ ，我們可以說 $σ_1=-σ_2$ 。

引入方向的原因將會在後面清楚地說明。

$n$ 維鏈

記住，一個單純復形包含了這個復形中每一個最高維度的單純形的所有面。也就是說，如果我們有一個 $2$ 維復形（一個擁有最高維度單純形的單純復形是 $2$ 維單純形（三角形）），那這個復形也包含了所有比它低維的面（如邊和頂點）。

$C={{0}, {1}, {2}, {3}, {0, 1}, {0, 2}, {1, 2}, {2, 3}, {0, 1, 2}}$ 是由一個點雲(例如數據集)構成的單純復形結構， $X={0, 1, 2, 3}$ 。

$C$ 是一個 $2$ 維復形，因為它最高維的單純形是 $2$ 維單純形（三角形）。我們可以把這個復形分解成一系列的子集，其中每組都由所有 $k$ 維單純形組成。在單純同調理論中，這些組叫做鏈群，並且任意特定組是k維鏈群 $C_k(X)$ 。例如 $C$ 的 $1$ 維群組是 $C_1(X)={{0, 1}, {0, 2}, {1, 2}, {2, 3}}$ 。

抽象代數基礎

「鏈群」中的「群」事實上有一個特定的數學意義。「群」的概念來自抽象代數，一個概括了你高中代數課上學過的課題的數學領域。不用說，它很抽象，但我會儘力從一些容易概念化的具體例子開始，然後才慢慢抽象出來，得到最基礎的概念。我將覆蓋到群，環，域，模，向量空間和各種其他小主題，當他們出現的時候。一旦我們解決了這些問題，我們將會到鏈群的討論中。

群

被稱為群的數學結構可以被認為是對對稱概念的概括。有一個完善的研究群的數學體系叫群論。我們不會在這裡深入研究群，因為我們只需要知道我們需要知道的。為了我們的目的，群是一個具有對稱性的數學對象。從幾何學的角度來說，這可能是最容易理解的，但你會發現，群是如此普遍，以至於許多不同的數學結構都可以從群論的角度受益。

目測我們可以在這個三角形上看到一些不改變結構的可能的操作。我畫了對稱線，這表示你可以在這 $3$ 條線上鏡像，最後還是得到同樣的三角形結構。更重要的是，你可以在平面上轉化這個三角形並且仍然是相同的結構。你也可以將三角形旋轉 $120$ 度，它仍然保持三角形的結構。群論為管理這些類型的操作及其結果提供了精確的工具。

這是群的數學定義：

群：是集合 $G$ 和一個二元運算 $*$ （或者其他你喜歡的符號），這一運算將 $a, bin G$ 映射到 $cin G$ 上，寫作 $a*b=c, forall a, b, c in G$ 。這個集合和它的運算被寫成有序對 $(G, *)$ 。另外，為了成為一個有效的群，集合和運算必須滿足以下條件：
1. 結合律： $forall a, b, cin G, (a*b)*c=a*(b*c)$

2. 單位元：存在一個元素 $e in G$ ，使得所有元素 $a in G$ ，等式 $a*e=e*a=a$ 成立。這樣的元素是唯一的，被稱為單位元素。
3. 逆元：對於所有 $ain G$ ，存在一個元素 $bin G$ ，通常表示為 $a^{-1}$ ，使得 $a*b=b*a=e$ ，其中 $e$ 是單位元素。
備註：運算 $*$ 不一定可以交換，即 $a*b=b*a$ 不一定成立。運算的順序可能有關係。如果沒有關係，則稱之為交換群。集合 $mathbb Z$ （整數集）和加法是一個交換群，因為 $1+2=2+1$ 。

「群」的概念看起來很隨意讓人不禁想問用途何在，但現在我們有希望把這個講清楚些。記住，所有的數學對象都是由一些(看似任意的)公理集合(基本上定義結構的規則集必須遵守)。你可以在集合上定義任何您想要的結構(只要它們邏輯一致而且有統一規則)，那你將需要一些數學對象/結構。有些結構比其他的更有趣。有些集合有很多結構(比如很多規則)，而有的則很少。通常，具有許多規則的結構僅僅是更通用/抽象結構的專門化。群只是一些數學結構(被人為賦予了規則的集合)，具有有趣的屬性，並且在很多領域都很有用。但是由於他們是如此的普遍，所以有時比較難確切地解釋他們。

讓我們看看我們能不能從上面「群化」我們的三角形示例。我們可以把三角形看作是一組被標記的頂點，就當它是 $2$ 維單純形。既然我們已經標記了三角形的頂點，我們可以很容易地把它描述為集合:

$t={a, b, c}$

但是我們如何定義 $t$ 的二元運算？我不確定，讓我們試一試。我們將構建一個表，它會向我們展示當我們在 $t$ 中「運算」兩個元素時會發生什麼。我認真的完成以下二元運算 ${(a, b)的映射|a, bin t }$ 並看看它是不是有效的群。如下圖。

為了了解 $a*b$ 是什麼，你從第一行開始看，找到 $a$ ，然後在左列找到 $b$ ，它們相交的地方即是結果。在我舉的例子中， $a*b=a$ 。注意，我已經定義了這個操作是不可交換的，所以 $a*b≠b*a$ 。你必須從上一行開始，然後到左邊的行(按順序)。

現在你應該能夠很快地看出，這實際上不是一個有效的群，因為它違反了群的公理。例如元素 $bin t$ ，你找不到一個單位元素 $e$ ，使得 $b*e=b$ 。

所以我們再來一次。這一次，我想要創建一個有效的群。

你應該檢查一下，這實際上是一個有效的群，這一次這個群是可交換的，所以我們稱它為交換群。單位元素是 $a$ ，因為 $a*b=b*a=b，a*c=c*a=c$ 。注意，表格本身目測就能看出來有對稱性。

結果表明，有限的群，就像有限的拓撲空間一樣，可以被表示為有向圖，這有助於可視化(數學的模式很漂亮，不是嗎？) 這些群的圖有一個特殊的名稱: Cayley圖。構造一個Cayley圖比構造拓撲空間的圖要複雜得多。我們必須向Cayley圖形添加另一個屬性，除了直接使用箭頭(邊)，我們還為每個箭頭分配一個運算。因為如果箭頭從 $a$ 指向 $b$ ，表示在群中， $a$ 運算生成 $b$ 。並不是所有的箭頭都是相同的運算，所以在可視化的幫助下，我們通常會使每一種類型的運算都與一個不同顏色的箭頭相關聯。

在我們構建一個Cayley圖之前，我們需要了解一個群的生成集是什麼。記住，群 $(G, *)$ 是集合 $G$ 加二元運算 $*$ 。生成集是子集 $S subseteq G$ ，比如 $G = {a * b mid a,b in S}$ 。總之，這說明生成集 $S$ 是 $G$ 的子集，但如果我們在 $S$ 的元素中實現二元運算 $*$ ，很可能它就變成完整的集合 $G$ 。就好像說 $S$ 是 $G$ 的壓縮。可能存在很多生成集。那我們的集合 $t={a, b, c}$ 和運算 $*$ 的生成集該怎麼定義呢？好，看一下運算表部分，我已經用紅色標出了。

你發現我標出了子集 ${b, c}$ ，因為這兩個元素可以生成完整的集合 ${a, b, c}$ 。但是事實上 ${b}$ 和 ${c}$ 也能分別生成完整的集合。例如， $b*b=c，b*b*b=a$ （我們也可以寫成 $b^2=c$ 和 $b^3=a$ ）。同樣， $c*c=b，c*c*c=a$ 。因此，通過在 $b$ 或者 $c$ 上反覆使用運算 $*$ ，我們可以生成集合的三個元素。而a是集合的單位元素，所以 $a^n=a, n in N$ 。

因為存在兩個可能性來生成元， $b$ 和 $c$ ，所以這裡有兩種不一樣的箭頭，代表不一樣的運算。也就是說，我們有「 $b$ 」箭頭和「 $c$ 」箭頭（代表 $*b$ 和 $*c$ ）。為了構建群 $(G, *)$ 的Cayley圖的邊集 $E$ ，生成集 $S subseteq G$ 是邊集 $E = {(a,c) mid c = a* b land a,c in G land b in S}$ 其中每條邊都被 $b∈S$ 用顏色標記。

Cayley圖的結果是：

在這個Cayley圖中，我們為兩個生成元 $b$ 和 $c$ 畫了兩種箭頭，然而，我們只需要選其一種，因為只要一種就能生成整個群。所以，一般來說，我們只要選最小的生成元來畫Cayley圖，這種情況下，我們只需要紅色箭頭就夠了。

所以這個群是等邊三角形的旋轉對稱，因為我們可以旋轉三角形 $120$ 度而不改變它，那我們的群將 $120$ 度的每一次循環表示為「加」( $*$ )生成元 $b$ 的群運算。我們還可以加單位元素，這看起來就像不旋轉它一樣。在這我們能看出這基本集合 ${a, b, c}$ 中的元素「加」 $b$ 是怎麼看起來像順時針旋轉 $120$ 度的：

這也被叫做與 $mathbb Z_3$ 同構的 $3$ 階循環群。 $mathbb Z_3$ ？同構？你都在問什麼？

同構主要是在保持結構的兩個數學結構之間存在一對一(雙射)映射。這就像它們是一樣的結構但是有不同的標籤一樣。我們剛研究的三角形的旋轉對稱群是與整數模 $3$ （ $mathbb Z_3$ ）同構的。模運算意味著在某一點上，運算循環回到開始。不像整數 $mathbb Z$ ，如果你一直加 $1$ ，你會得到一個更大的數，在模運算中，最終你加 $1$ 會回到起始元素(單位元素 $0$ )。想想時鐘的時針，它是整數模 $12$ （ $mathbb Z_{12}$ ），因為如果你再增加一個小時它最終會循環回來。

這是整數模 $3$ 的加法表:

所以，在 $mathbb Z_3$ 中， $1+1=2$ ，但 $2+2=1$ ，而 $1+2=0$ 。整數模 $x$ 形成一個循環群(帶有一個生成元)，其中元素 $x$ 和 $0$ 是單位元素。

好了，這就是群的基本知識，讓我們繼續討論環和域。

環和域

現在我們繼續學習一些關於環的知識，然後再輪到域。提前聲明，域和環是群的特例，也就是說，它們是帶有群規則和附加規則的集合。所有環都是群，所有域都是環。

環：是定義了兩個二元運算 $*$ 和 $ullet$ 的集合 $R$ ，它滿足下面這三個公理（環公理）：

1. $R$ 在 $*$ 運算下是交換群，也就是 $(R, *)$ 滿足群的公理。
2. 當運算 $ullet$ 滿足結合律 $(aullet (bullet c)=(aullet b)ullet c)$ 並且 $(R, ullet)$ 有單位元素 $(exists e in R 滿足eullet b=bullet e=e)$ 時， $(R, ullet)$ 構成一種叫幺半群的數學結構。
3. $*$ 和 $ullet$ 滿足分配律，即 $a, b, cin R$ ，有：
$aullet (b*c)=(aullet b)*(aullet c)$ （左分配律）
$(b*c)ullet a=(bullet a)*(cullet a)$ （右分配律）

最著名的環是 $mathbb Z$ ，因為它有兩個熟悉的運算 $+$ 和 $imes$ 。因為環也是群，我們提到整數群的生成元。因為整數從 ${ -n…-3, -2, -1, 0, 1, 2, 3…n}$ 跨度很大，所以在加法運算（ $+$ ）中，存在兩個生成元 ${ -1, 1}$ ，因為我不停 $1+1+1+…$ 可以得到所有正整數，而 $-1+-1+-1+…$ 可以得到所有負整數，並且 $-1+1=0$ 。

而下面是域的定義。

域：是定義了兩個二元運算 $*$ 和 $ullet$ 的集合 $F$ ，對於 $forall a, b, cin F$ ，它滿足以下條件。
結合律 $a*(b*c)=(a*b)*c, aullet (bullet c)=(aullet b)ullet c$ 交換律 $a*b=b*a, aullet b=bullet a$ 分配律 $aullet (b*c)=(aullet b)*(aullet c), (b*c)ullet a=(bullet a)*(cullet a)$ 恆等 $a*0=a=0*a, aullet 1=a=1ullet a$ 逆元素 $a*(-a)=0=-a*a, aullet a^{-1}=1=a^{-1}ullet a$ ，如果 $a≠0$
其中 $0$ 是 $*$ 運算下的單位元素， $1$ 是 $ullet$ 運算下的單位元素。

顯然，一個域的需求要比一個群多得多，為了注意，我一直在用符號 $*$ 和 $ullet$ 作為群，環，域的二元運算，但更常用的是 $+$ 和 $imes$ 。我最初不使用這些符號的唯一原因是我想強調指出，這些符號並不僅僅適用於你所熟悉的數字，而是抽象的運算，它可以在滿足要求的任何數學結構上起作用。但是現在你明白了，我們可以用更熟悉的符號。所以 $+=*$ ， $×=ullet$ ，而 $a÷b=a×b^{-1}$

還記得整數集 $mathbb Z$ 是最熟悉的環嗎？整數集不構成域，因為在 $mathbb Z$ 中，不是每個元素都有它的逆元素。例如，如果 $mathbb Z$ 是域，那麼 $5×5^{-1}=1$ ，然而 $5^{-1}$ 不是整數。如果我們考慮的是實數集 $mathbb R$ ，那 $5^{-1}=1/5$ 。因此，一個通過加（ $+$ ）和乘（ $×$ ）定義的域，同時也暗中定義了減（ $-$ ）和除（ $div$ ）。所以如果一個集合是域，除了單位元素，所有元素都能進行除運算；正如你從小學就知道 $0$ 不能作除數一樣。而且這一切都是對稱的，加法中 $1$ 的逆元素是 $-1$ ， $2$ 的逆元素是 $-2$ 。

注意到逆的對稱性了嗎？每一組互逆的數都與集合的中心，即為 $0$ ，距離相等。但因為 $0$ 是中心，所以它沒有逆，也不能用除法來定義。

所以退一步說，群論是關於研究對稱性的。任何具有對稱特徵的數學對象都可以被編組為群，然後用代數方法來確定哪些保持對稱的操作可以在群中進行。如果我們不關心對稱性，我們只想研究具有二元運算和結合律的集，那麼我們可以研究幺半群。

為什麼我們要學習群、環和域？

好的，我們學習了群、環、域的基礎，但為什麼呢？我已經說過了，我們需要理解群來理解那些需要計算單純復形的同調的鏈群。但更普遍的是，群、環和域讓我們在任何數學對象上都能使用我們熟悉的高中代數工具，這些工具滿足群/環/域（不只是數字）相對寬鬆的需求。所以我們能對像單純復形這種數學對象進行加，減（群），乘（環），除（域）。此外，我們還可以用一些未知的變數來解方程，包括不是數字的抽象數學對象。

直觀上，向量是n維的數字列表，例如 $[1.2, 4.3, 5.5, 4.1]$ 。重要的是，我確信您已經了解了將向量相加並將它們乘以標量的基本規則。例如，

$[1.2, 4.3, 5.5, 4.1]+[1, 3, 2, 1]=[1.2+1,4.3+3,5.5+2,4.1+1]=[2.2, 7.3, 7.5, 5.1]$

…總之，在向量加法中，它們必須是相同的長度，然後相應的元素相加。也就是說，每個向量的第一個元素加在一起，等等。而對於標量…

$2×[1.2, 4.3, 5.5, 4.1]=[2.2, 8.6, 11.0, 8.2]$

…向量中的每個元素都乘以標量。

但等等！向量的定義沒有提到任何信息說向量的元素是數量或列表。向量可以是一個符合域標準的任何有效的數學結構的集合。只要向量空間的元素可以通過域的元素（通常是實數或者整數）放大或縮小，並加在一起生成新的元素，而這新的元素仍是向量空間中的元素。

這是向量空間的正式定義，一種元素是向量的數學結構。

向量空間：在域 $F$ 上的向量空間 $V$ 是被叫做向量的對象的集合，其中向量能和標量進行加減乘除運算。因為 $V$ 和加運算構成交換群，而對於任意 $f in F, v in V$ ，我們都有元素 $fv in V$ （ $f×v$ 的結果仍在 $V$ 中）。標量乘法是分配律和結合律，而域的乘法恆等式在向量上恆等。

例如，最熟悉的數字向量來自域 $mathbb R$ 的向量空間。

那麼，模和向量空間一樣，除了它是在環上定義的以外。記住，每個域都是環，所以相較於向量空間，模是一個更隨意（更普遍）的數學結構。

（修改自< http://www.math.uiuc.edu/~r-ash/Algebra/Chapter4.pdf >）

我們還應該討論向量空間(或模)的基礎。

我們有一個有限集 $S={ a, b, c}$ ，我們想用它來構建一個模（或者向量空間）。我們可以在環 $R$ 上用這個集合構建模。在這種情況下，我們的模在數學上的定義是： $M = {(x* a, y* b, z* c) mid x,y,z in R}$

或者等效於

$M = {(x*g, y*g, z*g) mid x,y,z in R, g in S}$

其中 $*$ 是我們模的二元「乘」運算。但因為 $R$ 是環，這必須還有第二個二元運算，我們可以叫它「加」，用 $+$ 表示。注意到我用的是圓括弧，因此順序很重要，例如 $(a, b, c)≠(b, a, c)$ 。

現在， $M$ 中的每一個元素是以 ${ xa, yb, zc}$ 的形式（為了方便，我們省略了 $*$ ），因為它構成了這個模的基礎。我們可以從它底層的環R中加和縮放每個元素 $M$ 。如果我們用整數集 $mathbb Z$ 代替環，那我們可以通過下面方法來加和縮放：

$m_1, m_2 {in M} \ m_1 = (3a, b, 5c) \ m_2 = (a, 2b, c) \ m_1 + m_2 = (3a+a, b+2b, 5c+c) = (4a, 3b, 6c) \ 5*m_1 = 5 * (3a, b, 5c) = (5*3a, 5*b, 5*5c) = (15a, 5b, 25c)$

如果我們只注意加運算，這個模也是一個群（因為每個模和向量空間都是一個群），但即使我們的生成集是一個像 ${ a, b, c}$ 這樣的有限集，一旦我們把它應用在像整數這樣的無限環上，我們就構建了一個無限的模或向量空間。

通常情況下，一個向量空間，我們可以提出很多個基，然而，有一個數學定理告訴我們所有可能的基都是相同大小的。這就引出了維度的概念。向量空間(或模)的維數是其基的大小。因此，對於上面給出的例子，基的大小是 $3$ (基有三個元素)，因此模塊的維度為 $3$ 。

再如， $mathbb R^2$ 形成了一個向量空間，其中 $mathbb R$ 是實數集。這樣定義： $mathbb R^2 = {(x,y) mid x,y in mathbb R}$ 。基本上我們有所有可能的實數對組成的無限集。這個向量空間的一個基就是 $(x,y) mid x,y in mathbb R$ ，這是理所應當的因為它最簡單，但是沒有人能阻止我們用 $(2x+1.55,3y-0.718) mid x,y in mathbb R$ 作基，因為我們最終得到了相同的向量空間。但無論我們如何定義我們的基，它總是有 $2$ 個元素，因此它的維數是 $2$ 。

當我有一個像 $mathbb R^2$ 這樣 $2$ 維的向量空間，我們可以像這樣分離它們的成分：

$mathbb R_x = {(x, 0) mid x in mathbb R} \ mathbb R_y = {(0, y) mid y in mathbb R} \ mathbb R^2 = mathbb R_x oplus mathbb R_y$

我們引入了新的符號，叫做直和 $oplus$ ，用來表示通過像 $(x,0)+(0,y)=(x+0,0+y)=(x,y) mid x,y in mathbb R$ 這樣構建向量空間的維數的過程。因此我們可以簡單的表示為 $mathbb R^2 = mathbb R oplus mathbb R$ 。

我們也可以說 $mathbb R^2$ 的基是集合 ${ (1, 0), (0, 1)}$ 的生成子空間，記作 $span{ (1, 0), (0, 1)}$ 或者有時甚至更簡單地用尖括弧 $<(1, 0), (0, 1)>$ 表示。 $span{ (1, 0), (0, 1)}$ 是「由基 $(1, 0)$ 和 $(0, 1)$ 的所有線性組合構成的集合」的簡寫。

什麼是線性組合？簡單地說， $x$ 和 $y$ 的線性組合是 $ax+by$ 形式的任何表達，其中 $a, b$ 是域 $F$ 中的常數。

因此 $(1, 0)$ 和 $(0, 1)$ 的其中一個可能的線性組合是：

$5(1, 0)+2(0, 1)=(5*1, 5*0)+(2*0, 2*1)=(5, 0)+(0, 2)=(5+0, 0+2)=(5, 2)$ 。但 $(1, 0)$ 和 $(0, 1)$ 的所有線性組合可以用 ${a(1,0) + b(0,1) mid a,b in mathbb R}$ 來表達，而這等同於 $span{ (1, 0), (0, 1)}$ 或者 $<(1, 0), (0, 1)>$ 。這個集合所有的實數都是由 $mathbb R^2$ 表示的。

關於向量空間的基，重要的是它們必須是線性無關的。這意味著一個元素不能被表示成另一個元素的線性組合。例如，基本元素 $(1, 0)$ 不能被 $(0, 1)$ 表示。 $otexists a,b in mathbb R land a,b eq 0$ ，使得 $a(0,1) + b(1,0) = (1,0)$ 。

因此總結，向量空間的基 $V$ 包含了元素 $B$ 的集合，使得每個元素 $bin B$ 是線性無關的，而 $B$ 的生成子空間生成整個向量 $V$ 。因此向量空間的維度 $dim(V)$ 是 $B$ 中元素的個數。

(參考: The Napkin Project by Evan Chen <Evan Chen &bullet; Napkin>)

鏈群

哎，好吧，我們克服了很多障礙，但是現在我們回到我們真正關心的問題：算出一個單純復形的同調群。您可能還記得，我們沒有討論單純復形的鏈群。我不想重複所有的事情，所以，如果你忘記了，就把這部分重新讀一遍。我會等你的…

讓 $S={{a}, {b}, {c}, {d}, {a, b}, {b, c}, {c, a}, {c, d}, {d, b}, {a, b, c}}$ 成為一個從一些點雲（如數據集）中構建的抽象的單純復形（如下圖所示）。 $n$ 鏈 $（C_n(S)）$ 是 $n$ 維單純形 $S$ 的子集。比如 $C_1(S)= {a, b}, {b, c}, {c, a}, {c, d}, {d, b}}$ 和 $C_2(S)={a, b, c}$ 。

現在，如果我們給它定義一個滿足群公理的二元加運算，讓它可以變成一個鏈群。有了這個結構，我們可以把 $C_n(S)$ 中的 $n$ 維單純形加在一起。更確切地說， $n$ 鏈群是群、環或域F中n鏈帶係數地相加。我準備用和n鏈一樣的 $C_n$ 符號來表示一個鏈群。 $C_n(S) = sum a_i sigma_i$

其中 $σ_i$ 指的是 $n$ 鏈 $C_n$ 的第 $i$ 個單純形， $a_i$ 是群、環或域的相應係數，而 $S$ 是一開始的單純復形。

技術上，任何域/群/環都可以被用來為鏈組提供係數，然而，就我們目的來說，最好用最簡單的群是循環群 $mathbb Z_2$ ，即模 $2$ 的整數。 $mathbb Z_2$ 只包含 ${ 0, 1}$ 使得 $1+1=0$ ，而且是域，因為我們可以定義一個加法和乘法運算來滿足域的公理。這非常有用，因為我們只是希望能夠說，在我們的 $n$ 鏈中存在一個單純形(即它的係數為 $1$ )或者不存在(係數為 $0$ )，如果我們有一個重複的單純形，當我們把它們加在一起時，它們就會消掉。這就是我們想要的性質。你可能會反對，說 $mathbb Z_2$ 不是個群，因為它沒有逆，例如 $-1$ ，但事實上它是有的，例如， $a$ 的逆是 $a$ 。即在 $mathbb Z_2$ 中， $a=-a$ 因為 $a+a=0$ 。這就是逆存在的所有要求，你只需要在你的團隊中有某個元素，滿足 $exists b in G, a+b=0, forall b in G$ （ $G$ 是一個群）。

如果我們把 $mathbb Z_2$ 當作群係數，那我們基本上可以忽略單純形的方向。這樣就方便多了。但為了完整性，我想要融入方向，因為在學術論文和商業上，我見過很多人把整個整數集 $mathbb Z$ 當作係數；如果我們用一個像 $mathbb Z$ 一樣帶負數的域，那我們的單純形需要有導向，就像 $[a, b]≠[b, a]$ 。這是因為如果我們用 $mathbb Z$ ，那麼 $[a, b]=-[b, a]$ ，因為 $[a, b]+[b, a]=0$ 。

記住，我們的最終目標是在數學上找到單純復形中的連通分支和 $n$ 維的圈圈。我們上面的單純復形 $S$ ，目測，擁有一個連通分支和一個 $2$ 維的圈或者孔。記住單純形 ${a, b, c} in S$ 是「被填充」的，中間沒有洞，這是一個固體。

我們現在開始定義邊界映射。看起來一個無導向的 $n$ 維單純形 $X$ 的邊界映射（或者簡稱為邊界）是 $X$ 的 ${ {X} choose {n-1}}$ 子集的集合。也就是說，邊界是所有 $X$ 的 $（n-1）$ 子集的集合。例如， ${ a, b, c}$ 的邊界是 ${{a, b}, {a, c}, {b, c}}$ 。

讓我們給出一個適用於定向單純形的更精確的定義，並提供一些符號。

邊界：帶有方向向量 $[v_0,v_1,v_2,...v_n]$ 的 $n$ 維單純形 $X$ 的邊界（ $partial(X)$ ）是： $partial(X) = sum^{n}_{i=0}(-1)^{i}[v_0, v_1, v_2, hat{v_i} ... v_n]$
其中第 $i$ 個向量被從序列中移除。
單個頂點的邊界是 $0$ ， $partial([v_i]) = 0$ 。

例如，如果 $X$ 是 $2$ 維單純形 $[a,b,c]$ ，那麼 $partial(X) = [b,c] + (-1)[a,c] + [a,b] = [b,c] + [c,a] + [a,b]$ 。

讓我們來看看如何從邊界的概念中得到上面 2 維復形中的一個簡單的圈。我們看到 $[b,c]+[c,d]+[d,b]$ 是形成圈或者循環的 $1$ 維單純形。如果我們得到這個帶有係數域 $mathbb Z$ 的集合的邊界，那麼

$partial([b,c] + [c,d] + [d,b]) = partial([b,c]) + partial([c,d]) + partial([d,b]) \ partial([b,c]) + partial([c,d]) + partial([d,b]) = [b] + (-1)[c] + [c] + (-1)[d] + [d] + (-1)[b] \ equire{cancel} cancel{[b]} + cancel{(-1)[b]} + cancel{(-1)[c]} + cancel{[c]} + cancel{(-1)[d]} + cancel{[d]} = 0$

這使我們有了一個更普遍的屬性，一個 $p$ 圈是 $C_n$ 中的 $n$ 鏈，其中 $C_n$ 的邊界 $partial(C_n) = 0$ 。

也就是說，為了找到鏈群 $C_n$ 中的 $p$ 圈，我們需要解決代數方程 $partial(C_n) = 0$ ，而它的解就是 $p$ 圈。不用擔心，當我們過一些示例時，這些都會變得有意義和更直觀的。

一個重要的結果是邊界的邊界總是 $0$ ，即 $partial_n partial_{n-1} = 0$ 。

鏈復形

我們剛看到邊界運算是如何分配的，例如，兩個單純形 $sigma_1, sigma_2 in S$ $partial(sigma_1 + sigma_2) = partial(sigma_1) + partial(sigma_2)$

鏈復形： $S$ 是一個單純 $p$ 復形。 $C_n(S)$ 是 $S$ 的 $n$ 鏈， $n≤p$ ，鏈復形 $mathscr C(S)$ 是 $mathscr C(S) = sum^{p}_{n=0}partial(C_n(S))$
換句話說
$mathscr C(S) = partial(C_0(S)) + partial(C_1(S)) + ... + partial(C_p(S))$

現在我們可以定義怎麼在單純復形中找到 $p$ 圈。

核： $partial(C_n)$ 的核（記作 $Ker(partial(C_n))$ ）是 $n$ 鏈 $Z_n subseteq C_n$ 的群，其中 $partial(Z_n) = 0$ 。

我們已經快好了，我們需要再多兩個概念，我們就可以定義單純同調。

邊界的像：邊界 $partial_n$ （一些 $n$ 鏈的邊界）的像 $Im(partial_n)$ 是邊界的集合。

例如，如果 $1$ 鏈是 $C_1 = {[v_0, v_1], [v_1, v_2], [v_2, v_0]}$

然後 $partial_1 = [v_0] + (-1)[v_1] + [v_1] + (-1)[v_2] + [v_2] + (-1)[v_0]$

$Im partial_1 = {[v_0-v_1],[v_1-v_2],[v_2-v_0]}$

因此 $partial_n$ 和 $Impartial_n$ 唯一的不同是邊界的像是集合形式的，而邊界是多項式形式的。

第 $n$ 個同調群：第 $n$ 個同調群 $H_n$ 定義為 $H_n=Kerpartial_n/Impartial_{n+1}$ 。

連通數：第 $n$ 個連通數 $b_n$ 定義為 $H_n$ 的維度， $b_n = dim(H_n)$ 。

預告

實際上我們已經涵蓋了大部分基本的數學知識，以便我們開始使用簡單復形來計算拓撲特徵，這就是我們下次要做的。

參考文獻（網站）

1. Applying Topology to Data, Part 1: A Brief Introduction to Abstract Simplicial and ?ech Complexes.

2. http://www.math.uiuc.edu/~r-ash/Algebra/Chapter4.pdf

3. Group (mathematics)

4. Homology Theory — A Primer

5. http://suess.sdf-eu.org/website/lang/de/algtop/notes4.pdf

6. Evan Chen &bullet; Napkin

參考文獻（學術刊物）

1. Basher, M. (2012). On the Folding of Finite Topological Space. International Mathematical Forum, 7(15), 745–752. Retrieved from http://www.m-hikari.com/imf/imf-2012/13-16-2012/basherIMF13-16-2012.pdf

2. Day, M. (2012). Notes on Cayley Graphs for Math 5123 Cayley graphs, 1–6.

3. Doktorova, M. (2012). CONSTRUCTING SIMPLICIAL COMPLEXES OVER by, (June).

4. Edelsbrunner, H. (2006). IV.1 Homology. Computational Topology, 81–87. Retrieved from Computational Topology

5. Erickson, J. (1908). Homology. Computational Topology, 1–11.

6. Evan Chen. (2016). An Infinitely Large Napkin.

7. Grigor』yan, A., Muranov, Y. V., & Yau, S. T. (2014). Graphs associated with simplicial complexes. Homology, Homotopy and Applications, 16(1), 295–311. HHA 16 (2014) No. 1 Article 16

8. Kaczynski, T., Mischaikow, K., & Mrozek, M. (2003). Computing homology. Homology, Homotopy and Applications, 5(2), 233–256. HHA 5 (2003) No. 2 Article 8

9. Kerber, M. (2016). Persistent Homology – State of the art and challenges 1 Motivation for multi-scale topology. Internat. Math. Nachrichten Nr, 231(231), 15–33.

10. Khoury, M. (n.d.). Lecture 6 : Introduction to Simplicial Homology Topics in Computational Topology : An Algorithmic View, 1–6.

11. Kraft, R. (2016). Illustrations of Data Analysis Using the Mapper Algorithm and Persistent Homology.

12. Lakshmivarahan, S., & Sivakumar, L. (2016). Cayley Graphs, (1), 1–9.

13. Liu, X., Xie, Z., & Yi, D. (2012). A fast algorithm for constructing topological structure in large data. Homology, Homotopy and Applications, 14(1), 221–238. HHA 14 (2012) No. 1 Article 11

14. Naik, V. (2006). Group theory : a first journey, 1–21.

15. Otter, N., Porter, M. A., Tillmann, U., Grindrod, P., & Harrington, H. A. (2015). A roadmap for the computation of persistent homology. Preprint ArXiv, (June), 17. Retrieved from [1506.08903] A roadmap for the computation of persistent homology

16. Semester, A. (2017). § 4 . Simplicial Complexes and Simplicial Homology, 1–13.

17. Singh, G. (2007). Algorithms for Topological Analysis of Data, (November).

18. Zomorodian, A. (2009). Computational Topology Notes. Advances in Discrete and Computational Geometry, 2, 109–143. Retrieved from CiteSeerX - Computational Topology

19. Zomorodian, A. (2010). Fast construction of the Vietoris-Rips complex. Computers and Graphics (Pergamon), 34(3), 263–271. Redirecting

20. Symmetry and Group Theory 1. (2016), 1–18. Redirecting