See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/235918443

Intelligent menu planning: recommending set of recipes by ingredients

Conference Paper · November 2012

DOI: 10.1145/2390776.2390778

CITATIONS READS
28 5,944

4 authors:

Fang-Fei Kuo Cheng-Te Li

Yahoo! Inc, Sunnyvale, United States National Taiwan University
13 PUBLICATIONS   387 CITATIONS    66 PUBLICATIONS   611 CITATIONS   

SEE PROFILE SEE PROFILE

Man-Kwan Shan Suh-Yin Lee

National Chengchi University National Chiao Tung University
83 PUBLICATIONS   1,293 CITATIONS    143 PUBLICATIONS   2,430 CITATIONS   

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Man-Kwan Shan on 06 June 2014.

The user has requested enhancement of the downloaded file.

 Intelligent Menu Planning:
Recommending Set of Recipes by Ingredients
Fang-Fei Kuo Cheng-Te Li
Department of Computer Science Graduate Institute of Networking and Multimedia
National Chiao-Tung University, Hsinchu, Taiwan National Taiwan University, Taipei, Taiwan
ffkuo@cs.nctu.edu.tw d98944005@csie.ntu.edu.tw
Man-Kwan Shan Suh-Yin Lee
Department of Computer Science Department of Computer Science
National Chengchi University, Taipei, Taiwan National Chiao-Tung University, Hsinchu, Taiwan
mkshan@nccu.edu.tw sylee@cs.nctu.edu.tw

