Binary Tree Implementation : Basic and Advanced Operation

Binary Trees

Introduction

We extend the concept of linked data structures to structure containing nodes with more than one self-referenced field. A binary tree is made of nodes, where each node contains a "left" reference, a "right" reference, and a data element. The topmost node in the tree is called the root.Every node (excluding a root) in a tree is connected by a directed edge from exactly one other node. This node is called a parent. On the other hand, each node can be connected to arbitrary number of nodes, called children. Nodes with no children are called leaves, or external nodes. Nodes which are not leaves are called internal nodes. Nodes with the same parent are called siblings.

More tree terminology:

• The depth of a node is the number of edges from the root to the node.
• The height of a node is the number of edges from the node to the deepest leaf.
• The height of a tree is a height of the root.
• A full binary tree.is a binary tree in which each node has exactly zero or two children.
• A complete binary tree is a binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right.

A complete binary tree is very special tree, it provides the best possible ratio between the number of nodes and the height. The height h of a complete binary tree with N nodes is at most O(log N). We can easily prove this by counting nodes on each level, starting with the root, assuming that each level has the maximum number of nodes:

n = 1 + 2 + 4 + ... + 2h-1 + 2h = 2h+1 - 1

Solving this with respect to h, we obtain

h = O(log n)

where the big-O notation hides some superfluous details.

Advantages of trees

Trees are so useful and frequently used, because they have some very serious advantages:

• Trees reflect structural relationships in the data
• Trees are used to represent hierarchies
• Trees provide an efficient insertion and searching
• Trees are very flexible data, allowing to move subtrees around with minumum effort

Traversals

A traversal is a process that visits all the nodes in the tree. Since a tree is a nonlinear data structure, there is no unique traversal. We will consider several traversal algorithms with we group in the following two kinds

• depth-first traversal
• breadth-first traversal

There are three different types of depth-first traversals, :

• PreOrder traversal - visit the parent first and then left and right children;
• InOrder traversal - visit the left child, then the parent and the right child;
• PostOrder traversal - visit left child, then the right child and then the parent;

There is only one kind of breadth-first traversal--the level order traversal. This traversal visits nodes by levels from top to bottom and from left to right.

As an example consider the following tree and its four traversals: PreOrder - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3 InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11 PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8 LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2

In the next picture we demonstarte the order of node visitation. Number 1 denote the first node in a particular traversal and 7 denote the last node.
These common traversals can be represented as a single algorithm by assuming that we visit each node three times. An Euler tour is a walk around the binary tree where each edge is treated as a wall, which you cannot cross. In this walk each node will be visited either on the left, or under the below, or on the right. The Euler tour in which we visit nodes on the left produces a preorder traversal. When we visit nodes from the below, we get an inorder traversal. And when we visit nodes on the right, we get a postorder traversal.

