Binary classification with strongly unbalanced classes I have a data set in the form of (features, binary output 0 or 1), but 1 happens pretty rarely, so just by always predicting 0, I get accuracy between 70% and 90% (depending on the particular data I look at). The ML methods give me about the same accuracy, and I feel, there should be some standard methods to apply in this situation, that would improve the  accuracy over the obvious prediction rule. 
 A: Several answers to this query have already provided several different approaches, all valid. This suggestion is from a paper and associated software by Gary King, eminent political scientist at Harvard. He has co-authored a paper titled Logistic Regression in Rare Events Data which provides some fairly cogent solutions.
Here's the abstract:

We study rare events data, binary dependent variables with dozens to
  thousands of times fewer ones (events, such as wars, vetoes, cases of
  political activism, or epidemiological infections) than zeros
  ("nonevents"). In many literatures, these variables have proven
  difficult to explain and predict, a problem that seems to have at
  least two sources. First, popular statistical procedures, such as
  logistic regression, can sharply underestimate the probability of rare
  events. We recommend corrections that outperform existing methods and
  change the estimates of absolute and relative risks by as much as some
  estimated effects reported in the literature. Second, commonly used
  data collection strategies are grossly inefficient for rare events
  data. The fear of collecting data with too few events has led to data
  collections with huge numbers of observations but relatively few, and
  poorly measured, explanatory variables, such as in international
  conflict data with more than a quarter-million dyads, only a few of
  which are at war. As it turns out, more efficient sampling designs
  exist for making valid inferences, such as sampling all variable
  events (e.g., wars) and a tiny fraction of nonevents (peace). This
  enables scholars to save as much as 99% of their (nonfixed) data
  collection costs or to collect much more meaningful explanatory
  variables. We provide methods that link these two results, enabling
  both types of corrections to work simultaneously, and software that
  implements the methods developed.

Here's a link to the paper ... http://gking.harvard.edu/files/abs/0s-abs.shtml
A: I have to disagree with all of the answers.  The original problem is not appropriate for classification at all but calls for an analysis of tendencies.  See http://fharrell.com/post/classification
Miscasting the task as a classification task is what has caused so much work for everyone, and has caused invalid statistical methods that discard valuable data to be considered.
A: Both hxd1011 and Frank are right (+1). 
Essentially resampling and/or cost-sensitive learning are the two main ways of getting around the problem of imbalanced data; third is to use kernel methods that sometimes might be less effected by the class imbalance.
Let me stress that there is no silver-bullet solution. By definition you have one class that is represented inadequately in your samples. 
Having said the above I believe that you will find the algorithms SMOTE and ROSE very helpful. SMOTE effectively uses a $k$-nearest neighbours approach to exclude members of the majority class while in a similar way creating synthetic examples of a minority class. ROSE tries to create estimates of the underlying distributions of the two classes using a smoothed bootstrap approach and sample them for synthetic examples. Both are readily available in R, SMOTE in the package DMwR and ROSE in the package with the same name. Both SMOTE and ROSE result in a training dataset that is smaller than the original one.
I would probably argue that a better (or less bad) metric for the case of imbalanced data is using Cohen's $k$ and/or Receiver operating characteristic's Area under the curve.
Cohen's kappa directly controls for the expected accuracy, AUC as it
is a function of sensitivity and specificity, the curve is insensitive to disparities in the class proportions. Again, notice that these are just metrics that should be used with a large grain of salt. You should ideally adapt them to your specific problem taking account of the gains and costs correct and wrong classifications convey in your case. I have found that looking at lift-curves is actually rather informative for this matter. 
Irrespective of your metric you should try to use a separate test to assess the performance of your algorithm; exactly because of the class imbalanced over-fitting is even more likely so out-of-sample testing is crucial.
Probably the most popular recent paper on the matter is Learning from Imbalanced Data by He and Garcia. It gives a very nice overview of the points raised by myself and in other answers. In addition I believe that the walk-through on Subsampling For Class Imbalances, presented by Max Kuhn as part of the caret package is an excellent resource to get a structure example of how under-/over-sampling as well as synthetic data creation can measure against each other.
A: Development of classifiers for datasets with imbalanced classes is a common problem in machine learning. Density-based methods can have significant merits over "traditional classifers" in such situation. 
A density-based method estimates the unknown density $\hat{p}(x|y \in C)$, where $C$ is the most dominant class (In your example, $C = \{x: y_i = 0\}$). 
Once a density estimate is trained, you can predict the probability that an unseen test record $x^*$ belongs to this density estimate or not. If the probability is sufficiently small, less than a specified threshold (usually obtained through a validation phase), then $\hat{y}(x^*) \notin C$, otherwise $\hat{y}(x^*) \in C$ 
You can refer to the following paper: 
"A computable Plug-in estimator of Minimum Volume Sets for Novelty Detection," C. Park, J. Huang and Y. Ding, Operations Research, 58(5), 2013.
A: This is the sort of problem where Anomaly Detection is a useful approach. This is basically what rodrigo described in his answer, in which you determine the statistical profile of your training class, and set a probability threshold beyond which future measurements are determined not to belong to that class.
Here is a video tutorial, which should get you started. Once you have absorbed that, I would recommend looking up Kernel Density Estimation.
A: First, the evaluation metric for imbalanced data would not be accuracy. Suppose you are doing fraud detection, that 99.9% of your data is not fraud. We can easy make a dummy model that have 99.9% accuracy. (just predict all data non-fraud).
You want to change your evaluation metric from accuracy to something else, such as F1 score or precision and recall. In the second link I provided. there are details and intuitions on why precision recall will work.
For highly imbalanced data, building a model can be very challenging. You may play with weighted loss function or modeling one class only. such as one class SVM or fit a multi-variate Gaussian (As the link I provided before.)
A: Class imbalance issues can be addressed with either cost-sensitive learning or resampling. See advantages and disadvantages of cost-sensitive learning vs. sampling, copypasted below:

