To establish reliable and long-range millimeter-wave (mmWave) communication, beamforming is deemed to be a promising solution. Although beamforming can be done in the digital and analog domains, both approaches are hindered by several constraints when it comes to mmWave communications. For example, performing fully digital beamforming in mmWave systems involves using many radio frequency (RF) chains, which are expensive and consume high power. This necessitates finding more efficient ways for using fewer RF chains while taking advantage of the large antenna arrays. One way to overcome this challenge is to employ (partially or fully) analog beamforming through proper configuration of phase-shifters. Existing works on mmWave analog beam design either rely on the knowledge of the channel state information (CSI) per antenna within the array, require a large search time (e.g., exhaustive search) or do not guarantee a minimum beamforming gain (e.g., codebook based beamforming). In this paper, we propose a beam design technique that reduces the search time and does not require CSI while guaranteeing a minimum beamforming gain. The key idea derives from observations drawn from real-life measurements. It was observed that for a given propagation environment (e.g., coverage area of a mmWave BS) the azimuthal angles of dominant signals could be more probable from certain angles than others. Thus, pre-collected measurements could used to build a beamforming codebook that regroups the most probable beam designs. We invoke Bayesian learning for measurements clustering. We evaluate the efficacy of the proposed scheme in terms of building the codebook and assessing its performance through real-life measurements. We demonstrate that the training time required by the proposed scheme is only 5% of that of exhaustive search. This crucial gain is obtained while achieving a minimum targeted beamforming gain.