122 When Life is Linear 棗ー 1 5 Figu re 12.2. A fictional season played between NCAA basketball teams. A directed edge points from the winning team tO the losing team. The weight Ofan edge indicates the difference between the winmng and losing scores. the steps of each method and see their similarities and differences. We'll restrICt our discussion tO four teams: College Of Charleston, Furman Uni- versity, Davidson College, and Appalachian State University. As ⅲ Fig- ure 12. し we'll represent the records of the teams by a graph where the vertlces are teams and a directed edge points om the winning team to the losing team. Although not needed for the Colley method, the weight of an edge indicates the difference between the winmng and losing scores. ln Figure 12.2 , we see, starting in the upper 厄代 and moving clockwise, the College of Charleston, Furman, Davidson, and AppaIachian State. For the CoIIey Method, the linear system is 0 5 4 5 where C, F, D, and correspond to the ratings for the CoIIege of Charleston, Furman, Davidson, and Appalachian State, respectively. So, C 0.5000 F 0.5833 D 0.5000 0.4 7 -4- 1 0 ・ 1 1 1

GO FO れ and MuItipIy 0 2D, the formula can be denved from the law of cosines which for similarlty as the angle between the taste vectors. the smallest value are identified as most similar. This time, we'll measure Of Ⅱ u ー v Ⅱ , where u and v are taste vectors. The tWO vectors that result in lfwe used our earlier method from Section 4.1 , we would find the value and mine IS becomes a vector. SO, Oscar's taste vector is [ 0 5 ]. Emmy's vector is [ 5 2 ] , the films 5 and 2 , and ー rate them ー 3 and 3. Each person's ratings again Oscar rates 月川夜・た〃〃″ん with a 0 and Gravity with a 5. Emmy rates Figu re 5.2. The law ofcosines helps derive a formula for the angle between vectors. Figure 5.2 (a) states 2 4 ThiS can be rearranged as = わ 2 十 0 ー 2 わ 0 cos . ー 42 十わ 2 十ド COS 図 graphically in this picture. The law 0f cosines states ure 5.2 (b). NOte hOW we are vlewing the addition and subtraction ofvectors NOW, let's view the sides Of the trlangle as vectors, which we see in Fig- 2 わ 0 2 2 We can wrlte 2 2 2 2 ー 2 恒Ⅱ 2 いⅡ。 s 〃 . 2 2 v ・ v ー 2v ・ u 十 u ・ u ⅵ 2 ー 2v ・ u + 恒

When Life is Linear 0 ■ 0 ■■ ■動■ Figu re 2 4. A simple matrix pattern (a) and a banded matrix's pattern (b). the time tO solution can be greatly reduced if the associated matr1X has a spy 可 0t 0f the form seen in Figure 2.4 (b). The reduction in time more strlking as the matnx grows, such as a matnx with 1 000 rows rather than 10 as pictured. What dO you notice about the structure Of the matr1X ⅲ Figure 2.4 (b)? Such matnces are called わ施 d. 2.3 Math in the Matrix Before moving tO the next section and performing mathematical operations on matrlces, let's learn tO construct a matr1X that, when viewed 仕 om afar, creates an image like that Of the Mona Lisa that we saw in Figure 2.1. Figu re 2.5. Using the pattern in Figure 2.4 (a) to create optical illusions.

Mining fO 「 Meaning 113 Figu 「 e 1 1 6. The average image computed over the library oftwelve U. S. Presidents seen in Figure Ⅱ .5 (a) and the average lmage subtracted 什 om the image 0fPresident Kennedy (b). Multiplying both sides by P, we get PPTPu. = Pitul, soPPT(Pui)=Åi(PuD, WhiCh means if u iS an elgenvector Of then pu iS an elgenvector Of C = PPT. We went from looking for eigenvectors of a 50 , 000 x 50 , 000 matrlx tO a 12 x 12 matrlx. Figure 11.7 depicts six eigenfaces (which again are simply eigenvec- tors) Ofthe six largest eigenvalues 0fC for our presidentiallibrary ofimages. Here we make the connectlon tO eigenvalues Of C and singular values. The singular values Of P are the square roots Of the nonzero elgenvalues Of C. How this is helpfullies in what we learned about singular values in Chap- ter 9 , namely their tendency t0 drop 0 in value quickly. This allows us t0 approximate a large collection 0f images, like 5 000 , with only a small subset Of eigenfaces. Figu re 1 1 .7. A half dozen eigenfaces of the library of twelve U. S. Presidents seen in Figure Ⅱ .5.

When Life is Linear Figu re 8.5. Clustering 叩 proximately 50 people by their friendships on Facebook. The network (a) and when grouped by the clusters created using one eigenvector (b). group is essentially non-family members although a few family members make their way intO this cluster. Plotting a matr1X is another useful way tO view the effect of clusterlng, especially ifthe network contains hundreds or thousands ofnodes. The 可 ot of the adJacency matnx of the graph in Figure 8.5 (a) appears in Figure 8.6 (a). After clusterlng, we reorder the matr1X so rows ln a cluster appear together ⅲ the matnx. Having done this, we see the matr1X in Figure 8.6 (b). The go 引 0f clustermg is t0 form groups with maximally connected components within a group and minimally connected components between different groups. We see this with the smaller, but dense, submatnx ⅲ the upper 厄代 and the larger submatrrx in the lower nght. The darker square 代当 ons in the 可 0t 0f the matr1X correspond t0 the clusters in Figure 8.5 (b). What if we tried more clusters? Can we? We will learn to break the matrlx into more groups in Chapter 11. 8.4 Seeing the PrincipaI ln this section, we see hOW elgenvectors can aid in data reduction and unveil underlying structure in information. As an example adapted from 卩 1 ] , let's ok at data sampled 什 om an ellipse centered at the ongin as seen in Fig- ure 8.7. We are looking for what are called the ・ⅲ c の記 co 川〃 0 〃劭な . We'll use the method called P 〃 c の記 CO 川〃 0 〃 e 厩〃 4 ゆ豆 s or PCA. For this example, we'll find one prlncipal component. lt is the direction where there is the most varlance. First, let's find the varlance in the horl- zontal direction. 、 Me compute the square Of the distance om every point tO

