Auto-generating a class hierarchy/inheritance tree from a data set of objects with properties

Question

What is an algorithm that will take as an input a flat list of objects with a varying degree of overlapping properties:

thing1 (instance of "Mammal", but we don't know this now)
  -eatsFood
  -reproduces
  -hasMilk

thing2 (instance of "Emu", but we don't know this now)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -doesNotFly

thing3 (instance of "Eagle", but we don't know this now)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -flies

thing4 (another instance of "Eagle", we just know it has the same "shape" as thing 3)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -flies

thing5 (instance of "BaldEagle", but we don't know this now)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -flies
  -hasWhiteHead

And return as an output a hierarchical class structure/inheritance tree/taxonomy like the following?

Notes:

1. The algorithm is able to identify a hierarchical structure in the objects' properties, including abstract classes that are not explicitly present as objects in our data set. For example, there are no instances of "Bird" or "Animal" in our object data set, however the algorithm is able to identify that "Eagle" and "Emu" both inherit from a common parent class (the abstract class "Bird") and that both the "Bird" and "Mammal" classes inherit from a common parent class (the abstract class "Animal").
2. The algorithm doesn't know or care about the class names ("Animal", "Mammal", "Bird", "Emu", "Eagle", "Bald Eagle"). We generate those ourselves based on the properties of the classes the algorithm has generated. I just put them here to aid the example, but they're not part of the algorithm.
3. The list of an object's properties in the data set will not necessarily be "in order" like they are here. Don't assume any order to the properties in the raw data.

Answer 1

It looks like your problem can be solved by transitive reduction followed by some post-processing.

Build a directed graph, with one vertex per "object shape". Draw an edge $u \to v$ if $u$ contains all of the fields of $v$ (possibly plus some more). This should form a dag. Now compute the transitive reduction of this dag. The result should be a tree (or forest of trees).

This almost gives you the desired solution. The one thing it doesn't do is invent new abstract base classes that weren't already present in the input. So, we can do some post-processing to create them. First, if the result has more than one tree, we'll create a new root (an abstract base class) that is a parent of all of those trees. The result is a (directed) tree.

Examine each node that has more than two children. This is the only place where we need to create new abstract base classes. Let $S$ denote the set of children. Now you have some choices about how you want to form a hierarchy based for $S$; there are multiple possibilities that are all consistent with the input data, and the question doesn't specify any criteria for choosing among them. So, I'll have you let you decide on how you want to select among them.

---

What's the running time? Constructing the graph and computing the transitive reduction can be done in $O(n^3)$ time, where $n$ is the number of different object shapes present in the input. (In fact, given the structure of the input, in this particular case it can actually be done in $O(n^2)$ time, but maybe that isn't important, since I suspect in practice $n$ might be fairly small.) The post-processing can also be done in $O(n^3)$ time (probably less if you care). So the overall running time is at most $O(n^3)$.

Of course, we can de-duplicate the shapes in the input before doing any processing: there is no need to keep more than one object of any particular shape. So, the running time depends only on $n$, the number of distinct shapes in the input, not on the number of objects in the input. It's easy to do the de-duplication in linear time using a hash table.