ࡱ > . \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~ 5@ K bjbj22 z X X = m% ( ( ( ( $ U U U P V , 0Y ] ] c " c c d ' b 4 R a p < ' ( ( c d ( c d b $ ( ¯ d \ +Y U K T - 0 ] ¯ ( ( ( ( ¯ : X Y D ; L $ Y Y Y D 0 u 0 Abstract Digital television brings us hundreds of channels and thousands of programmes each day. It is therefore becoming increasingly difficult for users to find programmes they may want to watch. TV personalisation systems such as TV Supreme try to solve this problem by learning the likes and dislikes of a user and then recommending programmes which match their preferences. However, the accurate recommendations that are possible through using a system like TV Supreme are only achievable given rich classification information (including the notion of fuzzy classification) about each available programme. Building these classifications manually is a very time consuming and error-prone process. The primary aim of this project was to build an automated system which takes a standard HTML/Text based TV listing, extracts each programme present and generates a rich classification for them, with minimal user interaction. The project used a heuristic approach, whereby a number of rules were defined to intelligently infer values for the classification from the limited information (such as textual description, start time and channel) available. A secondary objective was to integrate the solution with the existing TV Supreme database and application. This led to a requirement to find any matches for programmes that had been previously classified and stored in the database, so they were not needlessly classified again. At the end of the classification process a detailed schedule then had to be created, using the generated and database classifications where appropriate. TV Supreme could then use these schedules to produce its recommendations. The entire process had to be as adaptable as possible, so it could be used in a context other than TV Supreme with only minor alterations. The system developed provides a crucial missing component for TV personalisation systems. It has been extensively tested and provides classifications which were very accurate 90% of the time, with only a few modifications required. Given that there are currently only 200 heuristics, this is an impressive statistic. Since the system provides a simple method for adding heuristics, there is built-in potential for achieving even higher levels of reliability. Disclaimer This report is submitted as part requirement for the degree of BSc in Computer Science at the University of London. It is the product of my own labour except where indicated in the text. The report may be freely copied and distributed provided the source is acknowledged. Acknowledgements I would like to take this opportunity to thank my advisor Professor Norman Fenton for all his hard work. Without his advice and encouragement I do not believe I would be as happy with my project. I extend this thanks to the other members of the RADAR group who helped me when asked. Finally, I would like to thank my family and girlfriend for their support an encouragement throughout the year. TOC \h \z \t "Heading 1 James,1,Heading 2 James,2" HYPERLINK \l "_Toc39114637" 1. INTRODUCTION PAGEREF _Toc39114637 \h 1 HYPERLINK \l "_Toc39114638" 2. BACKGROUND PAGEREF _Toc39114638 \h 2 HYPERLINK \l "_Toc39114639" 2.1 Personalisation PAGEREF _Toc39114639 \h 2 HYPERLINK \l "_Toc39114640" 2.2 Current TV personalisation services PAGEREF _Toc39114640 \h 4 HYPERLINK \l "_Toc39114641" 3. RESEARCH PAGEREF _Toc39114641 \h 7 HYPERLINK \l "_Toc39114642" 3.1 TV Supreme PAGEREF _Toc39114642 \h 7 HYPERLINK \l "_Toc39114643" 3.2 TV Classification Systems PAGEREF _Toc39114643 \h 11 HYPERLINK \l "_Toc39114644" 4. REQUIREMENTS PAGEREF _Toc39114644 \h 14 HYPERLINK \l "_Toc39114645" 4.1 Primary System Objective PAGEREF _Toc39114645 \h 14 HYPERLINK \l "_Toc39114646" 4.2 Extended Requirements PAGEREF _Toc39114646 \h 14 HYPERLINK \l "_Toc39114647" 4.3 Classifications PAGEREF _Toc39114647 \h 15 HYPERLINK \l "_Toc39114648" 4.4 Use Case Diagram PAGEREF _Toc39114648 \h 16 HYPERLINK \l "_Toc39114649" 5. DESIGN PAGEREF _Toc39114649 \h 19 HYPERLINK \l "_Toc39114650" 5.1 The UML Approach PAGEREF _Toc39114650 \h 19 HYPERLINK \l "_Toc39114651" 5.2 Core Functionality PAGEREF _Toc39114651 \h 22 HYPERLINK \l "_Toc39114652" 6. IMPLEMENTATION PAGEREF _Toc39114652 \h 28 HYPERLINK \l "_Toc39114653" 6.1 Connecting to Database PAGEREF _Toc39114653 \h 28 HYPERLINK \l "_Toc39114654" 6.2 Parser PAGEREF _Toc39114654 \h 29 HYPERLINK \l "_Toc39114655" 6.3 Matcher PAGEREF _Toc39114655 \h 30 HYPERLINK \l "_Toc39114656" 6.4 Mapper PAGEREF _Toc39114656 \h 31 HYPERLINK \l "_Toc39114657" 6.5 Scheduler PAGEREF _Toc39114657 \h 33 HYPERLINK \l "_Toc39114658" 7. TESTING PAGEREF _Toc39114658 \h 35 HYPERLINK \l "_Toc39114659" 7.1 Use case testing PAGEREF _Toc39114659 \h 35 HYPERLINK \l "_Toc39114660" 7.2 Black box testing PAGEREF _Toc39114660 \h 37 HYPERLINK \l "_Toc39114661" 7.3 Validation Testing PAGEREF _Toc39114661 \h 38 HYPERLINK \l "_Toc39114662" 7.4 Requirements Tractability PAGEREF _Toc39114662 \h 39 HYPERLINK \l "_Toc39114663" 8. EVALUATION AND CONCLUSION PAGEREF _Toc39114663 \h 40 HYPERLINK \l "_Toc39114664" 8.1 Meeting the requirements PAGEREF _Toc39114664 \h 40 HYPERLINK \l "_Toc39114665" 8.2 Skills Developed PAGEREF _Toc39114665 \h 40 HYPERLINK \l "_Toc39114666" 8.3 System Improvements PAGEREF _Toc39114666 \h 40 HYPERLINK \l "_Toc39114667" 9. REFERENCES PAGEREF _Toc39114667 \h 41 HYPERLINK \l "_Toc39114668" 10. APPENDIX PAGEREF _Toc39114668 \h 42 HYPERLINK \l "_Toc39114669" 10.1 TV Class - User Manual PAGEREF _Toc39114669 \h 42 HYPERLINK \l "_Toc39114670" 10.2 System Manual PAGEREF _Toc39114670 \h 49 HYPERLINK \l "_Toc39114671" 10.3 Design Document PAGEREF _Toc39114671 \h 50 1. INTRODUCTION This project tackles the increasingly important problem of TV personalisation, specifically the problem of helping viewers to choose from the hundreds of available programmes. The context of the project is TV Supreme, a system developed by Agena Ltd that provides TV programme recommendations based on Bayesian Learning. TV Supreme has been integrated onto set-top digital boxes in test mode and is known to provide accurate recommendations. The success of its recommendation is due to its novel Bayesian Learning approach and its rich fuzzy programme classification scheme. However, all the testing has been based on a carefully built database of schedules and programmes, where each individual programme was classified manually by experts according to the TV Supreme scheme. What TV Supreme does not currently offer is an end-to-end solution, in which new programme data is classified and then built into a schedule. The classification problem is a major challenge. Building an automated classification system to integrate with TV Supreme was the primary objective of this project. The objective led to the following specific challenges: Building a rich classification for each programme from the small amount of information available Defining heuristics to aid in the classification Integrating with the existing database Making the system as independent as possible in sense of programme information input and classifications/schedules output. The report aims to detail how I went about completing the project. Section 2 looks at the field of personalisation and then some of the TV personalisation services currently available. Section 3 covers the research into TV Supreme and some techniques required for completing the project such as programme classification. In Section 4 the system requirements are explained and it is upon these that the success of the project is measured at the end of the report. The system design is outlined in Section 5 looking at the key features of the system and how they fit into the overall structure. Details of the implementation itself are explained in Section 6, highlighting some of the more complex aspects. Section 7 explains how the system was tested in order to discover if it met the requirements and goals. The success of the project is discussed in Section 8, along with any possible extensions which could be made and what was learnt from the entire experience. 2. BACKGROUND This section provides an overview of what personalisation is and the current state-of-the-art. Because of the focus of the project, a number of current TV personalisation services available are outlined along with a description of their effectiveness and drawbacks. 2.1 Personalisation In recent years there has been an explosion in the amount of information available to the individual in the form of news, TV programmes etc. This is known as the information overload problem and the question then arises; how can relevant information be found at the right time? Personalisation tries to tackle this problem by understanding that if everyone can receive the specific information which they require, then the fact that there is so much more out there will not pose a problem. The real challenge however is that personalisation should not hide information from a user which they require, but do not specifically request. Personalisation can have some pitfalls though, due to its nature it can lead to a lack of connectedness between individuals, meaning they receive very different news articles and a diverse range of entertainment from one another. [15, DeTurk, 2002] Taking the case of TV as a specific example, the days of having only 5 channels available to us are now over and soon there will be no way of avoiding these extra channels as the analogue service is phased out. For many of us digital and cable TV already brings us much more choice with hundreds of channels and thousands of programmes to watch each day. How do we find out what is on and decide what to watch without trawling through the many pages of the TV guide (with their reduced programme information) or going to each channel one at a time (a task which no longer involves only 5 stations and 2 minutes) [12, Changing Worlds, 2002]? Electronic programme guides (EPGs) try to solve this problem by displaying, on screen, what is on in the near future but this is a task in itself as, again, many pages are needed to display all the required information for every programme on every channel. While EPGs provide some crude support from personalisation (in the form of favourite channels and basic search functions) they make no attempt to understand or learn a viewers preferences. This is the true challenge of personalisation. There are a number of different approaches to personalisation and these are outlined below. To help explain each of them I will use the internet as an example which, of course, is another victim of the information overload problem. 2.1.1 User Defined Profiles When a user visits a site they are asked to register their details and personal interests as well as providing a username and password. Once done, this information is stored in their database and the next time that user logs on to the site their details are retrieved from the database and the pages are personalised as appropriate. This approach can be seen at the Yahoo website [17]. When new visitors come to the site who have not previously registered, they are given a profile based on the most popular of registered users who shared the same signature when they originally visited the site. This is possibly the simplest form of personalisation and involves maximum user input for a successful result to be reached but can be quite effective as, once registered, each individuals requirements are specifically defined and no assumptions have to be made. 2.1.2 Collaborative Filtering Collaborative filtering is a means of delivering information that users with the same preferences have liked, rather than just similar information to what that user has viewed before. Amazon.co.uk [1] implements this form of personalisation, whereby books other users bought are recommended if similarities are found between the individuals preferences. For this approach to work, we require a function that calculates the similarity between users, this is not easy but is essential in the process. Employing this method is very useful as it maintains diversity of the content delivered, as items which do not match the users preferences can still be suggested if another similar user liked that item. In some implementations when users first visit the site they must define their preferences. [8, Maltz and Ehrlich, 1995] Two problems we encounter with collaborative filtering are that there is a delay in the recommendation process until there is sufficient profile information to match users against. Secondly, new items may not be recommended straight away until they have been viewed by a number of users. More importantly, collaborative filtering is not true personalisation as the content delivered is based on others rather than the individual in question. 2.1.3 Case Based Reasoning Case based reasoning is reasoning by remembering. New personalisation problems are solved by looking at and possibly adapting the solutions to previous problems. When a user query is received by a web site a database of the previous queries is sought looking for similarities with the new one, if any are found, they are retrieved along with their solution. If an exact match between the two queries is found the stored solution can be used. If there was not an exact match, the solution can be partially re-used or adapted according to the differences. Once this is done, the new case is added to the database so it can be used in the future. Obviously, if no matches are found in the database, then the query has to be solved using the normal process. [7, various authors] This is one of the personalisation solutions which suffer from the cold start problem, whereby at first there will be no cases in the database and therefore nothing to match new queries against. It takes a while before there are enough cases for a benefit to be noticed. Also the more cases which are added to the database the more storage space is required and the longer the matching search will take. Another couple of problems are the cost of setting up the matching process and because recommendations are made on similarity, new items tend to be similar to previous items which leads to reduced diversity. [7, various authors] 2.1.4 Rule Based In rule based filtering when users visit a site they are asked to answer a number of questions (e.g. How old are you? What is your favourite TV channel? etc). Rules which have been defined by experts in the field can then be applied to their answers to achieve the required personalisation. For this approach to be successful users have to spend a good deal of time answering the question and if this is not done correctly the wrong content may be delivered. Another problem can occur when users are forced to answer questions they do not want to and are given incorrect personalised material due to the answer they gave. Most importantly, the personalisation required must be known beforehand so the rules can be defined. In some cases this is not possible and therefore Rule Based filtering cannot be employed. [11, Ramalila, 2000] 2.1.5 Bayesian Learning In some cases it will not always be known beforehand what content to deliver to each individual, Bayesian Learning aims to tackle this problem by reasoning about any uncertainty. First relationships must be defined between any common interests. Once this is done, it then remains to assign probabilities to these relationships as to how likely the event modelled will occur. An example relationship could be that if you like football, there is an 80% chance you have an interest in sports in general. Therefore sports content could be delivered to users who show an interest in football. These probabilities are known as the Prior opinion about the relationship being true and can be assigned across the network of relationships. One of the key aspects to Bayesian Learning is that these probabilities can change to increase their accuracy once real data is received, these revised opinions of the relations are captured by the Posterior distribution of probabilities across the network. So relationships which seemed plausible originally but no longer fit the data will seem much less likely and the probabilities of events which do fit the data well will increase. [6, Neal, 2002] This approach is very useful as it allows us to make predictions about the outcome of future events when only the inputs are known, which is the cornerstone of personalisation. Bayesian Learning, in practice, can be seen in Bayesian Belief Networks which is explained in section 3.1.2. 2.2 Current TV personalisation services There are currently some services which offer personalised TV/TV listings. These are outlined below, along with an explanation of their strengths and limitations. 2.2.1 TiVo TiVo is a personal video recorder (PVR) which can be integrated with TV, video, digital and cable systems to enable you to digitally record without video tapes. The main selling point of TiVo is not personalisation per se but the so called ability to pause live TV [3, TiVo Inc, 2001]. The underlying hardware is a digital disk. PVRs are an obvious candidate for personalisation systems. TiVo is an example of this with a number of nice features. If you have watched every episode of a series and forgot about or missed one near the end, TiVo will have registered that you always watched that programme and record it for you without any request. Secondly, it uses its own Thumbs Up/Thumbs Down technology so that when you like or dislike a programme, you can give it a 1-3 thumbs up/down rating. Tivo uses this data to learn what aspects of a programme you like/dislike and can then recommend or even record programmes based on your likes and dislikes. [3, TiVo Inc, 2001] TiVos ability to recommend programmes is based upon collaborative filtering. It has a centralised database for this and relies on uploading user preferences, these are compared with data held centrally and the results are then downloaded [3, TiVo Inc, 2002]. Unfortunately, TiVo uses a very crude classification system so individual preferences are very broad e.g. when you watch a comedy TiVo assumes you like/dislike all comedies, when you may only like/dislike certain aspects. Another pitfall in the system is that it is strongly reliant on user interaction, for each programme watched the ratings button on the remote control must be pressed, if this is not done TiVo will learn nothing. Also there is no distinction between different users, so it can only really build recommendations for one user, unless they share the same likes and dislikes or work together in their rating awards. 2.2.2 Personalised TV (PTV) PTV is a web site which offers personalised TV listings to every registered user. It recognises the information overload problem with the advent of digital TV and uses its own personalisation technologies to generate TV guides to match individual viewing preferences. The more you interact with the system the more accurate your TV guide will be. PTV uses user defined profiling, case based reasoning and collaborative filtering techniques to build its guides. When users register at the site they have to complete their profile which consists of a number of sections to do with their channel availability, preferred viewing times, genre preferences etc. Users can update their preferences by re-visiting this section of the site or by grading programmes which they have watched positively or negatively. [13, Cotter and Smyth][12, Changing Worlds, 2002] Once the users likes and dislikes are known the personalisation can begin. PTV does this in two ways. Firstly (case-based), by taking a users profile and creating a schema of their preferences, this is then compared to schemas of up and coming programmes, then depending on the level of similarity, they are recommended or discarded. Secondly (collaborative filtering), their profile schemas are compared with those of other users and, if there is a strong similarity, then programmes the similar user enjoyed can be recommended. Each of these techniques on their own would not produce satisfactory results, collaborative filtering will not ever recommend one-off programmes as they will not be in anyones preferences until they are over and case based reasoning recommends similar programmes, so would result in a reduced diversity. Together though and with the aid of user defined profiles the application overcomes these downfalls. [13, Cotter and Smyth] Unfortunately PTV is only available on the web and again requires a lot of user input to be successful. It does, however, use a stronger programme classification than just genre, but it forces programmes into strict classifications (e.g. a romantic comedy must be classified as either comedy or romance). 2.2.3 Mybestbets.tv Mybestbets.tv is an online entertainment (TV shows, movies, DVDs, music etc) personalisation service powered by Choice Stream. It claims to be different from all other services in that it does not rely on collaborative filtering. Instead it uses statistical techniques to analyse and classify entertainment content in terms of attributes that users care about. It aims to understand these attributes and then relate them to user preferences. It believes in doing this, more accurate recommendations will result. [10, Changing Worlds, 2002] The system is broken down into three key areas which help it achieve its goal: The Content Analyser classifies content using both explicit and implicit attributes. Explicit attributes are those which define concrete facts about a programme, such as actors, directors etc. Implicit attributes are more difficult to define, such as how much action a programme contains, for example. These implicit attributes are assigned values through unique statistical analysis of the entertainment content. The User Profiler aims to develop a detailed profile of a users needs and preference in terms of entertainment content attributes. For example, it would not only learn that a user like comedies it would take this further to understand what type of comedy they like e.g. Black Comedy, or how much action they like in a programme. These attributes are obtained by asking a number of specially designed questions at registration and applying statistical techniques to their answers. A user profile can also be developed over time by rating programmes which the user has liked and disliked. The Recommender is the final aspect of the system and uses the attributes developed in the analyser and profiler to match a persons needs and interests, with content which they will find most interesting and entertaining. Mybestbets.tv benefits from the immediate availability of recommendations, once the initial questionnaire has been completed users attribute profiles are available. These can then be compared to up and coming programmes attributes to find matches. Also, the idea of classifying content on some rather unorthodox attributes can be of great assistance in making recommendations, users will not always be happy to define whether they just like dramas or not, as it may depend upon what the drama is about, for example is it romantic or physiological, modern or olden days etc. However, this system still requires a lot of user involvement. Even after the initial questionnaire has been completed, recommendations can be made but they will only become more accurate with time and effort. Users must define content they enjoyed and that which they did not, without this the recommender will not perform to its optimum. Although you will notice a number of similarities with this system and TV Supreme described in section 3, one major key difference still exists. Mybestbets.tv is only a web based service, unlike TV Supreme which sits in TV set top boxes and requires no user involvement, which I believe is a substantial benefit. 3. RESEARCH This section details necessary research performed to complete the project. The main research focuses on TV Supreme and the underlying technology it implements to help it achieve its goal of programme recommendation. This was done in order to get a better idea of the field in which the classifier would be used. The other necessary research concerns TV Classification systems generally, along with implementations of these, which form the test bed for the system built. 3.1 TV Supreme TV supreme is a new piece of personalisation software which is designed to sit in a digital set top box and recommend programmes for individual users that match their preferences. TV Supreme differs from current TV personalisation software (described in Section 2) in that it requires no active user involvement when learning their preferences. TV supreme is also unique in that it does not need to compare user profiles (collaborative filtering) to assist in recommendation nor does it assess viewer preferences by finding textual similarities with programme names or descriptions (case-based filtering). Instead it uses highly sophisticated algorithms based on Bayesian networks (which use Bayesian Learning techniques) and an original approach to programme classification, both of which are described below. [14, Agena Ltd, 2002] TV Supreme has three key components which aid it in achieving its goal: Programme Classifier This uses meta-tag data to describe currently available programmes and then puts programmes into fuzzy groups based on their tags. Viewer Profile As a user watches the TV the system records what they are watching (passive learning) and builds up their preferences from this using a family of Bayesian Networks. Results will be available after a few days but become more accurate with time. It can help in the process to specifically define to what level a programme was enjoyed (i.e. loved it, liked it, hated it) but this is optional and the default is casual viewing. Programme Recommender Based on the users preferences this will recommend programmes which the user will most likely want to watch. The original programme classification structure is key in TV Supreme. It differs to most classification schemas in that it is far less crude. It has many attributes which encompass numerous aspects of TV programmes e.g. How much violence a programme contains, what the Target Audience of the programme is etc. One very important feature is how the system deals with the programme genre. In most cases genre is represented by few values e.g. comedy, drama etc, which some of the time are fine but comedy, for example, covers a wide range of programmes, not all of which may be of interest to specific individuals . It is much more practical to break down popular categories into more detail. Also a programme may not be well described by one genre alone. For example, is a romantic comedy, comedy or romance? Well, the answer is both but this is not normally represented. TV Supreme however, deals with both these problems by breaking down broad genres and giving weightings to each aspect of the programme in order to make up the overall genre. For example crime is a rather broad genre so it can be broken down into specific values as required. Crime: CaperCrime: GangsterCrime: Mystery/suspenseCrime: ViolentTable 3.1: Table showing how crime genre can be broken down for better classification When a programme cannot be classified into one genre it becomes necessary to add weightings to a selection, to represent how much of each genre the programme contains. This is done as follows. Programme_IDGenreWeighting111Talk: Cosy chat0.5111Comedy: Light0.3111Celebrities0.2Table 3.2: Table showing programme genre classification Table 3.2 tells us that the programme which has ID 111 (reference to another table) has three genre aspects, it is mainly a cosy talk show but is on the humorous side and involves celebrities. Most classification systems would have given this a Talk Show genre only. Many other attributes are used in the classification schema not only Genre, Violence and Target Audience are other examples. The other attributes are also broken down for better classification and can have weightings associated with them. As can be seen, the classification of a programme is essential in TV Supremes recommendation process and the existing database used has a very rich set of attribute values (a very small portion of which can be seen above). It was my job to classify new programmes to the level at which the system is accustomed. 3.1.1 Fuzzy Logic When a problem gets so complex that it is no longer possible to make precise statements about it we have to start using Fuzzy Logic. Fuzzy Logic is a process of taking a number of unclear (fuzzy) inputs, evaluating and analysing them so weightings can be assigned to each. Once this has been done, the weighted values can be combined to form one single output that is a non-fuzzy precise value. The perfect example of Fuzzy Logic in action is the human mind itself. For example, before we go out each day, we may need to decide if we should bring an umbrella, in making this decision a number of fuzzy inputs are analysed e.g. How the sky looks outside, weather conditions at this time of year normally, the weather forecast etc. None of these are exact indicators of whether it is going to rain or not but the mind weighs them up without us even realising it and makes a clear decision. This idea of Fuzzy Logic was thought to be so useful that it was extended for use in many complex systems such as self-focusing cameras, washing machines, which change program according to how dirty the clothes are, to name but a few [2, Krantz]. The use of Fuzzy Logic is not always advertised though, as most people would not want to know that their car anti-lock break system was driven by Fuzzy Logic, as you can imagine! An input is said to be fuzzy if it cannot be measured exactly. Some people believe this is the case with everything, as even the best measuring equipment can be fractionally wrong, these technicalities are normally overlooked though. Once the inputs in a Fuzzy Logic system are known, If-Then rules, weighting and averaging can be used to turn them into an output. [2, Krantz] Fuzzy logic is of particular use in TV Supreme as many of the inputs are not known precisely. For example, we assume a user likes comedies if they watch them all the time but we cannot be 100% sure. Deciding whether a user wants to watch a particular programme uses many of these fuzzy classification inputs from programme and preference information, before deciding upon a precise recommendation. 3.1.2 Bayesian Belief Networks Bayesian Belief Networks (BBNs) are used in a wide range of decision support systems to reason about uncertainty, precisely the problem TV Supreme is trying to embrace, in the sense that it is, at first, uncertain which programmes each user would like to watch. BBNs work around the concepts of Bayesian probability and Propagation (movement of evidence both forwards and backwards through the network calculating posterior beliefs at intermediate nodes), both of which have been around for a long time. However, not until recently, have advances been made that could handle propagation in networks with a reasonable number of variables. [5, Fenton, 2002] BBNs are directed graphs that consist of a number of nodes that represent the variables and arcs to connect them, which define casual/influential relationships. Each node also has a Node Probability Table (NPT), to model the probability of each state the variable can take occurring. These probabilities can come from both historic statistical data (objective), as well as the opinion of domain experts (subjective). This is essential in TV Supreme as there is not always historic data to support all variables and relationships. BBNs have increased in popularity over recent years due to the development of applications such as Hugin, which allow you to model the structural format of the Network in a graphical way and propagate evidence where necessary. For obvious reasons these are preferred to modelling the situation using mathematical formula and prose. The main use of BBNs comes from their ability to make statistical inferences, so if some evidence about events that have occurred is known and you wish to infer the probabilities of other events that have not yet occurred from this data, this can be easily done. All that is required of the user is to enter the evidence that is known at the corresponding nodes, propagation of this evidence will then take place throughout the network, updating intermediate nodes as necessary. Once this is complete, the probabilities of the events that have not yet occurred can then be read from the network where they may be the same, more or less likely. This propagation of evidence is a very complex task involving specially developed algorithms such as Hugins Junction Tree Algorithm. Without algorithms like this, the popularity of BBNs would have never grown. [5, Fenton, 2002] BBNs do suffer from a couple of drawbacks though: There is a point at which the number of Nodes and Arcs become too large and the posterior probabilities cannot be calculated, therefore causing the system to fail. This can of course be a major problem with safety critical systems. The prior evidence, objective or subjective, must be good. If it is to optimistic or pessimistic the entire network of results can be invalid. BBNs are used in TV Supreme to model programme aspects and the preferences users have towards these aspects. With these variables, their probabilities and relationships stored in the network, it is then possible to make predictions about how likely a specific user is to watch a specific programme. This is done by applying the evidence known about each individual user (from their profile) and programme (from its classification) to the BBNs, this evidence is then propagated through the network updating probabilities where required. Once complete the probability the user will want to watch the programme will be known. Based on this value TV Supreme will calculate a recommendation score for the user-programme combination. The higher the score the more the user will want to watch the programme. Here we see again the need for the classified programmes. A small example of the TV Supreme BBN can be seen in fig 3.1, where the user currently appears to enjoy Comedy, Crime and Romance programmes equally. Now we have the base network, we can add any other evidence known from the programme classifications. Say, for example, the user had a choice of two programmes, a comedy and a crime (i.e. Comedy Available and Crime Available are set to Yes and Romance Available is set to No) and they chose to watch the Comedy (i.e. Comedy Watched is set to Yes while Crime Watched and Romance Watched are set to No). Once this evidence is added to the BBN and propagated through we can see the users preferences have updated. It shows that they like comedy more than crime programmes as they chose one over the other. Their preference toward Romance stays the same though as this type of programme was not even available, so no assumptions are made. This new updated BBN can be seen in fig 3.2. Fig 3.1: User preference network with no evidence known Fig 3.2: Updated preference network with evidence Obviously, this is only a small basic example of the TV Supreme BBN but it does demonstrate how they are used to build up user preferences based on what users watch. The BBN can be used in a similar way to recommend programmes to users based on their current preferences, along with programme classification and availability information. 3.1.3 TV Supreme Database TV Supreme uses a database to store the programme information and classifications it requires to make user recommendations. My system interacts with this database in order to get existing programme information and to add new ones. The well-defined database structure must, however, be adhered to in order for TV Supreme to use the data effectively. In order to convey the complexity of integrating with the TV Supreme scheme, let me point out that altogether there are 116 genres and 95 types of actor alone, without detailing the other attributes used. Table 3.1 shows how the crime genre is broken down into four very specific values. The communication between my system and the database has two aspects, firstly it establishes a connection to the database from Java and secondly, it retrieves and adds information as required. The first step was achieved with the use of Javas JDBC classes, these allow a connection to be made between Java and a Microsoft database with a few simple lines of code. The second requirement was achieved with the use of SQL commands. The system creates these dynamically and executes them upon the database using the established connection, the database then carries out these operations, returning the results for Java to process. SQL (Structured Query Language) is the standard language for database manipulation and I was taught how to use it in the 2nd year Database Systems course. 3.2 TV Classification Systems To ascertain what aspects of a programme a user likes requires there to be a way of classifying them. Existing approaches use a crude scheme such as DVB (European TV standard group), where each programme is placed into a category (Genre) and if a user watches a lot of programmes from a specific category, any other programme from that genre will then be recommended, with little further analysis taking place. The genres are also very broad, Film/Drama for example, encompasses a high percentage of all programmes, and films can surely have their own category. TV Supremes classification system is far richer however and, although genre is used, it is done so at a much more detailed level and is only part of the classification scheme. Other aspects of a programme that are analysed are items such as how much action the programme contains. Obviously, trying to automate this process is difficult and relies on heuristics (rules), which look at certain aspects of the programme that are known and generate a realistic full classification based on these. To define these heuristics, I had to research into a number of programme aspects and how they may relate to its classification, such as the air time, air channel and any keywords in the programme description. I then decided these programme aspects/keywords could be held in a file along with the resulting changes that should be made to the classification of the programme in question should the keywords/aspects be found. When all relevant heuristics are applied to each programme a full classification will result. I did look into methods of information retrieval (IR), which I thought may be of use in the classification process in order to allow me to extract any useful information, for example using Hidden Markov Models. This, however, looked likely to complicate the matter further for a task in which it was not essential although I did see how such techniques could be of great use. Had there been more time, using such techniques may have improved the generated classifications. What follows is an outline of two current classification systems which will form the basis of the test bed for the system built. 3.2.1 Digiguide Digiguide is a web site which displays TV listings for most main stream TV channels. My system extracts the required programme information from the HTML this site generates. Unfortunately, Digiguide has a very crude classification scheme which no where near matches that of TV Supreme. Therefore, as mentioned above, I extract as much useful information as possible from the listings. The relevant heuristics are then applied to each programme to generate the required classification. In order to do this I had to understand what information I could get from Digiguide which would be of any use, so I went to the site and noted down all the attributes they use to classify each programme. I will now outline the classification system which I had to interact with. [16] Fig 3.3. Extract from Digiguide displaying a typical listing Time: The time the programme starts Title: The full name of the programme Sub Title (optional): Holds such information as the episode name Genre: Crude class to which the programme belongs e.g. Film Description: Text based description of what the programme is about Director (Films only): Name of the director of the film Starring (Optional): Names of the actors in the programme Repeat: If the programme has been on before Subtitles: If the programme has subtitles Year (Films only): Year in which the film was made Classification (Films only, optional): British Board for Film Classification rating e.g. U Star Rating: Mark out of 5 as to the quality of the programme Some of these attribute values could be used directly in the classification of a programme, others had to be expanded upon if they did not match up to the TV Supreme standard. In these listings, the Genre attribute given can cover too wide a range of programmes, hence needed to be modified. Films, for example, can have their own genre e.g. Action, yet they are only classified as Film. Some of the attributes that are required by TV Supreme were not present here at all. In this case and when attribute expanding was required, other aspects of the programme such as its description, air time etc, had to be analysed to generate appropriate values. If this was not done, the newly classified programmes would not map successfully into the database. 3.2.2 NDS NDS is a company which provide the user interface system for Skys digital service. They are currently in talks with Agena Ltd in the hope of adding TV Supreme recommendations as one of the services they offer. It was therefore essential that the system could interact with their TV Programme classification scheme. The format in which the data is held is far simpler than that of Digiguides (described above) but suffers from the same problems in that it nowhere near matches the required level of classification. Therefore the information present (outlined below) was used in order to generate the appropriate values. Fig 3.4. Extract from an NDS listing Attributes like channel name and title are used directly in the classification, others such as the air time, genre and description are further analysed in order to generate values for all the attributes TV Supreme requires to make recommendations. 4. REQUIREMENTS This section presents an outline of the system and specifies the requirements it was hoped would be implemented. A brief discussion of how some of the system functions were implemented is shown using use case descriptions. Some of the requirements which follow were known at the beginning of the project, but as an incremental approach was being taken whereby the system was developed in stages, others were added as the project developed. 4.1 Primary System Objective This project involved classifying programmes based upon some TV listings source data and adding them, if necessary, to the pre-existing database for TV Supreme to use as required, while maintaining its rich classification system. To do this, I used an online TV listing (available at HYPERLINK "http://www.mydigiguide.com" www.mydigiguide.com [16]), which holds the standard programme information you would expect to see e.g. title, air time, description etc. Obviously, the system would work with any HTML/text based TV listing with some minor modifications but, for this project, I used Digiguide specifically as it is an available resource which presents the basic listings information. It is also possible to use the NDS file format LSV (line separated values), where the required information is held in a compressed form, with each line of the file representing a programme attribute and seven lines encompassing an entire programme. This function was provided to demonstrate the ease at which a new input format could be handled. Fig 4.1: Initial system diagram The initial system diagram above lead to the following requirements: Get programme information from source file Create meta-tag data for each programme based on the information extracted Search database for each programmes existence; mark meta-tag object if its programme has been classified previously Classify programmes based on meta-tag data using pre-defined heuristics Map new programmes into the pre-existing database Provide a user interface to allow the administrator to perform these tasks. 4.2 Extended Requirements In addition to the primary system objective and the requirements which go with it, there were a number of other requirements. These were necessary to make a more complete system and also help integration with TV Supreme. They were as follows: View, edit and delete database programme records Check underlying database structure and update mapping process appropriately Build complete programme schedule with full programme classification information Keep the system as independent of Digiguide and TV Supreme as possible Fig 4.2: Extended system diagram The modules shown in red would require modification if the system was being used in a different context to TV Supreme. The alterations to the mapper are in terms of how the programme classification data is stored in the database. As this has been done using standard SQL, should a different database be used, making the required changes would not be a complex procedure. The first part of the scheduler, where the programme data is stored in a flat file for TV Supreme to use directly in its recommendation process, would need to be changed to follow the required format, or maybe removed if it were not required. The second part of the schedule process which generates a graphical version for the user to view, would require no modification however. The final point to note is that if source data other than NDS or Digiguide were used, a small parser module is required to define how to extract the necessary programme information. This can then be easily integrated with the source independent parser so the rest of the process remains unaffected. 4.3 Classifications The complexity of producing rich classifications is hard to covey in words. Therefore, fig 4.3 and 4.4 show example classifications for the programmes Animal Park and Deep Space Nine. Here it is possible to see that, from the small amount of information in the Title, Genre and Description, detailed classifications which successfully capture the programmes were produced. The aim of the project was to produce such classifications for all the programmes in the listings file. SHAPE \* MERGEFORMAT Fig 4.3: Programme classification for Animal Park SHAPE \* MERGEFORMAT Fig 4.4: Programme classification for Deep Space Nine 4.4 Use Case Diagram Use case diagrams use scenarios to capture and detail requirements. They use plain English and contain no system speak, so can be easily comprehended by the user. Once the use cases are outlined, they are expanded upon to form a step by step walkthrough of how the system will meet each requirement. All the individual use cases together form the system boundary, therefore interaction between the users (Actors) of the system and the use cases is shown in a very simplistic manner. Fig 4.5. TV Programme Classification System Use Case Diagram As can be seen there are six Use Cases in the system and, as mentioned above their operations can be described in detail. The descriptions to two of the main use cases, namely Parse Programme Data and Create new database entries for programmes, are shown below, the rest can be found in the HTML design documentation available on the project CD. SHAPE \* MERGEFORMAT Fig 4.6: Parse Programme Data Use Case Description SHAPE \* MERGEFORMAT Fig 4.7: Create New Database Entries Use Case Description 5. DESIGN This section details the system design; I will start with a comprehensive specification of the system architecture, which will lead on to an examination of how the system was designed to implement the required functionality. Further explanation of the design of the main aspects of the system will then be discussed such as the Parser, Matcher, Mapper and Scheduler. Finally, I will outline the user interface so a basic idea of how the system will operate can be gained at an early stage. 5.1 The UML Approach UML (Unified Modelling Language) is a collection of best engineering practices which have proven successful for modelling complex systems. In full, it is used to specify, visualise and document software. There are a number of different ways of modelling systems all with their own approach and notation. UML was created to standardise the process and is specifically geared toward the analysis and design of object oriented systems. It was therefore an ideal process to follow. UML has a number of steps, developing Use Case diagrams is part of the process and is dealt with in section 4.4, the other steps which I used are outlined in the following sections along with the results for these in relation to my system. 5.1.1 Class Diagram Once the system functionality had been outlined, the next step involved developing a class diagram to show the internal structure of the system. This maps directly into an object oriented programming language such as Java. Class diagrams are derived from the use case descriptions by analysing the nouns and verbs, nouns represent the classes, attributes or actors and verbs correspond to the methods (behaviours) the classes will have. Additional classes were added as helper classes (perform some function for one of the main classes) and other methods/attributes were added as required in implementation. Fig 5.1 shows the main classes that were required in the implementation of this system, helper classes, attributes and operations have been omitted for clarity. However, the full class diagram (with all classes, methods and attributes) can be found in the HTML design documentation available on the project CD. The full design of the Parser class can also be seen below to demonstrate how the other classes look and therefore why they were omitted. Fig 5.1. The Classifier Package Class Diagram Fig 5.2: Parser Class Design A package for the GUI is also used to allow the user to interact with the system and the system to interact with the functions of the Classifier API. This has a somewhat simple class diagram consisting of one main class and a number of helper classes. It is therefore not shown at this stage but can be found in the HTML design documentation on the project CD. 5.1.2 Sequence Diagrams Sequence diagrams show the dynamic interactions between the actors and classes, and between the classes themselves. There is one sequence diagram for each use case as they show how the system functions described are implemented using the methods and classes outlined in the class diagram. The sequence diagrams for two of the main use cases Parse Programme Data and Create New Database Entries for Programmes are shown in figs 5.3-5.5. The rest of the sequence diagrams for the other use cases can be found in the HTML design documentation on the project CD. Fig 5.3: Parse Programme Data Fig 5.4: Create New Database Entries for Programmes Fig 5.5: Create New Database Entries for Programmes Alternate Flow 1 5.2 Core Functionality I will now outline the design of the key functions of the system, namely the parser, matcher, mapper and scheduler, followed by a brief description of the user interface. 5.2.1 Parser Fig 5.6 shows an extract of Digiguides HTML data from which I had to extract as much programme information as possible. SHAPE \* MERGEFORMAT Fig 5.6: Digiguide HTML programme extract It is important to note that: HTML is purely text based and is constructed from many predefined tags each of which have a purpose, a Tag is enclosed in angled brackets such as
, the tag p indicates that a new paragraph should be inserted at this point. Some tags need to be ended, for example at the conclusion of a paragraph we must put
which indicates the closure of the paragraph tag. There are many other tags such as in these cases). I then went on to define methods which, when called, iterate through the array of attributes for a particular tag looking for a match to the tag/attribute value currently being parsed. If one is found a string detailing the match is stored. The text of these tags is then be dealt with as required based on the stored string.
The second class Parser performs the main functions associated with the parsing process, although some of this was tackled by the Java HTML parsing kit. Java deals with the processing of the specified file and calls the following methods as appropriate when different parts of the HTML structure are encountered: handleStartTag(), handleEndTag(), handlesimpleTag(), handleText(), handleError(), handleEndOfLineString(), handleComment(). I however had to write these methods so that the HTML was processed as required, meaning not all of the methods needed implementing as the structure they represent had no relevance in my system. The basic idea was that, when a tag was encountered, the appropriate method would be called, I would then use the TagData class to check if the current tag needed to be processed. If this were the case, a variable would be set so that when the handleText() method was called for its corresponding tag, the text could be processed accordingly. Handling the text involved creating new MetaTag objects (hold data about each programme) for each programme and storing the extracted information as required, such as programme title, start time etc.
The implementation of the LSV parser required the addition of an If statement in the Parser class to check the requested files extension and apply the above parsing process if it was html, otherwise the simple LSV parser could be used. For this, each line of the file is taken in turn and stored, as appropriate, in the current MetaTag object. Every seven lines the process starts again until there are no programmes left to parse. The TagData class was not required by the LSV parser.
Once the selected file has been fully processed by the required parser, one last task remains. This is to check each parsed programme against all of the others to see whether they are on more than once in that listing. If this is the case, they are flagged so they can be treated as one programme, where required, in the rest of the classification process.
6.3 Matcher
The matcher has one task and that is to check each MetaTag programme with every entry in the database looking for a match. If one is found, it means the programme has already been classified and therefore does not need to be analysed further until creation of the schedule. The match conditions were described in the design section and I will now outline how these were implemented.
First of all the database is queried for all the required programme information, once this is done, each of the MetaTag objects is taken in turn and is run through the matching algorithm. For each processed MetaTag programme, one of the following four outcomes occurs:
If a strong match (all required attribute matches are present) is found, a reference to the Title ID of the matching database programme is stored in the MetaTag object
If a weak match (not all required attributes matches are present) is found the Title ID reference is stored but a flag is set. Therefore the programme can be checked with the administrator to see if they agree with the match.
If no match is found the MetaTag object has a flag set depicting it as a new programme
A MetaTag object is also flagged if more than one match is found. Whether they are strong or weak, reference to each of the matching database Title IDs are stored. The administrator then deals with this choice.
Once this process is complete each of the flagged objects (case 2 & 4 above) are taken in turn. If there is more than one database match (case 4), they are all displayed to the administrator for them to select which, if any, bear the strongest resemblance to the given programme. If they select none of the records, the next flagged object is dealt with. Otherwise, the full classification of the selected record is retrieved from the database and displayed to the user so they can analyse the match in full. At this stage, they can choose to accept the suggested match, mark the MetaTag programme as new, or inherit all the attributes of the suggested match into a new database record, which can be manipulated later as required. This may be done if most of the attributes of the new programme are the same, but the administrator wanted to make some changes while still keeping the old record as it is.
Clearly, if there are a number of strong matches, the administrator will only have to pick which one to accept. They will not then have to view the full classification to decide if there is a match. Also, if there is only one match found, the administrator will be shown the full classification straight away and will then select one of the described options. Once all flagged programmes have been dealt with, the matching process is complete.
Each flagged meta-tag object is retrieved by the GUI with a call to the nextFlag() method of the matcher class. This returns the next flagged MetaTag object in the sequence along with the required database attributes of the matching record and a reference to why it has been flagged. The GUI then deals with the flagged object, as required, and depending upon the option selected by the administrator, the appropriate method is called by the GUI to the Matcher class e.g. markAsNew(), inheritMeta(), acceptMeta() etc. This has to be done for all flagged meta-tag objects to achieve the desired matching results.
6.4 Mapper
The mapping process is implemented in a number of steps, which can be outlined as follows:
Firstly, the heuristics are read in from the XML files and stored as HeuristicTransformation objects, this is done using the same principals as that of the HTML parser but for XML instead. By using some of Javas XML libraries the raw text processing is taken away from me, I must then define how to handle each tag and what to do with its associated text. Therefore, when the required tags are met their text is extracted and stored, as appropriate, in the current HeuristicTransformation object. This is done for every heuristic in the given files. A small example of one of the keyword heuristics is shown in fig 6.1. In this case the keyword Alien is the condition which must be met for the heuristic to be applied to the specific programme and the other tags/value combinations, represent the changes to the classification which should be made.
Fig 6.1: Example of a keyword heuristic
Each of the MetaTag objects obtained by the parser is taken in turn. If they have their newProgramme flag set then the operation which builds a classification is called.
A Programme object is then created to hold the new classification. First the channel name the programme is being aired on is retrieved from the MetaTag object and checked against each of the channel heuristic conditions (channel names). If a match is found, that heuristic is then applied. Next, the heuristic is checked to see if it has any time period heuristics associated with it. If this is the case, the air time of the current programme is obtained from its MetaTag object and checked against each of the time period conditions. If it is within any of these periods, then the corresponding heuristics are applied. Each time a new heuristic is executed, the classification of the current programme changes.
Next the programme description, title, and category are retrieved from the MetaTag object, tokenised (split up into individual words) and stored in an array list. Each keyword heuristic is then taken in turn and its keyword/word pattern condition checked against each of the tokenised words in the array list. If a match is found, the corresponding heuristic is applied to the current Programme object.
Once steps 3 and 4 above have been done for all new programmes, they are ready to be added to the database. Before this happens I first display each of the suggested mappings to the user for them to modify, if need be, one at a time. When they are satisfied with the current mapping they can submit it. Upon submission, the programme object (the classification) is checked to make sure the stored attributes are within the valid range. If not, they are normalised so they are as close to the users request as possible, whilst being valid. SQL commands are then generated for the programme and executed upon the database, resulting in the new programme and its classification being added. The next mapping is then displayed. If, however, before submitting the mapping the user believes there is a matching classified record in the database, which may have been missed, they can search for that record themselves and, if found, can ask for a direct match to be made between the current programme and the database record, or the database record can be inherited (as described in 6.3) into a new record and the modifications which the user felt were needed can be made to this new record at the end of the Mapping process. Obviously, in these cases the suggested classification is then discarded as a previous classification is being used.
Fig 6.2: Screenshot from the mapping stage
This presentation of the mapping is done for each of the newly classified Programmes, in turn, until all have been added to the database. The mappings do not have to be shown to the user, they can simply be added after the initial classification process is complete. However, by giving the user a chance to check and change them, you ensure the correct classification is achieved. Once all new programmes have been added to the database the Mapping process is complete.
6.5 Scheduler
The final step in the process is the creation of the programme schedule, which directly allows TV Supreme to use the classified programmes in its recommendation process. This basically involves writing the programme data out to a text flat file which TV Supreme can interface with, the structure of the file is explained in section 5.2.4. The process is described below:
Firstly, any control information which is needed for the schedule to conform to its structure is retrieved from the Database and stored, such as which classification attributes are active (currently used in the recommendation process), how many values represent each classification attribute (Target Audience has 5, Adult, Infant.) etc.
Next a check is made to see if a schedule file for the current programme listings date already exists (there is only one file per day, i.e. Sunday2ndFebuary.rec, which will contain all the programmes that will be shown that day). If this is the case, its header information must be altered before the new programmes can be added. Otherwise a new file can be created without dealing with any other concerns. Below is the code which performs this check.
this.currentFile = new File(date+".rec");
if(this.currentFile.exists() == true){
//Deal with the case that the file exists and new data must be added to it
}
else{
//The file does not exist and a new one must be created
}
In the case that a new file is required it is created with the appropriate name (ListingsDate.rec), and then the required header information is written to it, such as the number of programmes in the file, control information such as the number of attributes used to classify each programme etc. Once this is done, each of the programmes parsed from the TV listing is taken in turn. The relevant data must be compiled so it can be added, in the correct format, to the schedule file for the current programme.
If the current parsed programme has been classified by the system itself a lot of this information is readily available. If, however, the programme was matched with a pre-existing database entry, this information is retrieved from the database itself using SQL commands. Once known, the programme data and classification is added to the file, adhering to the structure and using the control information where appropriate. Below are some examples of the content which is added to the schedule for each programme.
out.println(new Long(p.getDatabaseID()).toString());//The title identifier for the programme
out.println(mt.getProgrammeTitle());//The name of the programme
out.println(p.getDVBGenre());//The DVB genre of the programme (one of 11 pre-defined values)
out.println(new Long(p.getYear()).toString());//The year the programme was made
out.println(mt.getProgrammeDescription());//The programme description.
out.println("^^");//Character sequence signifying the end of the programme's description
Once this has been done for all parsed programmes, the schedule file is complete and ready for use by the TV Supreme system.
Where a file for the required date already exists, the procedure is slightly different. First of all, the header information relating to the number of programmes stored in the schedule is modified to take account of the new programmes which are about to be added. Once this is done, each new programme is individually added to the end of the schedule, using the same procedure described above.
As an extra function, I decided to display the schedule graphically to the user to allow them to check the success of the entire process. This is done by presenting the user with a time line of the programmes which have been parsed, matched and mapped. They can then select any of these programmes and have its details presented to them, such as title, start time, duration, description etc and its full classification. Once the user is happy with the schedule, the process is complete and the system will return to the main menu.
Fig 6.3: Screenshot from the Schedule stage
7. TESTING
This section describes the range of testing done by myself in order to discover the existence of any faults. I will then explain how I went about correcting them in order to deliver a reliable bug free system. I employed a number of testing techniques namely, use case testing, black box testing and finally validation testing.
7.1 Use case testing
Use case testing involved looking at the normal and alternate flows of each use case and making sure that whatever path a user may take they would not encounter any bugs. A brief summary of my investigation for each use case can be found below.
7.1.1 Parse Programme Data
This stage of the system was rather error free. The problems experienced were more in the form of missing data. At first when dealing with HTML files, I was not extracting all the required information correctly. Upon selecting a file and completing the parsing process, I would print out the state of the newly created MetaTag objects, in order to make sure everything had been extracted correctly. In doing this, I realised the date and channel information had not been stored. This was because I had failed to add their tag details as one of the search criteria in the TagData class. A few simple additions were made to the code in order for the Use Case to be complete. The Tag data for the date and channel name I was failing to extract is re-visited below:
Date: Monday 25th November
Channel: BBC 1
7.1.2 Search for Pre-existing Programmes
This Use Case threw up an interesting problem in that the system would sometimes find a match for a parsed programme which it was certain about (strong match), and another which it was not (weak match). In this situation where more than one match had been found, the system took the correct course of action, which was to flag the programme for user review. I later realised, as the system had found a strong match, there was no need to ask the user which to use. I therefore modified the code so that when strong and weak matches were both found for one programme, the weak ones would be discarded. The table of outcomes depending on the matches found can be seen in table 7.1.
ProgrammeStrong MatchWeak MatchActionEastenders, 2002Eastenders, 2002Eastenders, 1998Eliminate weak match and move to next programmeTitanic, 1998Titanic, 1998----------------------Move to next programmeFriends, ????---------------------Friends, 2002Flag for user reviewSmallville, ????-------------------------------------------Flag as new programmeTable 7.1: Matchers actions
I obviously had to carefully check the database when I received the output data on the matches the system had found in order to be confident it was working correctly, not missing any matches and not finding ones which did not exist. Not until this had been done a number of times was I satisfied.
7.1.3 Create new database entries for programmes
This was the most complex Use Case to test and was done over a long period of time. In fact due to the nature of the system, to get to the end stages, you had to complete the preceding ones. This meant the system was quite thoroughly tested on a daily basis. At first, I dealt with some minor problems with the XML heuristic extraction process, whereby some attribute values were being stored in two parts when they should have been stored as one, e.g. Adult=1.0 (indicates the programme is solely aimed at Adults) was being broken up into Adult and =1.0., as was the problem with many values with the same structure. I rectified this problem by adding a constraint so attributes like this one would not be stored unless they contained the = character.
The majority of the testing came once the classifications were being displayed, some of the attribute values (Comedy, Crime etc) were not being recognised. I realised this came down to the very small problem of mismatches between the spelling of the values in the Database and those in the heuristic files. Although this could solved for the current heuristics, should the user add more at a later date, the same problem could re-occur. I therefore added an error message informing the user to check the heuristic files if any spelling mismatches were found.
The final big problem I had was with the generated classifications, where parent and child attribute values were occurring together, which was not permitted. For example, Sports: Football and Sports: Golf are children of the Sports genre. I therefore had to add a method which checked the classification (both before it was displayed to the user and before it was added to the database) and added the weighting of a parent attribute to its child (the child attribute more specifically define the programme). An example can be seen in fig 7.1.
Fig 7.1: Parent-Child classification example
7.1.4 Build Complete Programme Schedule
This Use Case was the easiest to test for two reasons:
The generated schedule file could be opened in TV Supreme, if any errors occurred then the schedule had not been created correctly, otherwise the process was fine.
The visual schedule presented to the user could be immediately compared to that of Digiguide to make sure everything was correct. An example comparison can be seen in fig 7.2.
The one problem I did have was, as suggested, highlighted by TV Supreme. It appeared I had inadvertently started the counting of attribute values at 1, when it should have been 0, this meant when the file was opened by TV Supreme an IndexArrayOutOfBounds exception occurred.
Fig 7.2: Digiguide to TV Class schedule comparison
7.1.5 Edit programme database
In implementing this use case I encountered many problems with the use of SQL. Fortunately, I could normally solve them by looking at my notes from the Database Systems course, looking on the web or Posting questions on the comp.lang.java.database newsgroup. These errors were normally caused through my misuse of the SQL syntax. Although this function threw up a number of errors they would later save me time in the implementation of other functions, which required the same techniques, i.e. Matching and Mapping.
7.2 Black box testing
For these sets of tests I gave the system to a number of family members and friends. Armed with only small details of what I had been doing in the past six months and the system user manual, I asked them to play with the system and try as many of the functions as possible. This allowed me to get a good idea of how operational personnel would use TV Class and any problems they might encounter. I asked the testers not to hold back and to really try and break the system, this way I would be in a better position to discover any remaining faults and, subsequently, rectify them. I have listed some of the feed back comments I received in table 7.2. These ranged from parts of the user manual which were not fully comprehended, right to sequences of events which caused the system to crash.
ID
Comment: I was unsure how to use the system help function, I tried using the F1 key as indicated but this did not seem to work. I also noticed two Help buttons available on each page but wasnt sure how they were different.
3Action: I realised I had not activated the F1 key to open the system help. I therefore made the required changes. I also clearly defined the Help functions in the user manual.
7Comment: In the Map function I was shown a new programme classification. I altered it until I thought it represented the programme correctly, I then pressed the Submit Mapping button. I expected the next programme classification to appear, this did not happen and no matter what I did I could not get off the current page.Action: Looking at the users print screen, which I asked them to save if they encountered any problems like this, I discovered they had not entered a weighting for one of their attribute values. I therefore thought it best to add an error message if this happened to assist them in discovering their mistake.
14Comment: After I had parsed a TV Listing, I pressed the match button expecting some matches to appear. However, nothing happened and the Match button was now greyed out and the Map button was available. I was not sure if something had gone wrong.Action: Although not obvious to the user, this would happen if no matches were found between the parsed programmes and the pre-existing database programmes. I therefore decided to add a small summary box to the Create a Schedule menu, which would inform the user what the system had just done, i.e. in this case the Summary box would say, The Matching process is complete.Table 7.2: Example black box testing results
There were many of these reports and I have only added a few here to give an idea of what happened in the black box stage.
This type of testing is essential for a number of reasons, maybe the most important of which are as follows:
Employing testing techniques which only involve the individual/team which designed and implemented the system can be very dangerous. A lot of the time they will be very bad testers as will only tests parts of the system which they know work, while being very reluctant to cause the system to malfunction, even if they know this is possible.
Allowing people who have a working knowledge of programming and computer science to test a system will not accurately mimic its intended use, by potentially computer illiterate individuals.
Hence it was best to use testers who knew nothing about the implemented system and also those who did not have a strong computing background.
7.3 Validation Testing
The above sections deal with the verification of the system, i.e. checking it meets the requirements. In order to discover the quality (validation) of the programme classifications produced (fig 7.3 shows an example classification), my supervisor Prof Norman Fenton and a number of other members of the RADAR group tested the system. Their general consensus of the classifications was that they were very accurate. This was important as a system that works but does not meet any quality requirements is almost useless.
SHAPE \* MERGEFORMAT
Fig 7.3: Programme classification for Roseanne
Another system quality indicator is its performance. If, for example, certain functions take an inordinate amount of time to complete, then the system will be of very little use. I did therefore place a number of time constraints on certain system operations, so they should finish their execution in a pre-defined time, this sometimes depended upon the number of TV Listings programmes in the process. A table of these constraints followed by the average system performance is shown below. The run-time timing information was achieved through using Javas Time class.
ConditionExpected TimeAverage Time35 Programmes60 Programmes35 Programmes60 ProgrammesParsing process1 s1.5 s314 ms344 msMatching process0.5 s0.75 s264 ms351 msMapping process3 s5 s2.3 s4 sScheduler1 s1.5 s1 s1.3 sTable 7.3: Efficiency testing results
As can be seen, the average times are all within the valid range, meaning the system met its performance requirements.
7.4 Requirements Tractability
Looking at the requirements outlined in sections 4.1 and 4.2, there are a couple of points which need clarifying with regard to numbers 8 and 10.
Requirement 8 talks about having the functionality to check the database structure and update the mapping process where necessary. Although this is not done explicitly, I do support structural changes by holding the heuristics in a user editable file. This allows users to add support for any new attribute values in the database simply by adding them to the heuristic files where appropriate. For example, if a new Genre Atomic Football was added to the database, this could be added to any keyword or channel heuristics as you would any other, 19:30
Coronation Street (Soap)
Ken's fury finally boils over and he violently lashes out at Ade. Richard receives the news he's been pinning his hopes on. Roy is astonished when Vera nails her colours to the mast
Starring: William Roache, Dean Ashton, Brian Capron, David Neilson, Liz Dawn
(Widescreen, Subtitles) (Visit the Official Web Site)