1:  package com.examples.ajay;  
2:  import java.util.ArrayDeque;  
3:  import java.util.ArrayList;  
4:  import java.util.List;  
5:  import java.util.Queue;  
6:  import java.util.Stack;  
7:  import org.w3c.dom.ls.LSInput;  
8:  class Node{  
9:       int data;  
10:       Node left;  
11:       Node right;  
12:  }  
13:  class Item{  
14:       int data;  
15:       int level;  
16:  }  
17:  class Height{  
18:       int data;  
19:  }  
20:  public class BinaryTreeImplementation {  
21:       private static int count = 0;  
22:       private static int preOrderIndex = 0;  
23:       public static int max(int i, int j) {  
24:            if(i < j) return j;  
25:            else return i;  
26:       }  
27:       public static void preorder(Node node){  
28:            if(node == null) return;  
29:            System.out.print(node.data + " ");  
30:            preorder(node.left);  
31:            preorder(node.right);  
32:       }  
33:       public static void postorder(Node node){  
34:            if(node == null) return;  
35:            postorder(node.left);  
36:            postorder(node.right);  
37:            System.out.print(node.data + " ");  
38:       }  
39:       public static void inorder(Node node){  
40:            if(node == null) return;  
41:            inorder(node.left);  
42:            System.out.print(node.data + " ");  
43:            inorder(node.right);  
44:       }  
45:       public static void levelOrder(Node node){  
46:            Queue<Node> queue = new ArrayDeque<Node>();  
47:            queue.add(node);  
48:            while(!queue.isEmpty()){  
49:                 Node temp = queue.remove();  
50:                 System.out.print(temp.data + " ");  
51:                 if(temp.left != null) queue.add(temp.left);  
52:                 if(temp.right != null) queue.add(temp.right);  
53:            }  
54:       }  
55:       public static void preorderIteration(Node node){  
56:            Stack<Node> stack = new Stack<Node>();  
57:            stack.push(node);  
58:            while(!stack.isEmpty()){  
59:                 Node temp = stack.pop();  
60:                 System.out.print(temp.data + " ");  
61:                 if(temp.right != null) stack.push(temp.right);  
62:                 if(temp.left != null) stack.push(temp.left);  
63:            }  
64:       }  
65:       public static void postorderIteration(Node node){  
66:            Stack<Node> stack = new Stack<Node>();  
67:            if(node == null) return;  
68:            do{  
69:                 while(node != null){  
70:                   if(node.right != null)     stack.push(node.right);  
71:                      stack.push(node);  
72:                      node = node.left;  
73:                 }  
74:                 node = stack.pop();  
75:                 if((node.right != null) && (!stack.isEmpty()) && (node.right == stack.peek())){  
76:                      stack.pop();  
77:                      stack.push(node);  
78:                      node = node.right;  
79:                 }else{  
80:                      System.out.print(node.data + " ");  
81:                      node = null;  
82:                 }  
83:            }while(!stack.isEmpty());  
84:       }  
85:       public static void inorderIteration(Node node){  
86:            Stack<Node> stack = new Stack<Node>();  
87:            if(node == null) return;  
88:            do{  
89:                 while(node != null){  
90:                      stack.push(node);  
91:                      node = node.left;  
92:                 }  
93:                 if(stack.empty()) break;  
94:                 node = stack.pop();  
95:                 System.out.print(node.data + " ");  
96:                 node = node.right;  
97:            }while(true);  
98:       }  
99:       public static int maximum(Node root){  
100:            int max = Integer.MIN_VALUE;  
101:            int left, right;  
102:            if(root == null) return max;  
103:            left = maximum(root.left);  
104:            right = maximum(root.right);  
105:            if(left > right) max = left;  
106:            else max = right;  
107:            if(max < root.data) max = root.data;  
108:            return max;  
109:       }  
110:       public static boolean searchElement(Node root, int data){  
111:            boolean isLeft = false;  
112:            boolean isRight = false;  
113:            if(root == null) return false;  
114:            if(root.data == data) return true;  
115:            isLeft = searchElement(root.left, data);  
116:            isRight = searchElement(root.right, data);  
117:            if(isLeft == false && isRight == false) return false;  
118:            else return true;  
119:       }  
120:       public static int sizeOfTree(Node root){  
121:            if(root == null) return 0;  
122:            int leftSize = sizeOfTree(root.left);  
123:            int rightSize = sizeOfTree(root.right);  
124:            return leftSize + rightSize + 1;  
125:       }  
126:       public static Node createFullBST(int height){  
127:            if(height == 0) return null;  
128:            Node temp = new Node();  
129:            temp.left = createFullBST(height-1);  
130:            temp.data = count++;  
131:            temp.right = createFullBST(height-1);  
132:            return temp;  
133:       }  
134:       public static int heightTree(Node root){  
135:            if(root == null) return 0;  
136:            int leftHeight = heightTree(root.left) + 1;  
137:            int rightHeight = heightTree(root.right) + 1;  
138:            if(leftHeight > rightHeight ) return leftHeight;  
139:            else return rightHeight;  
140:       }  
141:       public static Item deepestNode(Node root, int level){  
142:            if(root == null) return null;  
143:            Item left = deepestNode(root.left, level+1);  
144:            Item right =deepestNode(root.right, level+1);  
145:            if(left == null && right == null){  
146:                 Item item = new Item();  
147:                 item.data = root.data;  
148:                 item.level = level;  
149:                 return item;  
150:            }else{  
151:                 if(left != null && right != null){  
152:                      if(left.level > right.level){  
153:                           return left;  
154:                      }else{  
155:                           return right;  
156:                      }  
157:                 }  
158:                 else if(left == null) return right;  
159:                 else return left;  
160:            }  
161:       }  
162:       public static boolean isIdentical(Node root1, Node root2){  
163:            if(root1 == null && root2 == null) return true;  
164:            if(root1 == null || root2 == null) return false;  
165:            if(root1.data == root2.data){  
166:                 boolean isLeft = isIdentical(root1.left, root2.left);  
167:                 boolean isRight = isIdentical(root1.right, root2.right);  
168:                 if(isLeft == true && isRight == true) return true;  
169:                 else return false;  
170:            }else return false;  
171:       }  
172:       public static Height diameterTree(Node root, Height height){  
173:            Height leftHeight = new Height();  
174:            Height rightHeight = new Height();  
175:            if(root == null){  
176:                 height.data = 0;  
177:                 return height;  
178:            }  
179:            Height ldiameter = diameterTree(root.left, leftHeight);  
180:            Height rdiameter = diameterTree(root.right, rightHeight);  
181:            height.data = max(leftHeight.data, rightHeight.data) + 1;  
182:            Height newHeight = new Height();  
183:            newHeight.data = max(leftHeight.data + rightHeight.data + 1, max(ldiameter.data, rdiameter.data));  
184:            return newHeight;  
185:       }  
186:       public static void allPathToLeaf(Node root, int[] list, int pathLength){  
187:            if(root == null) return;  
188:            list[pathLength] = root.data;  
189:            pathLength++;  
190:            if(root.left == null && root.right == null){  
191:                 for(int i = 0; i < pathLength; i++){  
192:                      System.out.print(list[i] + " -> ");  
193:                 }  
194:                 System.out.println();  
195:            }else{  
196:                 allPathToLeaf(root.left, list, pathLength);  
197:                 allPathToLeaf(root.right, list, pathLength);  
198:            }  
199:       }  
200:       public static boolean isPathWithSum(Node root, int sum){  
201:            if(sum == 0) return true;  
202:            if(sum != 0 && root == null) return false;  
203:            if(sum < 0) return false;  
204:            sum -= root.data;  
205:            boolean leftpart = isPathWithSum(root.left, sum);  
206:            boolean rightpart = isPathWithSum(root.right, sum);  
207:            if(leftpart || rightpart) return true;  
208:            else return false;  
209:       }  
210:       public static int sumAllElements(Node root){  
211:            if(root == null) return 0;  
212:            int leftSum = sumAllElements(root.left);  
213:            int rightSum = sumAllElements(root.right);  
214:            return leftSum + rightSum + root.data;  
215:       }  
216:       public static void getMirror(Node root){  
217:            if(root == null) return;  
218:            Node temp = root.left;  
219:            root.left = root.right;  
220:            root.right = temp;  
221:            getMirror(root.left);  
222:            getMirror(root.right);  
223:       }  
224:       public static Node constuctPreorderInorderTree(int[] preorder, int[] inorder, int inStart, int inEnd){  
225:            if(inStart > inEnd) return null;  
226:            Node node = new Node();  
227:            node.data = preorder[preOrderIndex++];  
228:            int index = search(inorder, node.data, inStart, inEnd);  
229:            if(index != -1){  
230:                 node.left = constuctPreorderInorderTree(preorder, inorder, inStart, index - 1);  
231:                 node.right = constuctPreorderInorderTree(preorder, inorder, index + 1, inEnd);  
232:            }  
233:            return node;  
234:       }  
235:       private static int search(int[] inorder, int key, int inStart, int inEnd) {  
236:            for(int i = inStart; i <= inEnd; i++) if(inorder[i] == key) return i;  
237:            return -1;  
238:       }  
239:       private static boolean printAncesstor(Node node, int key){  
240:            if(node == null) return false;  
241:            if(node.data == key){  
242:                 System.out.print(node.data+ " ");  
243:                 return true;  
244:            }  
245:            boolean isLeft = printAncesstor(node.left, key);  
246:            boolean isRight = printAncesstor(node.right, key);  
247:            if(isLeft || isRight){  
248:                 System.out.print(node.data + " ");  
249:                 return true;  
250:            }else return false;  
251:       }  
252:       public static void main(String[] args) {  
253:            Node root = createFullBST(4);  
254:            System.out.println("Preorder with recursion : ");   
255:            preorder(root);  
256:            System.out.println("\nPreorder without recursion : ");   
257:            preorderIteration(root);  
258:            System.out.println("\nPostorder with recursion : ");   
259:            postorder(root);  
260:            System.out.println("\nPostorder without recursion : ");   
261:            postorderIteration(root);  
262:            System.out.println("\nInorder with recursion : ");   
263:            inorder(root);  
264:            System.out.println("\nInorder without recursion : ");   
265:            inorderIteration(root);  
266:            System.out.println("\nLevel with recursion : ");   
267:            levelOrder(root);  
268:            System.out.println("\n\nMaximum in Tree is : "+ maximum(root));  
269:            if(searchElement(root, 5)){  
270:                 System.out.println("\nYes !! Present");  
271:            }else System.out.println("\nNo !! Not Present");  
272:            System.out.println("\nSize of Tree : "+sizeOfTree(root));  
273:            System.out.println("\nHeight of Tree : "+heightTree(root));  
274:            Node node1 = new Node();  
275:            node1.data = 1;  
276:            node1.left = new Node();  
277:            node1.left.data = 2;  
278:            node1.right = new Node();  
279:            node1.right.data = 3;  
280:            node1.left.left = new Node();  
281:            node1.left.left.data = 4;  
282:            node1.right.right = new Node();  
283:            node1.right.right.data =5;  
284:            node1.left.left.left = new Node();  
285:            node1.left.left.left.data = 6;  
286:            Node node2 = new Node();  
287:            node2.data = 1;  
288:            node2.left = new Node();  
289:            node2.left.data = 2;  
290:            node2.right = new Node();  
291:            node2.right.data = 3;  
292:            node2.left.left = new Node();  
293:            node2.left.left.data = 4;  
294:            node2.right.right = new Node();  
295:            node2.right.right.data =5;  
296:            node2.left.left.left = new Node();  
297:            node2.left.left.left.data = 9;  
298:            node2.left.right = new Node();  
299:            node2.left.right.data = 6;  
300:            node2.left.right.right = new Node();  
301:            node2.left.right.right.data = 7;  
302:            node2.left.right.right.right = new Node();  
303:            node2.left.right.right.right.data = 8;  
304:            Item deepest = deepestNode(node1, 0);  
305:            System.out.println("\nDeepest node of Tree : "+deepest.data);  
306:            System.out.println("\nIs tow Trees Identcal : "+ isIdentical(node1, node2));  
307:            Height height = new Height();  
308:            height.data = 0;  
309:            System.out.println("\nDiameter of tree : "+ diameterTree(node2, height).data);  
310:            int[] list = new int[1000];  
311:            allPathToLeaf(node2, list, 0);  
312:            System.out.println("\nDoes it have path : "+ isPathWithSum(node2, 10));  
313:            System.out.println("\nSum all elements of tree : "+sumAllElements(root));  
314:            System.out.println("\nBefore Mirror :");  
315:            preorder(node2);  
316:            getMirror(node2);  
317:            System.out.println("\nAfter Mirror :");  
318:            preorder(node2);  
319:            System.out.println("\n=================================================================");  
320:            int[] inorder = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };  
321:            int[] preorder = {7, 3, 1, 0, 2, 5, 4, 6, 11, 9, 8, 10, 13, 12, 14};  
322:            Node constructedTree = constuctPreorderInorderTree(preorder, inorder, 0, inorder.length - 1);  
323:            postorder(constructedTree);  
324:            System.out.println("\n=================================================================");  
325:            System.out.println("\nAncesstors : "+ printAncesstor(node2, 8));  
326:       }  
327:  }  

