Now, I want to focus on three main kinds of trees that try to accommodate some special kind of information, and they're very, very useful kind of trees. The dendogram, decision trees, and flow charts. Let me start with dendrograms. So what is a dendrogram? A dendogram is this specific kind of representation that you see here, and first of all it's a binary tree. What does it mean to be a binary tree? Well, it simply means that each node can have maximum two children, it can't be more than two. Another property is that they are typically used to represent the result of a specific data mining algorithm that is called Hierarchical Clustering. So, let me first describe in a few words, if possible, what is hierarchical clustering. The basic idea of hierarchical clustering is, it's an automated data analysis procedure that works as follows. If you have a collection of objects and there is a distance function or a similarity function defined between these objects, then this algorithm basically connects these objects together and describes them, groups them into hierarchical structures. Don't worry that's going to be much, much clearer in a moment. Let me show you an animation of how this works. So, let's say that you have a number of data points, the one that you see in the set on the left and that the distance between them is the similarity function that we are using here. When I say distance, I mean the actual physical distance that you see on the screen, it's the Euclidean distance between these points. Now, at any given moment, the algorithm looks for the closest objects to group together. So, if you look at these a cloud of points, we can identify the first set of points are closest are these ones that are marked in the visualization. So what the algorithm does is to group them together and create a group. Now, not only the algorithm groups them together but it also represents with the height of the lines, how much distance there is between them, that's very important because it's a relevant characteristic of a dendrogram. So, the next the pair is the one that I highlighted here. So, these two points need to be grouped together. Again, their distance is mapped to the height of the lines that connect them, and as you can see, since the distance has to be a little higher than the previous pair, in the dendrogram we have the lines are a little taller than the pair of lines that you see in the previous pair. Now, we can keep grouping objects together and every time they're grouped together, there is a new pair of branches that connects either points between them, or points with groups, or groups with groups. So, this keeps on going until the last step, that is basically connecting the two last set of groups into one root node. So, this is roughly speaking, the procedure that is used in hierarchical clustering to build hierarchical structure on top of a set of points and in particular, how to build a dendrogram. A very important characteristic of the dendrogram is not just the structure but the fact that the height of the lines is actually meaningful. It does represent the distance between the objects that are below the nodes. So that's very, very important. As I said previously, this structure is very common in biology. So, here is an example of a phylogenetic tree that has been calculated looking at DNA data from a group of organisms, and in particular, using genetic distance as the distance function that characterizes these nodes. What is really interesting about this technique is that it can be used virtually with any dataset where it's possible to define a distance or similarity function between the data points, and that's why it's so versatile and so useful. So, here is an example with a completely different kind of dataset, a much simpler one to observe. Here is the dataset of cars. The cars are the rows that you see in this table, and the columns represent the variables that describe these cars. Now, as you can see, there is a dendogram that has been built to group together and organize these elements in a way that similar elements are grouped together, and that's by the way the reason why you see these very distinct patterns into these matrix visualization. Let me give you one last example. Here is another visualization that groups together times series of companies in the stock market. The reason why I'm showing you that is because I want to give you a better sense of the fact, as I said, every time can define a similarity function between objects, you can build these complex kind of hierarchy. Here, the objects are complex objects. These are all timelines and it's possible to describe, to define a distance function between timelines. Since this has been done by the creator of this visualization, it is also possible to create a dendrogram that describes the actual structure.