ABSTRACT One may come up with an intuitive manner for menu planning: by
With the growth of recipe sharing services, online cooking recipes searching the menu database and exploiting some ingredient
associated with ingredients and cooking procedures are available. Many matching method, we can easily find those menus possessing
recipe sharing sites have devoted to the development of recipe similar ingredients as the user-specified ones. However, such
recommendation mechanism. However, there is a need for users to plan method suffers from two points. First, direct ingredient matching
menu of meals by ingredients. While most research on food related will neglect how well the recipes of a menu accompany with each
research has been on recipe recommendation and retrieval, little research other. While the co-occurrence of recipes in collection of menus
has been done on menu planning. In this paper, we investigate an
provides information about which recipes fit each other, it will be
intelligent menu planning mechanism which recommending sets of recipes
by user-specified ingredients. Those recipes which are well-accompanied useful to take the collective knowledge about menu plans into
and contain the query ingredients are returned. We propose a graph-based consideration. Second, the user-specified ingredients might not be
algorithm for menu planning. The proposed approach constructs a recipe covered by any menus in the database. Instead, a satisfactory
graph to capture the co-occurrence relationships between recipes from menu for such kind of query will be a novel one, which never
collection of menus. A menu is generated by approximate Steiner Tree exactly appears in existing menus. And thus we need to compose
Algorithm on the constructed recipe graph. Evaluation of menu collections a new menu, composed by partial recipes from existing menus.
from Food.com shows that the proposed approach achieves encouraging
results. While most research on food related research has been on recipe
recommendation and retrieval, to the best of our knowledge, little
Categories and Subject Descriptors research has been done on menu planning. In this paper, we
H.2.8 [Database Management]: Database Applications; H 3.3. investigate an intelligent menu planning mechanism which
Information Storage and Retrieval]: Information Search and recommending sets of recipes by user-specified ingredients. Those
Retrieval recipes which are well-accompanied and contain the query
Keywords ingredients are returned. We propose a graph-based algorithm for
Menu Planning, Recipe Recommendation, Cooking, Ingredient, menu planning. The proposed approach constructs a recipe graph
Minimum Steiner Tree. to capture the co-occurrence relationships between recipes from
collection of menus. A menu is generated by approximate Steiner
1. INTRODUCTION Tree Algorithm on the constructed recipe graph. Evaluation of
With the growth of recipe sharing services, online cooking recipes menu collections from Food.com shows that the proposed
associated with ingredients and cooking procedures are available. approach achieves encouraging results.
Many recipe sharing sites have devoted to the development of
The contributions of this paper are the following. First, we
recipe recommendation and retrieval mechanism.
propose the menu planning problem which recommending a set of
However, there is a need for users to plan menu of meals by recipes by ingredients. Second, to generate the set of recipes based
ingredients. The menu can be used to organize several recipes to on collective knowledge, the recipe graph is developed to capture
make whole meals for daily dinner, holiday events, party planning, the accompaniment between recipes from menus of food sharing
and so on. A dinner menu could consist of Chicken Salad as the web sites. Third, we propose to utilize the minimum Steiner Tree
salad, Coconut Shrimp as the appetizer, Vegetable Lasagna as the algorithm on the constructed recipe graph to solve the menu
main dish, and Blueberry Cake as the dessert. Many recipe planning problem and present an approximate Steiner Tree
sharing websites have provided users the functionality to share Algorithm for the large recipe graph.
menus of recipes and to search for menus by ingredients.
2. RELATED WORK
Recipe recommendation and retrieval has been the subject of
Permission to make digital or hard copies of all or part of this work for cooking related research. One of the earlier works is Kalas, a
personal or classroom use is granted without fee provided that copies are social navigation system for food recipe, developed by Svensson
not made or distributed for profit or commercial advantage and that et al. [11]. Ueda et al. proposed a personalized recipe
copies bear this notice and the full citation on the first page. To copy recommendation method based on user’s food preferences [12,
otherwise, or republish, to post on servers or to redistribute to lists, 13]. A user’s food preference in terms of ingredients is derived
requires prior specific permission and/or a fee.
from his/her recipe browsing activities and menu planning history.
CEA’12, November 2, 2012, Nara, Japan.
Copyright 2012 ACM 978-1-4503-1592-0/12/11...$15.00.
Xie et al. [16] proposed a hybrid semantic item model for recipe are identified. Next, the recipe graph which captures the
search by example. The hybrid semantic item model represents accompaniment information between recipes is constructed from
different kinds of features of recipe data. Forbes presents an collected menus of recipes as well as the recipe equivalence
approach for recipe recommendation to incorporate recipe content information. Finally, given query ingredients, the Menu Planning
into matrix factorization method [1]. Experimental results showed module with approximate Steiner Tree algorithm on the
the algorithm not only improves the recommendation accuracy but constructed recipe graph is utilized to generate the menu of
is also useful for swapping ingredients and creating recipe recipes satisfying the query ingredients.
variations. While most research models recipes in terms of
ingredients, Wang et al. [15] model cooking procedures of Figure 2 shows an example of the recipe graph. The graph
Chinese recipes as directed graphs and proposed a substructure consists of eleven nodes; each corresponds to a recipe. For ease of
similarity measurement based on the frequent graph mining. illustration, each node is labeled with recipe name and part of
Another branch of research has focused on the recipe ingredients. There is an edge between two recipe nodes if two
recommendation for healthy food. Mino et al. investigated the recipes appear in the same menu. Each edge is associated with its
cost, which will be described in the later section. If two recipes
recommendation of cooking recipes for a diet in which the
evaluation value of intake or consumption of calorie is considered tend to be more fit, the weight of their edge is lower.
in the events of a user's schedule during the period of a diet [5]. 4. RECIPE EQUIVALENCE IDENTIFICATION
Linear programming approach is utilized with the constraints of In the crawled recipes from food.com (details are described in
carbohydrate, lipid, protein, salt, and increasing the amount of Section 7), since these recipes are manually contributed by users,
vegetable intake. Karikome and Fujii propose a system to help some recipes, which actually represents for the same one, are
users for planning nutritionally balanced menus [3]. considered to be different. To deal with such problem for accurate
Considerations of recipes that correct the user’s nutritional recipe recommendation, we develop the recipe equivalence
imbalance are incorporated into the recipe retrieval process. identification component in our framework. The goal aims at
Visualization of dietary habits are also provided by this system. identifying those very similar recipes and regarding them as the
Shidochi et al. proposed an approach to extract replaceable same recipe. From the collected data, each recipe is associated
ingredients from recipes in to satisfy users' various demands, with a set of ingredient labels (after some preprocessing on the
such as calorie constraints and food availability [9]. In order to free texts of ingredient descriptions for each recipe). We consider
develop a strategy for changing users eating and cooking that if two recipes possess more the same ingredients, they tend to
behaviors, Pinxteren et al. proposed a user-centered similarity be the equivalence with one another (i.e., have higher potential to
measure for recommendation of healthier alternatives which are be the same recipe). Given two recipes ! and ! , with the
perceived to be similar to users commonly selected meals [7]. The corresponding sets of ingredients !! and !! , we use Jaccard
similarity measure can be used to promote new recipes that fit
similarity to measure their extent of equivalence. Specifically, the
users’ lifestyle. By considering the user’s cooking competence,
Wagner et al. presented a context-aware recipe retrieval and Jaccard similarity is defined as ! !! , !! = |!! ∩ !! | |!! ∪ !! |.
recommendation system to motivate users for healthy food If ! !! , !! is higher than a pre-defined threshold !, the recipes !
preparation [14]. The system tracks the user’s cooking activities and ! are regarded to be equal one. We apply such similarity
with sensors in kitchen utensils and recommends healthy recipes computation to all the recipes for aggregating equivalent recipes
that may increase the user’s cooking competence. to the same one. The threshold ! is set to be 0.5 in this work. Note
While most work on cooking related research focus on recipe that in fact we can refer to Wang et al.’s sophisticated method
recommendation and retrieval, to the best of our knowledge, little [15], which considers the cooking procedure, to measure the
work has been done on the menu planning by ingredients. similarity between two recipes. Since this is not our main purpose,
here we devise the abovementioned simple but effective manner.
Menu of
Social Recipe
Sites
Recipes 5. RECIPE GRAPH
In this section, we give the definition of the recipe graph and the
formal definition of the menu planning problem.
Recipe Equivalence [Definition 1] (Recipe Graph) Let A = {a1,..., am} be a universe of
Identification m ingredients. A recipe graph is defined as an undirected
weighted graph G = (V, E). Each node i in V = {1,..., n} is a recipe
Query that possesses a set of ingredients Ti ⊆ A. Each edge (i, j) in E is
Ingredients
Recipe Graph the relationship between two recipes, i and j, and edge weight
Menu Plan
Construction represents the distance between recipes.
[Definition 2] (Recipe Distance) Given a recipe graph G = (V, E)
and a collection of menus, the recipe distance between two recipes
Menu Planning i and j is defined as the reciprocal of the number of co-
occurrences of recipes i and j within the collection of menus. In
Figure 1. Proposed Framework for Intelligent Menu Planning. other words, if two recipes tend to be co-occurring in menus, the
weight of their edge is lower.
3. PROPOSED FRAMEWORK
[Definition 3] (Menu Cost) Given a recipe graph G = (V, E) the
The framework of the proposed approach for intelligent menu cost of a menu, i.e. a set of recipes, P, P ⊆ V, is defined as the
planning is shown in Figure 1. First, menus of recipes generated sum of the weights of edges of the minimum spanning tree on the
by users are collected from social recipe sites such as food.com, induced subgraph G[P], denoted by C(P).
allrecipe.com and myrecipes.com. Then, the equivalent recipes
[Definition 4] (Menu Planning Problem) Given a recipe graph G required nodes, the minimum Steiner tree problem is to find the
= (V, E) and a query consisting of a set of query ingredients Q, minimum-cost spanning tree that connect the required nodes. We
and the designated number of required courses r, the menu can transform the menu plan problem into the minimum Steiner
planning problem is to return a menu plan, i.e., a set of recipes, P tree problem by adding a new node wj for each ingredients aj. Each
⊆ V, |P| = r, such that (1) ! ⊆ !∈! !! , and (2) the menu cost new vertex wj is connected to a node i ∈ V if and only if aj ∈ Ti. In
C(P) is minimized. other words, a new ingredient node corresponding to ingredient aj
is connected to each recipe node that possesses ingredient aj. The
Take Figure 2 as an example, the recipe node “Italian Bread” has distance between an ingredient node and a recipe node is a large
co-occurrence relationship with five recipes. Among the recipes, number, larger than the sum of all the pairwise distances of the
Tiramisu has the highest co-occurrence relationship since the cost nodes.
is the lowest, while Stuffed Shells has the lowest relationship with
Italian Bread. For the menu {“Mozzarella, Tomato and Basil However, since the Steiner tree problem is NP-hard, it will take
Salad”, “Lasagna”, “Italian Bread”}, the menu cost is 0.23 and the much time to generate the menu when the recipe graph is large.
minimum spanning tree is shown with blue color in the graph. In To tackle the large recipe graph, this paper presents an efficient
this example, given query ingredients {tomato, flour, basil} algorithm modified from our previous work on people search in
(shown in red color on the figure), the Menu Planning module will attributed social networks [4]. Our proposed method is an
generate the set of recipes {“Mozzarella, Tomato and Basil approximation algorithm consisting of three major steps. First,
Salad”, “Lasagna”, “Italian Bread”} (nodes with blue frame), according to the query ingredients, an abstract structure, called
rather than {“Mozzarella, Tomato and Basil Salad”, “Lasagna”, group graph is extracted from the recipe graph. The group graph
“Almond Cake”}. will be helpful in reducing the search space to generate the set of
recipes. Then, a compact recipe graph, called query relevance
6. MENU PLAN GENERATION graph is constructed from the original recipe graph based on the
To solve the menu planning problem, one approach is to transform group graph. Finally, we propose a Connector-Steiner algorithm
this problem into the minimum Steiner tree problem [8]. Given an to compose the menu from the recipe relevance graph.
undirected graph with non-negative costs on edges, and some
Vegetable'Soup Tiramisu Lasagna Almond'Cake
Onion Espresso,Coffee Beef 0.25 Flour
0.1 Tomato Butter
Tomato Egg
Carrot 7 Parmesan,Cheese Almond
Sugar
Zucchini Mascarpone,Cheese Mozzarella,Cheese Sugar Egg
Chicken,Broth Ladyfingers Lasagna,Noodle
0.33
0.11 0.1
0.33 Mozzarella,'Tomato'
Stuffed'Shells 0.11 and'Basil'Salad
Egg Tomato
Parmesan,Cheese
0.5 Italian'Bread 0.13 Mozzarella,Cheese
Shell,Pasta Flour Basil
0.25 Spaghetti,sauce Butter Olive,Oil
Olive,Oil
0.14 0.51 0.5 0.8
Bread'Pudding
Caesar'Salad 0.13 Spinach'Salad
Bread Mushroom'Risotto
Spinach Mushroom
Egg Romaine,Lettuce Mushroom Rice
Brown,Sugar Parmesan,Cheese Tomato
0.33 Olive,Oil
Milk Olive,Oil 0.5 Onion 0.2 Parmesan,Cheese
Vegetable,Oil