R Tutorial : Handling XML in R

Working with XML Data in R

A common task for programmers these days is writing code to analyze data from various sources and output information for use by non-coders or business executives. Although you can use any language for this type of analysis, I've found that R simplifies working with almost any modern data type, including XML, a popular choice for storing large amounts of complex data. In this article, I'll step through the process of examining XML data in an R program, so you can see how easy R makes working with XML files.

I first began analyzing XML data while I was working within the public health department at Cornell's Medical School. We'll use the same data source, PubMed, for this article. For this example, I pulled data about papers authored by Dr. Madhu Mazumdar in 2012 from PubMed's API, which is called Entrez.

NOTE

To view or use the code examples in this article, download the code file. The full code referenced in this article is included for the purposes of helping readers follow along in R. In thepubmed_sample.xml file, the data entries begin with the <PubmedArticle> tag and end with</PubmedArticle>.

When dealing with XML data, the main package we'll rely on is XML. However, for our analysis in this example, we'll also need the plyr, ggplot2, and gridExtra packages:

• plyr to turn the XML into a dataframe
• ggplot to create aesthetically pleasing graphs
• gridExtra to put multiple graphs on one canvas

Our first step is to get these packages from the nearest Comprehensive R Archive Network (CRAN) mirror and load them into our current R session:

install.packages("XML")
install.packages("plyr")
install.packages("ggplot2")
install.packages("gridExtra")

require("XML")
require("plyr")
require("ggplot2")
require("gridExtra")

Next we need to set our working directory and parse the XML file as a matter of practice, so we're sure that R can access the data within the file. This is basically reading the file into R. Then, just to confirm that R knows our file is in XML, we check the class. Indeed, R is aware that it's XML.

setwd("C:/Users/Tobi/Documents/R/InformIT") #you will need to change the filepath on  your machine
xmlfile=xmlParse("pubmed_sample.xml")
class(xmlfile) #"XMLInternalDocument" "XMLAbstractDocument"

Now we can begin to explore our XML. Perhaps we want to confirm that our HTTP query on Entrez pulled the correct results, just as when we query PubMed's website. We start by looking at the contents of the first node or root, PubmedArticleSet. We can also find out how many child nodes the root has and their names. This process corresponds to checking how many entries are in the XML file. The root's child nodes are all named PubmedArticle.

xmltop = xmlRoot(xmlfile) #gives content of root
class(xmltop)#"XMLInternalElementNode" "XMLInternalNode" "XMLAbstractNode"
xmlName(xmltop) #give name of node, PubmedArticleSet
xmlSize(xmltop) #how many children in node, 19
xmlName(xmltop[[1]]) #name of root's children

