Big Data Tutorial V4
•Download as PPTX, PDF•
19 likes•28,209 views
Marko Grobelnik, Blaz Fortuna, Dunja Mladenic International Semantic Web Conference (ISWC) 2013, Sydney
Recommended
More Related Content
What's hot
What's hot (20)
Similar to Big Data Tutorial V4
Similar to Big Data Tutorial V4 (20)
Recently uploaded
Recently uploaded (20)
Big Data Tutorial V4
- 1. Marko Grobelnik, Blaz Fortuna, Dunja Mladenic Jozef Stefan Institute, Slovenia Sydney, Oct 22nd 2013
- 2. Big-Data in numbers Big-Data Definitions Motivation State of Market Techniques Tools Data Science Applications ◦ Recommendation, Social networks, Media Monitoring Concluding remarks
- 11. „Big-data‟ is similar to „Small-data‟, but bigger …but having data bigger it requires different approaches: ◦ techniques, tools, architectures …with an aim to solve new problems ◦ …or old problems in a better way.
- 12. Volume – challenging to load and process (how to index, retrieve) Variety – different data types and degree of structure (how to query semistructured data) Velocity – real-time processing influenced by rate of data arrival From “Understanding Big Data” by IBM
- 13. 1. Volume (lots of data = “Tonnabytes”) 2. Variety (complexity, curse of dimensionality) 3. Velocity (rate of data and information flow) 4. Veracity (verifying inference-based models from comprehensive data collections) 5. Variability 6. Venue (location) 7. Vocabulary (semantics)
- 15. Comparing volume of “big data” and “data mining” queries
- 16. …adding “web 2.0” to “big data” and “data mining” queries volume
- 17. Big-Data
- 19. Key enablers for the appearance and growth of “Big Data” are: ◦ Increase of storage capacities ◦ Increase of processing power ◦ Availability of data
- 31. Source: WikiBon report on “Big Data Vendor Revenue and Market Forecast 2012-2017”, 2013
- 35. …when the operations on data are complex: ◦ …e.g. simple counting is not a complex problem ◦ Modeling and reasoning with data of different kinds can get extremely complex Good news about big-data: ◦ Often, because of vast amount of data, modeling techniques can get simpler (e.g. smart counting can replace complex model-based analytics)… ◦ …as long as we deal with the scale
- 36. Research areas (such as IR, KDD, ML, NLP, Se mWeb, …) are subcubes within the data cube Usage Quality Context Streaming Scalability
- 37. A risk with “Big-Data mining” is that an analyst can “discover” patterns that are meaningless Statisticians call it Bonferroni‟s principle: ◦ Roughly, if you look in more places for interesting patterns than your amount of data will support, you are bound to find crap
- 38. Example: We want to find (unrelated) people who at least twice have stayed at the same hotel on the same day ◦ ◦ ◦ ◦ ◦ 109 people being tracked. 1000 days. Each person stays in a hotel 1% of the time (1 day out of 100) Hotels hold 100 people (so 105 hotels). If everyone behaves randomly (i.e., no terrorists) will the data mining detect anything suspicious? Expected number of “suspicious” pairs of people: ◦ 250,000 ◦ … too many combinations to check – we need to have some additional evidence to find “suspicious” pairs of people in some more efficient way Example taken from: Rajaraman, Ullman: Mining of Massive Datasets
- 39. Smart sampling of data ◦ …reducing the original data while not losing the statistical properties of data Finding similar items ◦ …efficient multidimensional indexing Incremental updating of the models ◦ (vs. building models from scratch) ◦ …crucial for streaming data Distributed linear algebra ◦ …dealing with large sparse matrices
- 40. On the top of the previous ops we perform usual data mining/machine learning/statistics operators: ◦ Supervised learning (classification, regression, …) ◦ Non-supervised learning (clustering, different types of decompositions, …) ◦ … …we are just more careful which algorithms we choose ◦ typically linear or sub-linear versions of the algorithms
- 41. An excellent overview of the algorithms covering the above issues is the book “Rajaraman, Leskovec, Ullman: Mining of Massive Datasets” Downloadable from: http://infolab.stanford.edu/~ullman/mmds.html
- 43. Where processing is hosted? ◦ Distributed Servers / Cloud (e.g. Amazon EC2) Where data is stored? What is the programming model? ◦ Distributed Storage (e.g. Amazon S3) ◦ Distributed Processing (e.g. MapReduce) How data is stored & indexed? ◦ High-performance schema-free databases (e.g. MongoDB) What operations are performed on data? ◦ Analytic / Semantic Processing
- 45. Computing and storage are typically hosted transparently on cloud infrastructures ◦ …providing scale, flexibility and high fail-safety Distributed Servers ◦ Amazon-EC2, Google App Engine, Elastic, Beanstalk, Heroku Distributed Storage ◦ Amazon-S3, Hadoop Distributed File System
- 46. Distributed processing of Big-Data requires non-standard programming models ◦ …beyond single machines or traditional parallel programming models (like MPI) ◦ …the aim is to simplify complex programming tasks The most popular programming model is MapReduce approach ◦ …suitable for commodity hardware to reduce costs
- 47. The key idea of the MapReduce approach: ◦ A target problem needs to be parallelizable ◦ First, the problem gets split into a set of smaller problems (Map step) ◦ Next, smaller problems are solved in a parallel way ◦ Finally, a set of solutions to the smaller problems get synthesized into a solution of the original problem (Reduce step)
- 48. Google Maps charts new territory into businesses Google 4 Google selling new tools for businesses to build their own maps Maps 4 Businesses 4 New 1 Google promises consumer experience for businesses with Maps Engine Pro Charts 1 Territory 1 Tools 1 … Google is trying to get its Maps service used by more businesses
- 49. Google Maps charts new territory into businesses Google selling new tools for businesses to build their own maps Businesses Charts Maps 2 1 … Google promises consumer experience for businesses with Maps Engine Pro Businesses 2 Engine Map 2 Google is trying to get its Maps service used by more businesses 1 Territory Map 1 2 1 Maps 2 Service 1 …
- 50. Businesses 2 1 Task 1 Businesses 2 Charts Charts 1 … Maps 2 Territory 1 Businesses 2 Engine 1 … … 2 Engine Task 2 Businesses 1 Maps 2 Service 1 … Reduce 1 Split according to the hash of a key In our case: key = word, hash = first character Maps 2 Territory 1 … Maps 2 Service 1 … Reduce 2
- 52. We concatenate the outputs into final result Reduce 1 Businesses 4 Charts 1 Businesses 4 Engine 1 Charts 1 Engine 1 … … Reduce 2 Maps 4 Maps 4 Territory 1 Territory 1 Service 1 Service 1 … …
- 53. Apache Hadoop [http://hadoop.apache.org/] ◦ Open-source MapReduce implementation Tools using Hadoop: ◦ Hive: data warehouse infrastructure that provides data summarization and ad hoc querying (HiveQL) ◦ Pig: high-level data-flow language and execution framework for parallel computation (Pig Latin) ◦ Mahout: Scalable machine learning and data mining library ◦ Flume: Flume is a distributed, reliable, and available service for efficiently collecting, aggregating, and moving large amounts of log data ◦ Many more: Cascading, Cascalog, mrjob, MapR, Azkaban, Oozie, …
- 54. Hype on Databases from nineties == Hadoop from now Hadoop Hadoop Hadoop http://iggyfernandez.wordpress.com/2013/01/21/dilbert-likes-hadoop-clusters/
- 55. “[…] need to solve a problem that relational databases are a bad fit for”, Eric Evans Motives: ◦ Avoidance of Unneeded Complexity – many use-case require only subset of functionality from RDBMSs (e.g ACID properties) ◦ High Throughput - some NoSQL databases offer significantly higher throughput then RDBMSs ◦ Horizontal Scalability, Running on commodity hardware ◦ Avoidance of Expensive Object-Relational Mapping – most NoSQL store simple data structures ◦ Compromising Reliability for Better Performance Based on “NoSQL Databases”, Christof Strauch http://www.christof-strauch.de/nosqldbs.pdf
- 56. BASE approach ◦ Availability, graceful degradation, performance ◦ Stands for “Basically available, soft state, eventual consistency” Continuum of tradeoffs: ◦ Strict – All reads must return data from latest completed writes ◦ Eventual – System eventually return the last written value ◦ Read Your Own Writes – see your updates immediately ◦ Session – RYOW only within same session ◦ Monotonic – only more recent data in future requests
- 57. Consistent hashing ◦ Use same function for hashing objects and nodes ◦ Assign objects to nearest nodes on the circle ◦ Reassign object when nodes added or removed ◦ Replicate nodes to r nearest nodes White, Tom: Consistent Hashing. November 2007. – Blog post of 2007-11-27. http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html
- 58. Storage Layout ◦ Row-based ◦ Columnar ◦ Columnar with Locality Groups Query Models ◦ Lookup in key-value stores Distributed Data Processing via MapReduce Lipcon, Todd: Design Patterns for Distributed Non-Relational Databases. June 2009. – Presentation of 2009-06-11. http://www.slideshare.net/guestdfd1ec/design-patterns-for-distributed-nonrelationaldatabases
- 59. Map or dictionary allowing to add and retrieve values per keys Favor scalability over consistency Examples: ◦ Run on clusters of commodity hardware ◦ Component failure is “standard mode of operation” ◦ ◦ ◦ ◦ Amazon Dynamo Project Voldemort (developed by LinkedIn) Redis Memcached (not persistent)
- 60. Combine several key-value pairs into documents Documents represented as JSON " Title " : " CouchDB ", " Last editor " : "172.5.123.91" , " Last modified ": "9/23/2010" , " Categories ": [" Database ", " NoSQL ", " Document Database "], " Body ": " CouchDB is a ..." , " Reviewed ": false Examples: ◦ Apache CouchDB ◦ MongoDB
- 61. Using columnar storage layout with locality groups (column families) Examples: ◦ Google Bigtable ◦ Hypertable, HBase open source implementation of Google Bigtable ◦ Cassandra combination of Google Bigtable and Amazon Dynamo Designed for high write throughput
- 62. Infrastructure: Kafka [http://kafka.apache.org/] ◦ A high-throughput distributed messaging system Hadoop [http://hadoop.apache.org/] ◦ Open-source map-reduce implementation Storm [http://storm-project.net/] ◦ Real-time distributed computation system Cassandra [http://cassandra.apache.org/] ◦ Hybrid between Key-Value and Row-Oriented DB ◦ Distributed, decentralized, no single point of failure ◦ Optimized for fast writes
- 63. Mahout ◦ Machine learning library working on top of Hadoop ◦ http://mahout.apache.org/ MOA ◦ Mining data streams with concept drift ◦ Integrated with Weka ◦ http://moa.cms.waikato.ac.nz/ Mahout currently has: • Collaborative Filtering • User and Item based recommenders • K-Means, Fuzzy K-Means clustering • Mean Shift clustering • Dirichlet process clustering • Latent Dirichlet Allocation • Singular value decomposition • Parallel Frequent Pattern mining • Complementary Naive Bayes classifier • Random forest decision tree based classifier
- 65. Interdisciplinary field using techniques and theories from many fields, including math, statistics, data engineering, pattern recognition and learning, advanced computing, visualization, uncertainty modeling, data warehousing, and high performance computing with the goal of extracting meaning from data and creating data products. Data science is a novel term that is often used interchangeably with competitive intelligence or business analytics, although it is becoming more common. Data science seeks to use all available and relevant data to effectively tell a story that can be easily understood by non-practitioners. http://en.wikipedia.org/wiki/Data_science
- 68. Analyzing the Analyzers An Introspective Survey of Data Scientists and Their Work By Harlan Harris, Sean Murphy, Marck Vaisman Publisher: O'Reilly Media Released: June 2013 An Introduction to Data Jeffrey Stanton, Syracuse University School of Information Studies Downloadable from http://jsresearch.net/wiki/projects/teachdatascience Released: February 2013 Data Science for Business: What you need to know about data mining and data-analytic thinking by Foster Provost and Tom Fawcett Released: Aug 16, 2013
- 69. Recommendation Social Network Analytics Media Monitoring
- 71. User visit logs ◦ Track each visit using embedded JavaScript Content ◦ The content and metadata of visited pages Demographics ◦ Metadata about (registered) users
- 72. User ID cookie: 1234567890 IP: 95.87.154.251 (Ljubljana, Slovenia) Requested URL: http://www.bloomberg.com/news/2012-0719/americans-hold-dimmest-view-oneconomic-outlook-since-january.html Referring URL: http://www.bloomberg.com/ Date and time: 2009-08-25 08:12:34 Device: Chrome, Windows, PC
- 73. News-source: ◦ www.bloomberg.com Article URL: ◦ http://www.bloomberg.com/news /2011-01-17/video-gamersprolonged-play-raises-risk-ofdepression-anxiety-phobias.html Author: ◦ Elizabeth Lopatto Produced at: ◦ New York Editor: ◦ Reg Gale Publish Date: ◦ Jan 17, 2011 6:00 AM Topics: ◦ U.S., Health Care, Media, Technology, Science
- 74. Topics (e.g. DMoz): ◦ ◦ ◦ Health/Mental Health/…/Depression Health/Mental Health/Disorders/Mood Games/Game Studies Keywords (e.g. DMoz): ◦ Health, Mental Health, Disorders, Mood, Games, Video Games, Depression, Recreation, Browser Based, Game Studies, Anxiety, Women, Society, Recreation and Sports Locations: ◦ ◦ Singapore (sws.geonames.org/1880252/) Ames (sws.geonames.org/3037869/) ◦ Duglas A. Gentile ◦ Iowa State University (dbpediapa.org/resource/ Iowa_State_University) Pediatrics (journal) People: Organizations: ◦
- 75. Provided only for registered users ◦ Only some % of unique users typically register Each registered users described with: ◦ Gender ◦ Year of birth ◦ Household income Noisy
- 76. List of articles based on ◦ Current article ◦ User‟s history ◦ Other Visits In general, a combination of text stream (news articles) with click stream (website access logs) The key is a rich context model used to describe user
- 77. “Increase in engagement” ◦ Good recommendations can make a difference when keeping a user on a web site ◦ Measured in number of articles read in a session “User experience” ◦ Users return to the site ◦ Harder to measure and attribute to recommendation module Predominant success metric is the attention span of a user expressed in terms of time spent on site and number of page views.
- 78. Cold start ◦ Recent news articles have little usage history ◦ More sever for articles that did not hit homepage or section front, but are still relevant for particular user segment Recommendation model must be able to generalize well to new articles.
- 79. Article age [minutes] Access logs analysis shows, that half of the articles read are less then ~8 hours old Weekends are exception
- 80. History ◦ Time ◦ Article Current request: ◦ ◦ ◦ ◦ Location Requested page Referring page Local Time
- 81. Each article from the time window is described with the following features: ◦ ◦ ◦ ◦ ◦ Popularity (user independent) Content Meta-data Co-visits Users Features computed by comparing article‟s and user‟s feature vectors Features computed onthe-fly when preparing recommendations
- 83. Measure how many times one of top 4 recommended article was actually read 1 21% 2-10 11-50 24% 32% 5137%
- 84. Feature space Training set ◦ Extracted from subset of fields ◦ Using vector space model ◦ Vector elements for each field are normalized ◦ ◦ ◦ ◦ One visit = one vector One user = a centroid of all his/her visits Users from the segment form positive class Sample of other users form negative class Classification algorithm ◦ ◦ ◦ ◦ Support Vector Machine Good for dealing with high dimensional data Linear kernel Stochastic gradient descent Good for sampling
- 85. Real-world dataset from a major news publishing website Tested prediction of three demographic dimensions: Three user groups based on the number of visits: Evaluation: ◦ 5 million daily users, 1 million registered ◦ Gender, Age, Income ◦ ≥2, ≥10, ≥50 ◦ Break Even Point (BEP) ◦ 10-fold cross validation Category Male Female Size 250,000 250,000 Category 21-30 31-40 41-50 51-60 61-80 Size 100,000 100,000 100,000 100,000 100,000 Category 0-24k 25k-49k 50k-74k 75k-99k 100k149k 150k254k Size 50,000 50,000 50,000 50,000 50,000 50,000
- 88. 22.00% 21.00% 20.00% 19.00% Text Features 18.00% Named Entities 17.00% All Meta Data 16.00% 15.00% 14.00% 0-24 50-74 150-254
- 90. Observe social and communication phenomena at a planetary scale Largest social network analyzed till 2010 Research questions: How does communication change with user demographics (age, sex, language, country)? How does geography affect communication? What is the structure of the communication network? “Planetary-Scale Views on a Large Instant-Messaging Network” Leskovec & Horvitz WWW2008 90
- 91. We collected the data for June 2006 Log size: 150Gb/day (compressed) Total: 1 month of communication data: 4.5Tb of compressed data Activity over June 2006 (30 days) ◦ ◦ ◦ ◦ ◦ 245 million users logged in 180 million users engaged in conversations 17,5 million new accounts activated More than 30 billion conversations More than 255 billion exchanged messages “Planetary-Scale Views on a Large Instant-Messaging Network” Leskovec & Horvitz WWW2008 91
- 92. “Planetary-Scale Views on a Large Instant-Messaging Network” Leskovec & Horvitz WWW2008 92
- 93. “Planetary-Scale Views on a Large Instant-Messaging Network” Leskovec & Horvitz WWW2008 93
- 94. Count the number of users logging in from particular location on the earth “Planetary-Scale Views on a Large Instant-Messaging Network” Leskovec & Horvitz WWW2008 94
- 95. Logins from Europe “Planetary-Scale Views on a Large Instant-Messaging Network” Leskovec & Horvitz WWW2008 95
- 96. Hops Nodes 1 10 2 78 3 396 4 8648 5 3299252 6 28395849 7 79059497 8 52995778 9 10321008 10 1955007 11 518410 12 149945 13 44616 14 13740 15 4476 16 1542 17 536 18 167 19 71 Social-network 20 6 degrees of separation [Milgram ‟60s] 21 Average distance between two random users is 6.622 23 90% of nodes can be reached in < 8 hops 29 16 10 3 24 “Planetary-Scale Views on a Large Instant-Messaging Network” Leskovec & Horvitz WWW2008 2 25 3
- 98. The aim of the project is to collect and analyze global main-stream and social media ◦ …documents are crawled from 100 thousands of sources ◦ …each crawled document gets cleaned, linguistically and semantically enriched ◦ …we connect documents across languages (cross-lingual technology) ◦ …we identify and connect events http://render-project.eu/ http://www.xlike.org/
- 99. The NewsFeed.ijs.si system collects ◦ 40.000 main-stream news sources ◦ 250.000 blog sources ◦ Twitter stream …resulting in ~500.000 documents + #N of twits per day Each document gets cleaned, linguistically and semantically annotated
- 100. Plain text Extracted graph of triples from text Text Enrichment “Enrycher” is available as as a web-service generating Semantic Graph, LOD links, Entities, Keywords, Categories, Text Summarization
- 101. Reporting has bias – same information is being reported in different ways DiversiNews system allows exploring news diversity along: ◦ Topicality ◦ Geography ◦ Sentiment
- 102. Having stream of news & social media, the task is to structure documents into events “Event Registry” system allows for: ◦ ◦ ◦ ◦ ◦ ◦ Identification of events from documents Connecting documents across many languages Tracking events and constructing story-lines Describing events in a (semi)structured way UI for exploration through Search & Visualization Export into RDF (Storyline ontology) Prototype operating at ◦ http://mustang.ijs.si:8060/searchEvents
- 106. Big-Data is everywhere, we are just not used to deal with it The “Big-Data” hype is very recent Can we do “Big-Data” without big investment? ◦ …growth seems to be going up ◦ …evident lack of experts to build Big-Data apps ◦ …yes – many open source tools, computing machinery is cheap (to buy or to rent) ◦ …the key is knowledge on how to deal with data ◦ …data is either free (e.g. Wikipedia) or to buy (e.g. twitter)