Our Thoughts

Big Data is certainly the buzz term of the year and there is no doubt that the presentation of Big Data technology into the mainstream has presented a vast array of opportunities not just for web companies but for enterprise companies across virtually all verticals.

Platforms such as Hadoop now allow companies to mine and process unstructured data and large amounts of data in a much more efficient manner but they are certainly not the magic bullets or finished articles that end users are demanding.

The explosion of cloud technologies have increased the demand from end users who now want their software as a service and on demand but right now, whilst there are “Big Data” companies beginning to offer this type of service, the market is a long way from offering recommendations, advanced sentiment or predictive analytics in a SaaS fashion.

The reality is that most organisations outside the big web companies such as Amazon, Google and NetFlix are still finding their feet with the technology and trying to understand how to use it to deliver on their strategic goals. Even the organisations that have defined this are realising that a Hadoop developer is not going to give you the perfect tools you need and in fact data scientists are required to model the algorithms needed to really gain customer or machine to machine insight.

As the Big Data world matures and companies really start to get to grips with how to use it, the demand for data scientists will completely out strip supply as will it also for data visualisation experts who will need to make sense of the mathematical results coming from their real time sentiment analysis algorithms and turn it into a nice end user experience.

Making sense of big data requires a combination of engineering and data science expertise – having the typically low level specialist technical skills as well as the ability to get behind the science of the data is equally important. With so many new big data solutions emerging from distributed scalable systems like Hadoop to NoSQL database solutions and new machine learning techniques, the technology has evolved faster than the workforce skills in the majority of organisations. Also fuelling this evolution is the wide acceptance of open source technology by large enterprise customers. As the de facto technology solution for big data, Hadoop is beginning to gain wider adoption amongst large enterprises as they seek to gain competitive edge in a way traditional platforms did not allow. Whilst there are pockets of talent in the UK & Europe, there is a widespread shortage in trained staff in this geographic region.

The end-user customers and vendor community are all competing for the most talented big data developers and data scientists. Big Data Partnership firmly believe it is critical for end users to adapt and enable themselves to compete in an increasingly data-driven economy by cross-training their workforce to deal with tomorrows challenges today. To gain real competitive edge, you have to have the right talent and the right teams with the relevant skill set. Apart from a minority of early-adopter companies, this does not exist today across may of the enterprises. Recruiting is one option but with very few individuals available, companies will struggle to source suitable candidates without paying a significant premium. Formal training and certification will play an increasing role to identify experts in big data, Apache Hadoop, Apache Cassandra and other key technologies. It is important that companies act now and budget for training existing staff in these new technologies which we believe will help attract talent, retain staff and increase job satisfaction.

In summary, the are still a number of hurdles to overcome for companies wanting to adopt big data including the technology itself but there is no doubt that it will and is changing the way that organisations look at consumers and technologies such as Hadoop and Mahout will become key tools when deciding where and who to advertise to or provide services to.

Big Data Partnership offer a variety of public open enrolment and on-site private big data training including Hadoop and Cassandra training & certification helping the adoption of enterprise big data solutions.

The advances in big data technology are opening up new ways to collect and transport large amounts of data more efficiently. This revolution has boosted research and development of real-time algorithms and methods. Traditionally, machine learning algorithms were not designed for real-time processing. In fact, data science competitions (e.g the Netflix prize, Kaggle) were criticised as the winning algorithms were often computationally expensive which made them impractical to use. This is rooted in the perception that the accuracy is more important that the speed of the algorithm, as the original setup of data mining was offline, often computed in batches. This started to change with the appearance of big data, as more algorithms were rethought in a scalable way. Most of the time scalability alone does not compromise the accuracy of the algorithms, as the computation is essentially the same. Real time processing of big data analytics has brought a more fundamental change, as it restricts the computational complexity of algorithms that can be employed in this scenario. A real-time streaming algorithm should meet the following criteria: it should process one example at a time, inspect it at most once, use a limited amount of memory, work in a limited amount of time and be ready to predict at any time.