To see the first two entries, we can do the following.

# have a look at the content of the first child entry
xmltop[[1]]
# have a look at the content of the 2nd child entry
xmltop[[2]]

Our exploration continues by looking at subnodes of the root. As with the root node, we can list the name and size of the subnodes as well as their attributes. In this case, the subnodes areMedlineCitation and PubmedData.

#Root Node's children
xmlSize(xmltop[[1]]) #number of nodes in each child
xmlSApply(xmltop[[1]], xmlName) #name(s)
xmlSApply(xmltop[[1]], xmlAttrs) #attribute(s)
xmlSApply(xmltop[[1]], xmlSize) #size

We can also separate each of the 19 entries by these subnodes. Here we do so for the first and second entries:

#take a look at the MedlineCitation subnode of 1st child
xmltop[[1]][[1]]
#take a look at the PubmedData subnode of 1st child
xmltop[[1]][[2]]

#subnodes of 2nd child
xmltop[[2]][[1]]
xmltop[[2]][[2]]

The separation of entries is really just us, indexing into the tree structure of the XML. We can continue to do this until we exhaust a path—or, in XML terminology, reach the end of the branch. We can do this via the numbers of the child nodes or their actual names:

#we can keep going till we reach the end of a branch
xmltop[[1]][[1]][[5]][[2]] #title of first article
xmltop[['PubmedArticle']][['MedlineCitation']][['Article']][['ArticleTitle']] #same command, but more readable

