Can one group the SHA-256 outputs depending on partial inputs? Is it possible to predict a hash key based on half key?
Let's have some example:

I have 100000000 hash results, and they are generated by either

sha256( "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" . md5(random()) );


or

sha256( "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb" . md5(random()) );


So, when someone generates a new hash (based on method "aa" ou method "bb"), is there any way that I can predict if hash is more a "aa" generated type or more a "bb" one?

I have already tried some type of Bayes classification, because I know that can only be there 2 types of results. But for each result I cannot classify hashes so that I have a good Bayes training.

Is this theoretically possible?
Somewhat simplified, if that were possible, you would have found a vulnerability in SHA-256. The kind of attack you're talking about is called a preimage attack, ie figuring out information on the original message from the hash. There have been some attacks of that kind against a weakened version of SHA-256 but no successful ones against the standard algorithm.

Of course your MD5 only adds 128 bits of entropy and your other data one (either all a or all b), but a brute force attack against 129 bits isn't what you're looking for either.