第4章 線性代數

4.1 向量

抽象地說，向量是指可以加總（以生成新的向量），可以乘以標量（即數字），也可以生成 新的向量的對象。

具體來說（對我們而言），向量是有限維空間的點。即使你本無意視你的數據為向量，將數值數據表示為向量也是非常好的處理方式。

比如，如果你有很多人的身高、體重、年齡數據，就可以把數據記為三維向量 (height, weight, age)。如果你教的一個班有四門考試，就可以把學生成績記為四維向量 (exam1, exam2, exam3, exam4)。

最簡單的入門方法是將向量表示為數字的列表。一個包含三個數字的列表對應一個三維空 間的向量，反之亦然：

<code>
height_weight_age
 
=
 
[70,
      
                                    
170
,
    
                                     
40
]
     
grade 
 
=
 
[95,
    
               
80
，#考試2
               
75
，#考試3
               
62
]
   /<code>

首先，我們常常需要對兩個向量做加法。向量以分量方式做運算。這意味著，如果兩個向量v和w長度相同，那它們的和就是一個新的向量，

其中向量的第一個元素等於 v[0] +w[0], 第二個元素等於v[1] +w[1], 以此類推。（如果兩個向量的長度不同，則不能相加。)

例如， 向量[1, 2]加上向量[2, 1] 等於[1+2 , 2+1] 或[3, 3] , 如圖 4，1

圖4-1

我們可以很容易的實現這個功能： 對向量調用zip函數， 同時用列表解析使向量的相應元素相加：

<code>
def
 
vector_add
(v , w)

			
""
"adds corresponding elements"
""
 
       
return
 [v_i + w_i 
                    
for
 v_i , w_i 
in
 zip(v , w)]
同樣，對兩個向量做減法，只需要使向量的相應元素相減：
def
 
vector_subtract
( v, w)
:
       
""
"subtracts corresponding elements"
""
 
       
return
 [v_i - w_i
                    
for
 v_i, w_i 
in 
 zip(v, w)]
               /<code>

有時，我們需要對一系列向量做加法。即生成一個新向量， 其第一個元素是這一系列向量第一個元素的和，第二個元素是這一系列向量第二個元素的和，以此類推。最簡單的方法是每次遞加一個向量：

<code>
def
  
vector_sum
(vectors)
:

       
"""sums all corresponding elements"""
       result = vectors[
0
]                                                     
       
for
 vector 
in
 vectors[
1
: ]:                                           
             result = vector_add(result,  vector)                     
        
return
 result/<code>

當你思考這個解決方法時，我們正通過 vector_add 函數，即使用 reduce 的方式來加總這 一系列的向量。換句話說，我們用高級的函數更加簡潔地實現了這個功能：

<code>
def
 
vector_sum
(vectors) 
:

      
return
 reduce(vector_add, vectors)/<code>

4.2　矩陣

矩陣是一個二維的數據集合。我們將矩陣表示為列表的列表，每個內部列表的大小都一 樣，表示矩陣的一行。如果 A 是一個矩陣，那麼 A[i][j] 就表示第 i 行第 j 列的元素。按照 數學表達的慣例，我們通常用大寫字母表示矩陣。例如：

<code>A = 
[[1, 2, 3],   # A有2行3列      
       [4, 5, 6]]
 
B = 
[[1, 2],      # B有3行2列      
       [3, 4],      
       [5, 6]]
/<code>

在數學中，矩陣的第一行通常稱為“第 1 行”，第一列通常稱為“第 1 列”。 而我們需要將矩陣的形式和 Python 的列表統一起來：Python 中的列表從 0 開始索引，所以，我們將矩陣的第一行稱為“第 0 行”，將第一列稱為“第 0 列”。

基於列表的列表這種表達形式，矩陣 A 具有 len(A) 行和 len(A[0]) 列，我們把這稱作它的 形狀（shape）：

<code>
def
 
shape
(A)
: 
     
       num_rows = len(A)     
       num_cols = len(A[
0
])   
if
 A 
else
 
0
    
       
return
 num_rows, num_cols/<code>

如果一個矩陣有 n 行 k 列，則可以記為 n×k 矩陣。我們可以把這個 n×k 矩陣的每一行都 當作一個長度為 k 的向量，把每一列都當作一個長度為 n 的向量

<code>
def
 
get_row
(A, i)
:
     
      
return
 A[i]               
 
def
 
get_column
(A, j)
:
     
      
return
 [A_i[j]              
                
for
 A_i 
in
 A]    /<code>

同樣，我們也可以根據形狀和用來生成元素的函數來創建矩陣。可以通過一個嵌套的列表 解析來實現：

