Entropy-based estimation is a promising approach to the problem of predicting the power dissipated by a digital system for which an architectural description is available. For achieving good performance of the power estimation tool, an accurate computation of the input and output entropies of the Boolean functions implemented by the circuit is essential. For small designs, the calculation can be carried out exactly, thanks to the compact representation and ease of manipulation of Boolean and pseudo-Boolean functions provided by BDD-like data structures. For large circuits, on the other hand, resorting to approximate computations is mandatory. Techniques to determine an upper bound on the exact entropy values have been developed in the recent past. Unfortunately, the results provided by such techniques are, in some cases, not satisfactory; in other words, the assumptions made to simplify the calculation --- total absence of correlation among the output signals of a circuit --- are in many cases too strong to guarantee a reasonable tightness of the approximate entropy values to the exact ones. In this paper, we propose a method to determine the entropy of large logic circuits with a level of accuracy which is far beyond the one provided by existing approaches. We partition the set of output signals according to the information about the functional correlations that may exist among such signals, and we compute the approximate entropy values after performing output clustering. The heuristics we employ to drive the clustering phase are mutuated from previous work on state variable partitioning for approximate FSM traversal. Experimental results, obtained on a large collection of benchmarks, are very promising.