Figure 2. An Example of Recipe Graph for Menu Planning.

Tomato Flour
Vegetable'Soup Tiramisu Lasagna Almond'Cake
0.25
0.17
0.11 Tomato
0.11 0.33 0.1 0.33
Stuffed'Shells
0.5 Flour Mozzarella,'Tomato'
0.25 Italian'Bread and'Basil'Salad
0.13
0.14 Basil
0.51 0.5 0.8
0.13
Spinach'Salad
Bread'Pudding Caesar'Salad Mushroom'Risotto 0.2
0.33 0.5

Figure 3. The Query Ingredient Grouping of the Recipe Graph in Figure 2.

 Tomato 0.25
Flour 6.3 Connector-Steiner Tree Algorithm
The last step is the Connector-Steiner Tree algorithm to generate
Tomato 0.33
the menu plan with lower cost. We start the graph search by
0.13 0.0
selecting an ingredient node from the query relevance graph. The
Flour Basil ingredient node with the highest degree will be selected as the
0.38 0.13 seed node. The central idea of the Connect-Steiner Tree algorithm
is to consider the replaceability of the three kinds of connectors.
Figure 4. The Group Graph of the Recipe Graph in Figure 2. Considering now we have the round-k resulting subgraphs (i.e., k
recipes as candidates to be returned), the members of subgraphs
Vegetable'' Lasagna Almond'Cake could be overlap, direct, and indirect connectors, and now we aim
0.25
Soup to find the (k+1)th subgraph. We claim the found nodes with the
0.1 Flour 0.33 Basil
query ingredients in previous k rounds are strongly replaceable.
Italian'' We can find other recipes with the query ingredients in the query
Mozzarella,'Tomato'
Bread 0.13 and'Basil'Salad relevance graph. Therefore we attempt to avoid the discovered
node with the query ingredients occurring in the following-round
0.8 subgraph results. This action will lead the Steiner Tree algorithm
Tomato
Spinach'Salad to find alternative subgraphs to return alternative recipes with
query ingredients in the following effective subgraphs. For those
Figure 5. The Query Relevance Graph of the Recipe Graph in
nodes without satisfying the query ingredients, we regard they are
Figure 2.
weakly replaceable and allow no occurrence restriction on them in
6.1 Group Graph Construction the following rounds.
The first step is to group the nodes in the recipe graph according Algorithm 1. Connector-Steiner Tree Algorithm
to query ingredients. A group, with respect to a query ingredient, Input: the recipe graph GLR = (VLR, ELR);
for example, ai, is a connected subgraph, in which each node a set of query ingredients T = {a1,...,ar}.
contains at least ai. Note that for a query ingredient ai, it can have Output: A list of menu plans P=<p1...,pn>.
more than one group since there could exist several disconnected 1: for k = 1 to n do
subgraphs belonging to ai. Figure 4 shows the grouping of the 2: Uk ← s, where s∈T and s is picked by degree.
recipe graph in Figure 2. 3: while (T \ Uk) ≠ φ do
After aggregating nodes into groups, a group graph is constructed 4: v* ← argmin u T\Uk Dist(u, Uk) in GLR.
∈

