Despite the efforts of information security experts, cybercrimes are still emerging at an alarming rate. Among the tools used by cybercriminals, malicious domains are indispensable and harm from the Internet has become a global problem. Malicious domains play an important role from SPAM and Cross-Site Scripting (XSS) threats to Botnet and Advanced Persistent Threat (APT) attacks at large scales. To ensure there is not a single point of failure or to prevent their detection and blocking, malware authors have employed domain generation algorithms (DGAs) and domain-flux techniques to generate a large number of domain names for malicious servers. As a result, malicious servers are difficult to detect and remove. Furthermore, the clues of cybercrime are stored in network traffic logs, but analyzing long-term big network traffic data is a challenge. To adapt the technology of cybercrimes and automatically detect unknown malicious threats, we previously proposed a system called MD-Miner. To improve its efficiency and accuracy, we propose the MD-MinerP here, which generates more features with identification capabilities in the feature extraction stage. Moreover, MD-MinerP adapts interaction profiling bipartite graphs instead of annotated bipartite graphs. The experimental results show that MD-MinerP has better area under curve (AUC) results and found new malicious domains that could not be recognized by other threat intelligence systems. The MD-MinerP exhibits both scalability and applicability, which has been experimentally validated on actual enterprise network traffic.