To address these requirements, streaming algorithms were designed in a fashion that a learned model is constantly updated to reflect the incoming examples from the stream. After processing an incoming example, the algorithms are required to be able produce predictions regardless of data sparsity. Cutting-edge methodology for streaming data has come from a number of diverse directions, from on-line learning, randomised linear algebra, to distributed optimisation methodology for cloud computing, to multi-class classification problems in the presence of noisy and spurious data. Generally speaking, these methods are light, but some parts of the prediction might be based on pre-computed models. In fact, the offline-online cycle is a good compromise between traditional machine learning and real time analysis, as it pushes the heavier part of the model offline which is refined by the online part of the method as new observations come in.

Incremental learning algorithms represent an approach that fits well with the requirements posed in real time analytics. In essence, these algorithms have an offline core model that can be trained on historical data and new observations are rolled into the model incrementally. In order to keep the models fast, this incremental update only partially updates the model based on the concept drift that is detected in the stream, and the next full update commences offline at a scheduled time. This enables the system to react to new observations quickly, which is the compromise between speed and accuracy. It is important to note that depending on the type of algorithm employed, it is possible to update to model fully, in which case there is no need to maintain an offline part of the algorithm. In fact, the main criterion that makes an incremental algorithm an online learning algorithm is whether it can update the model and produce real time predictions.

Real time analytics have been employed in a wide variety of scenarios including social media, personalisation, finance and various scientific disciplines. However, tools that can deal with large volumes of data in real time are still scarce and are mainly in-house solutions.

Classification:
The Hoeffding option tree is an incremental decision tree induction algorithm. Hoeffding trees exploit the fact that a small sample can often be enough to choose an optimal splitting attribute.

Naïve Bayes is a very simple and computationally light classifier, the update of the model and the classification of the new samples can be done in real-time. Naïve Bayes is a good example of incremental learning without an offline component, as this model can produce prediction without historical data, which improves as new observations arrive.

Clustering:
StreamKM++ computes a small weighted sample of the data stream and it uses the k-means++ algorithm as a randomised seeding technique to choose the first values for the clusters.

D-Stream uses an online component that maps each input data record into a grid and an offline component that computes the grid density and clusters the grids based on the density. The algorithm adopts a density decaying technique to capture the dynamic changes of a data stream.

Regression:
Incremental LDA updates the least square solution of the LDA when new samples arrive. The advantage of this method is that it performs a full update of the model which results in the exact least square solution of batch LDA.

SAIRT is an incremental version of binary regression trees. It adapts the induced model when facing data streams involving unknown dynamics, like gradual and abrupt function drift, changes in certain regions of the function, noise, and virtual drift. It monitors the usefulness of nodes and forgets examples from selected regions, storing the remaining ones in local windows associated to the leaves of the tree.

With businesses becoming increasingly sensitive to customer opinion of their brand, monitoring consumer feedback is becoming ever more important. Additionally, the recognition of social media as an important and valid source of customer opinion has brought about a need for new systems and a new approach.

Traditional approaches of reactive response to any press coverage by a PR department, or conducting infrequent customer surveys whether online or by phone are all part of extremely slow-cycle feedback loops, no longer adequate to capture the ever-changing shifts in public sentiment.

They represent a huge hindrance to any business looking to improve brand relations, delay in feedback can cost real money. Inevitably, the manual sections of traditional approaches create huge delays in information reaching its users. These days, we need constant feedback and we need low-latency – the information needs to be almost real-time. Wait a few moments too long, and suddenly the intelligence you captured could be stale and useless.

A social media listening post

Witness the rise of the “social media listening post”: a new breed of system designed to plug directly in to social networks, constantly watching for brand feedback automatically around the clock. Some forward-thinking companies have already built such systems. How does yours keep track right now? If your competitors have it and you don’t, does that give them a competitive advantage over you?

