Taxonomy pt 3

In my last adventure in taxonomies I had hopes of using Neo4J and Neo4JClient to implement a taxonomy. However, I could never implement the Cypher-queries that worked in Neo4J through the .Net-library Neo4JClient. I got a "400 bad request"-error, struggled, tore my imaginary hair, gave up and changed the route to QuickGraph.

QuickGraph is a graph engine and not a database. It is not a big issue when it comes to a small taxonomy, but would pose problems for huge taxonomies since it holds all data in memory. For me it was a relief, since QuickGraph is something I know and feel comfortable with.

Installation of QuickGraph is straightforward. Just download, build and set a reference.

As a reminder a taxonomy is something where the meaning of a certain term is valid over a specific time. In this case the time is in which revision the term was defined. Like this:

I am using a directed graph where each revision of the taxonomy is descendant of the last revision.

As a practice set I used the gulls in the last blog (check it out).

Step 1.  Create an object that will hold each gull.


    public class Taxon 
    {
        public Guid TaxonId { get; set; }
        public string ScientificName { get; set; }
        public string CommonName { get; set; }
        public int Revision { get; set; }
    }


Since each scientific name can be used in several revisions I use a guid to know which unique taxon it is.

Step 2. Instantiate a directed graph.

BidirectionalGraph<Taxon, IEdge<Taxon>> graph = new BidirectionalGraph<Taxon, IEdge<Taxon>>();

This basically means that the nodes will be of the type Taxon and that the edges will connect two Taxon objects. Bidirectional means that each nod will no who it is descendent from and who derives from it.

Step 3. Implement the InsertTaxon function.


        public void InsertTaxon(Taxon taxon, List<Taxon> ancestors, BidirectionalGraph<Taxon, IEdge<Taxon>> graph)
        {
            graph.AddVertex(taxon);
            foreach (Taxon item in ancestors)
            {
                TaggedEdge<Taxon, double> outEdge = new TaggedEdge<Taxon, double>(taxon, item, 1);
                graph.AddEdge(outEdge);

            }
        }

We're basically inserting the taxon for a new revision of a taxonomy and connects it to all taxons it derives from. By using a TaggedEdge we have a weighted graph. I just default it to one though.

Step 4. Implement the FindTaxon method.


        public IEnumerable<Taxon> FindTaxon(String scientificName, int fromRevision, int toRevision)
        {
            //Find the taxon with the same scientific name from the chosen revision
            Taxon searchTaxon = graph.Vertices.Where(s => s.ScientificName == scientificName && s.Revision == fromRevision).First();
            //use that taxon to find the possible taxons at the to revision
            List<Taxon> results = new List<Taxon>();
            results.AddRange(GetAllDescendantsAtTime(searchTaxon, toRevision));
            return results.Distinct();
        }


        private List<Taxon> GetAllDescendantsAtTime(Taxon searchTaxon, int toRevision)
        {
            List<Taxon> results = new List<Taxon>();
            foreach (Taxon inNode in graph.InEdges(searchTaxon).Where(s => s.Source.Revision <= toRevision && s.Source.Revision > searchTaxon.Revision).Select(n => n.Source))
            {
                if (inNode.Revision != toRevision)
                    results.AddRange(GetAllDescendantsAtTime(inNode, toRevision));
                else
                    results.Add(inNode);
            }
            return results;
        }

So what we basically do is to find what say a Herring Gull was at revision 1 of the taxonomy and then see what it might be at revision 3.
We accomplish this by walking the graph recursively until we find all revision 3 species that are  based on the Herring Gull. The answer would be European Herring Gull, Yellow Legged Gull, Vega Gull, Caspian Gull and American Herring Gull. 

To note: This approach would need a specific graph for each taxonomy and, yeah, there are probably some algorithms that solves the problem faster than mine.

For me: This is perfect! Now I will just make a complete interface to it and use it in all my birding projects!

See you!

Taxonomy pt 2

In my last entry I discussed the special constraints and problems that occur when you need to implement a classification system that changes over time.

This time we will take the discussion a little bit deeper and look at the basic API of a taxonomy component.

A taxonomy is a graph where each taxon has a limited life span and is traceable through previous revisions of the taxonomy.
If I would use birds as an example (and I really like to do that). The Armenian gull, Larus armenicus, is considered a specie by The Association of European Rarities Committees.
It was first considered a sub specie of Herring Gull (L. argentatus), but after that specie was split into European Herring Gull, Larus argentatus, American Herring Gull, Larus smithsonianus, Caspian Gull, Larus cachinnans, Yellow-legged Gull, Larus michahellis, Vega Gull, Larus vegae and the Armenian Gull, Larus armenicus.

To complicate stuff further another taxonomy, namely birdlife.org, doesn't consider it to be a valid specie but lumps it together with Yellow-legged Gull (Larus michahellis).

