Recommender system based on pairwise association rules Expert Systems With Applications 115 (2019) 535–542 Contents lists available at ScienceDirect Expert Systems With Applications journal homepage: www.elsevier.com/locate/eswa Recommender system based on pairwise association rules Timur Osadchiy a , ∗, Ivan Poliakov a , Patrick Olivier a , Maisie Rowland b , Emma Foster b a Open Lab, School of Computing, Newcastle University, Newcastle upon Tyne, United Kingdom b Institute of Health and Society, Newcastle University, Newcastle upon Tyne, United Kingdom a r t i c l e i n f o Article history: Received 4 April 2018 Revised 9 July 2018 Accepted 10 July 2018 Available online 21 August 2018 Keywords: Association rules Cold-start problem Data mining Ontologies Recommender systems a b s t r a c t Recommender systems based on methods such as collaborative and content-based filtering rely on ex- tensive user profiles and item descriptors as well as on an extensive history of user preferences. Such methods face a number of challenges; including the cold-start problem in systems characterized by ir- regular usage, privacy concerns, and contexts where the range of indicators representing user interests is limited. We describe a recommender algorithm that builds a model of collective preferences indepen- dently of personal user interests and does not require a complex system of ratings. The performance of the algorithm is analyzed on a large transactional data set generated by a real-world dietary intake recall system. © 2018 The Authors. Published by Elsevier Ltd. This is an open access article under the CC BY license. ( http://creativecommons.org/licenses/by/4.0/ ) 1 a t l 2 d b u p E f s u e a c r t s U N k m F i s p p m a i u fi i c w n M i b m ( c & h 0 . Introduction Recommender systems aim to identify consumer preferences nd accurately suggest relevant items (e.g. products, services, con- ent). They are used in various application domains, including on- ine retail, tourism and entertainment ( Covington, Adams, & Sargin, 016; Linden, Smith, & York, 2003 ). Widely adopted recommen- ation techniques often utilize collaborative filtering or content- ased recommendation methods ( Pazzani & Billsus, 2007 ). Collaborative filtering produces recommendations based on ser preference models that are generated from explicit and/or im- licit characteristics and metrics corresponding to user interests. xplicit indicators normally imply users assigning ratings to items; or example, to products viewed in, or purchased from, an online tore. Examples of implicit indicators include the amount of time sers spend interacting with content (e.g. watching a video) or lev- ls of interaction (e.g. scroll offset of a web page containing an rticle they are reading). Items that are positively rated or pur- hased by consumers with similar preference models are used as ecommendations for target users. User similarity can be expressed hrough correlations in purchasing history or ratings given to the ame products, which can be further amplified with demograph- ∗ Corresponding author at: Open Lab, School of Computing, Newcastle University, rban Sciences Building, 1 Science Square, Science Central, Newcastle upon Tyne, E4 5TG, United Kingdom. E-mail addresses: t.osadchiy@newcastle.ac.uk (T. Osadchiy), ivan.polia ov@newcastle.ac.uk (I. Poliakov), patrick.olivier@newcastle.ac.uk (P. Olivier), aisie.rowland@newcastle.ac.uk (M. Rowland), emma.foster@newcastle.ac.uk (E. oster). u u c m o a t ttps://doi.org/10.1016/j.eswa.2018.07.077 957-4174/© 2018 The Authors. Published by Elsevier Ltd. This is an open access article u cs (e.g. age, gender, occupation). Content-based filtering identifies imilarities between items based on a set of their descriptors (e.g. urpose of an item, author, artist, keywords). Items similar to those ositively rated or purchased by the target user, are used as recom- endations. Collaborative and content-based filtering recommender systems re therefore heavily dependent on extensive user- or item- profile nformation and are most effective when there is a rich history of ser preferences or behavior. Sparse data sets and lean user pro- les typically result in low-quality recommendations or an inabil- ty to produce recommendations at all. This is referred to as the old-start problem, where new users are added into the system ith empty behavior profiles or new items are added that have ot been reviewed or rated by anyone ( Shaw, Xu, & Geva, 2010 ). any solutions to the cold-start problem have been considered, ncluding hybrid methods that combine collaborative and content- ased filtering ( Schein, Popescul, Ungar, & Pennock, 2002 ), and ethods that aim to predict user preferences from demographics Lika, Kolomvatsos, & Hadjiefthymiades, 2014 ), or knowledge of so- ial relationships ( Carrer-Neto, Hernández-Alcaraz, Valencia-García, García-Sánchez, 2012 ). There are, however, a number of application contexts where sers interact anonymously; for example, online shops where an nregistered user browses and adds products to their basket to heck out later. In other contexts, such as email recipient recom- endation ( Roth et al., 2010 ), applications requiring high levels f privacy, or those where individual interactions with a system re necessarily infrequent (e.g. dietary surveys Bradley et al., 2016 ) here are no features and ratings to exploit, and the construction nder the CC BY license. ( http://creativecommons.org/licenses/by/4.0/ ) https://doi.org/10.1016/j.eswa.2018.07.077 http://www.ScienceDirect.com http://www.elsevier.com/locate/eswa http://crossmark.crossref.org/dialog/?doi=10.1016/j.eswa.2018.07.077&domain=pdf http://creativecommons.org/licenses/by/4.0/ mailto:t.osadchiy@newcastle.ac.uk mailto:ivan.poliakov@newcastle.ac.uk mailto:patrick.olivier@newcastle.ac.uk mailto:maisie.rowland@newcastle.ac.uk mailto:emma.foster@newcastle.ac.uk https://doi.org/10.1016/j.eswa.2018.07.077 http://creativecommons.org/licenses/by/4.0/ 536 T. Osadchiy et al. / Expert Systems With Applications 115 (2019) 535–542 o g g c l t t I a t a m fi a b t t u t D c fi l A B C o w t t a t q p e o 3 3 v d b p t w s i d i d D l m t 4 c t d f t of personal behavior and preference models is not possible. To ad- dress these challenges we describe a recommender algorithm that is independent of any personal user model and does not require a complex system of ratings. Based on a set of observed items se- lected by a user, the algorithm produces a set of items ranked by confidence of their being observed next. In designing the under- lying algorithm, we review existing methods that aim to address similar tasks, adapt them to meet the constraints of the application context that is our primary concern (dietary surveys), and propose a novel alternative. The performance of three methods is compared through the task of recommending omitted foods in a real world dietary recall system. 2. Related work While various approaches have been proposed to address the cold-start problem in recommender systems, the majority of these rely on knowledge of content ( Popescul, Pennock, & Lawrence, 2001 ) and users ( Lika et al., 2014 ), including social relationships between users ( Carrer-Neto et al., 2012 ), whereas our concern is with contexts where such information is not available. Shaw et al. addressed the cold-start problem in recommender systems by us- ing a data analysis technique, which is applied to large data sets for discovering items that frequently appear together in a single transaction. This technique is known as association rules ( Agrawal, Imielinski, & Swami, 1993; Shaw et al., 2010 ). Each association rule normally consists of a set of antecedent items that lead to a con- sequent item with a certain confidence. Pazzani and Billsus con- sider the list of topics of books users voted for as transactions, which allowed them to extract association rules for topics that fre- quently appeared together as part of a user’s interests ( Pazzani & Billsus, 2007 ). To expand preferences for each user, the algo- rithm then generates all possible combinations of topics for every book the user voted for and filters association rules, where the an- tecedent part of the rule matches one of the combinations. The consequent list of topics is added to the preferences of that user. In combination with a domain ontology association rules can be effectively employed for extracting, understanding and for- malizing new knowledge ( Ruiz, Foguem, & Grabot, 2014; Sene, Kamsu-Foguem, & Rumeau, 2018 ). However, association rules have to be adapted for recommendation tasks since they are primar- ily designed to be used as exploratory tools ( Rudin, Letham, Salleb-Aouissi, Kogan, & Madigan, 2011 ) to discover previously un- known relations that need to be analyzed for their interesting- ness ( Atkinson, Figueroa, & Pérez, 2013 ). As we will probably want to provide more specificity, and recommend the exact titles of the books instead of generic categories, this potentially leads to a vast number of mined association rules and matching all pos- sible combinations of the observed items may not result in rules being found. Furthermore, a consequent item may appear in mul- tiple matching rules, meaning that a function must be introduced that aggregates the confidences of found rules into a single score for the consequent item. Finally, only the associations with a sup- port (i.e. how often a rule holds as true across the data set) higher than a defined threshold are normally extracted ( Li & Deng, 2007 ). The produced list of rules is supposed to be of a reasonable size, to allow manual examination. In a recommender system, even as- sociations with low frequencies could still be relevant, if other rel- evant rules with higher confidence are not found. This requires the extraction of as many rules as possible, making the mining process a computationally expensive task ( Zheng, Kohavi, & Mason, 2001 ). Roth et al. (2010) introduced a method for building implicit so- cial graphs based on histories of interaction between users and es- timations of their affinity and applied it to the problem of email recipient recommendation. Based on a set of email addresses se- lected by a user (the seed group) the algorithm extracts all groups f contacts with whom the user has ever exchanged emails. Here a roup of contacts is a set of email contacts that were observed to- ether in a recipient list. For each of the contacts in each group, ex- luding members of the seed group, an interaction score is calcu- ated based on the volume of messages exchanged with that group, he recency of those messages, and the number of intersections of he seed group with the group of contacts that is being considered. nteraction scores of contacts that are present in multiple groups re aggregated into a single interaction score, which is then used o rank the set of email recommendations. The implicit social graph is a promising alternative to mining ssociation rules. It instead measures the confidence of recom- ended items based solely on observed transactions that are pre- ltered by intersections with given items. However, the method lso estimates the relevance of a group of recommended emails ased on the strength of social interaction of the target user with hat group, which is not a meaningful metric for applications hat do not assume communication (or other interaction) between sers. Association rules and implicit social graphs are data en- ities that represent item-to-group relationships. However, uMouchel and Pregibon (2001) suggested that a more effi- ient approach to discovering “interesting” associations is to first nd pairs of items that frequently appear together and then ana- yze larger sized item sets that contain those pairs. For example, if BC appears in a data set with a certain frequency, then pairs AB, C and AC would be at least as frequent as the triplet. Raeder and hawla (2011) effectively analyzed associations through a graph f individual items connected to each other with edges that are eighted by the frequency of two items appearing together. Items hat have stronger relationships with each other are compared o other items form clusters, which are then targeted for further nalysis. Similar to the implicit social graph this method avoids he need to mine all possible association rules, but without re- uiring any additional indicators of relevance except for the item airs frequencies. The relevance of produced recommendations is ffectively inf erred from the likelihood of their appearing with the bserved items. . Associated food recommender algorithm .1. Intake24 We introduce a new recommendation algorithm that was de- eloped for Intake24, a system for conducting 24-h multiple-pass ietary recall surveys ( Bradley et al., 2016 ). Intake24 is designed to e a cost-effective alternative to interviewer-led 24-h recalls and rovides respondents with a web-based interface through which hey enter their dietary intake for the previous day. Respondents ill likely only ever use the system if they are a part of a dietary tudy and only for a short period of time. Within a survey, a respondent typically records their dietary ntake for the previous day on three separate occasions. A single ay normally consists of four to seven meals (e.g. breakfast, morn- ng snack, lunch etc.) which include a selection of foods, drinks, esserts, condiments, and such (referred to generically as foods). uring the first step of a recall session, a respondent reports a ist of names of foods consumed during each of the previous day’s eals in a free-text format. For each text entry, the system re- urns a list of relevant foods selected from a taxonomy of around 800 foods, organized in a tree-based, multi-level structure. Spe- ific foods are terminal nodes of this taxonomy and are linked to heir nutrient values and portion size estimation methods. Respon- ents select one food from the returned list to add to their meal; or example: Coca-Cola (not diet); Beef, stir fried (meat only); Toma- oes, tinned; Basmati rice; Onions, fried; Chilli powder; Kidney beans . T. Osadchiy et al. / Expert Systems With Applications 115 (2019) 535–542 537 t 4 a o I t m s o d a t c i w t d m r s t n f t d p a p 3 a s o a r o a a o e t p t s s s o o 3 r s E q w s i r m t e l h d I n r s d d s t p 3 R s c p f t i s s i p m t ( ( i s t b i c d t c Completing an accurate recall requires respondents to be able o identify foods they ate from a database that covers more than 800 foods; for example, there are more than 30 types of bread lone. Thus, one of the key features in determining the usability f a dietary recall system is its presentation of food search results. f respondents are not able to readily identify items from a list re- urned in response to their textual description of the food, they are ore likely to select foods perceived as the closest match or even kip reporting the intake of that food. In other words, the relevance f search results, in terms of prioritizing them appropriately, may irectly affect the accuracy of dietary recall through level of effort nd time required to select the correct foods and report intake. The main application for the recommender algorithm is to au- omate the extraction of questions about foods that are commonly onsumed together (associated foods). In Intake24, this feature is mplemented as a link between an antecedent food (e.g. toast, hite bread ) and the consequent associated food category (e.g. but- er/margarine/oils ) along with a question that is asked if a respon- ent selects the antecedent food (e.g. Did you have any butter or argarine on your toast? ). Such food associations prompts are cur- ently hand-crafted by trained nutritional experts, which for thou- ands of foods is inevitably a time consuming process that is prone o omissions. Eating habits depend on region, culture, diet, and a umber of other factors, which requires defining new associations or every context in which a system is deployed. Furthermore, over ime new foods and recipes emerge and dietary trends change. In- eed, existing rules are often curated based only on personal ex- erience or previous research, and no published study has evalu- ted their appropriateness or explored alternative data driven ap- roaches to extracting such associations. .2. Generic procedure Our approach assumes that the patterns in eating behaviors of n observed population; that is, the respondents who took part in urveys conducted in a given country, has some relevance to those f an individual in that population. The recommender algorithm ssumes no prior knowledge about an individual except their cur- ently selected food items. The algorithm is trained on a large set f observed meals and produces a model of the eating behavior of given population, where a meal is a group of uniquely identifi- ble foods (e.g. vanilla ice cream, pear juice) reported to be eaten n a single occasion. Each individual food can be recorded as being aten only once during a meal. During the recommendation step, he resulting model accepts a set of foods, which we refer to as in- ut foods IF , and returns a set of recommended foods RF mapped o likelihoods of being reported along with IF (recommendation cores). IF are excluded from recommendations. In the following ection we discuss three possible implementations that were con- idered for the recommender algorithm. Along with the description f our methods we include examples of generated models and rec- mmendations for a sample transaction data set. .3. Association rules We introduce a recommender algorithm based on association ules (AR) that generates a model of eating behavior from a data et of meals (in the training step) in the form of association rules. ach rule consists of a set of antecedent foods and a single conse- uent food, together with the confidence that the consequent food ill be present in a meal given the antecedent foods that were ob- erved. The procedure for retrieving association rules is described n Agrawal et al. (1993) . The AR algorithm makes predictions from stored association ules with antecedent part antc similar to IF , and produces recom- endations from the consequent parts of the rules. To do so, AR akes association rules that have a consequent food that is differ- nt from any of IF and the antecedent foods antc that include at east one of IF ( Algorithm 1 ). The algorithm calculates the likeli- Algorithm 1: Recommendations based on association rules. function Recommend input : AM, association rules based model IF , foods selected by a respondent returns : RF , list of food recommendations 1 RF ← ∅ ; 2 foreach rule r l ∈ AM & r l.consequent / ∈ IF : 3 f ← rl.consequent; 4 if ∃ a f : a f ∈ rl.antecedent & a f ∈ IF : 5 if f / ∈ RF : 6 RF [ f ] ← 0 7 ant c ← rl.antecedent ; 8 c ← rl.con f idence ; 9 intr ← size ({ a f : a f ∈ antc & a f ∈ IF } ) ; 10 ms ← intr 2 / (size (antc) ∗ size (IF )) ; 11 RF [ f ] ← RF [ f ] + c ∗ ms 12 return RF ood of a recommended food f to be selected next as the confi- ence of the rule c multiplied by the similarity between antc and F (i.e. match score ms ). The match score ms is calculated as the umber of foods that appear both in IF and antc (i.e. intersections) aised to the power of two and divided by the size of IF and the ize of antc . We introduce the match score so that the recommen- ations from the rules with antc that are more similar to IF pro- uce recommendations that will appear higher. We then sum the cores for every f as its single recommendation score RF [ f ]. Recommendations produced by AR applied to the example ransaction data set { abcd, ade, de, ab } and given items { ab } are rovided in Table 1 . .4. Transactional item confidence We adapted the implicit social graph method described in oth et al. (2010) for our food recommendation task, which re- ulted in a recommender algorithm based on transactional item onfidence (TIC). One key difference to our food recommendation roblem is that the original email recipient recommendation task or which the implicit social graph was developed assumed two ypes of relationships between items in a data set (outgoing and ncoming emails). Our data set assumes only one type of relation- hip, which is the co-occurrence of foods in a meal. For that rea- on, TIC produces recommendations based on similarity of histor- cally observed transactions to IF and the frequency of foods ap- earing in those transactions. During the training step, TIC converts all reported meals to a ap of unique meals (or transactions) TM , so that there are no wo transactions of the same length containing the same foods Algorithm 2 ). For every food f in a transaction m , the confidence conditional probability) is calculated as TM [ m, f ] of f being present n m given that the rest of the foods from m were observed. To do o, the algorithm counts the number cf of reported meals that con- ain all the foods from m , excluding f , and divides it by the num- er cm of reported meals containing all of the foods from m . This s similar to the confidence measured in AR, but in this case we alculate it only for the full-sized meals that were observed in the ata set M , and not for all possible combinations of foods within hose meals. At the recommend step, the algorithm retrieves all transactions ontaining any of the input foods IF ( Algorithm 3 ). Within each of 538 T. Osadchiy et al. / Expert Systems With Applications 115 (2019) 535–542 Table 1 Recommender algorithm based on association rules applied to the example data set. Model based on AR Filtered rules Recommendations 1. a ⇒ b 0.67, d 0.67, c 0.33, e 0.33 1. a ⇒ d 0.67, c 0.33, e 0.33 d: 2.50 2. b ⇒ a 1.00, c 0.50, d 0.50 2. b ⇒ c 0.50, d 0.50 c: 1.96 3. c ⇒ a 1.00, b 1.00, d 1.00 6. a, b ⇒ c 0.50, d 0.50 e: 0.29 4. d ⇒ a 0.67, e 0.67, b 0.33, c 0.33 7. a , c ⇒ d 1.00 5. e ⇒ d 1.00, a 0.50 8. a , d ⇒ c 0.50, e 0.50 6. a, b ⇒ c 0.50, d 0.50 9. a , e ⇒ d 1.00 7. a, c ⇒ b 1.00, d 1.00 10. b , c ⇒ d 1.00 8. a, d ⇒ b 0.50, c 0.50, e 0.50 11. b , d ⇒ c 1.00 9. a, e ⇒ d 1.00 14. a, b , c ⇒ d 1.00 10. b, c ⇒ a 1.00, d 1.00 15. a, b , d ⇒ c 1.00 11. b, d ⇒ a 1.00, c 1.00 12. c, d ⇒ a 1.00, b 1.00 13. d, e ⇒ a 0.50 14. a, b, c ⇒ d 1.00 15. a, b, d ⇒ c 1.00 16. a, c, d ⇒ b 1.00 17. b, c, d ⇒ a 1.00 Algorithm 2: Training the model based on transactional item confidence. function Train input : M, data set of all meals returns : T M, map of unique meals with confidence for every food 1 T M ← ∅ ; 2 foreach meal m ∈ M : 3 if m / ∈ T M : 4 T M[ m ] ← ∅ 5 cm ← size ({ m 1 : m 1 ∈ M & m ∈ m 1 } ) ; 6 foreach food f ∈ m : 7 m 2 ← { f 1 : f 1 ∈ m & f 1 � = f } ; 8 c f ← size ({ m 3 : m 3 ∈ M & m 2 ∈ m 3 } ) ; 9 T M[ m, f ] ← c f /cm 10 return TM Algorithm 3: Recommendations based on transactional item confidence. function Recommend input : T M, map of unique meals with confidence for every food IF , foods selected by a respondent returns : RF , list of food recommendations 1 RF ← ∅ ; 2 foreach meal m ∈ T M : 3 if ∃ f 1 : f 1 ∈ m & f 1 ∈ IF : 4 foreach food f ∈ m & f / ∈ IF : 5 if f / ∈ RF : 6 RF [ f ] ← 0 7 con f ← m [ f ] ; 8 inter ← size ({ f 2 : f 2 ∈ m & f 2 ∈ IF } ) ; 9 RF [ f ] ← RF [ f ] + inter ∗ con f 10 return RF t v 3 d o a w P t a t C t a c t t c i the retrieved transactions m , foods f that are not included in IF are mapped to a score that is calculated as the number of intersections of m with IF (i.e. similarity) multiplied by the food’s confidence TM [ m, f ]. Multiple scores for f measured from different transactions are summed into a final recommendation score RF [ f ]. Recommendations produced by the TIC applied to an example ransaction data set { abcd, ade, de, ab } given items { ab } are pro- ided below ( Table 2 ). .5. Pairwise association rules Unlike the previous two algorithms, which produce recommen- ations from association rules and transactions similar to currently bserved IF , the recommender algorithm based on pairwise associ- tion rules (PAR) recommends foods that are likely to be observed ith any of IF in pairs. During the training stage ( Algorithm 4 ), AR for every observed food f counts the number OD [ f ] of meals Algorithm 4: Training the model based on pairwise associa- tion rules. function Train input : M, data set of all meals returns : P M, pairwise association rules 1 OD ← ∅ , food occurrences; 2 CD ← ∅ , food co-occurrences; 3 foreach meal m ∈ M : 4 foreach food f ∈ m : 5 if f / ∈ OD & f / ∈ CD : 6 OD [ f ] ← 0 ; 7 CD [ f ] ← ∅ ; 8 OD [ f ] ← OD [ f ] + 1 ; 9 foreach food f 1 ∈ m & f 1 � = f : 10 if f 1 / ∈ CD [ f ] : 11 CD [ f, f 1] ← 0 12 CD [ f, f 1] ← CD [ f, f 1] + 1 13 P M ← [ OD, CD ] ; 14 return PM hat contain that food. For every observed pair of foods { f, f 1}, it lso counts the number CD [ f, f 1] of reported meals that contain hat pair. At the recommend step ( Algorithm 5 ), PAR retrieves pairs D [ inf ], where one food inf is observed in IF . For every pair { inf, f }, he algorithm calculates the conditional probability p , of f being in meal, given that inf was observed as the number of meals that ontain that pair CD [ inf, f ], divided by the number of meals OD [ inf ] hat contain only inf . For example, if item A appeared 10 times in he data set and co-occurred with item B only 2 times, then the onditional probability that item B will occur the next time the A s present is 0.2. Multiple probabilities retrieved for f from differ- T. Osadchiy et al. / Expert Systems With Applications 115 (2019) 535–542 539 Table 2 Recommender algorithm based on transactional confidence applied to the example data set. Model based on TIC Filtered rules Recommendations 1. a 1.00, b 1.00, c 1.00, d 1.00 1. a 1.0, b 1.00, c 1.00, d 1.00 d: 3.00 2. d 1.00, a 0.50, e 0.50 2. d 1.00, a 0.50, e 0.50 c: 2.00 3. d 1.00, e 0.67 e: 0.50 4. a 1.00, b 0.67 Algorithm 5: Recommendations based on pairwise association rules. function Recommend input : P M, pairwise association rules IF , foods selected by a respondent returns : RF , list of food recommendations 1 RF ← ∅ ; 2 P ← ∅ , conditional probabilities of foods; 3 W ← ∅ , conditional probability weights; 4 OD ← P M[ OD ] , food occurrences ; 5 CD ← P M[ CD ] , food co-occurrences ; 6 foreach input food in f ∈ IF : 7 foreach food f ∈ CD [ in f ] & f / ∈ IF : 8 if f / ∈ P & f / ∈ W : 9 P [ f ] ← ∅ ; 10 W [ f ] ← ∅ 11 p ← CD [ in f, f ] / OD [ in f ] ; 12 P [ f ] ← P [ f ] + { p} ; 13 W [ f ] ← W [ f ] + { OD [ in f ] } 14 foreach food f ∈ P : 15 RF [ f ] ← sum (P [ f ]) ∗ sum (W [ f ]) 16 return RF e P i d t m g s a f c p R a 1 C w s t v 4 p p W f i s T R p d m a c o r r t W e p w e a l ( D 1 t a ( a s m fi t ( e b A c a n i Z p i a s fi o t ( 5 5 d nt associations are summed into its single recommendation score [ f ]. As demonstrated in Roth et al. (2010) the number of times tems are observed together is an important relevance metric. In- eed, if we simply aggregate the probabilities derived from mul- iple associations, we lose information as to whether a recom- ended food has ever been observed with all IF . For example, iven two input items C and D , the aggregation may produce two cores R CD (A ) = 0 . 5 , where item A appeared with both C and D , nd R C (B ) = 0 . 5 , where item B appeared only with item C . There- ore A should receive a higher score. Likewise we take into ac- ount the frequency of an input food inf that matched a retrieved air. For example, we may have two equal scores, R C (A ) = 0 . 5 and D (B ) = 0 . 5 , where A and B historically appeared only with items C nd D respectively; but C appeared 10 times and item D appeared 00 times, which implies that the recommendation produced by should have a higher score. For these reasons, the algorithm eights aggregated probabilities P [ f ] by multiplying them by the ummed frequency of inf . Recommendations produced by PAR applied to the example ransaction data set { abcd, ade, de, ab } given items { ab } are pro- ided in Table 3 . . Methodology We compare the three algorithms for 20 0 0 0 randomly sam- led meals, each containing no fewer than two foods, reported by articipants of various ages in the UK between 2014 and 2018. e also randomize the order of foods in each meal. We use k- old ( k = 10 ) cross validation to segment the data set into train- ng and testing sets ( Salzberg, 1997 ). On each step we use nine ubsets for training a model, leaving out one subset for testing. he testing procedure is similar to the procedure described in oth et al. (2010) : we sample a few foods from each meal (in- ut foods), leaving the rest (at least one food) to simulate respon- ents’ omitted foods to be guessed by the algorithm. Every trained odel makes predictions, starting from an input size of one food nd gradually incrementing it to five. In the course of the evaluation, we plot the precision-recall (PR) urves for every algorithm on every increment. For the purposes f the evaluation, we measure the recall as the percentage of cor- ect predictions out of the total number of foods selected by the espondent, and the precision as the percentage of correct predic- ions out of the total number of predictions made by the algorithm. e count predictions that were present in the set of foods actually ntered by the respondent (excluding input foods) as correct (true ositives). We analyze the quality of the top 15 recommendations, hich is a slightly larger size than viewed by most users ( Burges t al., 2005; Van Deursen & Van Dijk, 2009 ). As the measure of lgorithm ranking quality for every size of input foods we calcu- ate the mean value of Normalized Discounted Cumulative Gain nDCG) at rank 15 ( Burges et al., 2005 ) as nDC G 15 = DC G 15 /IDC G 15 . iscounted cumulative gain is measured as DCG 15 = ∑ 15 i =1 (2 r(i ) − ) / log (i + 1) , where r ( i ) is the relevance score of the i th food. As he relevance score, we use 0 for a wrong prediction and 1 for correct prediction. Thus, the Ideal Discounted Cumulative Gain IDCG) in our case is always 1, which is a single correct prediction s the first result. We then select the implementation that demon- trates the highest performance and apply it to the task of recom- ending foods omitted by respondents with a lower level of speci- city, and for ranking search results returned in response to their ext queries. For the implementation of AR we use the FP-growth algorithm frequent patterns algorithm) ( Li & Deng, 2007 ). FP-growth is an fficient and scalable association rules mining algorithm that is ased on building frequent-pattern tree structure. In contrast to priori-like algorithms that serve the same purpose, the FP-growth ompresses a large database into a much smaller data structure voiding costly repeated database scans and generation of a large umber of candidate sets. We use a parallel version of FP-growth mplemented in the Apache Spark framework ( Li, Wang, Zhang, hang, & Chang, 2008; Meng et al., 2016 ). As a parameter, this im- lementation accepts the minimum support for an item set to be dentified as frequent and the minimum confidence for the gener- ted association rules. To gather as many association rules as pos- ible we set both the minimum support and the minimum con- dence to the lowest value (3 × 10 4 ) that allows the completion f the mining process of our data set on our machine within a ime limit of 5 minutes. The evaluation is conducted on Mac Pro 2.9 GHz Intel Core i5, 16 GB). . Results .1. General performance As can be observed from the PR curves ( Figs. 1 and 2 ), PAR pro- uces the largest area under the curve, which increases with the 540 T. Osadchiy et al. / Expert Systems With Applications 115 (2019) 535–542 Table 3 Recommender algorithm based on pairwise association rules applied to the example data set. Model based on PAR Filtered rules Recommendations 1. a 3.0 ⇒ b 2.0, d 2.0, c 1.0, e 1.0 1. a 3.0 ⇒ d 2.0, c 1.0, e 1.0 d: 5.8 2. b 2.0 ⇒ a 2.0, c 1.0, d 1.0 2. b 2.0 ⇒ c 1.0, d 1.0 c: 4.2 3. c 1.0 ⇒ a 1.0, b 1.0, d 1.0 e: 1 4. d 3.0 ⇒ a 2.0, e 2.0, b 1.0, c 1.0 5. e 2.0 ⇒ d 2.0, a 1.0 Fig. 1. Precision-Recall curves for an input size of 2 foods. Fig. 2. Precision-Recall curves for an input size of 4 foods. Table 4 Mean training and recommendation times in mil- liseconds. Model Training Mean recommendation AR 3905.1 39.5 PAR 6904.9 2.5 TIC 93710.2 32.0 Fig. 3. The ratio of mean nDCG for the top 15 results to the number of input foods. Fig. 4. The ratio of recall for the 15 results to the number of input foods for pair- wise association rules with the first and the second levels of specificities and man- ually entered associated food prompts. 5 r f a f a i t i e r c c c size of input foods. PAR also demonstrates higher nDCG than TIC and AR for all input sizes ( Fig. 3 ). PAR is the second fastest algo- rithm to produce a model (after AR) but the fastest to produce a single set of recommendations ( Table 4 ). Based on this comparison, PAR is selected to be used for the implementation of the associ- ated foods recommender algorithm. At the same time, these results demonstrate that the quality of predictions produced by PAR is still relatively low. In the following experiments we aim to improve the performance of the algorithm by exploiting the context of the task it is used for. .2. Associated food questions To compare the efficacy of recommendations produced by the ecommender algorithm to the existing hand-coded associated ood questions we go through the same evaluation procedure as bove, except that on the recommend step a trained model returns ood categories instead of exact foods. In this case, true positives re considered to be foods selected by the respondent (excluding nput foods) that belong to one of the food categories predicted by he recommender algorithm. The taxonomy of foods implemented n Intake24 allows control of the specificity of the returned cat- gories. So, we demonstrate the performance of the algorithm in eturning the direct parent category of a food (first level, e.g. Flake ereals is the parent category for Choco flakes ) and a more generic ategory (second level, e.g. Breakfast cereals ) that is a parent of the ategory with the first-level specificity ( Fig. 4 ). Since the existing T. Osadchiy et al. / Expert Systems With Applications 115 (2019) 535–542 541 Table 5 Omitted foods captured with pairwise association rules but not with manually entered associated food prompts. Input foods First-level specificity Second-level specificity Chicken breast; Fanta; Instant potato Gravy Sauces, condiments, gravy and stock Bananas; Fruit and yoghurt smoothie; Semi skimmed milk Sugar Sugar, jams, marmalades, spreads and pates Blackcurrant squash (juice), e.g ribena; Heinz beans and sausages Brown bread toasted Brown, wholemeal and 50:50 bread Porridge, made with skimmed milk; Tea; White sugar Butter Butter/margarine/oils Tuna mayo sandwich; Volvic mineral water, still or fizzy Chocolate covered biscuits Sweet biscuits Bread sticks; Coffee Dips Pickles, olives, dips and dressings Cheese and tomato pizza (includes homemade); Raspberries Ice cream Ice cream & ice lollies Cheese sandwich; Tea Crisps and snacks Crisps, snacks and nuts Green Olives; Water Wine Alcohol Bottled mineral water; Chicken breast fillet; Chips, fried; Hot sauce Fizzy drinks Drinks Still energy drink, eg Lucozade Hydroactive, Gatorade, Powerade; Tuna in brine, tinned; White bread sliced Mayonnaise Sauces/condiments/gravy/stock a t r d f a w 7 l r o s I t l d o c d e f 5 s fi t t m 2 e e V w t t n t b a Fig. 5. The ratio of mean nDCG for the top 15 results to the number of input foods for the search results ranked based on pairwise association rules and FRC. u q p i s t a w o g 6 e w m i f a u p r p ssociated food questions do not store any relevance scores plot- ing their PR curves or assessing their nDCG is impossible. For that eason we compare the recall of the top 15 recommendations pro- uced by the algorithm to the recall of all hand-coded associated oods rules extracted for given input foods. In the simulation of respondents omitting foods hand-coded ssociation food rules recognize 8.3% of omitted foods at most, hereas the recommender algorithm’s peak recall is at 58.0% and 9.1% for the first and the second levels of specificity respectively. Table 5 includes examples of commonly forgotten foods estab- ished in the validation of Intake24 ( Bradley et al., 2016 ) but cor- ectly predicted by the recommender algorithm with two levels f specificity. At the time of writing this paper, none of these as- ociations were covered by hand-coded associated foods rules in ntake24. In addition to that, controlling the specificity of the re- urned recommendations allows us to address the cold-start prob- em, so that new foods that have not been reported by any respon- ents can still be captured by their categories. However, the names f some food categories predicted with the second-level specificity ould be perceived as too generic (e.g. ”Pickles, olives, dips and ressings”) and may require being assigned names that would be asier to understand by respondents when displayed in associated ood prompts. .3. Search ranking In response to a respondent’s text query, the existing Intake24 earch algorithm ranks foods based on two types of scores. The rst is the matching cost of the known food description against he query. The matching cost is based on several metrics, including he edit distance between matched words (the approximate string atching is performed using Levenshtein automata Burges et al., 005 ); phonetic similarity of words (using a pluggable phonetic ncoding algorithm that depends on the localization language, .g. Soundex or Metaphone for English Elmagarmid, Ipeirotis, & erykios, 2007 ); the relative ordering of words; the number of ords not matched; and so forth. The lower the matching cost, he better the food name matches the query. The second score is he likelihood of the food being selected, which is measured by the umber of times the food was previously reported. The results are hen sorted, first by decreasing food report count (FRC) and then y increasing matching cost. The evaluation of the associated foods recommender algorithm pplied to the task of ranking search results, follows the same eval- ation procedure, with some variations. In response to each text uery that was recorded into the Intake24 database for each re- orted food (excluding input foods), we retrieve a list of foods us- ng the existing search algorithm. We count foods selected by a re- pondent as true positives and the rest of the results as false nega- ives. We compare the mean nDCG produced by the existing search lgorithm and by the new search algorithm, where FRC is replaced ith PAR. As we can see from the figure below ( Fig. 5 ), PAR slightly utperforms FRC starting from an input size of two foods, with the ap gradually widening as the number of input foods increases. . Conclusions We aimed to address one of the key issues in automated di- tary assessment, which is unintentional under-reporting. To do so, e developed an associated foods recommender algorithm to re- ind respondents of omitted foods and improve the ranking qual- ty of search results returned in response to respondents’ free-text ood name queries. The algorithm, in contrast with collaborative nd content-based filtering approaches, is independent of personal ser profiles and does not require an extensive history of users’ references or a multitude of item descriptors. Instead, the algo- ithm uses transactions performed by respondents from a given opulation to build a collective model of preferences. 542 T. Osadchiy et al. / Expert Systems With Applications 115 (2019) 535–542 D E L L L L M P P R R R R S V Z We considered three approaches to the implementation of the recommender algorithm, based on an implicit social graph ( Roth et al., 2010 ), association rules ( Agrawal et al., 1993 ), and an- alyzing pairwise association rules ( DuMouchel & Pregibon, 2001 ). The evaluation, performed on a large data set of real dietary re- calls, has demonstrated that the implementation based on pair- wise association rules performs better for the defined task. By con- trolling the specificity of the produced recommendations within a reasonable level we achieved a recall of 79.1%. That is signifi- cantly higher than food associations hand-coded by trained nutri- tionists, the recall for which reached only 8.3%. Where a respon- dent filled in at least one food, the recommender algorithm im- proves the ranking of search results. The algorithm was evaluated on dietary recalls of respondents from the UK. As a future work we are planning to analyze how dietary specificities of different regions affect the accuracy of the recommender algorithm. Although the evaluation results described in this paper were produced by analyzing food contents of meals reported by respondents in Intake24, the described methods apply to any recommender tasks where selection of items by the target user can be observed (e.g. email recipients or tags recommenda- tions on community platforms). Supplementary material Supplementary material associated with this article can be found, in the online version, at doi: 10.1016/j.eswa.2018.07.077 . References Agrawal, R., Imielinski, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. In Proc. 1993 ACM SIGMOD international conference on management of data, SIGMOD’93: 22 (pp. 207–216). ACM. doi: 10.1145/170036. 170072 . Atkinson, J. , Figueroa, A. , & Pérez, C. (2013). A semantically-based lattice approach for assessing patterns in text mining tasks. Computación y Sistemas, 17 (4) . Bradley, J., Simpson, E., Poliakov, I., Matthews, J. N. S., Olivier, P., Adamson, A. J., & Foster, E. (2016). Comparison of INTAKE24 (an online 24-h dietary recall tool) with interviewer-led 24h recall in 11–24 year-old. Nutrients, 8 (6), 358. doi: 10. 3390/nu8060358 . Burges, C., Shaked, T., Renshaw, E., Lazier, A., Deeds, M., Hamilton, N., & Hullen- der, G. (2005). Learning to rank using gradient descent. In Proceedings of the 22nd international conference on machine learning (pp. 89–96). ACM. doi: 10.1145/ 1102351.1102363 . Carrer-Neto, W., Hernández-Alcaraz, M. L., Valencia-García, R., & García- Sánchez, F. (2012). Social knowledge-based recommender system. Application to the movies domain. Expert Systems with Applications, 39 (12), 10990–110 0 0. doi: 10.1016/j.eswa.2012.03.025 . Covington, P., Adams, J., & Sargin, E. (2016). Deep neural networks for youtube rec- ommendations. In Proceedings of the 10th ACM conference on recommender sys- tems, RecSys ’16 (pp. 191–198). ACM. doi: 10.1145/2959100.2959190 . uMouchel, W., & Pregibon, D. (2001). Empirical bayes screening for multi-item associations. In Proceedings of the 7th ACM SIGKDD international conference on knowledge discovery and data mining, KDD’01 (pp. 67–76). ACM. doi: 10.1145/ 502512.502526 . lmagarmid, A. K., Ipeirotis, P. G., & Verykios, V. S. (2007). Duplicate record detec- tion: A survey. IEEE Transactions on Knowledge and Data Engineering, 19 (1), 1–16. doi: 10.1109/TKDE.2007.250581 . i, C. R. J., & Deng, Z. H. (2007). Mining frequent ordered patterns without candi- date generation. In Proceedings 4th international conference on fuzzy systems and knowledge discovery, FSKD 2007: Vol. 1 (pp. 402–406). IEEE. doi: 10.1109/FSKD. 2007.402 . i, H., Wang, Y., Zhang, D., Zhang, M., & Chang, E. (2008). Pfp: Parallel fp-growth for query recommendation. In Proceedings of the 2008 ACM conference on recom- mender systems (pp. 107–114). ACM. doi: 10.1145/1454008.1454027 . ika, B., Kolomvatsos, K., & Hadjiefthymiades, S. (2014). Facing the cold start prob- lem in recommender systems. Expert Systems with Applications, 41 (4 PART 2), 2065–2073. doi: 10.1016/j.eswa.2013.09.005 . inden, G., Smith, B., & York, J. (2003). Amazon.com recommendations: Item-to- item collaborative filtering. IEEE Internet Computing, 7 (1), 76–80. doi: 10.1109/ MIC.2003.1167344 . eng, X., Bradley, J., Yavuz, B., Sparks, E., Venkataraman, S., Liu, D., et al. (2016). Ml- lib: Machine learning in apache spark. The Journal of Machine Learning Research, 17 (1), 1235–1241. doi: 10.1145/2882903.2912565 . azzani, M. J., & Billsus, D. (2007). Content-based recommendation sys- tems. In The adaptive web: Vol. 4321 (pp. 325–341). Springer. doi: 10.1007/ 978- 3- 540- 72079- 9 _ 10 . opescul, A. , Pennock, D. M. , & Lawrence, S. (2001). Probabilistic models for uni- fied collaborative and content-based recommendation in sparse-data environ- ments. In Proceedings of 17th conference on uncertainty in artificial intelligence (pp. 437–4 4 4). Morgan Kaufmann Publishers Inc . aeder, T., & Chawla, N. V. (2011). Market basket analysis with networks. Social Net- work Analysis and Mining, 1 (2), 97–113. doi: 10.1007/s13278- 010- 0 0 03- 7 . oth, M., Ben-David, A., Deutscher, D., Flysher, G., Horn, I., Leichtberg, A., et al. (2010). Suggesting friends using the implicit social graph. In Proceedings of 16th ACM SIGKDD international conference on knowledge discovery and data mining (pp. 233–242). ACM. doi: 10.1145/1835804.1835836 . udin, C. , Letham, B. , Salleb-Aouissi, A. , Kogan, E. , & Madigan, D. (2011). Sequential event prediction with association rules. In Proceedings of 24th annunal confer- ence on learning theory (pp. 615–634) . uiz, P. P. , Foguem, B. K. , & Grabot, B. (2014). Generating knowledge in maintenance from experience feedback. Knowledge-Based Systems, 68 , 4–20 . Salzberg, S. L. (1997). On comparing classifiers: Pitfalls to avoid and a recommended approach. Data Mining and Knowledge Discovery, 1 (3), 317–328 . Schein, A. I., Popescul, A., Ungar, L. H., & Pennock, D. M. (2002). Methods and met- rics for cold-start recommendations. In Proceedings of the 25th annual interna- tional ACM SIGIR conference on research and development in information retrieval, SIGIR ’02 (pp. 253–260). ACM. doi: 10.1145/564376.564421 . ene, A. , Kamsu-Foguem, B. , & Rumeau, P. (2018). Discovering frequent patterns for in-flight incidents. Cognitive Systems Research, 49 , 97–113 . Shaw, G., Xu, Y., & Geva, S. (2010). Using association rules to solve the cold- start problem in recommender systems. In Pacific-Asia conference on knowl- edge discovery and data mining: 6118 (pp. 340–347). Springer. doi: 10.1007/ 978- 3- 642- 13657- 3 _ 37 . an Deursen, A. J., & Van Dijk, J. A. (2009). Using the Internet: Skill related problems in users’ online behavior. Interacting with Computers, 21 (5–6), 393–402. doi: 10. 1016/j.intcom.20 09.06.0 05 . heng, Z., Kohavi, R., & Mason, L. (2001). Real world performance of association rule algorithms. In Proceedings of 7th ACM SIGKDD international conference on knowledge discovery and data mining, KDD’01 (pp. 401–406). ACM. doi: 10.1145/ 502512.502572 . https://doi.org/10.1016/j.eswa.2018.07.077 https://doi.org/10.1145/170036.170072 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0002 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0002 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0002 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0002 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0002 https://doi.org/10.3390/nu8060358 https://doi.org/10.1145/1102351.1102363 https://doi.org/10.1016/j.eswa.2012.03.025 https://doi.org/10.1145/2959100.2959190 https://doi.org/10.1145/502512.502526 https://doi.org/10.1109/TKDE.2007.250581 https://doi.org/10.1109/FSKD.2007.402 https://doi.org/10.1145/1454008.1454027 https://doi.org/10.1016/j.eswa.2013.09.005 https://doi.org/10.1109/MIC.2003.1167344 https://doi.org/10.1145/2882903.2912565 https://doi.org/10.1007/978-3-540-72079-9_10 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0015 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0015 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0015 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0015 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0015 https://doi.org/10.1007/s13278-010-0003-7 https://doi.org/10.1145/1835804.1835836 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0018 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0018 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0018 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0018 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0018 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0018 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0018 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0019 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0019 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0019 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0019 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0019 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0020 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0020 https://doi.org/10.1145/564376.564421 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0022 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0022 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0022 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0022 http://refhub.elsevier.com/S0957-4174(18)30441-X/sbref0022 https://doi.org/10.1007/978-3-642-13657-3_37 https://doi.org/10.1016/j.intcom.2009.06.005 https://doi.org/10.1145/502512.502572 Recommender system based on pairwise association rules 1 Introduction 2 Related work 3 Associated food recommender algorithm 3.1 Intake24 3.2 Generic procedure 3.3 Association rules 3.4 Transactional item confidence 3.5 Pairwise association rules 4 Methodology 5 Results 5.1 General performance 5.2 Associated food questions 5.3 Search ranking 6 Conclusions Supplementary material References