I’d argue for the need for most big brands to have such a system these days. Gone are the days when businesses could wait months for surveys or focus groups to trickle back with a sampled response from a small select group. In that time, your brand could have been suffering ongoing damage, and by the time you find out, valuable customers have been lost. Intelligence is readily available these days on an near-instantaneous basis, can you afford not to use it?

Some emerging “Big Data” platforms offer the perfect tool for monitoring public sentiment toward a company or brand, even in the face of the rapid explosion in data volumes from social media, which could easily overwhelm traditional BI analytics tools. By implementing a social media “listening post” on cutting-edge Big Data technology, organisations now have the opportunity to unlock a new dimension in customer feedback and insight into public sentiment toward their brands.

Primarily, we must design the platform for low-latency continuous operation to allow complete closure of the feedback loop – that is to say, events (news, ad campaigns etc) can be monitored for near-real time positive/negative/neutral response by the public – thus bringing rapid response, corrections in strategy, into the realm of possibility. Maybe you could just pull that new ad campaign early if something disastrous and unexpected happened to public reaction to the material? It’s also about understanding trends and topics of interest to a brand audience, and who are the influencers. Social media platforms like Twitter offer a rich granular model for exploring this complex web of social influence.

The three main challenges inherent in implementing a social media listening post are:

• Data volume
• Complexity of data integration – e.g. unstructured, semi-structured, evolving schema etc
• Complexity of analysis – e.g. determining sentiment: is it really a positive or negative statement with respect to the brand?

To gain a complete picture of public opinion towards your brand or organisation through social media, many millions of web sites and data services must be consumed, continuously around the clock. They need to be analysed in complex ways, far beyond traditional data warehouse query functionality. Even just a sentiment analysis capability on its’ own poses a considerable challenge, and as a science is still an emerging discipline, but even more advanced techniques in Machine Learning may prove necessary to correctly interpret all signals from the data. Data format will vary greatly among social media sources, ranging from regular ‘structured’ data through semi-and unstructured forms, to complex poly-structured data with many dimensions. This structural complexity poses extreme difficulty for traditional data warehouses and up-front ETL (Extract-Transform-Load) approaches, and demands a far more flexible data consumption platform.

So how do we architect a system like this? Generally speaking, at its core you will need some kind of distributed data capture and analysis platform. Big Data platforms were designed to address problems where you have Volume, Variety, or Velocity of data – and most often, all three. In this particular use-case, we need to look towards the cutting-edge of the technology, and look for a platform which supports near-real time, streaming data capture and analysis, with the capability to implement Machine Learning algorithms for the analytics/sentiment analysis component.

For the back-end, a high-throughput data capture/store/query capability is required, suitable for continuous streaming operation, probably with redundancy/high-availability, and a non-rigid schema layer capable of evolving over time as the data sources evolve. So-called “No-SQL” database systems (which in fact stands for “Not Only SQL” rather than NO SQL) such as Cassandra, HBase or MongoDB offer excellent properties for high-volume streaming operation, and would be well suited to the challenge, or there are also commercial derviatives of some of these platforms on the market, such as the excellent Acunu Data Platform which commercialises Cassandra.

Additionally a facility for complex analytics, most likely via parallel, shared-nothing computation (due to the extreme data volumes) will be required to derive any useful insight from the data you capture. For this component, paradigms like MapReduce are a natural choice, offering the benefits of linear scalability and unlimited flexibility in implementing custom algorithms, and libraries of Machine Learning such as the great Apache Mahout project have grown up around providing a toolbox of analytics on top of the MapReduce programming model. Hadoop is an obvious choice when it comes to exploiting the MapReduce model, but since the objective here is to achieve near-real time streaming capability, it may not always be the best choice. Cassandra and HBase (which in fact runs on Hadoop) can be a good choice since they offer the low-latency characteristics, coupled with MapReduce analytic capabilities.

Finally, some form of front-end visualization/analysis layer will be necessary to graph and present results in a usable visual form. There are some new open-source BI Analytics tools around which might do the job, or a variety of commercial offerings in this area. The exact package to be selected for this component is strongly dependent on the desired insight and form of visualization and so is probably beyond the scope of this article, but of course requirements are clearly that it needs to interface with whatever back-end storage layer you choose.