GGß 48 When Life is Linear Figu re 6.3. A grayscale image of a box that is 300 by 300 pixels (a) and the image after 川 0 rows in the middle third are multiplied by 1.5. operators, like our use Of the matrIX P in swapplng rows, that will perform your visual effect. What vanations would you try? 6.1.2 Brightened Eyes NOW, let's ok at multiplying a row by a nonzero number. Let's begin with a gray box that is 300 by 300 pixels as seen in Figure 6.3 (a). We'll multiply the rows ⅲ the middle third by 1.5 and visualize the image again. We see the new image in Figure 6.3 (b). Remember,larger values correspond t0 lighter pixel values in grayscale images. Let's d0 this again, but now our matr1X will be a grayscale image ofthe Mona Lisa seen in Figure 6.4 (b). The image has 786 rows and 579 columns. Let's multiply every row 仕 om row 320 to 420 by 1.5 and then visualize the Figu re 6.4. A grayscale image of the Mona Lisa (b) and the image after I()() rows are multiplied by 1.5 (a) and when 心 but those same IOO rows are multiplied by 0.5 (c).

し↓しし 132 When Life is Linear come. and, as you may find as you create your ideas, there are many more tO bly take it intO new directions. As we've seen, there are many applications complete this b00k? Those ideas can be your steps ⅲ the field and possl- shading (b). Figu re 13.1. A wireframe model of a Viking (a) and the character rendered with

28 When Life is Linear Figu 「 e 4.5. A handwritten 3 that is not correctlyidentified by our algorithm. This method correctly classifies all 3s in Figure 4.3. Much more com- plicated algorithms for digit recognition exist since it can be diffcult tO fully recognize handwrltten digits. Sometimes, we wrlte sloppily and wrlte numerals that are hard t0 read. For example, the digit in Figure 4.5 is intended to be a 3 , but our algorlthm classifies it as a 5. See why? The elements ofthe digit 5 that are within it. While not perfect, this is a simple and accessible algonthm for classifying digits. DO any ideas come t0 mind as to how you might alter it? 、 Me are now ready tO return tO arlthmetic and learn tO multiply, which will give us another way tO measure similarlty.

Mining fO 「 Meaning ロロ 107 ロロ ロロロ ロロ ロロ ロ ロ ロロロ Figu re 11.1. Plotting the adjacency matrix of a gr 叩 h. We see the adJacency matnx visualized in Figure 11.2 (a). Here we see little organization or a pattern Of connectivity with my fnends. If we partition the group int0 two clusters using the Fiedler method outlined in Section 8.3 , after reordermg the rows and columns SO clusters appear ln a group, 、 see the matnx in Figure 11.2 (b). Remember, we partitioned the matr1X intO clusters. 、 Ve see this with the smaller but dense, matnx in the upper に代 and the larger matr1X in the : をれ物を : 0 Figure 11.2. The adJacency 0f500 Facebook friends (a). The matnx after reordering the rows and columns intO tWO clusters found using an eigenvector (b).

77 Stretch and Shrink を・をを Figu re 8.6. Looking at the Facebook social network in Figure 8.5 ofapproximately 50 friends via the ad. 」 acency matrix. the x-axis, illustrated by the dotted lines in Figure 8.8 (a). This equals 600 , glVing the vanance Of the data over the y-coordinates. That is, the measure Of hOW spread out is the data in the . y-direction. Compare this tO the var ト ance in the vertical direction. The square Of the distance from every point to the y-axis, illustrated by the dotted lines in Figure 8.8 (b), is 2400. From these tWO numbers, we find the data tO be more spread out over the x- coordinates. You can see this visually since the data points are farther away from each 0ther honzontally than vertically. 0 8 CD 4 ・つ」 0 ワ」 0 Figure 87. Points sampled from an ellipse centered at the origin. 20 5 00