Can training examples with almost the same features but different output cause machine learning classification algorithms to perform poorly? We usually filter out features (columns) that have low correlation or no significant impact on target variable. How would an algorithm, being trained with high dimensional data set (let’s say, more than thousands of features) contain rows with very high correlation but have different target variable, perform? Wouldn’t it make the ML algorithm confused in classification task?

Let me give a simple example to explain what I mean. Assume, we are given the price of a car and the task is to classify it as either of ‘Cheap Car’, ‘Budget Car’, ‘Luxury Car’, and ‘Elite Car’. Further assume, the distance between two rows is generally expected to be greater than 1000. For example, if a row describes a Car with price 1000, the next higher level car in our classification expected to be at least 2000. What if there is some anomaly in data set like a car with price 1000 classified as ‘Cheap’ whereas a car with price 1050 classified as ‘Elite’. That is grossly wrong. We eliminate irrelevant features. Shouldn’t there be something to eliminate confusing training examples?
The answer is yes, highly similar instances in your dataset that have different target classes will cause your model to perform poorly. 

The reason for this is at the core of how all classification machine learning algorithms work. The goal of a classifier is find a function which can separate the two classes. Thus, if these two classes are very mixed then the probability of making a classification error increases and thus you will lose precision in your resulting classification. 

One method to correct this problem is to add more features to your dataset. You should try to find features which will distance the distributions of these two classes. For example if classifying cats and dogs, it would not be a good idea to use features such as: number of legs, number of eyes, etc. This will cause the classes to be indistinguishable. Try adding features such as: weight, frequency of cry, etc. This can be difficult to do often as collecting additional data is expensive. You can also try to transform your data to a new feature space. A transformation mapping your features to a different space can cause their distributions to distance themselves.