Given the cutting-edge nature of many of the systems required, a solid operational team is really essential to maintain and tune the system for continuous operation. Many of these products have complex tuning requirements demanding specialist skill with dedicated headcount. Some of the commercial open-source offerings have support packages that can help mitigate this requirement, but either way, the need for operational resource must never be ignored if the project is to be a success.

The technologies highlighted here are evolving rapidly, with variants or entirely new products appearing frequently, as such it would not be unreasonable to expect significant advancement in this field within the 6-12 month timeframe. This will likely translate into advancement on two fronts: increased and functional capability of the leading distributed data platforms in areas such as query interface and indexing capability, and reduced operational complexity and maintenance requirements.

Further information

This blog posting written by Tim Seears, CTO of Big Data Partnership featured in the July 2012 issue of Broadgate Consultants Newsletter and published on their website: (http://www.broadgateconsultants.com/blog/). 

Big Data Partnership and Broadgate Consultants are working together to help organisations unlock the value in their big data. We would be delighted to discuss further the use case outlined above should you wish to explore adapting these concepts to your own business.

(This is the second part of the post – How to analyse your customer social profile in 24 hours – Data and Collection)

Community Level

After collecting the data as described in the previous post, we can look into the data and visualize some aspects of it. There are many questions we can ask of this data, however an obvious one is what are the people who are engaged in the given topic talking about? This is important to understand in order to identify how the organization can approach these users and market itself. We can get a quick overview of this by producing a word cloud of the most used words in the tweets.

This gives a high level overview of the topics that might be worth looking into. Note that this goes beyond the initially specified tags (see the previous post), as it discovers a number of associations between the given topics and what people actually talk about. This high level extraction can be replaced by more sophisticated methods that can assign importance to the topics based on the influence of the user and how close they are to the target organisations. Essentially, this is a trade-off between exploring new topics and exploiting known topics.

We can also produce a word cloud of the topics, followers of the organisation were talking about.

As these tweets were not restricted to the topics of the target organisation, we get a wide range of keywords here. It is clear, that apart from the main topics that interests most of the people, these people have a slight divergence from the average towards the target organisation. This divergence is what we are interested in identifing. You can spot some keywords that would not turn up from a randomly sampled population of Twitter, for example cfpreform, GreenpeaceUK, overfishing, BristolZooGdns etc. This suggests that the followers of this account are more interested in nature related topics.

Individual Level

Now we can look at what can be derived about the people who form these two communities. We would like to understand who are the influential people who form opinions and spread information. In other words, we aim to identify who the influencers are and therefore who the organisation should start to engage with more closely. This information can also be fed back to the previous analysis by weighting topics and keyword depending on how influential the originator of the tweet is. The simplest way to identify people is to look how active they are and how many followers they have (note that these two factors are not independent).  In the literature, other factors were incorporated into this score including the number of retweets and mentions.  The figure below shows the top-20 followers of the RSPB acount.

These users produced around 7% of the tweets we collected. It is important to concentrate on these people as the information they find interesting is very likely to spread. Users in the long tail should not be abandoned too, however, it is more problematic to define a strategy to reach out to those users. The same approach can also be applied to the users of the target topic; the top influences can be identified and targeted. However, the long tail distribution is even more apparent in that case, as the top-20 users produced only 5% of the tweets.

User profiling

Apart from detecting whether a user is influential, a number of additional charateristics can be inferred. From example, using various data-mining and predicting techniques, my Twitter profile analysis says that

• I am 25-34 year old
• I live near London, England, United Kingdom
• I can potentially reach 1378 users
• My network is composed of 25-34 year olds followed by 18-20 year olds
• I frequently talk about android, apple and big data
• My personality type is inquisitive, cautious (source: http://twanalyst.com/)
• My style is academic

Social profiles tell us a lot about the interest of its owner and also about people/organisations they follow and people who are following them. This blog post is a summary of what information you can get by collecting and analysing your customer profiles in 24 hours. In fact, after unlocking of the data, this process can be automated and can produce real-time analysis/prediction giving invaluable insights into human behavior from multiple aspects. I’ll give an example of this analysis using Twitter, and highlight what information gathering is possible and what can be done with that data.

In our example, we are interested in analysing the customer profiles of RSPB (Royal Society for the Protection of Birds). There are two interesting (and highly related) aspects that we want to capture. First, what are the topics that are somehow related to the organisation and the people who are actively contributing to these topics. We can then use this data to discover related trends and topics and understand what users are engaged in. Secondly, we want to know about the actual followers of the organisation, as the profiles of the followers may also tell a lot about the organisation and what interests these users.

Data collection is the first step in this process.  From the topic side we can simply identify a number of search terms that are related to the organisation and obtain the number of hashtags that occur in the results of this search, we then follow up each lead iteratively to a certain depth (after 2-3 steps the hashtags became unrelated). We gather all of the data that Twitter allows us to pull back in time and start to continually crawl these terms for a period of time. The topics returned include a variety of things, more general topics like #nature, #wildlife, #birds and more specific ones to the organisation (for example #rspbsteppingup). This process of selection can be updated periodically to capture trending topics.

We can also start to collect data from the followers of the organisation. This is a bit tricky as Twitter restricts the number of requests for its REST API, so the user profiles cannot be collected directly (especially in this case, when we have around 40K user profiles to crawl). One solution we have found to bypass this problem is to use the search API to collect the profiles.

After running the two crawlers overnight, we get

from the RSPB account followers

• 27605 user profile
• 341k tweets

from the related topics and tags (80 tags and search terms were identified)

• 15727 users
• 50k related tweets

It is interesting to note that the number of tweets collected from the topics rather is much less than followers, but it also contains less noise and therfore is more related to the target organisation. The tweets collected from the followers contains a wide variety of topics, only a small proposition of which are related to the organisation. This allows us to capture user interest in a more general sense, but is still loosely related to the target organisation.

(Click the link here for Part II which includes graphics showing the exciting results).

Hadoop is a grassroots phenomenon that emerged in the social networking and consumer Internet world. As always, there are early adopters who take risks on the cutting edge, and there are more conservative organizations watching the pioneers from the sidelines.

This played out in 2011 as early customer experiences with Hadoop were shared via conferences, online forums and vendor white papers. Experts think Hadoop is on the edge of a tipping point, as some of the earliest Hadoop implementers move from experiments to adoption. As a result, people implementing Hadoop today are benefiting from the lessons learned by the early pioneers.

In 2012 and 2013, we will see a growing body of case studies and the emergence of best practices as Hadoop technology matures and gets deployed in traditional enterprise environments. In short, Hadoop’s momentum will grow exponentially in the next 18 months.

If becoming mainstream is step four in the technology adoption process, Hadoop will move through step two and into step three this year and next.

[Extract by Matt Howard who is a general partner at Norwest Venture Partners (NVP)]

With the increasing popularity and the addiction of companies towards Hadoop, also Hadoop being an unanimous solution for Big data platforms makes the Hadoop development team to focus on the current architectural deficiencies and make Hadoop free from such underlying architectural issues. In that path a new Hadoop MapReduce version has taken birth MapReduce 2.0 (MRv2) or YARN. MapReduce has undergone a complete overhaul in hadoop-0.23 and now we have MapReduce 2.0 (MRv2) or YARN.

Let me take this opportunity to give the brief introduction to YARN, The basic change in MRv2 is the split-up of two major functionalities of JobTracker into separate daemons. They are,

1. Resource Management
2. Scheduling/Monitering

In order to achieve this new components have been introduced, namely,

1. ResourceManager (RM)
2. ApplicationsManager
3. NodeManager (NM)
4. ApplicationMaster (AM)
5. Container

I) ResourceManager (RM)
The ResourceManager (RM) is the key service offered in YARN. Clients can interact with the framework using ResourceManager. ResourceManager is the master for all other daemons available in the framework.
ResourceManager has two major components,

1. Scheduler
2. ApplicationsManager

a) Scheduler
1. The Scheduler is responsible for allocating resources to the various running applications subject to familiar constraints of capacities, queues etc.
2. It is a pure scheduler since it does not monitor or track the status of the application instead it purely performs its scheduling function based the resource requirements of the applications
3. It schedules the resources depending the resource “Container”
4. The Scheduler has the pluggable policy plug-in which is responsible for partitioning the cluster resources among the various queues, applications etc, for example
a) CapacityScheduler
b) FairScheduler