to model the connections between groups. The idea is that if the 5: if Path (v*, Uk) ≠ φ then
group graph possesses lower costs to connect groups, it will guide 6: Uk ← Uk ∪ {Path(v*, Uk)}.
the menu plan generation to find subgraphs with lower costs. 7: Uk ← Uk \ {a1, ..., ar}.
Therefore, given two groups, we leverage the distance measure in 8: p ← {vt| vt∈Uk and t∈Xt and vt pj, j=1,...,k-1}.
single-link clustering to find the path with minimum sum of 9: weight(et=(vt, t)) ←weight(et=(vt, t))×LARGEVALUE(=1000).
weights. Specifically, to connect two groups grpx and grpy, the 10: LIST ← (p, Cost(Uk)).
minimum shortest path, defined by 11: Sort LIST according to Cost(Uk) and return as the ranked list of
menus P=<(p1,Cost1),...,(pn,Costn)>, where Cost1<, ..., <Costn.
!"# !"#! , !"#! = !"#$%&!∈!"#! ,!∈!"#! {!"#$(!"#ℎ! !, ! )}
where dist(pathG(i,j)) computes the distance of the i-j path
Here we describe the proposed Connector-Steiner Tree algorithm,
pathG(i,j) in the original recipe graph G. In addition, to eliminate
as shown in Algorithm 1. For each round, initially, the algorithm
redundant group connections, if nodes in a certain msp, except for
starts by selecting a query ingredient node based on the degree
! ∈ !"#! , ! ∈ !"#! , belong to !"#! , (! ≠ !, ! ≠ !), we will not
from ingredient nodes of the query relevance graph (line 2). Then,
consider such msp into the construction of group graph. Figure 4
each round of the sub-procedure (line 3-6) finds the ingredient
shows the constructed group graph of the recipe graph in Figure 2.
node v* with the mini-mum distance to the set of nodes that have
6.2 Query Relevance Graph Construction already been added to the current result Uk. All the nodes along
the shortest path from this ingredient node to the current solution
Taking the group graph as the guidance, the query relevance
are added to the current solution set. After the above sub-
graph GR is constructed from the original recipe graph. Such
procedure, we remove the terminal ingredient nodes from GLR[Uk]
process has three steps. The first is to restore the group nodes. For
(line 7). In the end of each round (line 8-10), we identify the
each group node, we find the induced subgraph in the original
recipe vt with the query ingredient t in current result Uk and
recipe graph corresponding to all nodes contained in it. The
associate a larger weight value to the edge et be-tween t and vt to
second is for the group links. For each group link, we find the
avoid returning vt as the following answers. In addition, we also
corresponding path of recipe nodes in the original recipe graph,
record the current answer pk and the cost of the current effective
and embed the path into the induced subgraph derived from the
subgraph. After the n rounds, we sort the answer recipes
first step. Then for each query ingredient, a new type of node,
according to costs and return a ranked list of answer recipes as the
ingredient node, is added into the relevance graph. A new edge is
result of menu plan formation (line 11).
connected from the ingredient node to each recipe node that
possesses that ingredient. For these newly added edges between 7. EVALUATION
ingredient nodes and connectors, we associate a positive weight
In this section, we present the performance evaluation of our
higher than the sum of all weights in the recipe graph. Figure 5
solution to the proposed menu planning problem. The aim is to
shows the query relevance graph of the recipe graph in Figure 2.
compare the quality between our planned menus (i.e., the
recommended set of recipes) and the original recipes in the menus.
7.1 Data Collection and Statistics are considered as the query ones. We vary the !! value as
We collect the menus and recipes from food.com, which is one of !! = 4, 6, 8, 10 to exhibit the effectiveness of our planned results.
the most popular recipe-sharing websites, where users can create, We will also show the goodness score for the recipes in the testing
rate, and share menus and cooking recipes. We downloaded 4,754 menu. The second experiment is to investigate the effect of the
menus and 226,025 recipes. Each menu contains a set of recipes. number of query ingredients on the goodness of the planned menu.
And each recipe consists of a set of ingredients. There are totally We fix the number of recipes in a testing menus by setting !! = 6,
5,073 kinds of ingredients in the all recipes. In addition, each and vary the number of ingredients that are used as the query ones.
recipe is associated with a set of categorical tags, which describes For a testing menu containing !! ingredients, we randomly select
the course it belongs to, main ingredient, cuisine/region, !! ×!% ingredients to be the query ones. We vary !% to be 20%,
preparation, occasion, diet, and nutrition for each recipe. Totally 40%,60%,80%,100% and compute the separated goodness scores.
there are 524 tags in the data. Table 1 shows some statistics about
menus, recipes, ingredients, and tags. We also show the frequency
7.2.1 Tag Entropy (TE)
We propose Tag Entropy to capture the tag distribution in a menu.
distribution for both the numbers of recipes and ingredients in
The tag entropy is defined as
menus and recipes in Figure 6(a) and 6(b) respectively.
!
Table 1. Statistics about menus, recipes, ingredients, and tags. !" !! = − !"#$ !! log ! !"#$(!! )
!!!
Description Average Value where !! is the set of tags in menu !, !"#$(!! ) is the probability
# of recipes per menu 6.88 of tag !! in the menu. The ! and ! values are the number of tracks
# of ingredients per recipe 8.57 and tags in ! respectively. Note that maximum value of the tag
# of tags per recipe 13.66 entropy is the number of tags ! rather than 1. The idea of tag
# of ingredients per menu 42.13 entropy aims to understand the coherence of tags in a menu (each
menu contain a set of recipes and each recipe is associated with a
set of tags). Coherence indicates the degree of homogeneity of
recipes in a menu. It is noted that the lower the better for the tag
entropy of a menu. Since our collected menu dataset is generated
by a large number of users, our goal is to recommend sets of
recipes with tag entropies close to the average of user generated
ones (i.e., recipes in the testing menu).