<code>/<code>

有了這個函數，就可以生成一個 5×5 的單位矩陣（對角線元素是 1，其他元素是 0）：

<code>
def
 
is_diagonal
(i, j)
:
     
      
"""1's on the 'diagonal', 0's everywhere else"""
     
       
return
 
1
 
if
 i == j 
else
 
0
 
 
identity_matrix = make_matrix(
5
, 
5
, is_diagonal) 
 
 
 
 
 
/<code>

矩陣的重要性不言而喻，原因有以下幾個。

首先，可以通過將每個向量看成是矩陣的一行，來用矩陣表示一個包含多維向量的數據 集。例如，如果有 1000 個人的身高、體重和年齡，就可以創建一個 1000×3 的矩陣

<code>
data
  
=
 
[[70,
 
170
,
 
40
],
         
             
[65,
 
120
,
 
26
],
         
             
[77,
 
250
,
 
19
],
         
              
             
]
/<code>

第二，隨後我們會看到，可以用一個 n×k 矩陣表示一個線性函數，這個函數將一個 k 維的

向量映射到一個 n 維的向量上。我們使用的很多技術與概念都隱含著這樣的函數。

第三，可以用矩陣表示二維關係。在第 1 章中，我們曾經將網絡邊際表示為數據對 (i, j) 的集合。我們還可以通過建立矩陣 A 來實現這個描述：如果節點 i 和節點 j 有關係，則用 矩陣的元素 A[i][j] 為 1 來表示；若節點 i 和節點 j 沒有關係，則用 A[i][j] 為 0 來表示。

回想前面講過的關係：

<code>
friendships
 
=
 
[(0,
 
1
),
 
(0,
 
2
),
 
(1,
 
2
),
 
(1,
 
3
),
 
(2,
 
3
),
 
(3,
 
4
),
                
                        
(4,
 
5
), 
 
(5,
 
6
),
 
(5,
 
7
),
 
(6,
 
8
),
 
(7,
 
8
),
 
(8,
 
9
)]
/<code>

可以通過矩陣形式再現：

<code>  
 
friendships
 
=
 
[[0,
 
1
,
 
1
,
  
0
,
 
0
,
 
0
,
 
0
,
 
0
,
 
0
,
 
0
],
  
                       
[1,
 
0
,
 
1
,
 
1
,
 
0
,
 
0
,
  
0
,
 
0
,
 
0
,
 
0
],
  
                       
[1,
 
1
,
 
0
,
 
1
,
 
0
,
 
0
,
 
0
,
 
0
,
 
0
,
  
0
],
  
                       
[0,
 
1
,
 
1
,
 
0
,
 
1
,
 
0
,
 
0
,
 
0
,
 
0
,
 
0
],
  
                       
[0,
 
0
,
 
0
 
,
 
1
,
 
0
,
 
1
,
 
0
,
 
0
,
 
0
,
 
0
],
  
                       
[0,
 
0
,
 
0
,
 
0
,
 
1
,
 
0
 
,
 
1
,
 
1
,
 
0
,
 
0
],
  
                       
[0,
 
0
,
 
0
,
 
0
,
 
0
,
 
1
,
 
0
,
 
0
,
 
1
 
,
 
0
],
  
                       
[0,
 
0
,
 
0
,
 
0
,
 
0
,
 
1
,
 
0
,
 
0
,
 
1
,
 
0
],
  
                       
[0,
 
0
,
  
0
,
 
0
,
 
0
,
 
0
,
 
1
,
 
1
,
 
0
,
 
1
],
  
                       
[0,
 
0
,
 
0
,
 
0
,
 
0
,
  
0
,
 
0
,
 
0
,
 
1
,
 
0
]]
 /<code>

如果關係很少，這種表示形式的效率就會很低，因為必須存儲很多零。但是，通過矩陣表 示可以快速地查找確認某兩個節點是否是連接的——通過一個矩陣查找函數即可，不必 （有可能會）搜索每條邊：

<code>friendships[
0
][
2
] == 1  # true， 0和2是朋友
friendships[
0
][
8
] == 1  # false， 0和8不是朋友/<code>

同樣，若想找到一個節點的所有連接，只需檢查這個節點所在的列（或行）：

<code>friends_of_five = [i                                                             
                   for i, is_friend in enumerate(friendships[5])    
                   if is_friend]                                                       
/<code>

為了加速這個搜尋過程，我們之前給每個節點對象都添加了一個連接列表。但對於太大 的、擴展性強的圖形來說，成本太高，維護也很難。

本書隨後還會探討這些矩陣。