b) ApplicationsManager
1. ApplicationsManager is responsible for accepting job-submissions
2. Assigning the first container for executing the application specific ApplicationMaster
3. Provides the service for restarting the ApplicationMaster container on failure

II) NodeManager (NM)
NodeManager is similar to TaskTracker
1. NodeManager is responsible for Containers
2. Monitoring container resource usage (like cpu, memory, disk, network)
3. Reporting to the ResourceManager/Scheduler
III) ApplicationMaster (AM)
1. ApplicationMaster is responsible for negotiating appropriate resource containers from the Scheduler
2. Tracking the status and monitoring progress for applications running under this ApplicationMaster

IV) Container
Resource Container incorporates elements such as memory, cpu, disk, network etc. Only memory is supported in first version

Joins:-
=======

Joins is one of the interesting features available in MapReduce. Joins performed by Mapper are called as Map-side Joins.
Joins performed by Reducer can be treated as Reduce-side joins. Frameworks like Pig, Hive, or Cascading has support for performing joins.

Before diving into the implementation let us understand the problem throughly. If we have two datasets, for example,
one dataset having user ids, names and the other having the user activity over the application. In-order to find out which user
have performed what activity on the application we might need to join these two datasets such as both user names and the user activity
will be joined together.

Join can be applied based on the dataset size if one dataset is very small to be distributed across the cluster then we can use
Side Data Distribution technique.