7.2.2 Tag Co-occurrence Density (TCD)

We consider the co-occurrence relationship between recipes and
(a) (b) tags to design the second goodness metric. To evaluate how well
Figure 6. (a) The number of recipes (x-axis) occurs in the the co-occurrence relationship retained in our planned menus, we
number (frequency) of menus (y-axis). (b) The number of define a novel measure Tag Co-occurrence Density. For any two
ingredients (x-axis) occurs in the number (frequency) of tags !! and !! , which belong to different recipes in the generated
recipes (y-axis).
menu !, we compute their co-occurrence in the training set !!"#$%
7.2 Evaluation Setting and Plan ! !! , !! =
1
×
1, if!!! ∈ !! , !! ∈ !!
!!
We divide the menus into the training set and the testing set. We !!"!"# !! ,!! ∈!
!! !!!
0, otherwise
!∈!!"#$%
randomly choose 70% of menus for training while 30% for testing.
All the menus are used to construct the recipe graph, and the where !! and !! are two recipes in menu !, !! is the total number
weights on edges are computed. The constructed recipe graph of pairs of recipes in menu !, and !!!"#$ is number of training
contains 20,899 recipes nodes as well as 163,072 edges between menus. Then, we define the tag co-occurrence density of a certain
them. We use the testing set to generate the query ingredients for menu ! as
the task of menu planning. For each testing menu, the 1
corresponding original recipes are considered to be the good- !"# ! = × !! ,!! ∈!,!! !!! !(!! , !! )
!! ! ∈! ,! ∈!
quality ones (i.e., well-accompanied with each other to be a menu). ! ! ! !

