A Culinary Computational Creativity System - Computational Creativity Research: Towards Creative Machines - page 331

Fig. 16.8 An ontology of preparation methods
same dish and the same ingredient or ingredient type from the knowledge database.
In case no subgraph can be found for the ingredient or ingredient type, the search
can be extended to similar ingredient types. In the example of a salmon quiche, if the
repository does not contain any existing recipe for seafood quiche, we assume that
fish can be handled as meat, and consider the meat subgraphs of the quiche recipe
graphs.
The subgraphs are simplified following several preset rules. Certain tasks bring
no essential information to the high-level preparation process (“preheat”, “transfer”),
and are eliminated. Others become redundant once the subgraph has been pulled out
of the whole graph (such as two consecutive “add” or “mix” verbs), and are merged.
The resulting subgraphs for a given ingredient are then clustered, and each cluster
is assigned a suitability score. Clustering uses a weighted graph edit distance [ 29 ]
and a bisecting k -means algorithm, where k can be chosen so that the largest distance
in any cluster remains below a certain threshold. As a result, each cluster contains
subgraphs that all handle an ingredient roughly the same way from start to finish. The
score of each cluster is based on the number of subgraphs in the cluster, weighted by
the relevance of each subgraph to the recipe ingredient: subgraphs that start with the
same ingredient receive a higher weight than the ones that just deal with the same
ingredient type, which in turn weigh more than the subgraphs that use a substituted
ingredient type. A higher score indicates a cluster that describes a very common
action sequence, and/or closely matches the ingredient used in the new recipe.
With the subgraph clusters now sorted by decreasing suitability score, we select
the cluster with the highest rank as the preferred method for handling the ingredient.
Clusters with lower scores will be used as backups if a merged graph cannot be
obtained otherwise. It is important to note that since the suitability score calculation is