Side Data Distribution:-
====================
Side-Data is the additional data needed by the job to process the main dataset. The critical part is to make this side-data available to
all the map or reduce tasks running in the cluster. It is possible to cache the side-data in memory in a static field, so that the
tasks running successively in a task tracker will share the data. Using the Task JVM re-use feature we can handle this. When using
this feature we should make sure that the amount of memory needed to cache the data should not affect the memory needed for Shuffle
and sort phase.

Caching of side data can be done in two ways,

Job Configuration:- Using Job Configuration object setter method we can set the key-value pairs and the same can be retrieved in the
map or reduce tasks. We should be careful using this option to not to use huge amount of data to be shared in this way since the
configuration is read by the JobTracker, TaskTracker and the child JVMs and everytime the configurations will be loaded into the memory.

Distributed Cache:-
=================
Side-Data can be shared using the Hadoop’s Distributed cache mechanism. We can copy files and archives to the task nodes when the tasks
need to run. Usually this is the preferrable way over the JobConfigurtion.

If both the datasets are too large then we cannot copy either of the datasets to each node in the cluster as we did in the Side data distribution.
We can still join the records using MapReduce with a Map-side or reduce-side joins.

Map-Side Joins:-
===============
The inputs for to each map must be partitioned and sorted in a specific way. Each input dataset must be divided into the
same number of partitions, and it must be sorted by the same key (the join key) in each
source.  All the records for a particular key must reside in the same partition and which is mandatory. A map-side join can be used to
join the outputs of several jobs that had the same number of reducers, the same keys, and output files that are not splittable which means
the ouput files should not be bigger than the HDFS block size.

Using the org.apache.hadoop.mapred.join.CompositeInputFormat class we can achieve this. The join type (Inner or Outer) is configurable using
the join expression. for ex,
func ::= tbl(<class>,”<path>”);
We can set it to the CompositeInputFormat using,