{1} gives a list of advantages and disadvantages of cost-sensitive learning vs. sampling:

2.2 Sampling
Oversampling and undersampling can be used to alter
  the class distribution of the training data and both methods
  have been used to deal with class imbalance [1, 2, 3, 6, 10,
  11]. The reason that altering the class distribution of the
  training data aids learning with highly-skewed data sets is
  that it effectively imposes non-uniform misclassification
  costs. For example, if one alters the class distribution of the
  training set so that the ratio of positive to negative examples
  goes from 1:1 to 2:1, then one has effectively assigned
  a misclassification cost ratio of 2:1. This equivalency
  between altering the class distribution of the training data
  and altering the misclassification cost ratio is well known
  and was formally described by Elkan [9].
There are known disadvantages associated with the
  use of sampling to implement cost-sensitive learning. The
  disadvantage with undersampling is that it discards potentially
  useful data. The main disadvantage with oversampling,
  from our perspective, is that by making exact copies
  of existing examples, it makes overfitting likely. In fact,
  with oversampling it is quite common for a learner to generate
  a classification rule to cover a single, replicated, example.
  A second disadvantage of oversampling is that it
  increases the number of training examples, thus increasing
  the learning time.
2.3 Why Use Sampling?
Given the disadvantages with sampling, it is worth
  asking why anyone would use it rather than a cost-sensitive
  learning algorithm for dealing with data with a skewed
  class distribution and non-uniform misclassification costs.
  There are several reasons for this. The most obvious reason
  is there are not cost-sensitive implementations of all learning
  algorithms and therefore a wrapper-based approach
  using sampling is the only option. While this is certainly
  less true today than in the past, many learning algorithms
  (e.g., C4.5) still do not directly handle costs in the learning
  process.
A second reason for using sampling is that many
  highly skewed data sets are enormous and the size of the
  training set must be reduced in order for learning to be
  feasible. In this case, undersampling seems to be a reasonable,
  and valid, strategy. In this paper we do not consider
  the need to reduce the training set size. We would point
  out, however, that if one needs to discard some training
  data, it still might be beneficial to discard some of the majority
  class examples in order to reduce the training set size
  to the required size, and then also employ a cost-sensitive
  learning algorithm, so that the amount of discarded training
  data is minimized.
A final reason that may have contributed to the use of
  sampling rather than a cost-sensitive learning algorithm is
  that misclassification costs are often unknown. However,
  this is not a valid reason for using sampling over a costsensitive
  learning algorithm, since the analogous issue
  arises with sampling—what should the class distribution of
  the final training data be? If this cost information is not
  known, a measure such as the area under the ROC curve
  could be used to measure classifier performance and both
  approaches could then empirically determine the proper
  cost ratio/class distribution.

They also did a series of experiments, which was inconclusive:

Based on the results from all of the data sets, there is
  no definitive winner between cost-sensitive learning, oversampling
  and undersampling

They then try to understand which criteria in the datasets may hint at which technique is better fitted.
They also remark that SMOTE may bring some enhancements:

There are a variety of enhancements that people have
  made to improve the effectiveness of sampling. Some of
  these enhancements include introducing new “synthetic”
  examples when oversampling [5 -> SMOTE], deleting less useful majority-
  class examples when undersampling [11] and using
  multiple sub-samples when undersampling such than each
  example is used in at least one sub-sample [3]. While these
  techniques have been compared to oversampling and undersampling,
  they generally have not been compared to
  cost-sensitive learning algorithms. This would be worth
  studying in the future.


{1} Weiss, Gary M., Kate McCarthy, and Bibi Zabar. "Cost-sensitive learning vs. sampling: Which is best for handling unbalanced classes with unequal error costs?." DMIN 7 (2007): 35-41. https://scholar.google.com/scholar?cluster=10779872536070567255&hl=en&as_sdt=0,22 ; https://pdfs.semanticscholar.org/9908/404807bf6b63e05e5345f02bcb23cc739ebd.pdf
