When evaluating your algorithms, especially when your dataset is unbalanced, you should use more metrics than just accuracy. The accuracy is how many examples you have correctly identified in total. As you have seen if you have an unbalanced dataset where 0.5% of your instances are 1's then this will result in 99.5% accuracy if you blindly set all your outputs as zeroes. This is obviously wrong albeit the high accuracy. The accuracy is calculated as
$Accuracy = \frac{\sum{TP} + \sum{TN}}{\sum{TP} + \sum{TN} + \sum{FP} + \sum{FN}}$
where TP is true positive, TN is true negatives, FP is false positives and FN is false negatives.
If you want to capture the performance of your unbalanced dataset you should look into the percentage of FP and FN you are calculating. You can do this using the sensitivity and the specificity. Calculate the sensitivity as
$Sensitivity = \frac{\sum{TP} }{\sum{TP} + \sum{FN} }$
and the specificity as
$Specificity = \frac{\sum{TN} }{\sum{TN} + \sum{FP} }$.
An ideal classifier should have the accuracy, specificity and sensitivity all be 1. This would mean every sample is correctly classified. In your case where you are getting very high false negatives, you will see that your sensitivity will be very low. This is a measure with which you can state that your algorithm is performing poorly. It is good form to always include these metrics in any statistical study you are doing. Accuracy alone is not sufficient to prove that you are obtaining good results.
Moreover, there is the receiver-operator curve (ROC). This will tell you your false positive rate for any true positive rate. You can then calculate the area under this curve (AUC) to get a comparable metric of performance.
All of these should be used together when exclaiming the performance of your algorithm. The ROC and AUC can be omitted however leaving out the sensitivity and specificity of your algorithm is unwise.