inner(tbl(org.apache.hadoop.mapreduce.lib.input.SequenceFileInputFormat.class,
“hdfs://localhost:8000/usr/data”),
tbl(org.apache.hadoop.mapreduce.lib.input.SequenceFileInputFormat.class,
“hdfs://localhost:8000/usr/activity”));

We can achieve following kind of joins using Map-Side techniques,

1) Inner Join
2) Outer Join
3) Override – MultiFilter for a given key, prefered values from the right most source

Reduce-Side Joins:-
=================
Reduce-Side joins are more simple than Map-Side joins since the input datasets need not to be structured. But it is less efficient as both datasets have
to go through the MapReduce shuffle phase. the records with the same key are brought together in the reducer. We can also use the Secondary Sort technique
to control the order of the records.

Bloom Filter

A Bloom filter is a space-efficient probabilistic data structure that is used to efficiently encode sets and perform set membership tests, whether an element is a member of a set. False positives are possible, but false negatives are strictly not possible. i.e. a query returns either “inside set (may be wrong)” or “definitely not in set”.

How it works,

Let h1, h2, h3 … hk be the set of hash functions, where hash function is a compression function.
A Bloom filter calculates hi(x) = d and sets the d’th bit in the m-length bit-vector for all hash functions ‘hi’ and for each feature value ‘x’.

To test whether any element ‘x’ is present in the feature-set, you check that hi(x) bit is set for all hash functions ‘hi’. If any bit is not set, then ‘x’ is not in the set.

Implications

Bloom filters have false-positives due to hash collisions, but never have a false-negative. By adding more hash functions we can reduce the false-positives.

Removing an element from a simple Bloom filter is impossible because false negatives are not permitted, An element is mapped to k bits, and setting any one of those k bits to zero will remove the element, as a side-effect it also results in removing any other elements that was mapped onto that bit. Clearing any of the bits would introduce the possibility for false-negatives and which is not permitted.

One-time removal of an element from a Bloom filter can be simulated by having a second Bloom filter that contains items that have been removed. However, false positives in the second filter become false negatives in the composite filter, which are not permitted. In this approach re-adding a previously removed item is not possible, as one would have to remove it from the “removed” filter.

If the false-positive rate is too high then the filter need to be regenerated.

Feature Hashing

Feature hashing is similar to Bloom filters where we compute h(x) = d and set the d’th bit, except that only a single hash function is used unlike using k hash functions in the bloom filter. Increasing number of hash functions will increase error, which is why Bloom filters don’t work well.
Error increases as ‘k’ increases, minimum error achieved at k = 1, which is different from the usual Bloom filter set membership tests. Feature hashing is relatively a good approach where only one hash function is used. Using only one hash function also improve the performance of learning algorithms.

Locality sensitive hashing (LSH)

The main idea in Locality sensitive hashing (LSH) is to define a hash function ‘h’ such that h(s1) = h(s2) if the two sets ‘s1′ and ‘s2′ are similar. LSH is complementary to feature hashing, because it reduces the number of items while feature hashing reduces the number of features both feature hashing and locality-sensitive hashing could be combined in a real system.

Clustering Introduction:-

Clustering is one of the most popular techniques available in Machine learning field. This allows the system to group numurous entities into separate clusters/groups based on certain characteristics/features of the entities. Clustering is a widely used technique in many grouping problems like grouping similar news articles, blogs, emails, malwares etc based on their feature set. Clustering webpages will help indexing the webdata more effectively. This technique will enable the system to automatically find new categories (clusters) with out human interpretation. There are many clustering techniques to cluster the entities like K-means, X-means, Hierarchical clustering etc.

Problem:-

Consider a big clothes showroom and assume that they have not properly organized various dress materials like kids wear,  fancy, formal, party, ethnic, sports etc separately and dumped all kinds of wears altogether or scattered in the whole showroom. Then any customer entering the showroom might throughly check the whole showroom in-order to pick his/her required selections, then the customer might end up rounding and rounding the whole showroom to select his dress material. What-if these dress materials are categorized into various sections and each section is devoted for a particuar type like kids wear, formal, party, ethnic, sports etc then the customer can directly enter into his/her section of interest and can complete his/her shopping efficiently.