Finally, we can transform the XML into a more familiar structure—a dataframe. Our command completes with errors due to non-uniform formatting of data and nodes. So we must check that all the data from the XML is properly inputted into our dataframe. Indeed, there are duplicate rows, due to the creation of separate rows for tag attributes. For instance, the ELocationID node has two attributes,ValidYN and EIDType. Take the time to note how the duplicates arise from this separation.

#Turning XML into a dataframe
Madhu2012=ldply(xmlToList("pubmed_sample.xml"), data.frame) #completes with errors: "row names were found from a short variable and have been discarded"
View(Madhu2012) #for easy checking that the data is properly formatted
Madhu2012.Clean=Madhu2012[Madhu2012[25]=='Y',] #gets rid of duplicated rows

Taking a look at the titles of the column headings after calling the View() function on the dataframe, it's clear that they're the paths from the root through various child branches until the terminus or our data of interest is reached. Try to go through the XML document to see if you can follow the path to a specific piece of data in a column.

Now that our XML data is a dataframe, we can do some analysis. For instance, we might be interested in which authors contributed most to the articles of which Dr. Mazumdar was an author in 2012. We can make histograms for the first through eleventh authors, with the understanding that first authors contribute the most, and eleventh authors the least. The code below labels the relevant data for easy tracking and removes blank entries, which we don't want appearing in our histogram.

#looking at which authors played most active role
FirstAuthor=Madhu2012.Clean$MedlineCitation.Article.AuthorList.Author.LastName
SecondAuthor=Madhu2012.Clean$MedlineCitation.Article.AuthorList.Author.LastName.1
ThirdAuthor=Madhu2012.Clean$MedlineCitation.Article.AuthorList.Author.LastName.2

#removing NAs
Madhu2012.Na.Rm4=Madhu2012.Clean[!is.na(Madhu2012.Clean$MedlineCitation.Article.AuthorList.Author.LastName.3),]
FourthAuthor=Madhu2012.Na.Rm4$MedlineCitation.Article.AuthorList.Author.LastName.3
Madhu2012.Na.Rm5=Madhu2012.Clean[!is.na(Madhu2012.Clean$MedlineCitation.Article.AuthorList.Author.LastName.4),]
FifthAuthor=Madhu2012.Na.Rm5$MedlineCitation.Article.AuthorList.Author.LastName.4
Madhu2012.Na.Rm6=Madhu2012.Clean[!is.na(Madhu2012.Clean$MedlineCitation.Article.AuthorList.Author.LastName.5),]
SixthAuthor=Madhu2012.Na.Rm6$MedlineCitation.Article.AuthorList.Author.LastName.5
Madhu2012.Na.Rm7=Madhu2012.Clean[!is.na(Madhu2012.Clean$MedlineCitation.Article.AuthorList.Author.LastName.6),]
SeventhAuthor=Madhu2012.Na.Rm7$MedlineCitation.Article.AuthorList.Author.LastName.6
Madhu2012.Na.Rm8=Madhu2012.Clean[!is.na(Madhu2012.Clean$MedlineCitation.Article.AuthorList.Author.LastName.7),]
EighthAuthor=Madhu2012.Na.Rm8$MedlineCitation.Article.AuthorList.Author.LastName.7
Madhu2012.Na.Rm9=Madhu2012.Clean[!is.na(Madhu2012.Clean$MedlineCitation.Article.AuthorList.Author.LastName.8),]
NinthAuthor=Madhu2012.Na.Rm9$MedlineCitation.Article.AuthorList.Author.LastName.8
Madhu2012.Na.Rm10=Madhu2012.Clean[!is.na(Madhu2012.Clean$MedlineCitation.Article.AuthorList.Author.LastName.9),]
TenthAuthor=Madhu2012.Na.Rm10$MedlineCitation.Article.AuthorList.Author.LastName.9
Madhu2012.Na.Rm11=Madhu2012.Clean[!is.na(Madhu2012.Clean$MedlineCitation.Article.AuthorList.Author.LastName.10),]
EleventhAuthor=Madhu2012.Na.Rm11$MedlineCitation.Article.AuthorList.Author.LastName.10

