Computer Science › Section J · Database systems › Topic J.7
Data mining, big data, and NoSQL
A query answers the question you ask; data mining finds patterns you never thought to ask about. As data has grown too large for one machine, new ways of storing and processing it have grown up too.
Finding what nobody asked for
An ordinary database query retrieves stored facts: which loans are overdue, which customers live in Ohio. Data mining instead searches large collections for previously unknown patterns: that customers who buy one product tend to buy another, or that certain transactions look like fraud. It is used in marketing, lending, fraud detection and science, where it helps biologists find patterns in DNA and proteins, part of the field called bioinformatics. It grew out of statistics applied to large, varied data sets, and many argue it belongs as much to statistics as to computer science.
Data warehouses and data cubes
Mining usually runs on a data warehouse rather than on the live, operational database. A warehouse is a static collection, often a snapshot of one or more operational databases, gathered for analysis. Patterns are far easier to find in data that stays still, and heavy analysis would slow the live systems people depend on. Warehouse data is often arranged as a data cube, data viewed along several dimensions at once: sales by product, by store and by month, for instance. Slicing it one way compares stores; slicing another follows one product through the year.
Describing and discovering groups
Several forms of data mining deal with groups. Class description finds the properties that characterise a known group, such as what typical buyers of electric bicycles have in common. Class discrimination finds properties that separate two known groups, such as what distinguishes customers who renew a gym membership from those who cancel. Cluster analysis goes further and discovers the groups themselves: given the arrival times and spending of a café's customers, it might reveal two clusters, early commuters buying a single drink and late-morning groups ordering food. Description and discrimination start from known classes; clustering finds new ones.
Links, oddities and trends
Association analysis looks for items or events that occur together, such as products bought in the same shopping basket. Outlier analysis looks for entries that break the usual pattern. It can expose errors in the data, or fraud: a bank card used for months in one town that suddenly makes ten purchases abroad in an hour. Sequential pattern analysis looks for patterns over time, such as seasonal swings in electricity demand or the order in which students tend to drop out of a course. Such patterns often feed predictions: a new case that resembles a group will probably, not certainly, behave like it.
Worked example: an association rule
A shop studies 10 baskets: 5 contain pasta, 6 contain sauce and 4 contain both. Test the rule "pasta → sauce". Steps: (1) Support, how often the items appear together: 4 of 10 baskets, or 40%. (2) Confidence, how often baskets with pasta also hold sauce: \(4/5 = 80\%\). (3) Compare with sauce's overall rate, \(6/10 = 60\%\). Buying pasta raises the chance of sauce from 60% to 80%, so the rule carries information; the ratio \(0.8/0.6 \approx 1.33\) is called the lift. (4) Reverse the rule: "sauce → pasta" has confidence \(4/6 \approx 67\%\). Confidence depends on direction, so the two rules are not the same. (5) Ten baskets give only a hint to test on more data.
Pattern or coincidence?
Finding patterns is the easy part; judging them is hard. Search enough data and some patterns will appear purely by chance. Test thousands of product pairs and a few will seem linked by luck, such as umbrellas and birthday cards selling together one month; a camping shop's finding that tent buyers often buy head torches has an obvious reason and may well be worth acting on. Analysts check whether a pattern holds on fresh data and has a sensible reason. Mining also raises ethical questions about the rights of the people in the data and the accuracy of conclusions about them, as "Social impact of database technology: privacy" discusses.
Big data and MapReduce
Big data means data too large, too fast or too varied for traditional single-machine tools: the three Vs of volume, velocity and variety. Such data is spread over many machines. Distributed file systems split files into blocks and store copies of each block on several servers. Processing frameworks then send the work to the data. MapReduce, popularised by a Google paper in 2004 and widely used through the open-source Apache Hadoop, splits a job into a map phase, run in parallel on every machine, and a reduce phase that combines the results. Apache Spark later sped this up by keeping data in memory.
Worked example: counting words with MapReduce
Machine 1 holds the text "red fish blue fish" and machine 2 holds "blue sky red sky red". Count each word. Steps: (1) Map: each machine, in parallel, emits a pair (word, 1) for every word it holds. Machine 1 emits (red, 1), (fish, 1), (blue, 1), (fish, 1). (2) Shuffle: the framework gathers pairs with the same word together, so red receives [1, 1, 1], fish [1, 1], blue [1, 1] and sky [1, 1]. (3) Reduce: for each word, add its list. (4) Result: red 3, fish 2, blue 2, sky 2. (5) Check: the texts hold 4 + 5 = 9 words, and 3 + 2 + 2 + 2 = 9. The same phases scale to thousands of machines.
NoSQL databases
NoSQL, often read as "not only SQL", covers databases that relax the relational model for flexibility or scale. Key-value stores, such as Redis, map each key to a value and answer lookups very quickly. Document databases, such as MongoDB, store JSON-like documents whose structure may vary from one record to the next, much like nested objects. Wide-column stores, such as Apache Cassandra, spread enormous volumes of writes across many machines. Graph databases, such as Neo4j, store nodes and the relationships between them, which suits highly connected data like social networks. Many scale out by adding machines rather than buying one bigger server.
Consistency or availability
Spreading data over many machines brings a hard trade-off. The CAP theorem, conjectured by Eric Brewer in 2000 and proved by Seth Gilbert and Nancy Lynch in 2002, says that when a network partition cuts some machines off from others, a distributed system cannot guarantee both consistency, every read seeing the latest write, and availability, every request getting an answer. It must give up one until the partition heals. Many large NoSQL systems choose availability and accept eventual consistency, where copies may briefly disagree but converge once updates spread. A social network can tolerate a like count that lags for a second; a bank's balances usually cannot, so banks favour consistency.
Common mistakes to avoid
Treating data mining as ordinary querying: a query fetches known facts, while mining seeks unknown patterns. Confusing class description, which studies a known group, with cluster analysis, which discovers the groups. Reading confidence as support, or assuming a rule works the same in reverse. Trusting a pattern without checking it on fresh data. Thinking NoSQL means no query language at all; many NoSQL systems have rich query languages. Reading CAP as "pick any two at all times": the choice is forced only during a partition.
Key takeaways
Data mining discovers previously unknown patterns, usually in static data warehouses viewed as data cubes. Its forms include class description and discrimination, clustering, association (measured by support and confidence), outlier and sequential pattern analysis. Patterns must be tested, because some are coincidences. Big data is defined by volume, velocity and variety, and frameworks such as MapReduce and Spark process it in parallel. NoSQL databases are key-value, document, wide-column or graph stores, and the CAP theorem forces a choice between consistency and availability during a partition.
Flashcards
Flashcard
Discovering previously unknown patterns in large data collections
Test your understanding
Question 1 of 5
Of 20 baskets, 8 contain bread, 10 contain butter and 6 contain both. What is the confidence of the rule bread → butter?
Question 2 of 5
A café's customer records are analysed with no groups given in advance, and two customer groups emerge. Which form of data mining is this?
Question 3 of 5
Why is data mining usually run on a data warehouse rather than the operational database?
Question 4 of 5
In a MapReduce word count, what does the shuffle phase do?
Question 5 of 5
During a network partition, a distributed store keeps answering every request but some reads return slightly old values. What has it chosen?