So... depending on when you see this gull and which taxonomy you use it can be either a Herring gull, an Armenian gull or a Yellow-legged gull and then you're only checking two taxonomies and believe me, there are more out there...

What does this tell us?

1. A taxon has a time span.
2. A taxon is derived from one or more taxons.
3. A taxon is dependent of its taxonomy and several parallel taxonomies may exist.
4. To find a taxon from its key (the latin name in this case), you will need to know the key, the time and the taxonomy.

To find out that the Armenian gull nowadays is considered a sub specie of Yellow-legged gull in Birdlife, I would have to backtrack the taxonomy graph to find the Armenian gull and then follow it to present time to see that it has been included in Yellow-legged gull. 

Even though this example is about birds, the same will apply more or less to any other type of taxonomy.

In pseudo-code the core functions would be:

• Taxon InsertTaxon(Taxon taxon, List<Taxon> ancestors, DateTime validFrom) to insert a taxon based on zero or more ancestors.
• Taxon FindTaxon(String key, DateTime when, Taxonomy string) to find a taxon given a key, time and a certain taxonomy.

The signature can of course differ, but the basic design will be the same.

Next time we will take a look on how we can implement this.

Til then... Bye, bye!

The deadly flat foot

A long time ago I made a system for health statistics and I was demoing it for the stakeholders who of course knew a lot about epidemiology. One of them asked if I could use my system to find out the most common cause of death in Sweden over a time period. I was eager to show off my system and generated the query.

The result was flat foot.
I didn't feel that sure about my system after that.

So what had happened?

I had tons and tons of statistical material with gender, ages and cause of death over several years. The cause of death was marked with a diagnostic number, a so called ICD (International Classification of Disease). This ICD-code was versioned so you had a ICD-6, ICD-7, ICD-8 and so on.

Now, what I didn't know was that Sweden made a shift from ICD-7 to ICD-8 at a certain point of time. My stakeholders (stake holders?) knew this of course and set the trap with a smile.

In ICD-7 the code 746 stands for flat foot but in ICD-8 the code 746 stands for congenital anomalies of heart. So when I summarized the statistics using ICD-7 terminology for ICD-8 data... well, I guess you get the idea.

ICD is an interesting example of taxonomy, the science of classification. Other types of classifications can be the futile attempt to classify the internet into a hierarchy of subjects by yahoo, the classification of plants by Linnae or the subject classification at a library (the strange combinations of letter like Pcj:k that somehow describes a books subject).

Classifications is hierarchic by nature, a subdivision from all into smaller and smaller parts. An approach that is easy but has drawbacks when something fits equally well in two or more classes. (consider a book that is both about History and Math for example)

Classifications also change over time as we saw with the flat foot case. In ICD-8 flat foot had moved from 746 to 736. A change that is vital to know about in order to get correct statistics.

So each version of classification connects to the previous version. In ICD-7 the flatfoot at code 746 points to the 736 flat foot in ICD-8.

Other diagnoses had one code in ICD-7 and got several codes in ICD-8.

Ischaemic Heart Disease for example was 420 in ICD-7 but was covered by the codes 410-414 in ICD-8.

A fork.

This of course made it impossible to know which ICD-8 diagnose a person with the ICD-7 diagnose of  Ischaemic Heart Disease had.
All that could be said was that it was one of the diagnoses between 410 and 414 and maybe, maybe if we knew the relative distribution between the diagnoses 410-414 we could guess that it was 40% chance of 410, 15% chance of 411 and so on stumbling through fuzzy logic.

The opposite could also happen of course, that two classes in the old version is represented by a single class in the new. A join.

Similarly some classes may not have a representation in the new version and totally new classes could appear. You will not find HIV in the ICD-7 because originates from 1955 when the disease was unknown.

To complicate matters even more there can be several different classifications that each has their own versioning with forks and joins, but who's classes also connect to classes in other taxonomies.

With birds you have the Sibley-Ahlquist classification that sees the species differently from the traditional Clemens classification.

The national symbol of New Zeeland, the kiwi bird, is considered to be part of the kiwi order Apterygiformes in Clemens but in the Sibley-Ahlquist it is seen as a part of the ostrich order Struthioniformes.

Still, a kiwi is a kiwi and there is a very strong relationship between the kiwi class in the Clemens classification and its Sibley-Ahlquist sibling.

So how do we fit this thing called classifications into SQL Server?

We have seen that a classification consists of a hierarchy of classes that are connected to other versions of the classification and also to other classes in totally different classifications.

We do have pretty good possibilities to implement hierarchies in SQL Server, but a hierarchy only covers one version of a classification. If we want to be able to track changes and translate between different versions of a taxonomy, a hierarchy is not enough because it is not a hierarchy. It is a graph. And maybe it is a directed acyclic graph and maybe, maybe even a weighted variant.

You can put graphs in a relational database, but it is painful.

Better to use a dedicated graph database such as Neo4J or maybe use a mix of graph engine and a relational database.

More on this next time.