Next, we create histograms detailing counts of each author's last name per author type. Our analysis then aggregates the 11 diagrams onto three pages in a single PDF file for easy comparison. The PDF file is included in the code file for this article.

#write all the graphs to pdf on 3 canvases
a=ggplot(Madhu2012.Clean, aes(x=FirstAuthor)) + geom_histogram(binwidth=.5, colour="pink", fill="purple")+coord_flip()
b=ggplot(Madhu2012.Clean, aes(x=SecondAuthor)) + geom_histogram(binwidth=.5, colour="pink", fill="purple")+coord_flip()
c=ggplot(Madhu2012.Clean, aes(x=ThirdAuthor)) + geom_histogram(binwidth=.5, colour="pink", fill="purple")+coord_flip()
d=ggplot(Madhu2012.Na.Rm4, aes(x=FourthAuthor)) + geom_histogram(binwidth=.5, colour="pink", fill="purple")+coord_flip()
e=ggplot(Madhu2012.Na.Rm5, aes(x=FifthAuthor)) + geom_histogram(binwidth=.5, colour="pink", fill="purple")+coord_flip()
f=ggplot(Madhu2012.Na.Rm6, aes(x=SixthAuthor)) + geom_histogram(binwidth=.5, colour="pink", fill="purple")+coord_flip()
g=ggplot(Madhu2012.Na.Rm7, aes(x=SeventhAuthor)) + geom_histogram(binwidth=.5, colour="pink", fill="purple")+coord_flip()
h=ggplot(Madhu2012.Na.Rm8, aes(x=EighthAuthor)) + geom_histogram(binwidth=.5, colour="pink", fill="purple")+coord_flip()
i=ggplot(Madhu2012.Na.Rm9, aes(x=NinthAuthor)) + geom_histogram(binwidth=.5, colour="pink", fill="purple")+coord_flip()
j=ggplot(Madhu2012.Na.Rm10, aes(x=TenthAuthor)) + geom_histogram(binwidth=.5, colour="pink", fill="purple")+coord_flip()
k=ggplot(Madhu2012.Na.Rm11, aes(x=EleventhAuthor)) + geom_histogram(binwidth=.5, colour="pink", fill="purple")+coord_flip()

pdf("AuthorHistogram.pdf")
grid.arrange(a,b,c,d)
grid.arrange(e,f,g,h)
grid.arrange(i,j,k)
dev.off()

Page 1 of the results is shown in Figure 1. (The complete PDF is included in the code file for download.) However, when we look at the other pages, we see that of all the 19 articles published under Dr. Mazumdar's name in 2012 (whether in print or online), she was most often listed fourth, fifth, or sixth in the authors of the paper. This means that she was only moderately active in terms of writing the papers. Instead, we see that Dr. Memtsoudis was the primary writer of about 1/3 of the papers, with Dr. Ma as next most active. We should also note that most of the papers have just six or fewer authors. Hence, sometimes Dr. Mazumdar was the last author and thus contributed in a minor way.

Figure 1 Histogram for the first four authors used in analysis of level of contribution.

Finally, we can write the dataframe to a .csv or .txt file and import it into another program such as SQL, Python, or SAS. Or we might want to share our data with a collaborator. The output files are included in the code file for this article.

#exporting data
write.table(Madhu2012.Clean, "Madhu2012.txt", sep="\t", row.names=FALSE)
write.csv(Madhu2012.Clean, "Madhu2012.csv", row.names=FALSE)