Solution:-

Clustering techniques will help in identifying the similarities between the entities and cluster them into various categories. These different clusters will enable the system to mine the common patterns/rules from these clusters.

Clustering in Mahout:-

Mahout has support for various clustering techniques implemented in a distributed passion. Distributed/parallel implementations will directly relate to drastic improvement in the performance of the system as well as overcoming the limitation of limiting the input data size based on hardware in stand alone implementations.

Major clustering techniques available in Mahout 0.5 are,

• K-means             -   Exclusive clustering
• Fuzzy K-means – Overlapping clustering
• Dirichlet             -  Probabilistic clustering etc

K-means in Mahout:-

Suppose to say, we have to cluster the list of documents based on the content of each document. Then the following steps are involved,

1) Vectorizing:- The documents should be converted into a format which the algorithm can understand. Each document will be converted into a vector and all these vectors should be passed as input to the clustering algorithm (K-means). Each vector is a collection of similar values and each vector will have a dimension of its own.

The useful feature-set in clustering the text documents are TF-IDF (Term Frequency and Inverse Document Frequency)

• Term Frequency:- The number of occurrences of a term in document
• Inverse Document Frequency:- The uniqueness of a term in document. i.e., the unique terms associated with a given document

a) Calculating weights with TF-IDF:-  Assigning weights to terms based on TF-IDF features will give more accuracy to the clustering algorithm rather than using the plain TF-IDF feature-set. Before we dig into details let us see what IDF means,

For example, say if a document has ‘n’ words w1, w2, w3…wn with frequencies f1, f2, f3…fn respectively,

Then,  TFi of wi = fi

Then,  IDFi = 1/DFi where DFi is the number of documents the word presents in (say word wi).

To normalize the above equation we will multiply the equation with ‘N’ (which is number of documents)

So, IDFi = N/DFi, therefore the weight Wi is TFi * IDFi = TFi * N/DFi

In order to give give more priority to TF we will apply logarithm to the above equation, Thus the final formula for calculating weight for each term is,

Wi = TFi * log ( N / DFi )

Applying the above equation the weights for each term will be calculated and the vectors for each document will be created, finally the input data for the algorithm will look something like this,

ant      apple    bat    boll     story     …..

Doc1       2.85    0.0       3.6     5.87   1.897 …..

Doc2        0.0    1.23       0.0    6.87   4.5343 ….

……

From the above we can conclude that the words are represented as columns and documents as rows, so each vector signifies each row in the matrix. 0.0 represents that that particular word is not present in that document.

2) Selecting distance measure:- Distance measure plays a vital role in identifying the similarity between two different vectors. And there are many built-in distance measures available in Mahout clustering section. they are,

1. Euclidean Distance Measure
2. Squared Euclidean Distance Measure
3. Cosine Distance Measure
4. Tanimoto Distance Measure
5. Manhattan Distance Measure

Each one of the above has its own way of calculating distances between the vectors usually Tanimoto distance measure will be the better choice for calculating the distances between the text documents. Also Tanimoto distance measure is a combination of both Euclidean and Cosine distance measures. But it is suggested that each application has various requirements to tuning the application by changing the distance measures and evaluating the clusters generated is preferable approach.

3) Tuning features:- Also tuning some features offered by Mahout will lead the system to generate more accurate results like, N-gram collocations, Normalization, selecting appropriate “K” value etc.

4) After above all running the K-means over vectorized data and certain other features as mentioned above using the Mahout command-line commands or Mahout API we can generate the clustered results.

5) The generated results can be viewed using the Mahout command line or API.

Clustering can also be applied with recommendation algorithms where cluster-based recommendation will give us best results. Also clustering can be applied in combination with classification which will derive more efficient classification systems.