Throughout the evaluation, for each testing menu, we will where !! is number of tag pairs occurring in different two recipes
compute the goodness of both the planned set of recipes and the of menu !. The higher TCD value indicates that the recipes in a
original set of recipes for comparison. If the goodness score of a menu have stronger co-occurrence relationship.
planned set of recipes are close to the scores of the original sets of
recipes, the planned menu by our method is considered as an 7.3 Experimental Results
effective and good one. We will show the average goodness The results of the first experiment (varying the number of recipes
scores over the menus in the testing set. We propose two of testing menus) are shown in Figure 7(a) and 7(b) for tag
evaluation metrics, Tag Entropy (TE) and Tag Co-occurrence entropy and tag co-occurrence density respectively. We can
Density (TCD) described in Section 7.2.1 and 7.2.2, as the generally find that for both measures, the planned menus by our
goodness measures to understand the quality of the planned method are very close to the original ones. Such results indicate
menus. our method is capable of recommending sets of recipes which are
well-accompanied with each other, comparing to the user-
Our evaluation consists of two parts. The first experiment aims manually generated menus. We can find that the tag entropy
to understand how the size of a menu (i.e., the number of recipes values rise as the number of recipes in the query menu increases.
in a menu) affects the goodness score of the planned set of recipes. It is because more recipes could include more different tags in a
We consider each testing menu with !! recipes to generate a menu. As for the co-occurrence, the values go a bit lower when
query. If a testing menu has !! ingredients, all these !! ingredients the number of recipes increases. We think it results from that
 more recipes could relatively increase the space of tag pairs (i.e., [2] J. Freyne and S. Berkovsky, Intelligent Food Planning:
!! ), and then reduce the co-occurrence effects between tags. Personalized Recipe Recommendation, ACM International
Conference on Intelligent User Interface IUI, 2010.
[3] S. Karikome and A. Fujii, A System for Supporting Dietary
Habits: Planning Menus and Visualizing Nutritional Intake
Balance, International Conference on Ubiquitous Information
Management and Communication ICUIMC, 2010.
[4] C. T. Li, M. K. Shan, and S. D. Lin, Context-based People
Search in Attributed Social Networks, ACM International
Conference on Information and Knowledge Management
CIKM, 2011.
(a) (b) [5] Y. Mino and I. Kobayashi, Recipe Recommendation for a
Figure 7. Experimental results by varying the number of Diet Considering a User’s Schedule and the Balance of
recipes for the measures of (a) tag entropy and (b) tag co- Nourishment, IEEE International Conference on Intelligent
occurrence density. Computing and Intelligent Systems ICIS, 2009.
The results of the second experiment (varying the percentage of [6] K. Miyawaki, M. Sano, S. Yonemura, and M. Matsuoka, A
ingredients used as the query ones) are shown in Figure 8(a) and Cooking Support System for People with Higher Brain
8(b). For both measures, we can find values of the planned menus Dysfunction, ACM International Workshop on Multimedia
(red ones) are very close the original menus (blue ones). Even for Cooking and Eating Activities CEA, 2009.
though fewer numbers of ingredients (i.e., lower !%) are used for [7] Y. van Pinxteren, G. Geleijnse, and P. Kamsteeg, Deriving A
the query, the quality of our recommended sets of recipes are Recipe Similarity Measure for Recommending Healthful
competitive to the original ones. In general when the !% goes Meals, ACM International Conference on Intelligent User
lower, which implies less information is provided from the testing Interface IUI, 2011.
menu, the resulting quality will become a little worse (higher tag [8] G. Reich and P. Widmayer. Beyond Steiner's Problem: A
entropy). However, for the co-occurrence density, fewer numbers VLSI Oriented Generalization. International Workshop on
of ingredients will result in recommending smaller sets of recipes, Graph-theoretic Concepts in Computer Science, 1990.
which reduces the number of possible tag pairs (i.e., !! ), and thus [9] Y. Shidochi, T. Takahashi, I. Ide, and H. Murase, Finding
the TCD values will go a bit higher. Replaceable Materials in Cooking Recipe Texts Considering
Characteristic Cooking Actions, ACM International
Workshop on Multimedia for Cooking and Eating Activities
CEA, 2009.
[10] J. Sobecki, E. Babiak, and M. Slanina, Application of Hybrid
Recommendation in Web-Based Cooking Assistant, 10th
Conference on Knowledge-Based Intelligent Information and
Engineering Systems KES, 2006.
[11] M. Svensson, K. HooK, and R. Coster, Designing and
Evaluating Kalas: A Social Navigation system for food
(a) (b) recipes. ACM Transactions on Computer-Human Interaction
Figure 8. Experimental results by varying the percentage !% Vol. 12, No. 3, 2005.
of ingredients used as a testing query, for the measures of (a) [12] M. Uede, M. Takahata, and S. Nakajima, User’s Food
tag entropy and (b) tag co-occurrence density. Preference Extraction for Personalized Cooking Recipe
Recommendation, 2nd International Workshop on Semantic
8. CONCLUSION Personalized Information Management: Retrieval and
This paper presents an intelligent menu planning mechanism to Recommendation SPIM, 2011.
recommend sets of recipes for any user-specified ingredients. [13] M. Ueda, M. Takahata, and S. Nakajima, Recipe
Conceptually, we propose to consider that a good menu should Recommendation Method Based on User’s Food Preferences,
not only satisfy user-required ingredients but also contain recipes IADIS International Conference on e-Society, 2011.
which are well-accompanied with each other. Technically, we [14] J. Wagner, G. Geleijnse, and A. van Halteren, Guidance and
formulate the menu planning to be an optimization problem in a Support for Healthy Food Preparation in an Augmented
constructed recipe graph. Experimental results on the Food.com Kitchen, 2011 Workshop on Context-awareness in Retrieval
data exhibit the promising quality of the planned menus and Recommendation CaRR 2011.
recommended by our approach. [15] L. Wang, Q. Li, N. Li, G. Dong, and Y. Yang, Substructure
Similarity Measurement in Chinese Recipes, International
9. REFERENCES World Wide Web Conference WWW, 2008.
[1] P. Forbes and M. Zhu, Content-boosted Matrix Factorization [16] H. Xie, L. Yu, and Q. Li, A hybrid Semantic Item Model for
for Recommender Systems: Experiments with Recipe Recipe Search by Example, IEEE International Symposium
Recommendation, ACM International Conference on on Multimedia, 2010.
Recommender Systems RecSys, 2011.

View publication stats