That was interesting to learn. No big deal, right?

As you can imagine, R allows us to perform many other analyses on our XML data with ease. For example, we might be interested in finding out which journals published 2012 papers by Dr. Mazumdar, or which grants supported her work.

As we've seen in this example, with R, there's no need to shy away from unfamiliar data types such as XML. The world is your oyster!

Linear Algebra Review : Machine Learning

Linear Algebra Review

Khan Academy has excellent Linear Algebra Tutorials.

This online Linear Algebra text is also an excellent resource, particularly for a proof of the normal equation.

Matrices and Vectors

Matrices are 2-dimensional arrays:

A=⎡⎣⎢⎢⎢adgjbehkcfil⎤⎦⎥⎥⎥

The above matrix has four rows and three columns, so it is a 4 x 3 matrix.

A vector is a matrix with one column and many rows:

⎡⎣⎢⎢wxyz⎤⎦⎥⎥

So vectors are a subset of matrices. The above vector is a 4 x 1 matrix.

Notation and terms:

* Aij refers to the element in the ith row and jth column of matrix A.

* A vector with 'n' rows is referred to as an 'n'-dimensional vector

* vi refers to the element in the ith row of the vector.

* In general, all our vectors and matrices will be 1-indexed.

* Matrices are usually denoted by uppercase names while vectors are lowercase.

* "Scalar" means that an object is a single value, not a vector or matrix.

* R refers to the set of scalar real numbers

* Rn refers to the set of n-dimensional vectors of real numbers

Addition and Scalar Multiplication

Addition and subtraction are element-wise, so you simply add or subtract each corresponding element:

[acbd]+[wyxz]=[a+wc+yb+xd+z]

To add or subtract two matrices, their dimensions must be the same.

In scalar multiplication, we simply multiply every element by the scalar value:

[acbd]∗x=[a∗xc∗xb∗xd∗x]

Matrix-Vector Multiplication

We map the column of the vector onto each row of the matrix, multiplying each element and summing the result.

⎡⎣acebdf⎤⎦∗[xy]=⎡⎣⎢a∗x+b∗yc∗x+d∗ye∗x+f∗y⎤⎦⎥

The result is a vector. The vector must be the second term of the multiplication. The number of rows of the vector must equal the number of columns of the matrix.

An n x m matrix multiplied by an m x 1 vector results in an n x 1 vector.

Matrix-Matrix Multiplication

We multiply two matrices by breaking it into several vector multiplications and concatenating the result

⎡⎣acebdf⎤⎦∗[wyxz]=⎡⎣⎢a∗w+b∗yc∗w+d∗ye∗w+f∗ya∗x+b∗zc∗x+d∗ze∗x+f∗z⎤⎦⎥

An m x n matrix multiplied by an n x o matrix results in an m x o matrix. In the above example, a 3 x 2 matrix times a 2 x 2 matrix resulted in a 3 x 2 matrix.

To multiply two matrices, the number of columns of the first matrix must equal the number of rows of the second matrix.

Matrix Multiplication Properties

* Not commutative. A∗B≠B∗A

* Associative. (A∗B)∗C=A∗(B∗C)

The "identity matrix", when multiplied by any matrix of the same dimensions, results in the original matrix. It's just like multiplying numbers by 1. The identity matrix simply has 1's on the diagonal and 0's elsewhere.

When multiplying the identity matrix after some matrix, the square identity matrix should match the other matrix'scolumns. When multiplying the identity matrix before some other matrix, the square identity matrix should match the other matrix's rows.

Inverse and Transpose

The inverse of a matrix A is denoted A−1. Multiplying by the inverse results in the identity matrix.

A non square matrix does not have an inverse matrix. We can compute inverses of matrices in octave with the pinv(A) function [1].

The transposition of a matrix is like rotating the matrix once clockwise and then reversing it:

A=⎡⎣acebdf⎤⎦

AT=[abcdef]

In other words:

Aij=ATji